[phobos] std.algorithm.sort slow as molasses

[Brad Roberts]

Please file bugs with reduced test cases where seemingly obvious inlining 
isn't done.  I'd like to spend time on them.  Ref parameters were one of 
the things that blocked inlining until this most recent release (or maybe 
the one before that).  That works now. :)

On Fri, 2 Jul 2010, Sean Kelly wrote:

> Date: Fri, 2 Jul 2010 11:26:58 -0700
> From: Sean Kelly <sean at invisibleduck.org>
> Reply-To: Discuss the phobos library for D <phobos at puremagic.com>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Subject: Re: [phobos] std.algorithm.sort slow as molasses
> 
> 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 --------------
_______________________________________________
phobos mailing list
phobos at puremagic.com
http://lists.puremagic.com/mailman/listinfo/phobos