www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.partition is fucked

reply superdan <super dan.org> writes:
dis must be related to bug 2966 sayin' std.sort is fucked. problem must be with
std.partition. i tested and unstable partition is 10 times slower than stable.
should be faster akshully. so looked into tat and found in da loop for
std.partition unstable and found da range r1 is fucked.

        for (;;)
        {
            for (;;)
            {
                if (r.empty) return r;
                if (!pred(r.front)) break;
                r.popFront;
            }
            // found the left bound
            assert(!r.empty);
            auto r1 = r;
            for (;;)
            {
                if (pred(r1.back)) break;
                r1.popBack;
                if (r1.empty) return r;
            }
            // found the right bound, swap & make progress
            swap(r.front, r1.back);
            r.popFront;
            r1.popBack;
        }

r1 is popbacked a few times but then all tat is forgotten the next time around
da loop coz r1 is local to da loop. so da loop is quadratic methinks. what u
need iz save r outside loop & then popfront & popback from da same range 'n'
shit.
May 13 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
superdan wrote:
 dis must be related to bug 2966 sayin' std.sort is fucked. problem
 must be with std.partition. i tested and unstable partition is 10
 times slower than stable. should be faster akshully. so looked into
 tat and found in da loop for std.partition unstable and found da
 range r1 is fucked.

That is correct. Where were you yesterday when I was looking for this? :o) The fixed loop is: // Inspired from www.stepanovpapers.com/PAM3-partition_notes.pdf, // section "Bidirectional Partition Algorithm (Hoare)" auto result = r; for (;;) { for (;;) { if (r.empty) return result; if (!pred(r.front)) break; r.popFront; result.popFront; } // found the left bound assert(!r.empty); for (;;) { if (pred(r.back)) break; r.popBack; if (r.empty) return result; } // found the right bound, swap & make progress swap(r.front, r.back); r.popFront; result.popFront; r.popBack; } Note how the left edge of result follows the left edge of r, but the right edge stays put because partition() returns the right-hand-side range. r shrinks from both ends to exhaustion. The performance of std.sort is back to normal - still slower than the built-in sort (but not by orders of magnitude), probably because bumping ranges is at a disadvantage. Thanks David and superdan. Andrei
May 13 2009
next sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
Andrei Alexandrescu wrote:
 
 Note how the left edge of result follows the left edge of r, but the 
 right edge stays put because partition() returns the right-hand-side 
 range. r shrinks from both ends to exhaustion.

So all the elements that satisfy the predicate end up at the end of the original range instead of the beginning? Was that an arbitrary choice, or is there a reason for it?
May 13 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
 Andrei Alexandrescu wrote:
 Note how the left edge of result follows the left edge of r, but the 
 right edge stays put because partition() returns the right-hand-side 
 range. r shrinks from both ends to exhaustion.

So all the elements that satisfy the predicate end up at the end of the original range instead of the beginning? Was that an arbitrary choice, or is there a reason for it?

The elements satisfying the predicate are at the beginning, see e.g. the unittests. The range returned is (as always) the right-hand side, i.e. the range containing the elements that don't satisfy the predicate. Andrei
May 13 2009
parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Sean Kelly wrote:
 Andrei Alexandrescu wrote:
 Note how the left edge of result follows the left edge of r, but the
 right edge stays put because partition() returns the right-hand-side
 range. r shrinks from both ends to exhaustion.

So all the elements that satisfy the predicate end up at the end of the original range instead of the beginning? Was that an arbitrary choice, or is there a reason for it?

unittests. The range returned is (as always) the right-hand side, i.e. the range containing the elements that don't satisfy the predicate.

Weird. I'd always thought that the standard behavior was the opposite. That way partition could be passed a lessThan predicate and be used for sorting. Though I guess you can just use a greaterThan predicate instead.
May 13 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Sean Kelly wrote:
 Andrei Alexandrescu wrote:
 Note how the left edge of result follows the left edge of r, but the
 right edge stays put because partition() returns the right-hand-side
 range. r shrinks from both ends to exhaustion.

original range instead of the beginning? Was that an arbitrary choice, or is there a reason for it?

unittests. The range returned is (as always) the right-hand side, i.e. the range containing the elements that don't satisfy the predicate.

Weird. I'd always thought that the standard behavior was the opposite. That way partition could be passed a lessThan predicate and be used for sorting. Though I guess you can just use a greaterThan predicate instead.

