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

[Tim Peters]

[Elliot Gorokhovsky <elliot.gorokhovsky at gmail.com>]
> Another solution: check if there is more than one thread; if there is, then
> disable optimization. Is sorting in multithreaded programs common enough
> to warrant adding the complexity to deal with it?

Not a solution.  Not even close ;-)  Even if it made good sense,
there's nothing to stop a custom __lt__ method from creating new
threads _during_ a sort.

The best approach is indeed to pass the function pointer to every
location that needs it.  Note that a MergeState struct is already
created per sort invocation, That isn't a file global for much the
same reason.

However, it's not just threads that are a potential problem.  Suppose
a custom __lt__ method, invoked during a sort, does a new sort of its
own.  That's in the same thread, but may well want a different
specialized comparison function.  Solve _that_, and "the thread
problem" will almost certainly solve itself by magic too.  But solving
"the thread problem" doesn't necessarily solve "the same-thread
reentrancy problem".

That's why the MergeState struct is a function local ("auto" in silly
C terminology).  Since it lives in fresh stack space for each
invocation of `listsort()` it solves both the thread and reentrancy
problems:  every invocation of `listsort()` (regardless of whether
from different threads or from the same thread) gets its own
MergeState space.

You may or may not get simpler code by storing the function pointer as
a new member of the MergeState struct.  But however that's spelled, it
does need to be passed to each function that needs it.