std.partition is fucked

[Andrei Alexandrescu]

Lutger wrote:
> Andrei Alexandrescu wrote:
> 
>> Sean Kelly wrote:
>>> Andrei Alexandrescu wrote:
>>>> 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.
>>> The built-in sort uses an internal stack rather than recursion, which 
>>> makes its performance on a best-case dataset hard to beat.  I finally 
>>> satisfied myself by having a constant time overhead vs. the built-in 
>>> sort for best-case and beat it by polynomial time for worst-case (the 
>>> built-in sort doesn't adapt to worst-case datasets very well).
>> Yeah, I saw that fixed-size stack. I'm not sure whether that's 
>> responsible for much of its performance, one of these days I need to 
>> measure. My speculation is that the depth of the stack is small enough 
>> to not really contribute much to the running time.
>>
>> Andrei
> 
> Some time ago I reinvented these wheels for study purpose. A custom stack was a little faster but not that much. std.swap can't be inlined because it uses ref params, that cost also a bit since it's called 
> many times. Switching to another sort if a certain recursion depth is reached helped, but mostly in degenerate cases. 
> 
> I still have the thing somewhere, it is about twice as fast as builtin sort. It's not a lot of work but I could dig it up and provide some timings if you want. 

Would be interesting if it's not too much trouble.

If swap is not inlined that would be serious. Sort does a lot of swapping.


Andrei