Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork33.7k
Closed
Description
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 examplecalculate_log2_keysize(7) = 4 butcalculate_log2_keysize(8) = 3.
Lines 545 to 566 in9546eee
| /* Find the smallest dk_size >= minsize. */ | |
| staticinlineuint8_t | |
| calculate_log2_keysize(Py_ssize_tminsize) | |
| { | |
| #ifSIZEOF_LONG==SIZEOF_SIZE_T | |
| minsize= (minsize |PyDict_MINSIZE)-1; | |
| return_Py_bit_length(minsize | (PyDict_MINSIZE-1)); | |
| #elif defined(_MSC_VER) | |
| // On 64bit Windows, sizeof(long) == 4. | |
| minsize= (minsize |PyDict_MINSIZE)-1; | |
| unsigned longmsb; | |
| _BitScanReverse64(&msb, (uint64_t)minsize); | |
| return (uint8_t)(msb+1); | |
| #else | |
| uint8_tlog2_size; | |
| for (log2_size=PyDict_LOG_MINSIZE; | |
| (((Py_ssize_t)1) <<log2_size)<minsize; | |
| log2_size++) | |
| ; | |
| returnlog2_size; | |
| #endif | |
| } |
CPython versions tested on:
CPython main branch
Operating systems tested on:
No response