Repository navigation
calculate_log2_keysize in dictobject.c incorrect #133703
Description
Activity
Uh, it is my bug.
- minsize = (minsize | PyDict_MINSIZE) - 1; + minsize = (minsize - 1) | (PyDict_MINSIZE - 1);Thanks @methane for catching this:
- minsize = (minsize | PyDict_MINSIZE) - 1; + minsize = (minsize - 1) | (PyDict_MINSIZE - 1);
With that change, you can also simplify the return statement:
- return _Py_bit_length(minsize | (PyDict_MINSIZE-1)); + return _Py_bit_length(minsize);
Suggestion: for clarity you might instead write
minsize = PY_MAX(minsize, PyDict_MINSIZE) - 1; return _Py_bit_length(minsize);
This makes the lower bound explicit, reads more directly at a glance, and the performance difference (if any) should be negligible. The
PY_MAXvariant even “works” forminsize <= 0, although zero or negative sizes aren’t expected in practice.- added a commit that references this issue
on May 10, 2025 Sorry, I was wrong.
(minsize - 1) | (PyDict_MINSIZE - 1)is not correct when minsize=0.Py_MAX() uses conditional move on both of arm64 and amd64.
- added a commit that references this issue
on May 10, 2025 Well, you were correct to say I was wrong to assume the performance difference is necessarily negligible in this context. I’m going to look more closely into assembly-level costs. But yeah,
Py_MAX()is needed for whenminsize == 0.
Bug report
Bug description:
Originally reported by @ThomasBr0 in #132762
The
_Py_bit_length()and_BitScanReverse64()code paths are incorrect and don't always return the smallest log2 key size to fit the desired number of items. The bug is benign in the sense that the dictionaries are sometimes too big, but they're never too small.For example
calculate_log2_keysize(7) = 4butcalculate_log2_keysize(8) = 3.cpython/Objects/dictobject.c
Lines 545 to 566 in 9546eee
cc @methane @markshannon
CPython versions tested on:
CPython main branch
Operating systems tested on:
No response
Linked PRs