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
