[issue28731] _PyDict_NewPresized() creates too small dict

[INADA Naoki]

INADA Naoki added the comment:

> This optimization affects only 6-element (and perhaps to less extend 11-element) dicts. But in any case this is good enhancement.

This affects when minused = (n*2/3)+1 .. n-1 (n=8, 16, ...)

n=8: 6, 7
n=16: 11, 12, ..15

> Naoki, could you please make microbenchmarks for 5- and 7-element dicts with your next patch?

+ /home/inada-n/local/py36/bin/patched -m perf timeit --compare-to /home/inada-n/local/py36/bin/master -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5}'
master: ..................... 568 ns +- 18 ns
patched: ..................... 567 ns +- 23 ns

Median +- std dev: [master] 568 ns +- 18 ns -> [patched] 567 ns +- 23 ns: 1.00x faster
Not significant!
+ /home/inada-n/local/py36/bin/patched -m perf timeit --compare-to /home/inada-n/local/py36/bin/master -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6}'
master: ..................... 1.01 us +- 0.04 us
patched: ..................... 756 ns +- 20 ns

Median +- std dev: [master] 1.01 us +- 0.04 us -> [patched] 756 ns +- 20 ns: 1.33x faster
+ /home/inada-n/local/py36/bin/patched -m perf timeit --compare-to /home/inada-n/local/py36/bin/master -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6, "g":7}'
master: ..................... 1.12 us +- 0.03 us
patched: ..................... 867 ns +- 31 ns

Median +- std dev: [master] 1.12 us +- 0.03 us -> [patched] 867 ns +- 31 ns: 1.29x faster
+ /home/inada-n/local/py36/bin/patched -m perf timeit --compare-to /home/inada-n/local/py36/bin/master -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6, "g":7, "h":8}'
master: ..................... 1.04 us +- 0.03 us
patched: ..................... 1.03 us +- 0.04 us

Median +- std dev: [master] 1.04 us +- 0.03 us -> [patched] 1.03 us +- 0.04 us: 1.00x faster
Not significant!
+ /home/inada-n/local/py36/bin/patched -m perf timeit --compare-to /home/inada-n/local/py36/bin/master -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6, "g":7, "h":8, "i":9, "j":10}'
master: ..................... 1.16 us +- 0.04 us
patched: ..................... 1.16 us +- 0.04 us

Median +- std dev: [master] 1.16 us +- 0.04 us -> [patched] 1.16 us +- 0.04 us: 1.00x faster
Not significant!
+ /home/inada-n/local/py36/bin/patched -m perf timeit --compare-to /home/inada-n/local/py36/bin/master -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6, "g":7, "h":8, "i":9, "j":10, "k":11}'
master: ..................... 1.67 us +- 0.06 us
patched: ..................... 1.39 us +- 0.04 us

Median +- std dev: [master] 1.67 us +- 0.06 us -> [patched] 1.39 us +- 0.04 us: 1.20x faster

----------

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