<div dir="ltr"><div class="gmail_quote"><div dir="ltr" class="gmail_msg">Thanks for looking at this!<br class="gmail_msg"><br class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">That's why I spent months of my life (overall) devising a sequence of sorting algorithms for Python that reduced the number of comparisons needed.</span><br class="gmail_msg"></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">Yes, that's why I think this is so cool: for a couple dozen lines of code, we can get (at least for some cases, according to my questionable benchmarks) the kinds of massive improvements you had to use actual computer science to achieve (as opposed to mere hackery).<br class="gmail_msg"> <br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">Note that when Python's current sort was adopted in Java, they still kept a quicksort variant for "unboxed" builtin types.  The adaptive merge sort incurs many overheads that often cost more than they save unless comparisons are in fact very expensive compared to the cost of pointer copying (and in Java comparison of unboxed types is cheap).  Indeed, for native numeric types, where comparison is dirt cheap, quicksort generally runs faster than mergesort despite that the former does _more_ comparisons (because mergesort does so much more pointer-copying).</span><br class="gmail_msg"></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">Ya, I think this may be a good approach for floats: if the list is all floats, just copy all the floats into a seperate array, use the standard library quicksort, and then construct a sorted PyObject* array. Like maybe set up a struct { PyObject* payload, float key } type of deal. This wouldn't work for strings (unicode is scary), and probably not for ints (one would have to check that all the ints are within C long bounds). Though on the other hand perhaps this would be too expensive? <br class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">I had considered something "like this" for Python 2, but didn't pursue it because comparison was defined between virtually any two types (34 < [1], etc), and people were careless about that (both by design and by accident).  In Python 3, comparison "blows up" for absurdly mixed types, so specializing for homogeneously-typed lists is a more promising idea on the face of it.</span><br class="gmail_msg"><br class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">The comparisons needed to determine _whether_ a list's objects have a common type is just len(list)-1 C-level pointer comparisons, and so goes fast.  So I expect that, when it applies, this would speed even sorting an already-ordered list with at least 2 elements.</span><br class="gmail_msg"><br class="gmail_msg"></div></blockquote></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">That's what my crude benchmarks indicate... when I applied my sort to a list of 1e7 ints with a float tacked on the end, my sort actually ended up being a bit faster over several trials (which I attribute to PyObject_RichCompare == Py_True being faster than PyObject_RichCompareBool == 1, apologies for any typos in that code).<br class="gmail_msg"> <br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">For a mixed-type list with at least 2 elements, it will always be pure loss.  But (a) I expect such lists are uncommon (and especially uncommon in Python 3); and (b) a one-time scan doing C-level pointer comparisons until finding a mismatched type is bound to be a relatively tiny cost compared to the expense of all the "rich comparisons" that follow.</span><br class="gmail_msg"><br class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">So +1 from me on pursuing this.</span><br class="gmail_msg"><br class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">Elliot, please:</span><br class="gmail_msg"><br class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">- Keep this on python-ideas.  python-dev is for current issues in Python development, not for speculating about changes.</span><br class="gmail_msg"><br class="gmail_msg"><span style="font-size:12.8px" class="gmail_msg">- Open an issue on the tracker:  <a href="https://bugs.python.org/" class="gmail_msg" target="_blank">https://bugs.python.org/</a></span><br class="gmail_msg"></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">OK<br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg"> </div><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg">- At least browse the info for developers:  <a href="https://docs.python.org/devguide/" class="gmail_msg" target="_blank">https://docs.python.org/devguide/</a><br class="gmail_msg"></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">Ya, I'm working on setting this up as a patch in the hg repo as opposed to an extension module to make benchmarking cleaner/more sane.<br class="gmail_msg"> <br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" 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">- Don't overlook Lib/test/sortperf.py.  As is, it should be a good test of what your approach so far _doesn't_ help, since it sorts only lists of floats (& I don't think you're special-casing them).  If the timing results it reports aren't significantly hurt (and I expect they won't be), then add specialization for floats too and gloat about the speedup :-)<br class="gmail_msg"><br class="gmail_msg"></div></div></blockquote></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">Ya, I mean they aren't special-cased, but homogenous lists of floats still fit in the tp->rich_compare case, which still bypasses the expensive PyObject_RichCompare. I'll guess I'll see when I implement this as a patch and can run it on sortperf.py.<br class="gmail_msg"> <br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><blockquote class="gmail_quote gmail_msg" 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">- I expect tuples will also be worth specializing (complex sort keys are often implemented as tuples).<br class="gmail_msg"></div></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">I'm not sure what you mean here... I'm looking at the types of lo.keys, not of saved_ob_item (I think I said that earlier in this thread by mistake actually). So if someone is passing tuples and using itemgetter to extract ints or strings or whatever, the current code will work fine; lo.keys will be scalar types. Unless I misunderstand you here. I mean, when would lo.keys actually be tuples?<br class="gmail_msg"></div><div class="gmail_msg"> </div><blockquote class="gmail_quote gmail_msg" 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><div class="gmail_extra gmail_msg">Nice start! :-)</div></div><br class="gmail_msg"></blockquote><div class="gmail_msg">Thanks! <br class="gmail_msg"></div></div></div></div></div></div>