News for hackers. Stuff that matters.
Re:The tech industry controls CS conference funding. What ar... by tialaramex on Saturday March 12, 2022 @08:16AM (#30651120)
> For example, if you ever attend a C++ talk by Googlers ... present about how they “optimized” some part of the STL

I'm guessing you're thinking about things like Swiss Tables. But the situation isn't that Swiss Tables "optimize" the STL's containers instead they're just the replacement you'd actually want. You can't "optimize" the STL containers, because they're defined in a way that's hostile to optimization.

Take std::unordered_set. Why is it so slow ? Well, your standard library is obliged to make this work roughly the same way as it would have when explained in a CS introductory Data Structures class in the 1980s. This is not necessary for the ordinary understanding or use of an "unordered set" which is why Swiss Tables has one that's much better, but if you've paid attention in that class you know there are buckets of keys with similar hash values so that's what the STL is obliged to provide.

If you just want an "unordered set" you do not want std::unordered_set despite the name, you want the much better replacements from Swiss Tables or various other offerings and it's unfortunate that std::unordered_set is in the standard and those are not.

Of course the other reason std::unordered_set is so slow for you isn't solved by Swiss Tables, but it was called out by the Googlers presenting Swiss Tables more than once. Your hash function is garbage. Even if you insist on using std::unordered_set because it was good enough thirty years ago or whatever, this part of the lesson is invaluable anyway.

When using data structures that are faster because of hashing, you defeat them by using poor quality hashes. To a first approximation if you aren't sure that you are using a good quality hash then you probably aren't. In any optimisation quest start by measuring, and in this case that means measuring: Is your hash actually any good at... hashing ?

Re:The tech industry controls CS conference funding. What ar... by kevinventullo on Saturday March 12, 2022 @10:22AM (#30651961)
To further support your point, the engineers at Facebook who worked on the F14 hashmaps/hashsets saw the same issues, and created two implementations as a result:

“Folly has chosen to expose a fast C++ class without reference stability as well as a slower C++ class that allocates each entry in a separate node. The node-based version is not fully standard compliant, but it is drop-in compatible with the standard version in all the real code we’ve seen.”

https://engineering.fb.com/2019/04/25/developer-tools/f14/

Re:The tech industry controls CS conference funding. What ar... by saagarjha on Saturday March 12, 2022 @05:02PM (#30655359)
This is basically my point, though. The things you’ve said (which are basically just what Google pushes) are correct. For their use case, they’ve found some good wins and there’s lots of interesting things under the hood enabling this. That’s cool, but these improvements come at a cost: the ABI (and in some cases, the API) is different. For Google this is OK because they can just ask their clients to adapt. This might be fine for you as well. But it’s definitely not the case for everyone, and ignoring it (at best) or actively harping on the standard for making concessions for the “dumb” reason of stability is not appropriate.
Re:The tech industry controls CS conference funding. What ar... by tialaramex on Saturday March 12, 2022 @10:47PM (#30657735)
I think you're arguing against a straw man? Maybe you can give a concrete example of the behaviour you're concerned about.

Neither of the Google C++ Swiss Table presentations I've seen were about how somehow std::unordered_set can be replaced by this completely different thing. The existing container is just useless, that's sad but there's nothing to be done about it because the ABI break cost is unacceptable.

Instead the talks were about why this thing (Swiss Tables) makes sense, how you can make use of it in your own software, and maybe about tricks you can use in your own data structures, or about how Hyrum's law interacts with this work.