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.
