4 ms·
What a fantastic post and explanation, big kudos to the author. I recently went from knowing next to nothing about hashtables, to implementing my own in C using
by bool3max 3y ago
What a fantastic post and explanation, big kudos to the author. I recently went from knowing next to nothing about hashtables, to implementing my own in C using simple separate chaining, and was surprised to find out that it's around twice as slow as an equivalent CPython `dict` benchmark, while also only being around 20% slower than an equivalent Golang `map` benchmark.
- ztraxc 3y agoFor inserting and looking up 10,000,000 integer values with string keys I get 6.4s for both Python and SBCL and 5.2 seconds for C++ (std::string, unordered_map). 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++" ...)
- bool3max 3y agoIn such an environment my implementation achieves a runtime of around 5.8s while Python3 manages 5.2s. 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.