<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Sun, Mar 5, 2017 at 6:30 PM INADA Naoki <<a href="mailto:songofacandy@gmail.com">songofacandy@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Good job.  I'll read your work later.<br class="gmail_msg"></blockquote><div><br></div><div>Thanks!<br><br class="gmail_msg"></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
So please don't use string-key dict specialization to rationalize<br class="gmail_msg">
list-sort specialization.<br class="gmail_msg"></blockquote><div><br></div><div>I'm not quite doing that: I agree that dict is a special case because of internal use. I'm just saying that I'm not the first person to try to exploit type homogeneity in data structures in CPython. However, my justification is independent of dict specialization. Namely, it's the following two considerations:<br><br>(1) lists are idiomatically type-homogeneous. To quote the Python documentation, "Lists are mutable, and *their elements are usually homogeneous* and are accessed by iterating over the list".<br></div><div>(2) it's not very common to have to "compare apples and oranges". While it's technically possible to define comparison between any two types you like, and in practice one sometimes compares e.g. ints and floats, in practice it's pretty safe to assume the lists you're sorting are going to be type-homogeneous 95% or 99% of the time.<br></div><div><br class="gmail_msg"></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I feel 2 (int, string) or 3 (int, string, tuple) special case may be worth enough if code is clean and benefit seems good.<br class="gmail_msg"></blockquote><div><br></div><div>I agree -- I only optimized for int, string, float, and tuple. However, my code optimizes sorting for *any* type-homogeneous list as well, by simply replacing PyObject_RichCompareBool with ob_type->richcompare, saving the method lookup time. This is what gives the speedups for non-latin strings and bigints in the benchmarks I shared in my original post: I don't have a special case compare function for them, but by setting the compare function pointer equal to ob_type->richcompare, I can at least save a little bit of method lookup time.<br><br>In terms of clean code, the special-case compare functions include assertions in #ifdef Py_DEBUG blocks that list all the requirements necessary to make them safe. The pre-sort check then verifies the assumptions for whichever optimized compare is going to be used. So all that's necessary to verify correctness is to convince oneself that (1) the assertions are sufficient and (2) the pre-sort check will never use a compare function for which it cannot prove the assertions. These two points are pretty easy to check:<br>(1) Just plug in the assertions in the original code, e.g. unicode_compare in Objects/unicodeobject.c. Then you have a bunch of if(1) and if(0) blocks, and if you delete the if(0) blocks you'll get exactly what I have in the patch.<br>(2) The pre-sort check code is very simple, and well commented.<br>I would add further that this patch only actually adds one line of code to listsort: assign_compare_function(lo.keys, saved_ob_size). The rest of the patch is just function definitions, and replacing PyObject_RichCompareBool with a function pointer (in the macro for ISLT(X,Y)).<br><br></div><div>Anyway, thanks in advance for your time!<br></div><div>Elliot<br></div></div></div>