Recent LLVM hash table improvements (opens in new tab)  🔧Compilers

LLVM had several hash tables using quadratic probing with in-band sentinel keys (empty, tombstone). DenseMap (replacement for std::unordered_map): DenseMapInfo::getEmptyKey() / getTombstoneKey(). SmallPtrSet (replacement for std::unordered_set ): hard-coded -1 (empty) and -2 (tombstone). StringMap (replacement for std::unordered_map ) Pointers, references, and iterators are invalidated by both insert. std::unordered_map, being node-based, keeps surviving-element pointers va...