map is a red-black tree, which keeps the data sorted. You should use map<> if you need to visit the data in-order with a for-each loop. Hashmaps can't visit the data in order.
Looking at the code more carefully, I'd actually bet its string that's slow, and not actually map.
unordered_map is actually known to have relatively bad performance on GCC and some other open-source implementations. I don't know if there's a spec-problem that favors a slower-hash table (rather than the modern open-addressing scheme, which is faster on modern computers), but I can believe unordered_map has an issue on common standard libraries today.
Three, then two frees() as the previous two strings are deallocated.
> ret[string("id.")+to_string(i%500000)]
Four. The ret[] operator searches for the string. Since it doesn't exist, it now has to malloc the key and insert the value in there. std::move() might solve that issue and cut this one out easily?
Eight, to place the value in there. Again, probably solved with std::move. +1 more free.
So eight mallocs and 6 frees?
---------
Yeah, C++ strings shoot yourself in the foot performance-wise. But they're easy to use and free of stupid malloc/free bugs, but it means that they will malloc/free a LOT more than you might guess with the untrained eye.
I know that Perl / PHP / etc. etc. were explicitly designed to be more favorable towards string manipulation. And I'd bet that there's some old C++98 stuff that might lock in the performance of string to this older, less performant model.
EDIT: I see you managed to avoid the problem of excessive mallocs/frees in the Rust code with "format". The C++ equivalent might be snprintf, though that dips down into C-style strings.
> I don't know if there's a spec-problem that favors a slower-hash table
Yes. std::unordered_map requires that pointers to stored values will always be valid (except if the value is erased). This makes open adressing effectively impossible. If you need max. performance, std::unordered_map is indeed not a good choice.
> The ret[] operator searches for the string. Since it doesn't exist, it now has to malloc the key and insert the value in there.
> So eight mallocs and 6 frees?
> Yeah, C++ strings shoot yourself in the foot performance-wise.
Most implementations of std::string use short string optimization. Typically, you can save up to 12 chars (32-bit) or 24 chars (64-bit) inside the actual string container without any memory allocation.
Looking at the code example, I would say that there won't be any mallocs at all for std::string.
I think the performance difference just comes from the suboptimal design of std::unordered_map, where each node has to be allocated on the heap. In open addressing hash tables, as used by PHP (and I guess also by Rust), the nodes live in a single large array. The only memory allocation you see is when the array has to be resized due to a rehash - which happens very rarely!
Thanks for the SSO pointer. I'll keep that in mind in the future.
> Yes. std::unordered_map requires that pointers to stored values will always be valid (except if the value is erased).
Hmm, that requirement also prevents Cuckoo-hashing.
The general pattern here (and this is problematic in a lot of languages), is the idea of having a "shortcut" into an object in a data-structure. For example, C++ and Java's "iterator-invalidation" rules are absolutely arcane, even if we removed the pointer-requirements.
Many data-structures want to move things around (cuckoo-hashing, open-addressing, robin-hood hashing... look 3 different, high-performance strategies and we're still just talking about hash tables!!). But those moves "invalidate" the shortcuts (be it a pointer or an iterator).
Some data-structures can have those pointers just fine (Red-and-black trees), others cannot. Representing all these possibilities with a fixed, easily understood interface that generalizes among all of these data-structures / decisions seems impossible.
------
Well, I guess that's why I keep rolling my own data-structures when I need performance guarantees... standard-library just has to make decisions that may or may not match my cases.
> Well, I guess that's why I keep rolling my own data-structures when I need performance guarantees...
Yes, this is what many companies do. std containers are good enough for the general case, but are certainly situations where you need something more fancy. However, before you roll your own, first check if there's a good library you can use. The world's best hashtable has already been written by other people :-)
For std::unordered_map, I don't know why they decided to add the no-iterator-invalidation requirement. If you really need that property, you could get most of the benefits by using unordered_map<unique_ptr<T>> instead of unordered_map<T>. So maybe not the best example of "don't pay for what you don't use".
Iterators can be invalidated (e.g. after a rehash). The requirement is rather that the address of the value itself must not change (so that pointers will remain valid).
> If you really need that property, you could get most of the benefits by using unordered_map<unique_ptr<T>> instead of unordered_map<T>.
I mean, its a hashmap we're talking about. I'm not sure if iterators even make sense in any regard. Things inside of a hashmap have no order at all.
And determining if a cell is full or empty in a hash-map isn't exactly efficient either (You pretty much have to visit those locations and see if a tombstone or empty symbol is there).
-------
I recognize that people want to foreach() over a HashMap, but I'm just not convinced its an efficient operation, nor a good fit for the iterator interface (especially with all this discussion of invalidations and movement...)
> I'm not sure if iterators even make sense in any regard. Things inside of a hashmap have no order at all.
Iteration doesn't necessarily imply a specified order.
> but I'm just not convinced its an efficient operation
Why does iteration have to be efficient?
> nor a good fit for the iterator interface
What would you use instead?
Iterator invalidation only comes into play when you erase elements. If you just iterate over a hashtable and, say, print the elements, you wouldn't have to worry about it at all.
In both Robin Hood and Cuckoo hashing, insertions will move elements around. That means the iterator guarantees (or: that you'd visit every element) could be broken).
So a foreach(cuckoo_table) operation may not in fact visit all elements if the table has an insert somewhere in the loop.
Vector: Inserts are allowed as long as element fits in vector.capacity(). Erase (which "shifts" the elements down) are allowed at the end of the vector (specifically: all locations "after" the erase are invalidated. So pop_back() is always legal)
List: All operations allowed, except for reading from an erased element.
map: All operations allowed, except for reading from an erased element.
unordered_map: ??? Under debate right now.
-------
So even if you had assurances that unordered_map.insert would work (ex: Robinhood hash, you check size() and compare to capacity(), much like a vector), the movement of data means that your iterator is basically invalidated on any insert.
So unordered_map(Robin-hood): Nothing. No erases, no insertions allowed during the foreach loop at all.
-------
This comes up in practice. The minute you have 2 threads, and a 2nd thread _might_ insert while the 1st thread _might_ be in a foreach loop, you suddenly have to have assurances for what is or isn't legal from an iterator-invalidation perspective.
I guess you could just have the entire for-each loop inside of a lock, but that seems a bit inefficient?
> So unordered_map(Robin-hood): Nothing. No erases, no insertions allowed during the foreach loop at all.
Yes, but this applies to any hashtable that might rehash on inseration (= most). In practice this is not a big problem. For example, you can just put the new elements / to be deleted keys on a std::vector and only insert/erase after the for-loop.
I don't see how this makes iteration itself problematic. You can still iterate over a std::unordered_map perfectly fine. Just don't erase/insert elements while iterating.
> I guess you could just have the entire for-each loop inside of a lock, but that seems a bit inefficient?
Yes, you would have to lock the whole for-loop. It's the same with any other data structures where the iterators can get invalidated on inseration/deletion, e.g. std::vector.
Even for containers where iterators are not invalidated, you have to be careful with fain-grained locks. For example, you can only increment the iterator while holding the lock!
std::ostringstream will certainly allocate its buffer on the heap. When you call the str() method to retrieve the final result, it will have to make another copy. So you will always have an extra allocation.
Note that std::format still returns a std::string (which might allocate memory, depending on the size of the string), but that doesn't matter if it is going to be moved anyways.
If you want to write into an existing buffer, you can use std::format_to_n as a modern replacement for snprintf.
C++ 20 has std::format for formatting. And an errata even fixed the typical C++ footgun of allowing you to write nonsense and then only discover the problem at runtime (maybe months later if this code is in an uncommon path), the committee agreed that yes, compilers should tell you if your constant string format won't work at compile time as would happen in Rust, and many other modern languages.
std::format("id.{}", i) // is fine
std::format("{}-{}", oops) // You need two parameters, compiler knows this
e.g. replacing std::unordered_map with robin_hood::hash_map makes the above C++ code go from 1.2 seconds to 0.5 seconds on my machine (std::map is around 1.3/1.4 seconds for libstdc++).
(though as others said, this test is in big part a test of std::string performance... replacing strings by int make times go down to ~0.1s here)
unordered_map is the hashmap.
map is a red-black tree, which keeps the data sorted. You should use map<> if you need to visit the data in-order with a for-each loop. Hashmaps can't visit the data in order.