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

[INADA Naoki]

Good job.  I'll read your work later.

> relatively simple optimization. I would also add that Python dictionaries
> already implement this optimization: they start out optimizing based on the
> assumption that they'll only be seeing string keys, checking to make sure
> that assumption holds as they go. If they see a non-string key, they
> permanently switch over to the general implementation.

Please notice dict is very very special.
Since Python is dynamic language, name resolution is done in runtime,
not compile time.
And most name resolution cause lookup string key from dict.

So please don't use string-key dict specialization to rationalize
list-sort specialization.
Each specialization should be considered carefully about balance between
maintenance cost and benefit.

I feel 2 (int, string) or 3 (int, string, tuple) special case may be
worth enough if
code is clean and benefit seems good.
But more complex cases can be done in third party libraries, like numpy.

In third party library, you can use more powerful optimization like nan-boxing.
In Python builtin list, this is hard because we guarantee object
identity is not changed.

Regards,