[issue10408] Denser dicts and linear probing

[Antoine Pitrou]

Antoine Pitrou <pitrou at free.fr> added the comment:

> FWIW, one way to make a dict denser without increasing the number of
> probes is to use Brent's Variation of Algorithm D in Knuth.  That
> optimizes the insertion order to minimize the number of collisions and
> lets you pack well over two-thirds full without degradation.

He, you suggested that several years ago on python-dev and I supplied
the code. Also, IIRC, it didn't bring any improvement - although I don't
remember which benchmarks, if any, were run.

But the experiment here is mostly to decrease the (direct and indirect)
cost of collisions by improving temporal locality of lookups.

----------

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