Python Dict – An Explorable Explanation
just-taking-a-ride.com
just-taking-a-ride.com
A few days ago, I wanted a concrete example about dynamic arrays. The examples in computer science textbook always uses a factor of 2 when expanding, since it is very convenient to demonstrate that it gives an amortized O(1) insertion time. Some people find it wasteful, and may resort to use a constant expansion (e.g. 128) instead, leading to a O(n / 128), i.e. O(n) insertion time instead.
But you can just make the expansion factor less than 2. I wanted a concrete example, so, naturally, I just went for CPython's implementation of `list`. It took me less than 2 minutes to find it: https://github.com/python/cpython/blob/main/Objects/listobje....
If you're curious, CPython essentially grows its dynamic array by ⅛ (12.5%) whenever it needs to.
It's literally current size + (current size/8) + fiddle
( the fiddle is there to prevent a fail to increase for small input (exercise for reader?) )
followed by a mask to ensure a multiple of 8.
The rational would be no floating point ops and all the weirdness that can entail plus the speed of raw shift | addition | mask.
You're correct that it deserves a twice over as the fiddle raises an eyebrow that invites investigation across inputs.
Python's dict implementation (in C) is good and the interpreter loop overhead is dwarfed by the dict overhead.
SBCL's implementation is in Lisp and achieves the same speed.
(For the general case of Python speed this benchmark is of course useless, since raw dicts written in C cannot be optimized much. Nevertheless it is sometimes quoted as "evidence" that "Python is almost as fast as C++" ...)
41% of the runtime of my impl. is spent on resizing (19 times) + finally freeing (once) the hashtable.
It's interesting that in your testing unordered_map managed a faster runtime than Python. I've attributed my implementation's defeat to the fact that it uses separate chaining while CPython uses open addressing (+ a bunch of other clever optimizations...), but seeing as unordered_map also uses separate chaining (as mandated by the C++ standard, apparently) and it managed a win in your testing, I'm interested to see how they do things.