3 ms·
> In my opinion, a hash map that needs to chase an extra pointer to do a lookup and uses insertion order to provide deterministic iteration order seems like a h
by masklinn 5y ago
> In my opinion, a hash map that needs to chase an extra pointer to do a lookup and uses insertion order to provide deterministic iteration order seems like a hash map that hates me.
In most cases it's the other way around: Python switched to compact hash map for performance reasons, the natural ordering was a side-effect of it:
* The compact hashmap scheme has much better memory behaviour (as befits its name) because the the storage buffer is contiguous instead of being sparse so less space is wasted on empty cells, this is especially important in a language like Python where everything is a reference and each entry is 24 bytes
* It can also be further optimised by making the indices in the array adaptive (Pypy does that though I don't think CPython does): if you have less than 255 entries (which is rather common especially in languages where most everything is a dict — again python) you can use an array of u8s instead of usize.
* Finally the primary purpose of the compact hashmap for Python was iteration speed: in a normal hashmap unless you have a very high load factor the map is full of holes iteration needs to skip over, and furthermore the hole locations are basically random so the branch is completely impredictable, even with tombstoning the compact dict has a much better predictability.
- pclmulqdq 5y agoI suppose that most people don't ever erase anything from a Python dictionary? Erasing items would lower the effective load factor of the array (or be O(n) so you can do a big memcpy). It's interesting that this highlights how Python users use dictionaries very differently from how I use hash tables (as a C and C++ programmer). In the last few years, people have been designing hash tables to run at much higher load factors, but if the decision was made before ~2018, I can see why the iteration speed argument would result in a structure like this.
- masklinn 5y ago> I suppose that most people don't ever erase anything from a Python dictionary? It's the tombstoning mentioned in both my comment and the essay (tombstoning is basically the amortisation of deletion), however you need a lot of deletion to fuck up your branching as much as a middling-load-factor hashmap does. > Erasing items would lower the effective load factor of the array (or be O(n) so you can do a big memcpy). It will, however: * maps which get items deleted from are a minority, more so for those which both get items deleted from and get iterated * once enough items have been deleted, the buffer can be shrunk in order to remove the tombstones (converting it back to a very dense array).