std.partition is fucked

[Lutger]

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.