4 ms·

unordered_map performs even worse than map. Tried it.

dragontamer 5y ago
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. ------------ > ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); Lets count the mallocs. > string("id.") One > to_string(i%500000) Two > string("id.")+to_string(i%500000) 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? > string("val.") Five > to_string(i) Six > string("val.")+to_string(i) Seven + 2x frees. > ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); 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.
- maleldil 5y ago
  > The C++ equivalent might be snprintf There's std::format from C++20 too[1]. One can use std::ostringstream instead, I suppose, but at that point I'd probably use snprintf too. [1] https://en.cppreference.com/w/cpp/utility/format/format https://en.cppreference.com/w/cpp/utility/format/format
  - spacechild1 5y ago
    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.
- spacechild1 5y ago
  > 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. The optimal method would be https://en.cppreference.com/w/cpp/container/unordered_map/emplace https://en.cppreference.com/w/cpp/container/unordered_map/em... > 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!
  - dragontamer 5y ago
    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.
- tialaramex 5y ago
  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
jcelerier 5y ago
that's absolutely untrue in a lot of cases: https://stackoverflow.com/questions/36392583/is-an-unordered-map-really-faster-than-a-map-in-practice https://stackoverflow.com/questions/36392583/is-an-unordered... of course one can always find faster, drop-in replacement libraries: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/ https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o... 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)

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. ------------ > ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); Lets count the mallocs. > string("id.") One > to_string(i%500000) Two > string("id.")+to_string(i%500000) 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? > string("val.") Five > to_string(i) Six > string("val.")+to_string(i) Seven + 2x frees. > ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); 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.

maleldil 5y ago
> The C++ equivalent might be snprintf There's std::format from C++20 too[1]. One can use std::ostringstream instead, I suppose, but at that point I'd probably use snprintf too. [1] https://en.cppreference.com/w/cpp/utility/format/format https://en.cppreference.com/w/cpp/utility/format/format
- spacechild1 5y ago
  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.
spacechild1 5y ago
> 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. The optimal method would be https://en.cppreference.com/w/cpp/container/unordered_map/emplace https://en.cppreference.com/w/cpp/container/unordered_map/em... > 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!
- dragontamer 5y ago
  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.
tialaramex 5y ago
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

jcelerier 5y ago

that's absolutely untrue in a lot of cases: https://stackoverflow.com/questions/36392583/is-an-unordered-map-really-faster-than-a-map-in-practice https://stackoverflow.com/questions/36392583/is-an-unordered... of course one can always find faster, drop-in replacement libraries: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/ https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o... 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)