[Python-ideas] Exploiting type-homogeneity in list.sort() (again!)

[Elliot Gorokhovsky]

On Sun, Mar 5, 2017 at 6:30 PM INADA Naoki <songofacandy at gmail.com> wrote:

> Good job.  I'll read your work later.
>

Thanks!

So please don't use string-key dict specialization to rationalize
> list-sort specialization.
>

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:

(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".
(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.

I feel 2 (int, string) or 3 (int, string, tuple) special case may be worth
> enough if code is clean and benefit seems good.
>

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.

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:
(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.
(2) The pre-sort check code is very simple, and well commented.
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)).

Anyway, thanks in advance for your time!
Elliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20170306/a43a180a/attachment-0001.html>