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

[David Mertz]

On Sun, Mar 5, 2017 at 8:33 PM, Elliot Gorokhovsky <
elliot.gorokhovsky at gmail.com> wrote:

> On Sun, Mar 5, 2017 at 9:25 PM Tim Peters <tim.peters at gmail.com> wrote:
>
>> 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 and
> 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?
>

Could we make the file global a table of comparison functions and have each
thread reference a position in the table? It would be fine if multiple
threads happened to use the position of e.g. the int comparison, just so
long as each chose the right slot in the table.

-- 
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.

On Sun, Mar 5, 2017 at 8:33 PM, Elliot Gorokhovsky <
elliot.gorokhovsky at gmail.com> wrote:

> 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
>
>
>
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>



-- 
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20170305/a730a8b2/attachment-0001.html>