Issue 4174: Performance optimization for min() and max() over lists

This adds a special case for min() and max() when iterating over lists.
For simple lists of floats, the improvement is some 15% on a windows 
machine using release build (non pgo)

I haven't tried the patch as is but I can spot two problems:
- you should use PyList_CheckExact instead of PyList_Check, because a
list subclass could override __getitem__
- when keyfunc is not NULL, you can't assume that the list size will
stay constant; indeed, calling keyfunc may mutate the list (try
something like `max(l, key=l.pop)`)

I've got no opinion on whether the speedup is worth the added
complexity. Perhaps a way of simplifying the patch would be to enable
the special path only when keyfunc==NULL. Others may comment.

Not that excited about adding this much code for such a small speedup.

Also, the list can change size during iteration so the for-loop needs to
be changed to:

     for(i = 1; i<PyList_GET_SIZE(v); i++)

Antoine, the list can mutate even when the keyfunc is NULL.  The rich
comparison can callback to arbitrary Python code.

> Antoine, the list can mutate even when the keyfunc is NULL.  The rich
> comparison can callback to arbitrary Python code.

Ouch, you are right.

Note that the item retrieved by PyList_GET_ITEM must be increffed before
being passed to the function.  Otherwise mutating the list can remove
the item from the list and destroy the underlying object, in which case
the current maxitem can refer to a freed object.  This pitfall is
described in http://docs.python.org/extending/extending.html#thin-ice in
some detail.

Given the drawbacks mentioned (and the fact that the current patch would
break when the list mutates under its feet), is this still valid?

Perhaps not.
I had however written a general list locking system, generalizing the 
way sort() locks a list for direct manipulation, and rewritten min and 
max to be able to use that.  Perhaps that approach would be of interest?

I am with Raymond here: I don't think the performance improvement would
be worth a significant complification of the code - unless the
improvement is /very/ large.

Should this patch just be rejected, then?  Or is the more general locking suggested in msg88021 of interest?

I think the patch should just be rejected. Workloads where min() / max() performance is a bottleneck have to be very rare.

I agree that the performance improvement isn't worth the extra code, or the risk of introducing bugs (the comments so far show that it's not trivial to get this right).

Closing as rejected.

nosy: + mark.dickinson
messages: + msg99793

keywords: patch, patch, needs review
resolution: rejected

messages: + msg99792

messages: + msg88107

messages: + msg88021

keywords: patch, patch, needs review
stage: test needed