[phobos] std.algorithm.sort slow as molasses

[David Simcha]

.
On Fri, Jul 2, 2010 at 12:21 PM, Andrei Alexandrescu <andrei at erdani.com>wrote:

> One simple solution would be for you to contribute dstat's sort to Phobos.
> However, I'd be curious what the reason of std's sort slowness is. I suspect
> it might be the fact that I use qsort all the way down instead of switching
> to insertion sort. What is your sort's strategy?
>
>
Insertion sort at 25 elements.  This is based on fairly heavy empirical
testing.  I tried disabling this and doing qsort all the way down.  This
only explains a small part of the difference (about 30 milliseconds'
worth).

I looked at the std.algorithm code and I think I see at least part of the
problem, but I don't know how to fix it w/o completely gutting the code and
rewriting it:

// This is probably not inlined b/c I don't think DMD can inline nested
functions
// that access the outer scope.  Someone please confirm this
bool pred(ElementType!(Range) a)
{
       return less(a, r.back);
}
auto right = partition!(pred, ss)(r);
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100702/49015881/attachment.html>