4 ms·

Can someone explain why std::unordered_map has to be slow? I vaguely remember that it's because it isn't allowed to invalidate references when inserting elemen

by creata 3y ago

Can someone explain why std::unordered_map has to be slow? I vaguely remember that it's because it isn't allowed to invalidate references when inserting elements.

kccqzy 3y ago
That's exactly it. Also because of that, it has to be implemented with chaining rather than open addressing.
tialaramex 3y ago
Yes, it's obliged to be the design you'd have been taught in the 1980s or maybe 1990s in a typical data structures class, linked lists of entry nodes rather than a modern open addressed map. You can satisfy typical real world needs with better structures now, even when people want stable references to the nodes, but you can't implement the API that std::unordered_map promises with the faster choices. So there are "near drop-in" replacements, but you can't actually swap those into the C++ standard library. The chained design has terrible locality, which means doing lookups (failed or successful) in the hash table will cause more memory fetches, which are very slow, compared to a modern design which was optimised for this. Imagine we're looking at a Swiss Table, we're looking for 12530, we hash that, we get an index into our hash table, that causes our first memory fetch, to pull in the RAM where that part of the hash table lives. We check the key, this one is wrong, we step to the next, it's in the same blob of RAM but it's wrong, we step to the next, it's empty, we're done, one memory fetch, nothing found. Now std::unordered_map, we're looking for 12530, we hash it, we get an index into our hash table, we do a memory fetch. We get a pointer to a node. We do another memory fetch, we have a key to examine, it's wrong, we get a pointer to another node, we do another memory fetch, we have another key to examine, this one is wrong too, but there are no more pointers, three memory fetches and nothing found.
- Const-me 3y ago
  I wonder why won’t they fix the performance by changing the API specification of these collections? I don’t think they care about backward compatibility. For example, in C++/20 they decided UTF-8 string literals (available for nearly a decade since C++/11) now returns them in a brand new `char8_t` type, which won’t automatically cast to the old `char` type. I once had to waste couple days of work fixing the issues caused by C++ language upgrade.

by creata 3y ago

Can someone explain why std::unordered_map has to be slow? I vaguely remember that it's because it isn't allowed to invalidate references when inserting elements.

kccqzy 3y ago

That's exactly it. Also because of that, it has to be implemented with chaining rather than open addressing.

tialaramex 3y ago

Yes, it's obliged to be the design you'd have been taught in the 1980s or maybe 1990s in a typical data structures class, linked lists of entry nodes rather than a modern open addressed map. You can satisfy typical real world needs with better structures now, even when people want stable references to the nodes, but you can't implement the API that std::unordered_map promises with the faster choices. So there are "near drop-in" replacements, but you can't actually swap those into the C++ standard library. The chained design has terrible locality, which means doing lookups (failed or successful) in the hash table will cause more memory fetches, which are very slow, compared to a modern design which was optimised for this. Imagine we're looking at a Swiss Table, we're looking for 12530, we hash that, we get an index into our hash table, that causes our first memory fetch, to pull in the RAM where that part of the hash table lives. We check the key, this one is wrong, we step to the next, it's in the same blob of RAM but it's wrong, we step to the next, it's empty, we're done, one memory fetch, nothing found. Now std::unordered_map, we're looking for 12530, we hash it, we get an index into our hash table, we do a memory fetch. We get a pointer to a node. We do another memory fetch, we have a key to examine, it's wrong, we get a pointer to another node, we do another memory fetch, we have another key to examine, this one is wrong too, but there are no more pointers, three memory fetches and nothing found.

Const-me 3y ago
I wonder why won’t they fix the performance by changing the API specification of these collections? I don’t think they care about backward compatibility. For example, in C++/20 they decided UTF-8 string literals (available for nearly a decade since C++/11) now returns them in a brand new `char8_t` type, which won’t automatically cast to the old `char` type. I once had to waste couple days of work fixing the issues caused by C++ language upgrade.