3 ms·

std::unordered_map is notoriously slow, several times slower than a fast hashmap implementation like Google's absl or Martin's robin-hood-hashing [1]. In additi

std::unordered_map is notoriously slow, several times slower than a fast hashmap implementation like Google's absl or Martin's robin-hood-hashing [1]. In addition, your implementation lets the hashmap grow from a small size. As you know the total length, you could preallocate the hash table and avoid rehashing. As typical hash table implementations double the capacity during rehashing, preallocating the buckets should be about twice as fast if we don't consider the cache and the complex mechanism behind the STL allocator. That said, std::sort is not the fastest sort implementation, either. It is hard to say which is faster for a small N of 10000. Your general point is still right in that an O(n*log(n)) algorithm is not necessarily slower than an O(n) algorithm in practice. [1]: https://github.com/martinus/robin-hood-hashing https://github.com/martinus/robin-hood-hashing

Const-me 3y ago
Adding `map.reserve( vec.size() );` indeed helped, but still slower than sorting these entries. Specifically, the time for the hash map is 740 μs this way. I think the main reason for the observed behavior is memory management. The sorted vector takes under 80kb of RAM, allocated with a single malloc() call, and the entire vector fits in L2 cache which is very fast to access. OTOH, without advanced shenanigans like custom allocators, the hash map needs 1 malloc() call per entry. On a general note, I noticed that when the data being handled fits in the faster in-core caches, dense buffers pretty often perform best, despite these theoretical big O-s. Even if this means spending some extra time to sort the data.
- attractivechaos 3y ago
  > the [std::unordered_map] hash map needs 1 malloc() call per entry. This is a key reason why std::unordered_map is several times slower than fast hashmap implementations that only use a couple of long flat arrays per hashmap object. Nonetheless, common STL implementations use their own allocators by default and would not call malloc() on small objects frequently.
- charlieyu1 3y ago
  Just learning c++, curious how reserve works. I thought map would allocate memory exponentially automatically, so an early reserve at best saves you a few reallocation
  - Const-me 3y ago
    That reserve() method only reserves memory for the hash table inside the container. It does help with performance to an extent, but the memory for the items stored in that map is still allocated one by one, as new entries are inserted into the map. I think the main reason why reserve() helped substantially weren’t saved malloc() calls, it were saved re-hashes. Each time the hash table grows, it needs to re-insert all items currently stored on the map into the new, larger table of these buckets.
  - tialaramex 3y ago
    Sort of. For std::unordered_map there are two types of memory allocation, there's a table, of pointers, and then there are nodes, which themselves have a pointer to a next node if any, forming a "chain". The table is indeed grown exponentially as you describe. If you tell std::unordered_map that you expect 10000 entries using reserve, it will calculate how big it would expect to grow a table for 10000 entries and make it that size immediately. The nodes however are created when you insert data. Even though you called reserve, it is an allocation each time you insert to make space for the new node. If you used a Swiss table (e.g. from Abseil) the reserve behaves more as a person might expect, it will allocate a data structure big enough to insert at least 10 000 entries successfully, and no further allocations are needed unless you keep going.
  - gumby 3y ago
    Don't forget those reallocations require copying as well. Also reallocation can increase memory fragmentation, not that it matters for this toy problem. Basically doing less computation is always a win when it's trivial to do so. This is not a c++ issue.
- nly 3y ago
  If you wanted to see the effect of memory allocations then you could use boosts intrusive unordered_set implementation https://www.boost.org/doc/libs/1_82_0/doc/html/boost/intrusive/unordered_set.html https://www.boost.org/doc/libs/1_82_0/doc/html/boost/intrusi... It doesn't own the underlying memory, so you can preallocate your nodes
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.
_a_a_a_ 3y ago
> Your general point is still right in that an O(n*log(n)) algorithm is not necessarily slower than an O(n) algorithm in practice. Sounds reasonable > for a small N of 10000 Ah, now that is not what I would call a small N
- tialaramex 3y ago
  10_000 is easily in the ballpark of constant factors k which really happen in software. Suppose my O(n) algorithm is a random access walk of nums. So I'm causing ~10_000 memory fetches, maybe they each take k=100 cycles, so it takes 1 million cycles total. But the O(n*log(n)) algorithm happens to be linear, it does access some nearby objects more than once, but every damn access is in cache. That's only 100_000 cycles, it's ten times faster despite you not thinking 10000 is a small N. Stalls are huge. A modern CPU can do a crazy amount of arithmetic in the time it takes to fetch from even an L3 shared cache, never mind main memory. If you need to go out, to the network or to "disk" it starts to look faster to do a whole bunch of difficult work again instead. Oh the 2417th digit of Pi is on the hard disk? Thanks but I'll just calculate it again instead 'cos I don't got all day.
  - _a_a_a_ 3y ago
    Thank you for the lesson in memory access times I actually know something about the subject already :-) > But the O(n*log(n)) algorithm I think you're badly missing out the "* log(n)" part. But on reflection, you have made your point, thank you.
    - tialaramex 3y ago
      > I think you're badly missing out the "* log(n)" part. Nope? But I can see why you might have missed it, instinctively log(10_000) feels like it should be pretty big. It feels big, doesn't it. Not as big as n, but surely a sizeable quantity. However the log to base 2 (which we might decide we prefer to care about here since this is computer science) is about 13. So yeah, the numbers work out fine. I guess it's possible my use of the word "linear" confused you. I'm talking linear in comparison to random access, not suggesting that somehow a log-linear complexity is the same as a linear complexity. But then, you know "something" about this so maybe not. EtA: Aha, I realised my mistake, I just used rough numbers, maybe you'd have realised if I'd written 132 870 cycles or something even though that's obviously not correct because it's excessive accuracy.

