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
