www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - How to override opCmp when two different sorts are needed?

reply John Bartelt <bartelt cox.net> writes:
I have a class that contains two variables. Sometimes I need to sort an array
of the class based on variable 1, and later in the same progam sort the array
based on variable 2.

Can someone give me an idea of how to do this (smartly, efficiently, cleverly,
polymorphically, ...)?

Best idea that I've had so far is to use a static flag in the class to indicate
which sort is desired, and then to have the overloaded opCmp() check the flag
before comparing.
Aug 13 2007
next sibling parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"John Bartelt" <bartelt cox.net> wrote in message 
news:f9quel$rou$1 digitalmars.com...
I have a class that contains two variables. Sometimes I need to sort an 
array of the class based on variable 1, and later in the same progam sort 
the array based on variable 2.

 Can someone give me an idea of how to do this (smartly, efficiently, 
 cleverly, polymorphically, ...)?

 Best idea that I've had so far is to use a static flag in the class to 
 indicate which sort is desired, and then to have the overloaded opCmp() 
 check the flag before comparing.

Write your own sort routine which takes a given predicate. :\ Tango provides such a routine in tango.core.Array; phobos provides no such analogue. With phobos, either write your own routine, or use std.c.stdlib.qsort. I'll let you decide which is more elegant.
Aug 14 2007
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Jarrett Billingsley wrote:
 "John Bartelt" <bartelt cox.net> wrote in message 
 news:f9quel$rou$1 digitalmars.com...
 I have a class that contains two variables. Sometimes I need to sort an 
 array of the class based on variable 1, and later in the same progam sort 
 the array based on variable 2.

 Can someone give me an idea of how to do this (smartly, efficiently, 
 cleverly, polymorphically, ...)?

 Best idea that I've had so far is to use a static flag in the class to 
 indicate which sort is desired, and then to have the overloaded opCmp() 
 check the flag before comparing.

Write your own sort routine which takes a given predicate. :\ Tango provides such a routine in tango.core.Array; phobos provides no such analogue. With phobos, either write your own routine, or use std.c.stdlib.qsort. I'll let you decide which is more elegant.

There's also Oskar's sort w/predicate http://www.csc.kth.se/~ol/array.d I thought the question was more about how to organize the software to control the change in behavior though. For that I think you'll have to think about who "owns" the change in behavior and to whom the change should be visible to. --bb
Aug 14 2007
prev sibling parent reply C. Dunn <cdunn2001 gmail.com> writes:
Jarrett Billingsley Wrote:
 Write your own sort routine which takes a given predicate.  :\
 
 Tango provides such a routine in tango.core.Array; phobos provides no such 
 analogue.  With phobos, either write your own routine, or use 
 std.c.stdlib.qsort.  I'll let you decide which is more elegant. 

It's not just a matter of elegance. C++ std::sort() is way, way faster than qsort in cstdlib because the comparison function gets inlined. Sorting is one place where inlining is critical.
Aug 14 2007
next sibling parent janderson <askme me.com> writes:
C. Dunn wrote:
 Jarrett Billingsley Wrote:
 Write your own sort routine which takes a given predicate.  :\

 Tango provides such a routine in tango.core.Array; phobos provides no such 
 analogue.  With phobos, either write your own routine, or use 
 std.c.stdlib.qsort.  I'll let you decide which is more elegant. 

It's not just a matter of elegance. C++ std::sort() is way, way faster than qsort in cstdlib because the comparison function gets inlined. Sorting is one place where inlining is critical.

In my experience/benchmarks (MS VC++ additions of C++ 2002/2003/2005) I've found that qsort is marginally faster at sorting then std::sort. Now it probably the type of data I was sorting however I don't support the way way faster argument. Note the data I was sorting was pointers, 10-200 elements many times a frame. Also note that std::sort will call the slow copy constructor if you use direct objects while qsort can't. Also MS std::sort is much slower in debug due to all the extra checks they put into iterators. -Joel
Aug 14 2007
prev sibling parent reply Regan Heath <regan netmail.co.nz> writes:
C. Dunn wrote:
 Jarrett Billingsley Wrote:
 Write your own sort routine which takes a given predicate.  :\
 
 Tango provides such a routine in tango.core.Array; phobos provides
 no such analogue.  With phobos, either write your own routine, or
 use std.c.stdlib.qsort.  I'll let you decide which is more elegant.
 

It's not just a matter of elegance. C++ std::sort() is way, way faster than qsort in cstdlib because the comparison function gets inlined. Sorting is one place where inlining is critical.

I believe the intention for D is that the optimizer will automagically inline everything it can. Regan
Aug 15 2007
parent reply Deewiant <deewiant.doesnotlike.spam gmail.com> writes:
Regan Heath wrote:
 C. Dunn wrote:
 It's not just a matter of elegance.  C++ std::sort() is way, way
 faster than qsort in cstdlib because the comparison function gets
 inlined.  Sorting is one place where inlining is critical.

I believe the intention for D is that the optimizer will automagically inline everything it can.

