Repository navigation
Performance optimization for min() and max() over lists #48424
Description
| BPO | 4174 |
|---|---|
| Nosy | @akuchling, @rhettinger, @jcea, @mdickinson, @pitrou, @kristjanvalur, @devdanzin, @hniksic |
| Files |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = None
closed_at = <Date 2010-02-22.17:25:53.259>
created_at = <Date 2008-10-22.15:18:08.271>
labels = ['interpreter-core', 'performance']
title = 'Performance optimization for min() and max() over lists'
updated_at = <Date 2010-02-22.17:30:55.775>
user = 'https://github.com/kristjanvalur'bugs.python.org fields:
activity = <Date 2010-02-22.17:30:55.775>
actor = 'mark.dickinson'
assignee = 'none'
closed = True
closed_date = <Date 2010-02-22.17:25:53.259>
closer = 'mark.dickinson'
components = ['Interpreter Core']
creation = <Date 2008-10-22.15:18:08.271>
creator = 'kristjan.jonsson'
dependencies = []
files = ['11857']
hgrepos = []
issue_num = 4174
keywords = ['patch', 'needs review']
message_count = 12.0
messages = ['75082', '75099', '75100', '75101', '75102', '75139', '87849', '88021', '88107', '99789', '99792', '99793']
nosy_count = 8.0
nosy_names = ['akuchling', 'rhettinger', 'jcea', 'mark.dickinson', 'pitrou', 'kristjan.jonsson', 'ajaksu2', 'hniksic']
pr_nums = []
priority = 'low'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue4174'
versions = ['Python 2.7', 'Python 3.2']
Activity
kristjanvalur commentedon Oct 22, 2008
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)
pitrou commentedon Oct 22, 2008
I haven't tried the patch as is but I can spot two problems:
list subclass could override getitem
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.
rhettinger commentedon Oct 22, 2008
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:
rhettinger commentedon Oct 22, 2008
Antoine, the list can mutate even when the keyfunc is NULL. The rich
comparison can callback to arbitrary Python code.
pitrou commentedon Oct 22, 2008
Ouch, you are right.
hniksic commentedon Oct 23, 2008
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.
devdanzin commentedon May 16, 2009
Given the drawbacks mentioned (and the fact that the current patch would
break when the list mutates under its feet), is this still valid?
kristjanvalur commentedon May 18, 2009
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?
pitrou commentedon May 20, 2009
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.
akuchling commentedon Feb 22, 2010
Should this patch just be rejected, then? Or is the more general locking suggested in msg88021 of interest?
pitrou commentedon Feb 22, 2010
I think the patch should just be rejected. Workloads where min() / max() performance is a bottleneck have to be very rare.
mdickinson commentedon Feb 22, 2010
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.