Summary
We propose modernizing llvm::FoldingSet<T> by transitioning it to an
open-addressing hash set, yielding a 1.4% to 1.5% compile-time speedup on
clang -O3.
This RFC describes FoldingSet, evaluates three open-addressing implementations
(Swiss Table and two variants of Knuth’s Algorithm R), and compares their
performance and memory trade-offs.
Background: What is FoldingSet?
FoldingSet<T>, heavily used in AST, SCEV, and SelectionDAG, uniquely stores
pointers (T*) by structural profile rather than pointer identity. For
example, when creating X + 1, SelectionDAG profiles the opcode, type, and
operands into a FoldingSetNodeID and queries FoldingSet<SDNode>, reusing
any existing node before allocating a new one.
Unique Characteristics of the Current Implementation
The current implementation of FoldingSet has several unique characteristics:
Intrusive Collision Chains
Every stored object derives from FoldingSetNode, which embeds a single
pointer:
class FoldingSetNode {
void *NextInFoldingSetBucket = nullptr;
...
};
In the current implementation, this pointer serves as the linked-list node
connecting elements in the same bucket collision chain.
Two-Phase FindNodeOrInsertPos
FoldingSet separates lookup and insertion so callers can construct nodes
lazily on a miss without re-probing on insert:
void *InsertPos = nullptr;
if (T *Existing = Set.FindNodeOrInsertPos(ID, InsertPos))
return Existing;
T *NewNode = new (Allocator) T(...);
Set.InsertNode(NewNode, InsertPos); // Skips re-probing
In-Place Node Modification and Circular Bucket Rings
Some users (e.g., SelectionDAG) mutate nodes in place before removal. Because
mutating a node changes its hash, RemoveNode(N) cannot locate N’s bucket by
re-profiling. The current implementation solves this with circular bucket
chains: RemoveNode(N) follows the ring to N’s predecessor to unlink N in
O(chain length) without needing its hash.
Proposed Modernization: Open-Addressing Hash Table
Repurposing FoldingSetNode
Instead of a collision pointer, FoldingSetNode caches the 32-bit hash:
class FoldingSetNode {
uint32_t FoldingSetHash = 0;
...
};
- Fast Removal:
RemoveNode(N)reads the cached hash directly fromNto
locate its slot without re-profiling. - Zero Growth Re-Profiling: Table doubling re-inserts existing nodes using
their cached hashes without invokingProfile().
Explored Implementations
We have implemented and evaluated three open-addressing designs:
-
PR #218156 (Swiss Table):
Uses 8-way SWAR/SIMD group probing on a 1-byte control metadata array (Ctrl),
matching 7-bit $H_2$ hash fingerprints in parallel to eliminate ~99.2% of
non-matching slots in a single word operation. Deletions place tombstones
(0xFE) reclaimed on rehash; operates at an 87.5% load factor (9.0 B/bucket). -
PR #218188 (1-bit Algorithm R):
Uses linear probing with occupancy tracked in a packed 1-bit bitmap (Used),
inspecting the cached 32-bit hash onFoldingSetNode. Deletions are completely
tombstone-free using Knuth TAOCP 6.4 Algorithm R (shifting downstream cluster
elements backward); operates at a 75% load factor (8.125 B/bucket). -
PR #218190 (Parallel Hashes Algorithm R):
Uses linear probing with Algorithm R deletion, but duplicates the full 32-bit
hash into a separateuint32_t Hashes[]table array alongsideBuckets[]
(similar toStringMap). Avoids node dereferences during hash mismatches;
operates at a 75% load factor (12.0 B/bucket).
Performance & Memory Evaluation
Across a wide benchmark suite of large C++ translation units, PR #218156
(Swiss Table) and PR #218188 (1-bit Algorithm R) deliver a 1.40% and
1.50% speedup on clang -O3, respectively.
FoldingSet bucket allocations account for ~3% of peak heap memory (~42 MB /
1.3 GB) when compiling SLPVectorizer.cpp. Below is Max RSS measured on
SLPVectorizer.cpp (3-run average; ASLR and THP disabled):
| Implementation | Table Footprint | Max Load Factor | Max RSS | % Overhead |
|---|---|---|---|---|
| Current implementation (Chained) | 8.000 B / bucket | 200% (2.0) | 1,295,303 KB | — |
| PR #218188 (1-bit Algorithm R) | 8.125 B / bucket | 75% (0.75) | 1,309,015 KB | +1.06% |
| PR #218156 (Swiss Table) | 9.000 B / bucket | 87.5% (0.875) | 1,316,964 KB | +1.67% |
| PR #218190 (Hashes Algorithm R) | 12.000 B / bucket | 75% (0.75) | 1,334,760 KB | +3.05% |
Analysis & Trade-Offs
- Table Footprint: Lower load factors (<= 75% ~ 87.5%) require allocating
more table buckets (2x to 2.67) than the chained design
(200%), increasing central table array memory from 4.0 B/node to
~10.3–10.8 B/node. - 1-bit vs. Parallel Hashes: Duplicating hashes in the table array
(PR #218190) increases table memory from 8.125 B to 12.0 B/bucket (+3.05% RSS
vs. +1.06% for PR #218188). However, this does not save cache misses on lookup
hits, where candidate nodes must be dereferenced to computeProfile()anyway.
Feedback Requested
Feedback is greatly appreciated! In an era where RAM is at a premium, is the
compile-time speedup worth the modest memory trade-off? If so, which
open-addressing option do you think is most appropriate?