std.partition is fucked

[Andrei Alexandrescu]

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