[phobos] std.algorithm.sort slow as molasses

[Sean Kelly]

The rules for inlining are weird.  When I wrote Array.sort I noticed that a nested function that took reference parameters (ie. swap) wasn't inlined either, so I changed mine to use indexes and accessed the outer array that way.  For this level of performance tuning you really have to look at the ASM output to see what's going on.

On Jul 2, 2010, at 9:39 AM, David Simcha wrote:

> .
> 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);
> 
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100702/61458618/attachment.html>