calculate_log2_keysize in dictobject.c incorrect

@ThomasBr0

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

Uh, it is my bug.

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

@methane

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.

pythongh-133703: dict: fix calculate_log2_keysize()

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.

pythongh-133703: dict: fix calculate_log2_keysize()

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.

gh-133703: dict: fix calculate_log2_keysize() (GH-133809)

pythongh-133703: dict: fix calculate_log2_keysize() (pythonGH-133809)

gh-133703: dict: fix calculate_log2_keysize() (GH-133809)

pythongh-133703: dict: fix calculate_log2_keysize() (pythonGH-133809)

Navigation Menu

Repository navigation

`calculate_log2_keysize` in `dictobject.c` incorrect #133703

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	/* 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
	}

calculate_log2_keysize in dictobject.c incorrect #133703

Description

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Activity

methane commented on May 9, 2025

angela-tarantula commented on May 9, 2025

methane commented on May 10, 2025

angela-tarantula commented on May 10, 2025

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

`calculate_log2_keysize` in `dictobject.c` incorrect #133703