3 ms·

It has some pretty bad containers, specifically unordered_map and map, and set. There are some good talks on why from ccp con and other varius developer cons. T

by fyrn_ 2y ago

It has some pretty bad containers, specifically unordered_map and map, and set. There are some good talks on why from ccp con and other varius developer cons. They are still usable mind you, just it's also true that unordered_map is slower then JS or Python hashmaps in some situations because of some really questionable design choices (exposing bucket nodes, overly restrictive iterator invalidation requirements, etc..)

krackers 2y ago
What's the recommended drop-in replacement? absl::flat_map?
- dataflow 2y ago
  One of the Abseil containers if you really need an associative container to begin with, but honestly often you can play quite a few tricks with just plain arrays if you get a little creative, with better performance profiles...
- tialaramex 2y ago
  You almost certainly don't need a "drop-in replacement" which is part of the problem. If you really just need a hash table, Abseil, Boost and Folly all provide several good options to suit your needs, and if you have a favourite utility library that's not one of those three it probably has at least one hash table type. A "drop-in replacement" would commit to all the weird things about the standard library type which result in poor performance, some of them might be important to you, and you'll probably insist oh, it's not a "drop-in" replacement if I can't have those, and across the entire C++ population that means there is no high performance drop-in replacement, the type guarantees any number of weird properties and you could depend on all those, so, too bad. The most likely reliance you'd have is reference stability, maybe you give out references to items in the table and they're long lived so you mustn't invalidate them when/ if there's a resize, let alone on unrelated changes to a table which keeps the same size. Abseil, Boost and Folly all provide types which lose some performance to get this back if it's all you need to be "drop-in". The most unlikely reliances are two fold, firstly maybe you insist on messing with the bucket API, which makes no sense in open addressed tables (ie all the ones with great performance). In this case you're wedded to std::unordered_map because the details of how the type is structured are welded into your code. Sucks to be you. Secondly though, you might have decided you care about the order, the std::unordered_map says it doesn't promise an order, but on a single platform none of the implementations actually kick you if you assume the order is preserved, so you can merrily write a unit test which checks that after adding fake users Alice, Bob and Carol to your user hash table, when asked for the users back in no particular order you get exactly: Carol, Alice, Bob. Is that a good unit test? No. But the replacements will make it go red, they're not "drop-in" replacements.
  - vitus 2y ago
    > Abseil, Boost and Folly all provide types which lose some performance to get this back if it's all you need to be "drop-in". Indeed, Google's initial migration from std::unordered_map to swisstables moved everyone to absl::node_hash_map since it was safer, even though flat_hash_map generally offers better performance. > after adding fake users Alice, Bob and Carol to your user hash table, when asked for the users back in no particular order you get exactly: Carol, Alice, Bob. Ow :( This reminded me of Matt Kulukundis at cppcon talking about migrating away from std::unordered_map, wherein he brought up this point exactly: https://youtu.be/JZE3_0qvrMg?t=740 https://youtu.be/JZE3_0qvrMg?t=740 Matt then goes on to describe how Abseil adds a nondeterministic iteration offset to each hash table to prevent anyone from relying on this moving forward.
    - tialaramex 2y ago
      I was thinking of Matt's talk, although also of how many fucking times I have fixed unit tests which do this. And not just in C++. Also: Unit test people, it's great that it's easy to check that "foo == 5" is true, and I can see why you thought it should be equally easy to check "foo == Carol, Alice, Bob" but could you perhaps nudge the developer to check they didn't mean "foo contains all of Carol, Alice, Bob" instead when they do that? Maybe have them pick "in order" versus "any order" with no default ? There are a few more like this, case sensitivity is one, my newest colleague is going to write a test for "dnsName = example.com" even though actually dnsName might sometimes be "EXAMPLE.COM" or "Example.Com" or even "eXAMplE.cOM" and it'd be nice if they were nudged to spend that extra moment to decide whether that's OK or not before a test goes red spuriously.
    - cempaka 2y ago
      Heh that last part is interesting, Java had the same issue with people's programs relying on (not guaranteed by the spec) deterministic order in HashMap/HashSet iteration and breaking after a JDK upgrade. They similarly added randomization to the iterators on the immutable collections returned by Map.of() and Set.of(), even though they could otherwise be deterministic since those collections never resize.
tialaramex 2y ago
I've watched a few talks about the STL containers. I don't think they're savage enough. In particular the C++ growable array type std::vector is often cited as good. Is it terrible? No. But it's still not actually as good as it should be, we can easily do better if we provide the proper API. Growable arrays are a very popular idea. Your preferred language almost certainly has them, but they might be built in to the language as an optimisation, if "normal" arrays in your language can grow and that's fast enough, chances are you're got the growable array type just as the only array, which is fine (but won't fly on tiny embedded systems). This type has amortized O(1) aka constant time growth, which is one of those tricks which is amazing if you've never seen it before, then it just seeps into your understanding of the world and so it's easy to imagine why C++ doesn't do any better. As a necessary optimisation beyond the amortized growth we must be able to tell a growable array hints about its future size. The only hint provided in the C++ STL is reserve, which tells the array its maximum final size. Rust calls this hint Vec::reserve_exact, if our array isn't this big, we should grow immediately, makes sense. Here's where the problem kicks in: Suppose I don't know the maximum final size, but I do know I need to put say, at least 50 more things in the container? Algorithmically the answer is actually yes, the amortized growth can be preserved if we either grow sooner or skip growth steps and otherwise the hint can be ignored, this is Rust's Vec::reserve If we try to use the C++ reserve here (aka Vec::reserve_exact) even though this isn't the final size, we destroy our amortized growth performance, our container may have lousy performance. If we just don't bother because we can't express our hint, our container has worse performance than necessary because we grow more often or less optimally.
- mandarax8 2y ago
  Easily solved manually reserving exponentially. All my projects use some variation of this: https://github.com/facebook/folly/blob/9f125c94e10fd01f5567cdbc317f8026de3a20b5/folly/container/Reserve.h#L49 https://github.com/facebook/folly/blob/9f125c94e10fd01f5567c... But I've burned myself on this a few times before.
  - jstimpfle 2y ago
    resize(size() + N), resize(size() - N) should do the trick too, unless default constructing your elements is costly or not defined. But I wonder what use case there is where you can't just push_back() one by one? The only potential issue here is that there might be a reallocation happening while append this range of N elements, but can't imagine what might break.

by fyrn_ 2y ago

krackers 2y ago

What's the recommended drop-in replacement? absl::flat_map?

dataflow 2y ago
One of the Abseil containers if you really need an associative container to begin with, but honestly often you can play quite a few tricks with just plain arrays if you get a little creative, with better performance profiles...
tialaramex 2y ago
You almost certainly don't need a "drop-in replacement" which is part of the problem. If you really just need a hash table, Abseil, Boost and Folly all provide several good options to suit your needs, and if you have a favourite utility library that's not one of those three it probably has at least one hash table type. A "drop-in replacement" would commit to all the weird things about the standard library type which result in poor performance, some of them might be important to you, and you'll probably insist oh, it's not a "drop-in" replacement if I can't have those, and across the entire C++ population that means there is no high performance drop-in replacement, the type guarantees any number of weird properties and you could depend on all those, so, too bad. The most likely reliance you'd have is reference stability, maybe you give out references to items in the table and they're long lived so you mustn't invalidate them when/ if there's a resize, let alone on unrelated changes to a table which keeps the same size. Abseil, Boost and Folly all provide types which lose some performance to get this back if it's all you need to be "drop-in". The most unlikely reliances are two fold, firstly maybe you insist on messing with the bucket API, which makes no sense in open addressed tables (ie all the ones with great performance). In this case you're wedded to std::unordered_map because the details of how the type is structured are welded into your code. Sucks to be you. Secondly though, you might have decided you care about the order, the std::unordered_map says it doesn't promise an order, but on a single platform none of the implementations actually kick you if you assume the order is preserved, so you can merrily write a unit test which checks that after adding fake users Alice, Bob and Carol to your user hash table, when asked for the users back in no particular order you get exactly: Carol, Alice, Bob. Is that a good unit test? No. But the replacements will make it go red, they're not "drop-in" replacements.
- vitus 2y ago
  > Abseil, Boost and Folly all provide types which lose some performance to get this back if it's all you need to be "drop-in". Indeed, Google's initial migration from std::unordered_map to swisstables moved everyone to absl::node_hash_map since it was safer, even though flat_hash_map generally offers better performance. > after adding fake users Alice, Bob and Carol to your user hash table, when asked for the users back in no particular order you get exactly: Carol, Alice, Bob. Ow :( This reminded me of Matt Kulukundis at cppcon talking about migrating away from std::unordered_map, wherein he brought up this point exactly: https://youtu.be/JZE3_0qvrMg?t=740 https://youtu.be/JZE3_0qvrMg?t=740 Matt then goes on to describe how Abseil adds a nondeterministic iteration offset to each hash table to prevent anyone from relying on this moving forward.
  - tialaramex 2y ago
    I was thinking of Matt's talk, although also of how many fucking times I have fixed unit tests which do this. And not just in C++. Also: Unit test people, it's great that it's easy to check that "foo == 5" is true, and I can see why you thought it should be equally easy to check "foo == Carol, Alice, Bob" but could you perhaps nudge the developer to check they didn't mean "foo contains all of Carol, Alice, Bob" instead when they do that? Maybe have them pick "in order" versus "any order" with no default ? There are a few more like this, case sensitivity is one, my newest colleague is going to write a test for "dnsName = example.com" even though actually dnsName might sometimes be "EXAMPLE.COM" or "Example.Com" or even "eXAMplE.cOM" and it'd be nice if they were nudged to spend that extra moment to decide whether that's OK or not before a test goes red spuriously.
  - cempaka 2y ago
    Heh that last part is interesting, Java had the same issue with people's programs relying on (not guaranteed by the spec) deterministic order in HashMap/HashSet iteration and breaking after a JDK upgrade. They similarly added randomization to the iterators on the immutable collections returned by Map.of() and Set.of(), even though they could otherwise be deterministic since those collections never resize.

tialaramex 2y ago

I've watched a few talks about the STL containers. I don't think they're savage enough. In particular the C++ growable array type std::vector is often cited as good. Is it terrible? No. But it's still not actually as good as it should be, we can easily do better if we provide the proper API. Growable arrays are a very popular idea. Your preferred language almost certainly has them, but they might be built in to the language as an optimisation, if "normal" arrays in your language can grow and that's fast enough, chances are you're got the growable array type just as the only array, which is fine (but won't fly on tiny embedded systems). This type has amortized O(1) aka constant time growth, which is one of those tricks which is amazing if you've never seen it before, then it just seeps into your understanding of the world and so it's easy to imagine why C++ doesn't do any better. As a necessary optimisation beyond the amortized growth we must be able to tell a growable array hints about its future size. The only hint provided in the C++ STL is reserve, which tells the array its maximum final size. Rust calls this hint Vec::reserve_exact, if our array isn't this big, we should grow immediately, makes sense. Here's where the problem kicks in: Suppose I don't know the maximum final size, but I do know I need to put say, at least 50 more things in the container? Algorithmically the answer is actually yes, the amortized growth can be preserved if we either grow sooner or skip growth steps and otherwise the hint can be ignored, this is Rust's Vec::reserve If we try to use the C++ reserve here (aka Vec::reserve_exact) even though this isn't the final size, we destroy our amortized growth performance, our container may have lousy performance. If we just don't bother because we can't express our hint, our container has worse performance than necessary because we grow more often or less optimally.

mandarax8 2y ago
Easily solved manually reserving exponentially. All my projects use some variation of this: https://github.com/facebook/folly/blob/9f125c94e10fd01f5567cdbc317f8026de3a20b5/folly/container/Reserve.h#L49 https://github.com/facebook/folly/blob/9f125c94e10fd01f5567c... But I've burned myself on this a few times before.
- jstimpfle 2y ago
  resize(size() + N), resize(size() - N) should do the trick too, unless default constructing your elements is costly or not defined. But I wonder what use case there is where you can't just push_back() one by one? The only potential issue here is that there might be a reallocation happening while append this range of N elements, but can't imagine what might break.