Changing std::sort at Google’s Scale and Beyond
TL;DR; We are changing std::sort in LLVM’s libcxx. That’s a long story of what it took us to get there and all possible consequences, bugs you might encounter with examples from open so…
Hasnain says:
Great read on sorting algorithms and incrementally upgrading a massive codebase (and the adventures learnt during that process). I loved the bit on adding more safety/randomization in code in debug mode, to avoid hitting Hyrum's law - it's a pattern I've seen in the past too (and, in the context of sorting/hashtables, funnily enough!)
"Consider randomization for the APIs that can be relied on at least in testing/debug mode. Seeding the hash function differently for not relying on the order of iteration of hashtables. If the function requires to be only associative, try to accumulate results in different order, etc."
Posted on 2022-04-21T00:45:51+0000