4 ms·

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 t

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

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