Optimize builtin functions min() and max()

[colorfulappl]

BPO	46192
Nosy	@sweeneyde, @erlend-aasland, @colorfulappl
PRs	gh-90350: Optimize builtin functions min() and max() #30286
Files	bench-minmax.py

^{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 = None
created_at = <Date 2021-12-29.10:04:55.181>
labels = ['interpreter-core', '3.11', 'performance']
title = 'Optimize builtin functions min() and max()'
updated_at = <Date 2021-12-31.14:22:47.367>
user = 'https://github.com/colorfulappl'

bugs.python.org fields:

activity = <Date 2021-12-31.14:22:47.367>
actor = 'Dennis Sweeney'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2021-12-29.10:04:55.181>
creator = 'colorfulappl'
dependencies = []
files = ['50528']
hgrepos = []
issue_num = 46192
keywords = ['patch']
message_count = 3.0
messages = ['409299', '409367', '409421']
nosy_count = 3.0
nosy_names = ['Dennis Sweeney', 'erlendaasland', 'colorfulappl']
pr_nums = ['30286']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue46192'
versions = ['Python 3.11']

[colorfulappl]

faster-cpython/ideas#199

[erlend-aasland]

Repeating my comment on #74472: If we are touching min() and max(), it would make sense, IMO, to port them to Argument Clinic. FTR, Argument Clinic got *args support in #62809 / bpo-20291.

@colorfulappl made a "competing" branch using AC on his local fork¹. However, that branch contained a bug with the key function; I made an amended version² for benchmarking. Here's some micro-benchmarks from optimised builds on macOS 12.1 w/Clang 13:

+---------------------------------------------------------+---------+-----------------------+----------------------+
| Benchmark | main | python/cpython#74472 | python/cpython#74472-ac |
+=========================================================+=========+=======================+======================+
| max(a, b) | 193 ns | 74.1 ns: 2.60x faster | 179 ns: 1.08x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| max(a, b, c, d, e) | 273 ns | 126 ns: 2.17x faster | 260 ns: 1.05x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| max([a, b]) | 267 ns | 185 ns: 1.44x faster | 239 ns: 1.12x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| max([a, b, c, d, e]) | 345 ns | 259 ns: 1.33x faster | 312 ns: 1.10x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| max((a,), (b,), key=lambda x: x[0]) | 707 ns | 444 ns: 1.59x faster | 513 ns: 1.38x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| max((a,), (b,), (c,), (d,), (e,), key=lambda x: x[0]) | 1.12 us | 831 ns: 1.35x faster | 930 ns: 1.20x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| max([(a,), (b,)], key=lambda x: x[0]) | 786 ns | 561 ns: 1.40x faster | 570 ns: 1.38x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| max([(a,), (b,), (c,), (d,), (e,)], key=lambda x: x[0]) | 1.19 us | 981 ns: 1.22x faster | 981 ns: 1.22x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| max([], default=-1) | 484 ns | 177 ns: 2.73x faster | 188 ns: 2.57x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+
| Geometric mean | (ref) | 1.68x faster | 1.29x faster |
+---------------------------------------------------------+---------+-----------------------+----------------------+

Footnotes

1. https://github.com/colorfulappl/cpython/commit/29b9559de31ae19e8d127d7a3063494b2d9791b0 ↩

2. https://github.com/erlend-aasland/cpython/tree/gh-30286-ac ↩

[sweeneyde]

Kind of like what's mentioned at faster-cpython/ideas#131 , it may be interesting to explore implementing min()/max() in Pure python, considering recent specializations to COMPARE_OP, and potential future specializations of FOR_ITER.

[arhadthedev]

@erlend-aasland Would you mind to publish https://github.com/erlend-aasland/cpython/tree/gh-30286-ac you mentioned as a PR, please? It will be a great opportunity to close gh-30286 and resolve this issue for good.