I'd imagine it's quite hard to inline a delegate or function pointer. In any case, the current optimizer is a joke in many ways. Functions, on the other hand, can be inlined, which is why std::sort and D's built-in sort beat C's qsort (assuming they use approximately the same algorithm): they're hard-coded to use "a < b", which is either a "cmp" x86 instruction or an inlineable call to a.opCmp(b) which usually translates to "int < int" and thus a "cmp" anyway. This is why I recently suggested (http://www.dsource.org/projects/tango/ticket/571) that Tango provide for something like: enum Dir : bool { Ascending, Descending } // I forget the correct syntax, sorry if this is wrong template sort(T, Dir D = Dir.Ascending) { bool compare(T a, T b) { static if (D == Dir.Ascending) return a < b; else return a > b; } void sort(T[] a) { // sort using compare for comparing } } This allows the user to choose whether to sort in ascending or descending order, and improves speed noticeably. Currently Tango uses a functor struct: struct IsLess(T) { bool opCall(T a, T b) { return a < b; } } Which is not inlined. A "call" instruction is generated for every comparison. -- Remove ".doesnotlike.spam" from the mail address.
Aug 15 2007
parent reply Regan Heath <regan netmail.co.nz> writes:
Deewiant wrote:
 Regan Heath wrote:
 C. Dunn wrote:
 It's not just a matter of elegance.  C++ std::sort() is way, way
 faster than qsort in cstdlib because the comparison function gets
 inlined.  Sorting is one place where inlining is critical.

inline everything it can.

I'd imagine it's quite hard to inline a delegate or function pointer. In any case, the current optimizer is a joke in many ways.

True about delegates/fpointers I reckon. I don't know why people keep hating on the optimizer. Isn't it the same optimizer used in DMC, a C compiler with 25 odd years of history? Sure, it's not 'optimized' for D specifically but it still holds it's own in shootout results in the general sense, right?
 Functions, on the other hand, can be inlined, which is why std::sort and D's
 built-in sort beat C's qsort (assuming they use approximately the same
 algorithm): they're hard-coded to use "a < b", which is either a "cmp" x86
 instruction or an inlineable call to a.opCmp(b) which usually translates to
"int
 < int" and thus a "cmp" anyway.
 
 This is why I recently suggested
 (http://www.dsource.org/projects/tango/ticket/571) that Tango provide for
 something like:
 
 enum Dir : bool { Ascending, Descending }
 
 // I forget the correct syntax, sorry if this is wrong
 template sort(T, Dir D = Dir.Ascending) {
 	bool compare(T a, T b) {
 		static if (D == Dir.Ascending)
 			return a < b;
 		else
 			return a > b;
 	}
 	
 	void sort(T[] a) {
 		// sort using compare for comparing
 	}
 }
 
 This allows the user to choose whether to sort in ascending or descending
order,
 and improves speed noticeably. Currently Tango uses a functor struct:
 
 struct IsLess(T) {
 	bool opCall(T a, T b) {
 		return a < b;
 	}
 }
 
 Which is not inlined. A "call" instruction is generated for every comparison.

Instead of limiting it to opCall why not define an Interface 'Sortable' and define a compare method which takes a mode flag and "Sortable rhs" or similar. Regan
Aug 15 2007
parent reply Deewiant <deewiant.doesnotlike.spam gmail.com> writes:
Regan Heath wrote:
 Deewiant wrote:
 I'd imagine it's quite hard to inline a delegate or function pointer.
 In any
 case, the current optimizer is a joke in many ways.

True about delegates/fpointers I reckon. I don't know why people keep hating on the optimizer. Isn't it the same optimizer used in DMC, a C compiler with 25 odd years of history? Sure, it's not 'optimized' for D specifically but it still holds it's own in shootout results in the general sense, right?

It's not _bad_ per se. I understand the problem is difficult and that Walter's doing it on his own, but I can't help but drool over the thought of an "Intel D Compiler". The main problems with the Digital Mars optimizer, IMO, are as follows. (Disclaimer: I understand that languages have to cater for many different environments and some of the following may only speed things up on my computer, while slowing things down on others. Still, there are ample resources on the 'Net regarding the performance of practically all parts of various processors.) - Almost no D support, as you say. For instance, slices: array[x .. x + y] array[x..$][0..y] array[0..y][x..$] (&array[x])[0..y] The above forms are equivalent, yet generate very different code. I feel that the middle two are clearer expressions of "take y elements starting from x" but they result in very slow code: it's actually the last one, using a pointer, that's the fastest. - Can't inline functions containing assembly language. This is very annoying: if you have a fast hand-coded micro-optimization you have to manually inline the function everywhere you use it. Otherwise, you tend to end up creating much slower code because the function isn't inlined. - No support for instruction sets beyond the basic x86. (MMX, SSE, 3DNow!, etc.) - In general, can't (or only rarely can) do stuff like loop unrolling, elimination of branching/jumps, and "loop invariant code motion" which is the fancy term for moving something like "x * y * z + a / b - c" from a loop which just sets all array elements to that value. It's really annoying to find that writing something as simple as "int tmp = x*2" prior to a loop and using tmp instead of x*2 can sometimes result in noticeable speedups. Some things which might just be me expecting too much, I don't know how good other optimizers are at this: - Poor execution path analysis. For instance: for (size_t i = 5; i < maximum_i; ++i) { for (size_t j = i; j >= 5; --j) // do stuff } Here, the inner loop tests for j >= 5. Since j = i, and i goes from 5 up to maximum_i, the test will always be true. Hence the test could be eliminated for the first iteration, making the inner loop equivalent to: size_t j = i; do { // stuff } while (j-- >= 5); Another example: assume the loop's contents are simply: array[j-1] = array[j]; Now, two subtractions are performed. First to get j-1, and then to decrement j in the while test. The value could be cached, which may speed things up. (Manually optimizing code combining the above two examples lead to a measurable speedup on a sort algorithm I was benchmarking yesterday.) - Doesn't do algebra very well (includes integer, floating point, boolean, and bit vector algebra). May also be related to the above. For instance: int x = -y; int a = x; int b = a + y; Here, b is set to "a + y", equivalent to "x + y", equivalent to "-y + y", equivalent to 0. This kind of stuff has to be caught manually. Optimizing_cpp.pdf over at http://www.agner.org/optimize/ compares the optimizations applied by C++ compilers in section 7.2, and it includes DMC. It's a bit unfair in that the compilers are of different ages, but I don't think there's been that much progress in any of the compilers anyway.
 Instead of limiting it to opCall why not define an Interface 'Sortable'
 and define a compare method which takes a mode flag and "Sortable rhs"
 or similar.
 