Const-me 3y ago

Adding `map.reserve( vec.size() );` indeed helped, but still slower than sorting these entries. Specifically, the time for the hash map is 740 μs this way. I think the main reason for the observed behavior is memory management. The sorted vector takes under 80kb of RAM, allocated with a single malloc() call, and the entire vector fits in L2 cache which is very fast to access. OTOH, without advanced shenanigans like custom allocators, the hash map needs 1 malloc() call per entry. On a general note, I noticed that when the data being handled fits in the faster in-core caches, dense buffers pretty often perform best, despite these theoretical big O-s. Even if this means spending some extra time to sort the data.

attractivechaos 3y ago
> the [std::unordered_map] hash map needs 1 malloc() call per entry. This is a key reason why std::unordered_map is several times slower than fast hashmap implementations that only use a couple of long flat arrays per hashmap object. Nonetheless, common STL implementations use their own allocators by default and would not call malloc() on small objects frequently.
charlieyu1 3y ago
Just learning c++, curious how reserve works. I thought map would allocate memory exponentially automatically, so an early reserve at best saves you a few reallocation
- Const-me 3y ago
  That reserve() method only reserves memory for the hash table inside the container. It does help with performance to an extent, but the memory for the items stored in that map is still allocated one by one, as new entries are inserted into the map. I think the main reason why reserve() helped substantially weren’t saved malloc() calls, it were saved re-hashes. Each time the hash table grows, it needs to re-insert all items currently stored on the map into the new, larger table of these buckets.
- tialaramex 3y ago
  Sort of. For std::unordered_map there are two types of memory allocation, there's a table, of pointers, and then there are nodes, which themselves have a pointer to a next node if any, forming a "chain". The table is indeed grown exponentially as you describe. If you tell std::unordered_map that you expect 10000 entries using reserve, it will calculate how big it would expect to grow a table for 10000 entries and make it that size immediately. The nodes however are created when you insert data. Even though you called reserve, it is an allocation each time you insert to make space for the new node. If you used a Swiss table (e.g. from Abseil) the reserve behaves more as a person might expect, it will allocate a data structure big enough to insert at least 10 000 entries successfully, and no further allocations are needed unless you keep going.
- gumby 3y ago
  Don't forget those reallocations require copying as well. Also reallocation can increase memory fragmentation, not that it matters for this toy problem. Basically doing less computation is always a win when it's trivial to do so. This is not a c++ issue.
nly 3y ago
If you wanted to see the effect of memory allocations then you could use boosts intrusive unordered_set implementation https://www.boost.org/doc/libs/1_82_0/doc/html/boost/intrusive/unordered_set.html https://www.boost.org/doc/libs/1_82_0/doc/html/boost/intrusi... It doesn't own the underlying memory, so you can preallocate your nodes

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.

_a_a_a_ 3y ago

> Your general point is still right in that an O(n*log(n)) algorithm is not necessarily slower than an O(n) algorithm in practice. Sounds reasonable > for a small N of 10000 Ah, now that is not what I would call a small N

tialaramex 3y ago
10_000 is easily in the ballpark of constant factors k which really happen in software. Suppose my O(n) algorithm is a random access walk of nums. So I'm causing ~10_000 memory fetches, maybe they each take k=100 cycles, so it takes 1 million cycles total. But the O(n*log(n)) algorithm happens to be linear, it does access some nearby objects more than once, but every damn access is in cache. That's only 100_000 cycles, it's ten times faster despite you not thinking 10000 is a small N. Stalls are huge. A modern CPU can do a crazy amount of arithmetic in the time it takes to fetch from even an L3 shared cache, never mind main memory. If you need to go out, to the network or to "disk" it starts to look faster to do a whole bunch of difficult work again instead. Oh the 2417th digit of Pi is on the hard disk? Thanks but I'll just calculate it again instead 'cos I don't got all day.
- _a_a_a_ 3y ago
  Thank you for the lesson in memory access times I actually know something about the subject already :-) > But the O(n*log(n)) algorithm I think you're badly missing out the "* log(n)" part. But on reflection, you have made your point, thank you.
  - tialaramex 3y ago
    > I think you're badly missing out the "* log(n)" part. Nope? But I can see why you might have missed it, instinctively log(10_000) feels like it should be pretty big. It feels big, doesn't it. Not as big as n, but surely a sizeable quantity. However the log to base 2 (which we might decide we prefer to care about here since this is computer science) is about 13. So yeah, the numbers work out fine. I guess it's possible my use of the word "linear" confused you. I'm talking linear in comparison to random access, not suggesting that somehow a log-linear complexity is the same as a linear complexity. But then, you know "something" about this so maybe not. EtA: Aha, I realised my mistake, I just used rough numbers, maybe you'd have realised if I'd written 132 870 cycles or something even though that's obviously not correct because it's excessive accuracy.