[phobos] std.algorithm.sort slow as molasses

[Andrei Alexandrescu]

Working around that would mess much of the elegance of std.sort, sigh. 
The nice thing is that sort reuses partition instead of writing a 
dedicated version of it (as I had in my implementation for a while). I 
was quite glad I'd pulled that off.

Andrei

David Simcha wrote:
> .
> On Fri, Jul 2, 2010 at 12:21 PM, Andrei Alexandrescu <andrei at erdani.com 
> <mailto: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);
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos