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

[Tim Delaney]

On 9 March 2017 at 21:04, Barry Scott <barry at barrys-emacs.org> wrote:

> It was not clear to me that you need to scan the list at the start to make
> sure its homogeneous. Given that the type check is so cheap will it
> slow the sort if you do the pointer check in the compare code? I am not
> suggesting you run rich compare full fat on each compare.
>

Isn't there already always a scan of the iterable to build the keys array
for sorting (even if no key keyword param is specified)? In which case
adding the homogenity check there seems like it shouldn't add much overhead
at all (I have to say that I was surprised with 10+% reductions in speed in
some of the heterogenous TimSort tests for this reason).

And could specific richcompares be refactored so there was a "we really
know what the types are is, no need to check" version available to sort()
(with the typechecking version available for general use/unoptimised
sorting)?

Tim Delaney
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20170310/0c5451d6/attachment.html>