[issue28731] _PyDict_NewPresized() creates too small dict

[INADA Naoki]

INADA Naoki added the comment:

This patch includes fix for ESTIMATE_SIZE macro. (see below)
Same fix is included in patch for issue28147.

>>> def estimate_size(n):
...     return n * 3 // 2  # Current ESTIMATE_SIZE
...
>>> def usable(n):
...     return n * 2 // 3
...
>>> def keysize(minsize):
...     size = 8
...     while size < minsize:  # Current implementation uses <=
...         size *= 2
...     return size
...
>>> def check():
...     for i in range(1000):
...         estimate = estimate_size(i)
...         size = keysize(estimate)
...         cap = usable(size)
...         if cap < i:
...             print(i, estimate, size, cap)
...
>>> check()
11 16 16 10
43 64 64 42
171 256 256 170
683 1024 1024 682
>>> # 
>>> estimate_size = lambda n: (n * 3 +1) // 2  # Fixed version
>>> check()
>>>

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue28731>
_______________________________________