[Python-Dev] Optimizing list.sort() by checking type in advance

[Elliot Gorokhovsky]

I'd like to reply to both questions with one email, if that's all right.

Bernardo Sulzbach asked, "How does this interfere with sorting very small
lists?", and ChrisA asked, "How much slower are sorts of heterogeneous
lists?". I modified the benchmark to answer both questions, the former at
the top, and the latter at the bottom (see the git repo):

*** 10 ints ***
F.fastsort(): 2.86102294921875e-06
F.sort(): 3.337860107421875e-06
*** 10 strings ***
F.fastsort(): 1.6689300537109375e-06
F.sort(): 1.6689300537109375e-06
*** 1e3 ints ***
F.fastsort(): 0.00013589859008789062
F.sort(): 0.00018906593322753906
*** 1e3 strings ***
F.fastsort(): 0.0002529621124267578
F.sort(): 0.0002772808074951172
*** 1e7 ints ***
F.fastsort(): 5.472854375839233
F.sort(): 7.8826072216033936
*** 1e7 strings ***
F.fastsort(): 10.104042053222656
F.sort(): 13.139304876327515
*** 1e7 ints + 1 float (to disable the optimization while keeping the
precheck)***
F.fastsort(): 7.57237982749939
F.sort(): 7.666172504425049

ChrisA suggested I also try "make test" or something to get a more
realistic benchmark. I will do that once I implement this as a patch, right
now it's an extension module that subclasses list, so I can't just drop it
into existing code without modification.

Let me know if you have any other questions/suggestions!

On Mon, Oct 10, 2016 at 12:18 AM Elliot Gorokhovsky <
elliot.gorokhovsky at gmail.com> wrote:

> Hi,
>
> I posted here a while back asking what you guys thought about implementing
> radix sort for strings in list.sort(). You gave me a lot of reasons why
> that would be a bad idea. However, it got me thinking, and I came up with
> something that you may find interesting.
>
> First, some simple benchmark results (numbers are seconds, check out the
> extension module at https://github.com/embg/python-fast-listsort.git):
>
> *** 1e3 ints ***
> F.fastsort(): 0.00018930435180664062
> F.sort(): 0.0002830028533935547
> *** 1e3 strings ***
> F.fastsort(): 0.0003533363342285156
> F.sort(): 0.00044846534729003906
> *** 1e7 ints ***
> F.fastsort(): 5.479267358779907
> F.sort(): 8.063318014144897
> *** 1e7 strings ***
> F.fastsort(): 9.992833137512207
> F.sort(): 13.730914115905762
>
> The optimization uses the fact that, in practice, we are almost always
> sorting keys of the same type (note: not objects of the same type, *keys*
> of the same type; we could have a complex key function like str that takes
> many different types, but the keys are still all the same type). So we can
> just do one typecheck up front and then do unsafe comparisons during the
> sort (if our initial check passes). Specifically, we check that for all the
> PyObject* in saved_ob_item, the ob->ob_type are the same. Then we replace
> PyObject_RichCompare with ob_type->tp_richcompare. Additionally, we can
> check for the very common cases of ints and strings and give optimized
> comparison functions for those cases. It might not seem like this would
> save a lot of time, but it turns out that PyObject_RichCompare is a massive
> clusterf**k that has to test tons of type stuff before it can actually
> compare. Cutting that out ends up saving a *lot* of time, as the benchmark
> demonstrates.
>
> What do you think? I'm planning on writing this up into a patch, but
> wanted to get some feedback on the implementation and ideas for improvement
> first.
>
> Thanks,
> Elliot
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20161010/2b73f811/attachment.html>