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

Elliot Gorokhovsky elliot.gorokhovsky at gmail.com
Sun Mar 5 22:16:25 EST 2017


On Sun, Mar 5, 2017 at 8:09 PM David Mertz <mertz at gnosis.cx> wrote:

>
> If we added __type_hint__ as None/type-object and added those comparisons
> to it on .insert()/.append()/etc, then we would be slower by some increment
> while all we were doing was adding things.  There could only be a win when
> the list is sorted (but a big win for that case).
>

Exactly.


>
> In real world code, how often are lists sorted? Also I'm not really
> confident that Elliot's estimates of 95% of lists being homogeneous holds,
> but the speedup he proposes would seem to win even if that percentage is a
> lot lower than 95%.  If only 10% of lists in real world code ever get
> `my_list.sort()` called on them, Steven's idea is probably not good.  If
> 50% of lists do, it probably is.  But then, it depends just how *often*
> lists that get sorted are re-sorted too.
>

I would imagine that fewer than even 10% of lists in real world code ever
get sorted. I mean, just crawl PyPI and look for `.sort()` or `sorted()`;
you'll find it's not that common. I know, because I was hoping to be able
to demonstrate non-trivial improvements on the benchmark suites, but they
just don't sort enough for it to show up. You only see application-level
speedups if you're doing a *lot* of sorting, like in DEAP Pareto selection
(DEAP is a popular Python evolutionary algorithms library; you sometimes
have to sort individuals in the population by fitness, and the population
is huge). And the cost of doing the pre-sort check isn't that bad,
anyway... I think that making *every* append slower just for sorting/etc
would be a net loss.

Anyway, like I said earlier, my patch could be a first step towards a more
broad optimization like this.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20170306/72a03c2f/attachment.html>


More information about the Python-ideas mailing list