Re: [Python-ideas] Submitted a PR!

[Elliot Gorokhovsky]

There is an "apple to apple" compare function. It's unsafe_object_compare.
If you look at the pre-sort check, you will find that if the list is
homogeneous but not of float, int, string, or tuple, it sets
compare_funcs.key_richcompare = ob_type->tp_richcompare and sets
compare_funcs.key_compare = unsafe_object_compare. The latter is a wrapper
for the former, bypassing the type checks in PyObject_RichCompareBool.
Examples of benchmarks that use this functionality include the non-latin
string and unbounded int benchmarks.

In the table at the bottom of my patch description, it's described as
follows:

Compare function for general homogeneous lists; just a wrapper for
ob_type->tp_richcompare, which is stored by the pre-sort check at
compare_funcs.key_richcompare. This yields modest optimization
(neighbourhood of 10%), but we generally hope we can do better.

Further, in the code, the comments describe it as follows:

/* Homogeneous compare: safe for any two compareable objects of the same
type.
* (compare_funcs.key_richcompare is set to ob_type->tp_richcompare in the
* pre-sort check.)
*/

Does that answer your question?



On Thu, Mar 9, 2017 at 6:18 PM Erik  wrote:

> Hi.
>
> I may be way off-base here, but having scanned the patch I'm not sure I
> agree that it's the right way forward.
>
> What seems to be happening is that the homogeneity of the list is
> determined somehow (whether tracked with a hint or scanned just-in-time)
> and then a specific comparison function for a known subset of built-in
> types is selected if appropriate.
>
> I had assumed that there would be an "apples-to-apples" comparison
> function in the type structure and that the patch was simply tracking
> the list's homogeneity in order to enter a (generic) alternative loop to
> call that function over PyObject_RichCompare().
>
> Why is that not the case? When a new C-level type is introduced (either
> a built-in or an extension module), why does the list object's code need
> to know about it in order to perform this optimisation?
>
> Why is there not a "tp_apple2apple" slot in the type structure which
> higher level functions (including the RichCompare() stuff - the first
> thing that function does is check the type of the objects anyway) can
> call if it determines that the two objects have the same type?
>
> Such a slot would also speed up "contains", "count", etc (for all
> classes) with no extra work, and no overhead of tracking or scanning the
> sequence's homogeneity.
>
> E.
>
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Submitted a PR!

[Erik]

Hi.

I may be way off-base here, but having scanned the patch I'm not sure I 
agree that it's the right way forward.


What seems to be happening is that the homogeneity of the list is 
determined somehow (whether tracked with a hint or scanned just-in-time) 
and then a specific comparison function for a known subset of built-in 
types is selected if appropriate.


I had assumed that there would be an "apples-to-apples" comparison 
function in the type structure and that the patch was simply tracking 
the list's homogeneity in order to enter a (generic) alternative loop to 
call that function over PyObject_RichCompare().


Why is that not the case? When a new C-level type is introduced (either 
a built-in or an extension module), why does the list object's code need 
to know about it in order to perform this optimisation?


Why is there not a "tp_apple2apple" slot in the type structure which 
higher level functions (including the RichCompare() stuff - the first 
thing that function does is check the type of the objects anyway) can 
call if it determines that the two objects have the same type?


Such a slot would also speed up "contains", "count", etc (for all 
classes) with no extra work, and no overhead of tracking or scanning the 
sequence's homogeneity.


E.

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-ideas] Submitted a PR!

[Elliot Gorokhovsky]

Just submitted a PR implementing this:
https://github.com/python/cpython/pull/582
-- just need someone to review it now :)

Thanks for all your feedback, everyone!

On Sun, Mar 5, 2017 at 12:19 AM Elliot Gorokhovsky <
elliot.gorokhov...@gmail.com> wrote:

> (Summary of results: my patch at https://bugs.python.org/issue28685 makes
> list.sort() 30-50% faster in common cases, and at most 1.5% slower in the
> uncommon worst case.)
>
> Hello all,
>
> You may remember seeing some messages on here about optimizing list.sort()
> by exploiting type-homogeneity: since comparing apples and oranges is
> uncommon (though possible, i.e. float to int), it pays off to check if the
> list is type-homogeneous (as well as homogeneous with respect to some other
> properties), and, if it is, to replace calls to PyObject_RichCompareBool
> with calls to ob_type->tp_richcompare (or, in common special cases, to
> optimized compare functions). The entire patch is less than 250 lines of
> code, most of which is pretty boilerplate (i.e. a lot of assertions in
> #ifdef Py_DEBUG blocks, etc).
>
> I originally wrote that patch back in November. I've learned a lot since
> then, both about CPython and about mailing list etiquette :). Previous
> discussion about this can be found at
> https://mail.python.org/pipermail/python-dev/2016-October/146648.html and
> https://mail.python.org/pipermail/python-ideas/2016-October/042807.html.
>
> Anyway, I recently redid the benchmarks much more rigorously (in
> preparation for presenting this project at my school's science fair),
> achieving a standard deviation of less than 0.5% of the mean for all
> measurements. The exact benchmark script used can be found at
> https://github.com/embg/python-fastsort-benchmark (it's just sorting
> random lists of/lists of tuples of [type]. While listsort.txt talks about
> benchmarking different kinds of structured lists, instead of just random
> lists, the results here would hold in those cases just as well, because
> this makes individual comparisons cheaper, instead of reducing the number
> of comparisons based on structure).
>
> I also made a poster describing the optimization and including a pretty
> graph displaying the benchmark data:
> https://github.com/embg/python-fastsort-benchmark/blob/master/poster.pdf.
> For those who would rather read the results here (though it is a *really*
> pretty graph):
>
> ***
> Percent improvement for sorting random lists of [type]
> (1-patched/unpatched):
> float: 48%
> bounded int (magnitude smaller than 2^32): 48.4%
> latin string (all characters in [0,255]): 32.7%
> general int (reasonably uncommon?): 17.2%
> general string (reasonably uncommon?): 9.2%
> tuples of float: 63.2%
> tuples of bounded int: 64.8%
> tuples of latin string: 55.8%
> tuples of general int: 50.3%
> tuples of general string: 44.1%
> tuples of heterogeneous: 41.5%
> heterogeneous (lots of float with an int at the end; worst-case): -1.5%
> ***
>
> Essentially, it's a gamble where the payoff is 20-30 times greater than
> the cost, and the odds of losing are very small. Sorting is perhaps not a
> bottleneck in most applications, but considering how much work has gone
> into Python's sort (Timsort, etc; half of listobject.c is sort code), I
> think it's interesting that list.sort() can be made essentially twice
> faster by a 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. So it's
> really the same idea, except here it doesn't matter as much what type we're
> dealing with, which is important, because lists are commonly used with lots
> of different types, as opposed to dictionaries, which overwhelmingly
> commonly use string keys, especially internally. (Correct me if I'm wrong
> in any of the above).
>
> I got a lot of great feedback/input on this patch as I was writing it, but
> after submitting it, I didn't hear much from anybody. (The reason I took so
> long to post was because I wanted to wait until I had the chance to do the
> benchmarks *right*). What do you all think?
>
> Thanks,
> Elliot
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/