[Python-ideas] Exploiting type-homogeneity in list.sort() (again!)
Elliot Gorokhovsky
elliot.gorokhovsky at gmail.com
Sun Mar 5 23:33:11 EST 2017
On Sun, Mar 5, 2017 at 9:25 PM Tim Peters <tim.peters at gmail.com> wrote:
>
> Would someone please move the patch along? I expect it's my fault it's
> languished so long, since I'm probably the natural person to review it, but
> I've been buried under other stuff.
>
> But the patch doesn't change anything about the sorting algorithm itself -
> even shallow knowledge of how timsort works is irrelevant. It's just
> plugging in a different bottom-level object comparison _function_ when that
> appears valuable.
>
> I've said from the start that it's obvious (to me ;-) ) that it's an
> excellent tradeoff. At worst it adds one simple (pre)pass over the list
> doing C-level pointer equality comparisons. That's cheap. The worst-case
> damage is obviously small, the best-case gain is obviously large, and the
> best cases are almost certainly far more common than the worst cases in
> most code.
>
Thank you so much for the support! Yes to all of those things!
>
> In reviewing my own code, after it was fiddled to work under Python 3
> there are no mixed-type lists that are ever sorted. There are lists with
> complex objects, but whenever those are sorted there's a `key=` argument
> that reduces the problem to sorting ints or tuples of builtin scalar types.
>
I'm adding that quote to the next version my poster :)
>
> One subtle thing to look at: thread safety. IIRC, the patch plugged the
> comparison function into a file global. That's obviously hosed if multiple
> threads sort different kinds of lists simultaneously.
>
Wow, that is a *very* good point. I never think about those kinds of
things, being a n00b, so thanks for catching that... I'll have to go in an
fix that. I'm not sure how, though, because the ISLT macro gets called in a
bunch of different functions. The only way I can think of to fix it would
be to pass the function pointer as an argument to *all* the functions that
use ISLT, which would be pretty messy. What do you think would be the
easiest fix?
Thanks!
Elliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20170306/aa1aa416/attachment.html>
More information about the Python-ideas
mailing list