# Recent LLVM hash table improvements

DevFeed: [Recent LLVM hash table improvements](<https://devfeed.tech/articles/recent-llvm-hash-table-improvements-31122.md>)

Original publisher: [Read original article](<https://maskray.me/blog/2026-06-07-recent-llvm-hash-table-improvements>)

Published: 2026-06-07T07:00:00Z

Content type: article

Language: en

Sources: [MaskRay](<https://devfeed.tech/sources/maskray.md>)

Topics: [LLVM](<https://devfeed.tech/topics/llvm.md>), [hash](<https://devfeed.tech/topics/hash.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [benchmarking](<https://devfeed.tech/topics/benchmarking.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [compiler](<https://devfeed.tech/tags/compiler.md>), [data-structures](<https://devfeed.tech/tags/data-structures.md>), [hash](<https://devfeed.tech/tags/hash.md>), [improvements](<https://devfeed.tech/tags/improvements.md>), [llvm](<https://devfeed.tech/tags/llvm.md>), [performance](<https://devfeed.tech/tags/performance.md>)

## AI overview

The article reviews recent improvements to LLVM hash tables, including replacing quadratic probing and tombstone or empty-key sentinels with linear probing, Algorithm R deletion, and bit-array occupancy. It also discusses pointer and iterator invalidation behavior and reports performance improvements in DenseMap.

## Source excerpt

LLVM has several hash tables. They used quadratic probing with in-band sentinel keys (empty, tombstone); recent work has been replacing that with linear probing with tombstone key removed. DenseMap (replacement for std::unordered_map): DenseMapInfo::getEmptyKey() / getTombstoneKey(). DenseSet: implemented using DenseMap compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h ports the implementation for sanitizers. SmallPtrSet (replacement for std::unordered_set<T *>): hard-coded -1 (empty) and -2 (tombstone). StringMap (replacement for std::unordered_map<std::string, V>) StringSet: implemented using StringMap FoldingSet (uniquing/hash-consing container, not a general map) For the open-addressed DenseMap and SmallPtrSet, pointers, references, and iterators are invalidated by insert. StringMap is different: each entry lives in a heap-allocated StringMapEntry<V> node, so entry pointers survive grow. std::unordered_map, being node-based, keeps surviving-element pointers valid across both insert and erase and only invalidates the erased element's own iterator. LLVM code rarely needs that stronger contract -- callers do not hold long-lived references into the container across mutation -- and that gap is what gives pass to relocating erase and bit-array occupancy. Recently, Tombstones have been removed from DenseMap and SmallPtrSet. erase() also invalidates pointers. DenseMap has also retired its empty-key sentinel, leading to significant performance improvements. DenseMap with integer keys (int/unsigned/size_t) had -1/-2 reserved -- a footgun, now fixed. StringMap got Algorithm R deletion too. Its entries are separately heap-allocated, so erase keeps entry pointers valid but invalidates iterators; erase-while-iterating moved to remove_if. FoldingSet dropped chaining for linear probing plus Algorithm R; the intrusive next-in-bucket pointer became a cached 32-bit hash.