If you just want to sort basic types with varying orderings, wrapping them in a class is a waste of memory and CPU. Currently, the routine takes any callable type: something with opCall, or a function pointer or delegate. The idea is to allow the option of ascending/descending because those are the two most common cases and result in major reduction of execution time. -- Remove ".doesnotlike.spam" from the mail address.
Aug 15 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Deewiant wrote:
 - Almost no D support, as you say. For instance, slices:
 
 array[x .. x + y]
 array[x..$][0..y]
 array[0..y][x..$]
 (&array[x])[0..y]
 
 The above forms are equivalent, yet generate very different code. I feel that

The third one is actually equivalent to array[x..y] and not to the other three.
Aug 15 2007
parent reply Deewiant <deewiant.doesnotlike.spam gmail.com> writes:
Frits van Bommel wrote:
 Deewiant wrote:
 - Almost no D support, as you say. For instance, slices:

 array[x .. x + y]
 array[x..$][0..y]
 array[0..y][x..$]
 (&array[x])[0..y]

 The above forms are equivalent, yet generate very different code.

The third one is actually equivalent to array[x..y] and not to the other three.

Good catch, you're right. It should of course be array[0..x+y][x..$]. I prefer the second form, anyway. -- Remove ".doesnotlike.spam" from the mail address.
Aug 15 2007
parent Regan Heath <regan netmail.co.nz> writes:
Deewiant wrote:
 Frits van Bommel wrote:
 Deewiant wrote:
 - Almost no D support, as you say. For instance, slices:

 array[x .. x + y]
 array[x..$][0..y]
 array[0..y][x..$]
 (&array[x])[0..y]

 The above forms are equivalent, yet generate very different code.

three.

Good catch, you're right. It should of course be array[0..x+y][x..$]. I prefer the second form, anyway.

I prefer the first form, I find the rest confusing. Regan
Aug 15 2007
prev sibling parent reply BCS <ao pathlink.com> writes:
Reply to John,

 I have a class that contains two variables. Sometimes I need to sort
 an array of the class based on variable 1, and later in the same
 progam sort the array based on variable 2.
 
 Can someone give me an idea of how to do this (smartly, efficiently,
 cleverly, polymorphically, ...)?
 
 Best idea that I've had so far is to use a static flag in the class to
 indicate which sort is desired, and then to have the overloaded
 opCmp() check the flag before comparing.
 

you could try some dirty hacks: // what you want to sort class Foo { int myCmp(Object o){...} } // struct of same size with my opCmp struct FooWrap { Foo f; int opCmp(Object o){return f.myCmp(o);} } Foo[] f = ...; // overlay array with new struct array and sort that (cast(FooWrap*)f.ptr)[0..f.length].sort
Aug 14 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
BCS wrote:
 // overlay array with new struct array and sort that
 (cast(FooWrap*)f.ptr)[0..f.length].sort

That probably looks better as "(cast(FooWrap[]) f).sort", which should be equivalent.
Aug 14 2007
parent BCS <ao pathlink.com> writes:
Reply to Frits,

 BCS wrote:
 
 // overlay array with new struct array and sort that
 (cast(FooWrap*)f.ptr)[0..f.length].sort
 

be equivalent.

yes but you might be able to slip that past in a code review (if coffee is in short supply). My version will get you tied to a post and shot (as you is proper) even if everyone else in the room is asleep!
Aug 14 2007