3 ms·
> I see a tendency to move from chaining hash tables to open addressing hash tables due to their better fit to modern CPU memory organizations. CPython recently
by masklinn 10y ago
> I see a tendency to move from chaining hash tables to open addressing hash tables due to their better fit to modern CPU memory organizations. CPython recently made such switch
CPython recently switched to the naturally ordered maps suggested by Raymond Hettinger in 2012[0] (Pypy had already implemented it in early 2015[1]) but AFAIK it has never used chaining. In the latest revision of dictobject.c you can find a note/comment[2] saying:
> The basic lookup function used by all operations. This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. Open addressing is preferred over chaining since the link overhead for chaining would be substantial (100% with typical malloc overhead).
This is attributed to guido@1256[3], and if you follow the link you end up back in March 1993 in the commit "Generalized version of dictionaries, with compatibility hacks." when the file was created...
[0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1...
[1] https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff...
[2] https://hg.python.org/cpython/annotate/default/Objects/dictobject.c#l663 https://hg.python.org/cpython/annotate/default/Objects/dicto...
[3] https://hg.python.org/cpython/annotate/7aa9613ffd36/Objects/dictobject.c#l103 https://hg.python.org/cpython/annotate/7aa9613ffd36/Objects/...
- tomnipotent 10y agoRaymond Hettinger gave a presentation a few weeks ago on the evolution of the Python dict implementation - one of the most insightful videos I've seen in a long time. https://www.youtube.com/watch?v=p33CVV29OG8 https://www.youtube.com/watch?v=p33CVV29OG8