<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Sun, Mar 5, 2017 at 10:51 AM David Mertz <<a href="mailto:mertz@gnosis.cx">mertz@gnosis.cx</a>> wrote:</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">Thanks for the hard work, this looks very promising.</div></div></div></div></blockquote><div><br></div><div>Thank you!<br> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">Real world data tends to be mostly-sorted.  So it would be useful for your benchmarks to include:</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">A) Performance on completely sorted data</div><div class="gmail_msg">  i) Of homogenous type</div><div class="gmail_msg">  ii) Of mixed type</div><div class="gmail_msg">B) Performance on mostly-sorted data</div><div class="gmail_msg">  i) Of homogenous type</div><div class="gmail_msg">  ii) Of mixed type</div></div></div></div></blockquote><div><br></div><div>You are entirely correct, as the benchmarks below demonstrate. I used the benchmark lists from Objects/listsort.txt, which are:<br><br>      \sort: descending data<br>      /sort: ascending data<br>      3sort: ascending, then 3 random exchanges<br>      +sort: ascending, then 10 random at the end<br>      %sort: ascending, then randomly replace 1% of elements w/ random values<br>      ~sort: many duplicates<br>      =sort: all equal<br><br></div><div>My results are below (the script can be found at <a href="https://github.com/embg/python-fastsort-benchmark/blob/master/bench-structured.py">https://github.com/embg/python-fastsort-benchmark/blob/master/bench-structured.py</a> ):<br>Homogeneous ([int]):<br>\sort: 54.6%<br>/sort: 56.5%<br>3sort: 53.5%<br>+sort: 55.3%<br>%sort: 52.4%<br>~sort: 48.0%<br>=sort: 45.2%<br><br>Heterogeneous ([int]*n + [0.0]):<br>\sort: -17.2%<br>/sort: -19.8%<br>3sort: -18.0%<br>+sort: -18.8%<br>%sort: -10.0%<br>~sort: -2.1%<br>=sort: -21.3%<br></div><div><br></div><div>As you can see, because there's a lot less non-comparison overhead in the structured lists, the impact of the optimization is much greater, both in performance gain and in worst-case cost. However, I would argue that these data do not invalidate the utility of my patch: the probability of encountering a type-heterogeneous list is certainly less than 5% in practice. So the expected savings, even for structured lists, is something like (5%)(-20%) + (95%)(50%) = 46.5%. And, of course, not *all* the lists one encounters in practice are structured; certainly not *this* structured. So, overall, I would say the numbers above are extremely encouraging. Thanks for pointing out the need for this benchmark, though!<br><br></div><div>Elliot<br></div></div></div>