.<div class="gmail_quote">On Fri, Jul 2, 2010 at 12:21 PM, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:andrei@erdani.com">andrei@erdani.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
One simple solution would be for you to contribute dstat's sort to Phobos. However, I'd be curious what the reason of std's sort slowness is. I suspect it might be the fact that I use qsort all the way down instead of switching to insertion sort. What is your sort's strategy?<br>
<br></blockquote></div><br>Insertion sort at 25 elements. This is based on fairly heavy empirical testing. I tried disabling this and doing qsort all the way down. This only explains a small part of the difference (about 30 milliseconds' worth). <br>
<br>I looked at the std.algorithm code and I think I see at least part of the problem, but I don't know how to fix it w/o completely gutting the code and rewriting it:<br><br>// This is probably not inlined b/c I don't think DMD can inline nested functions<br>
// that access the outer scope. Someone please confirm this<br>bool pred(ElementType!(Range) a) <br>{<br> return less(a, r.back);<br>}<br>auto right = partition!(pred, ss)(r);<br><br>