Nono, lessThan is a binary predicate whereas partition takes a unary predicate. The spec of partition is very simple: do whatever the hell it takes to put elements e that satisfy pred(e) before elements that don't. If you follow the way std.sort uses partition, you'll see that it passes a unary predicate that compares for less than against the chosen pivot. Andrei
May 13 2009
parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Sean Kelly wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Sean Kelly wrote:
 Andrei Alexandrescu wrote:
 Note how the left edge of result follows the left edge of r, but the
 right edge stays put because partition() returns the right-hand-side
 range. r shrinks from both ends to exhaustion.

original range instead of the beginning? Was that an arbitrary choice, or is there a reason for it?

unittests. The range returned is (as always) the right-hand side, i.e. the range containing the elements that don't satisfy the predicate.

Weird. I'd always thought that the standard behavior was the opposite. That way partition could be passed a lessThan predicate and be used for sorting. Though I guess you can just use a greaterThan predicate instead.

predicate. The spec of partition is very simple: do whatever the hell it takes to put elements e that satisfy pred(e) before elements that don't. If you follow the way std.sort uses partition, you'll see that it passes a unary predicate that compares for less than against the chosen pivot.

Okay, I think we're talking at cross-purposes :-) It seems we both agree that partition should place the elements satisfying pred before those that do not. And I should have been more clear about pred being a unary function. In any case, what I'm wondering is why partition returns the range representing the elements that do not satisfy pred. When I call partition, wouldn't I be interested in the result containing the elements that have satisfied the supplied predicate? Or does this cause problems for the sort routine.
May 13 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Sean Kelly wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Sean Kelly wrote:
 Andrei Alexandrescu wrote:
 Note how the left edge of result follows the left edge of r, but the
 right edge stays put because partition() returns the right-hand-side
 range. r shrinks from both ends to exhaustion.

original range instead of the beginning? Was that an arbitrary choice, or is there a reason for it?

unittests. The range returned is (as always) the right-hand side, i.e. the range containing the elements that don't satisfy the predicate.

That way partition could be passed a lessThan predicate and be used for sorting. Though I guess you can just use a greaterThan predicate instead.

predicate. The spec of partition is very simple: do whatever the hell it takes to put elements e that satisfy pred(e) before elements that don't. If you follow the way std.sort uses partition, you'll see that it passes a unary predicate that compares for less than against the chosen pivot.

Okay, I think we're talking at cross-purposes :-) It seems we both agree that partition should place the elements satisfying pred before those that do not. And I should have been more clear about pred being a unary function. In any case, what I'm wondering is why partition returns the range representing the elements that do not satisfy pred. When I call partition, wouldn't I be interested in the result containing the elements that have satisfied the supplied predicate? Or does this cause problems for the sort routine.

Oh, now I understand. Sorry. As a general rule, when they could return either the left or the right subrange of a range, functions in std.algorithm return the right range. This is because sentinel-terminated ranges cannot express the left-hand-side range. Partition is in fact the perfect example because it works with forward ranges. If you want to partition a singly-linked list, you'd have to return the right-hand sublist. There's nothing else you could possibly return! If you wanted to return the left-hand sublist, you'd have to return a different type of range (something like "list up to this node"). So for generality's sake, whenever you have a choice, return the right-hand part of a range. There is growing interest in defining additional ranges that express (at a cost) things like "the portion of a singly-linked list starting at node X and ending at node Y". For example, people want to do a find() and then deal with the portion _before_ the found element. I'd love to discuss that further, but I guess I'll have to wait for the d.next newsgroup. :oD Andrei
May 13 2009
next sibling parent Sean Kelly <sean invisibleduck.org> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 As a general rule, when they could return either the left or the right
 subrange of a range, functions in std.algorithm return the right range.
 This is because sentinel-terminated ranges cannot express the
 left-hand-side range.

Gotcha. That's unfortunate, but makes perfect sense.
 Partition is in fact the perfect example because it works with forward
 ranges. If you want to partition a singly-linked list, you'd have to
 return the right-hand sublist. There's nothing else you could possibly
 return! If you wanted to return the left-hand sublist, you'd have to
 return a different type of range (something like "list up to this node").
 So for generality's sake, whenever you have a choice, return the
 right-hand part of a range.

It looks like there may be another bug in partition then. The static else clause (ss == SwapStrategy.unstable) is supposed to work for forward ranges but it calls popBack(). It looks like only the semistable option is actually available to forward ranges. Is this correct?
 There is growing interest in defining additional ranges that express (at
 a cost) things like "the portion of a singly-linked list starting at
 node X and ending at node Y". For example, people want to do a find()
 and then deal with the portion _before_ the found element. I'd love to
 discuss that further, but I guess I'll have to wait for the d.next
 newsgroup. :oD

