`calculate_log2_keysize` in `dictobject.c` incorrect

[colesbury]

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) = 4 but calculate_log2_keysize(8) = 3.

cpython/Objects/dictobject.c

Lines 545 to 566 in 9546eee

	/* Find the smallest dk_size >= minsize. */
	static inline uint8_t
	calculate_log2_keysize(Py_ssize_t minsize)
	{
	#if SIZEOF_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 long msb;
	_BitScanReverse64(&msb, (uint64_t)minsize);
	return (uint8_t)(msb + 1);
	#else
	uint8_t log2_size;
	for (log2_size = PyDict_LOG_MINSIZE;
	(((Py_ssize_t)1) << log2_size) < minsize;
	log2_size++)
	;
	return log2_size;
	#endif
	}

cc @methane @markshannon

CPython versions tested on:

CPython main branch

Operating systems tested on:

No response

Linked PRs

• gh-133703: dict: fix calculate_log2_keysize() #133809
• [3.14] gh-133703: dict: fix calculate_log2_keysize() (GH-133809) #133861
• [3.13] gh-133703: dict: fix calculate_log2_keysize() (GH-133809) #133862

[methane]

Uh, it is my bug.

-     minsize = (minsize | PyDict_MINSIZE) - 1; 
+     minsize = (minsize - 1) | (PyDict_MINSIZE - 1);

[angela-tarantula]

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_MAX variant even “works” for minsize <= 0, although zero or negative sizes aren’t expected in practice.

[methane]

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.

[angela-tarantula]

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 when minsize == 0.