Repository navigation
Reduce the number of comparisons for range checking. #67741
Description
| BPO | 23553 |
|---|---|
| Nosy | @rhettinger, @pitrou, @serhiy-storchaka |
| 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 = None
created_at = <Date 2015-03-01.00:50:38.601>
labels = ['interpreter-core', 'performance']
title = 'Reduce the number of comparisons for range checking.'
updated_at = <Date 2015-03-02.04:13:50.021>
user = 'https://github.com/rhettinger'bugs.python.org fields:
activity = <Date 2015-03-02.04:13:50.021>
actor = 'rhettinger'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2015-03-01.00:50:38.601>
creator = 'rhettinger'
dependencies = []
files = ['38281', '38282', '38283', '38293']
hgrepos = []
issue_num = 23553
keywords = ['patch']
message_count = 13.0
messages = ['236928', '236931', '236933', '236934', '236935', '236938', '236939', '236940', '236942', '236945', '236946', '236948', '237011']
nosy_count = 5.0
nosy_names = ['rhettinger', 'pitrou', 'Arfrever', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue23553'
versions = ['Python 3.5']
Activity
rhettinger commentedon Mar 1, 2015
Python's core is full of bound checks like this one in Objects/listobject.c:
Abner Fog's high-level language optimization guide, http://www.agner.org/optimize/optimizing_cpp.pdf in section 14.2 Bounds Checking, shows a way to fold this into a single check:
The old generated assembly code looks like this:
_list_item:
subq $8, %rsp
testq %rsi, %rsi
js L227
cmpq 16(%rdi), %rsi
jl L228
L227:
... <error reporting and exit > ...
L228:
movq 24(%rdi), %rax
movq (%rax,%rsi,8), %rax
addq $1, (%rax)
addq $8, %rsp
ret
The new disassembly looks like this:
_list_item:
cmpl %esi, 16(%rdi)
ja L227
... <error reporting and exit > ...
L227:
movq 24(%rdi), %rax
movq (%rax,%rsi,8), %rax
addq $1, (%rax)
ret
Note, the new code not only saves a comparison/conditional-jump pair, it also avoids the need to adjust %rsp on the way in and the way out for a net savings of four instructions along the critical path.
When we have good branch prediction, the current approach is very low cost; however, Abner Fog's recommendation is never more expensive, is sometimes cheaper, saves a possible misprediction, and reduces the total code generated. All in all, it is a net win.
I recommend we put in a macro of some sort so that this optimization gets expressed exactly once in the code and so that it has a good clear name with an explanation of what it does.
serhiy-storchaka commentedon Mar 1, 2015
Yes, this is a technique commonly used in STL implementations. This is why sizes and indices in STL are unsigned.
But in CPython implementation sizes are signed (Py_ssize_t). The problem with using this optimization (rather low-level than high-level) is that we need to know unsigned version of the type of compared values.
Here is a bug. The type of i and Py_SIZE(a) is Py_ssize_t, so when casted to unsigned int, highest bits are lost. The correct casting type is size_t.
In changeset 5942fd9ab335 you introduced a bug.
rhettinger commentedon Mar 1, 2015
Yes, I had just seen that a early today and deciding whether to substitute size_t for the unsigned cast or whether to just revert. I believe size_t is guaranteed to hold any array index and that a cast from non-negative Py_ssize_t would not lose bits.
Wouldn't size_t always work for Py_ssize_t?
serhiy-storchaka commentedon Mar 1, 2015
Yes. But it wouldn't work for say off_t.
The consistent way is always use size_t instead of Py_ssize_t. But this boat has sailed.
rhettinger commentedon Mar 1, 2015
I'm only proposing a bounds checking macro for the Py_ssize_t case which is what all of our IndexError tests look for.
Also, please look at the attached deque fix.
serhiy-storchaka commentedon Mar 1, 2015
It looks correct to me, but I would change type and introduce few new variables to get rid of casts.
rhettinger commentedon Mar 1, 2015
Attaching a diff for the bounds checking Objects/listobject.c.
It looks like elsewhere in that file, (size_t) casts are done
for various reasons.
rhettinger commentedon Mar 1, 2015
Also attaching a bounds checking patch for deques.
serhiy-storchaka commentedon Mar 1, 2015
Parenthesis around Py_SIZE() are redundant.
Are there any benchmarking results that show a speed up? Such microoptimization makes sense in tight loops, but optimized source code looks more cumbersome and errorprone.
rhettinger commentedon Mar 1, 2015
I think the source in listobject.c would be benefit from a well-named macro for this. That would provide the most clarity. For deques, I'll just put in the simple patch because it only applies to a place that is already doing unsigned arithmetic/comparisons.
FWIW, I don't usually use benchmarking on these kinds of changes. The generated assembler is sufficiently informative. Benchmarking each tiny change risks getting trapped in a local minimum. Also, little timeit tests tend to branch the same way every time (which won't show the cost of prediction misses) and it tends to have all code and data in cache (so you don't see the effects of cache misses) and it risks tuning to a single processor (in my case a haswell). Instead, I look at the code generated by GCC and CLang to see that it does less work.
python-dev commentedon Mar 1, 2015
New changeset 1e89094998b2 by Raymond Hettinger in branch 'default':
Issue bpo-23553: Use an unsigned cast to tighten-up the bounds checking logic.
https://hg.python.org/cpython/rev/1e89094998b2
serhiy-storchaka commentedon Mar 1, 2015
My point is that if the benefit is too small (say < 5% in microbenchmarks), it
is not worth code churning. Actually my bar for microbenchmarks is higher,
about 20%.
rhettinger commentedon Mar 2, 2015
FWIW, here is a small patch to show how this could can be done consistently and with code clarity.
[-]Reduce the number of comparison for range checking.[/-][+]Reduce the number of comparisons for range checking.[/+]iritkatriel commentedon Sep 9, 2022
Is there anything left to do on this issue? It seems that at least some of it was already done in c208308 and f1aa8ae.