Yeah, it would be great if it were possible to slice and dice a range in any manner of different ways.
May 13 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:
 On Wed, 13 May 2009 17:17:33 -0400, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> wrote:
 
 Partition is in fact the perfect example because it works with forward
 ranges. If you want to partition a singly-linked list, you'd have to
 return the right-hand sublist. There's nothing else you could possibly
 return! If you wanted to return the left-hand sublist, you'd have to
 return a different type of range (something like "list up to this node").

It depends on if the sentinel is static. For example, it would be perfectly legal to specify a linked list as the nodes between node x and y, where y is null at runtime in the case of a full list. I'm not even sure the performance would suffer significantly. dcollections' linked list is a doubly linked list, but I use a sentinel dummy element to denote both the beginning and the end. It makes insertion/deletion code completely uniform because there is *always* a valid previous and next node for each node. No checking for "if this is the head node, update the original list pointer" Not being able to return a subrange of a container as fundamental as a linked list is a pretty significant oversight in my opinion.

Well it's not quite an oversight because I was well aware of the issue. The only thing is, I started with the narrowest interface I could to figure how far I can get. Primitives can be added to select range categories as needed. Andrei
May 13 2009
prev sibling next sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
Andrei Alexandrescu wrote:
 
 The performance of std.sort is back to normal - still slower than the 
 built-in sort (but not by orders of magnitude), probably because bumping 
 ranges is at a disadvantage.

