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
