[issue10408] Denser dicts and linear probing

[Raymond Hettinger]

Raymond Hettinger <rhettinger at users.sourceforge.net> added the comment:

My previous experiments along these lines showed it was a dead-end.  The number of probes was the most important factor and beat-out any effort to improve cache utilization from increased density.  

Doing extra work (more probes) in order to improve cache effects is very difficult because most real programs have an uneven access pattern so that the most frequently accesses items are usually already in cache.  So, the attempted improvement only helps the less frequently accessed items and isn't worth the extra number of probes.

Another result from earlier experiments is that benchmarking the experiment is laden with pitfalls.  Tight timing loops don't mirror real world programs, nor do access patterns with uniform random distributions.

----------

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