The built-in sort uses an internal stack rather than recursion, which makes its performance on a best-case dataset hard to beat. I finally satisfied myself by having a constant time overhead vs. the built-in sort for best-case and beat it by polynomial time for worst-case (the built-in sort doesn't adapt to worst-case datasets very well).
May 13 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
 Andrei Alexandrescu wrote:
 The performance of std.sort is back to normal - still slower than the 
 built-in sort (but not by orders of magnitude), probably because 
 bumping ranges is at a disadvantage.

The built-in sort uses an internal stack rather than recursion, which makes its performance on a best-case dataset hard to beat. I finally satisfied myself by having a constant time overhead vs. the built-in sort for best-case and beat it by polynomial time for worst-case (the built-in sort doesn't adapt to worst-case datasets very well).

Yeah, I saw that fixed-size stack. I'm not sure whether that's responsible for much of its performance, one of these days I need to measure. My speculation is that the depth of the stack is small enough to not really contribute much to the running time. Andrei
May 13 2009
parent reply Lutger <lutger.blijdestijn gmail.com> writes:
Andrei Alexandrescu wrote:

 Sean Kelly wrote:
 Andrei Alexandrescu wrote:
 The performance of std.sort is back to normal - still slower than the 
 built-in sort (but not by orders of magnitude), probably because 
 bumping ranges is at a disadvantage.

The built-in sort uses an internal stack rather than recursion, which makes its performance on a best-case dataset hard to beat. I finally satisfied myself by having a constant time overhead vs. the built-in sort for best-case and beat it by polynomial time for worst-case (the built-in sort doesn't adapt to worst-case datasets very well).

Yeah, I saw that fixed-size stack. I'm not sure whether that's responsible for much of its performance, one of these days I need to measure. My speculation is that the depth of the stack is small enough to not really contribute much to the running time. Andrei

Some time ago I reinvented these wheels for study purpose. A custom stack was a little faster but not that much. std.swap can't be inlined because it uses ref params, that cost also a bit since it's called many times. Switching to another sort if a certain recursion depth is reached helped, but mostly in degenerate cases. I still have the thing somewhere, it is about twice as fast as builtin sort. It's not a lot of work but I could dig it up and provide some timings if you want.
May 13 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Lutger wrote:
 Andrei Alexandrescu wrote:
 
 Sean Kelly wrote:
 Andrei Alexandrescu wrote:
 The performance of std.sort is back to normal - still slower than the 
 built-in sort (but not by orders of magnitude), probably because 
 bumping ranges is at a disadvantage.

makes its performance on a best-case dataset hard to beat. I finally satisfied myself by having a constant time overhead vs. the built-in sort for best-case and beat it by polynomial time for worst-case (the built-in sort doesn't adapt to worst-case datasets very well).

responsible for much of its performance, one of these days I need to measure. My speculation is that the depth of the stack is small enough to not really contribute much to the running time. Andrei

Some time ago I reinvented these wheels for study purpose. A custom stack was a little faster but not that much. std.swap can't be inlined because it uses ref params, that cost also a bit since it's called many times. Switching to another sort if a certain recursion depth is reached helped, but mostly in degenerate cases. I still have the thing somewhere, it is about twice as fast as builtin sort. It's not a lot of work but I could dig it up and provide some timings if you want.

Would be interesting if it's not too much trouble. If swap is not inlined that would be serious. Sort does a lot of swapping. Andrei
May 13 2009
next sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 If swap is not inlined that would be serious. Sort does a lot of swapping.

It only works for arrays, but what I ended up doing to get swap inlined was to pass it two array indices instead of two references. There must be some way to address this for ranges if ref parameters prevent inlining with DMD.
May 13 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 If swap is not inlined that would be serious. Sort does a lot of swapping.

It only works for arrays, but what I ended up doing to get swap inlined was to pass it two array indices instead of two references. There must be some way to address this for ranges if ref parameters prevent inlining with DMD.

Well the least we can do is to say static if (is(Range R == T[], T)) { ... use array-specific swap ... } else { ... use regular swap ... } Andrei
May 13 2009
prev sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7Bit

fwiw, I found the code and attached it with a benchmark found in the bugreport
(2966). It works only on arrays, might be buggy too. But it does sort ;)

Timings based on 1000_000 elements:

std.algorithm:  624 // modified with the fix posted in this thread
Builtin sort:  540
iterative introsort:  244
May 13 2009
prev sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Lutger (lutger.blijdestijn gmail.com)'s article
 Some time ago I reinvented these wheels for study purpose. A custom stack was
a little faster but not

 many times. Switching to another sort if a certain recursion depth is reached
helped, but mostly in

 I still have the thing somewhere, it is about twice as fast as builtin sort.
It's not a lot of work but I could

The sort I wrote for Tango uses the same basic heuristics, thanks to a ticket that either you or Stewart Gordon submitted long ago. I've been meaning to compare it against the sort routine in std.algorithm to see whether the Phobos routine could benefit from any of the same tweaks.
May 13 2009
next sibling parent reply Matti Niemenmaa <see_signature for.real.address> writes:
Sean Kelly wrote:
 The sort I wrote for Tango uses the same basic heuristics, thanks to
 a ticket that either you or Stewart Gordon submitted long ago.

*Ahem*, I believe that http://www.dsource.org/projects/tango/ticket/571 was one of mine ;-) -- E-mail address: matti.niemenmaa+news, domain is iki (DOT) fi
May 13 2009
parent Sean Kelly <sean invisibleduck.org> writes:
== Quote from Matti Niemenmaa (see_signature for.real.address)'s article
 Sean Kelly wrote:
 The sort I wrote for Tango uses the same basic heuristics, thanks to
 a ticket that either you or Stewart Gordon submitted long ago.

was one of mine ;-)

Darnit, I knew if I didn't look it up I'd get it wrong. Sorry about that :-)
May 13 2009
prev sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
Sean Kelly wrote:

 == Quote from Lutger (lutger.blijdestijn gmail.com)'s article
 Some time ago I reinvented these wheels for study purpose. A custom stack was
a little faster but not

 many times. Switching to another sort if a certain recursion depth is reached
helped, but mostly in

 I still have the thing somewhere, it is about twice as fast as builtin sort.
It's not a lot of work but I could

The sort I wrote for Tango uses the same basic heuristics, thanks to a ticket that either you or Stewart Gordon submitted long ago. I've been meaning to compare it against the sort routine in std.algorithm to see whether the Phobos routine could benefit from any of the same tweaks.

It wasn't me, I used the Tango code as one the sources to study this algorithm :)
May 13 2009
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Wed, 13 May 2009 22:24:51 +0400, Lutger <lutger.blijdestijn gmail.com> wrote:

 std.swap can't be inlined because it uses ref params

Can you elaborate on that one? I'm not so sure that it can't be inlined.
May 13 2009
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 13 May 2009 17:17:33 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 Partition is in fact the perfect example because it works with forward
 ranges. If you want to partition a singly-linked list, you'd have to
 return the right-hand sublist. There's nothing else you could possibly
 return! If you wanted to return the left-hand sublist, you'd have to
 return a different type of range (something like "list up to this node").

It depends on if the sentinel is static. For example, it would be perfectly legal to specify a linked list as the nodes between node x and y, where y is null at runtime in the case of a full list. I'm not even sure the performance would suffer significantly. dcollections' linked list is a doubly linked list, but I use a sentinel dummy element to denote both the beginning and the end. It makes insertion/deletion code completely uniform because there is *always* a valid previous and next node for each node. No checking for "if this is the head node, update the original list pointer" Not being able to return a subrange of a container as fundamental as a linked list is a pretty significant oversight in my opinion. -Steve
May 13 2009