Lesson 10.6 — ADTs and why they exist¶

Techniques: SmallVector (small-size optimization, SmallVectorImpl in APIs), DenseMap (open addressing: LLVM 23's linear probing with backward-shift deletion vs the classic tombstone design; DenseMapInfo; invalidation), SetVector, StringRef/ArrayRef/Twine (non-owning views and their lifetimes), StringMap, bit sets (BitVector, SparseBitVector), pointer packing (PointerIntPair, PointerUnion), arbitrary-precision numbers (APInt, APFloat) · Pebble uses: all of them; the labs use SmallVector, DenseMap, StringRef and APInt · Lab: Lab 10.2 · Prerequisites: Lessons 10.1–10.2; hash tables ([CLRS4, Ch. 11]) · Time: 4–5 hours

Most sets in a compiler hold a handful of elements: the operands of an instruction, the predecessors of a block, the users of a value. Most maps are keyed by pointers, and most strings are names that already live somewhere. The standard library's containers pay a heap allocation for every non-empty std::vector, a node allocation for every std::map or std::unordered_map entry, and a copy for every std::string argument. LLVM's ADT library replaces them with containers tuned for these cases [LLVM-PM, Car14]. This lesson explains each container's design, proves the property that makes it fast, and states exactly what invalidates your references into it. That last part is where the bugs are.

1. Problem and motivation¶

A compiler performs billions of tiny container operations per build. The costs that dominate are allocation, cache misses (pointer chasing through nodes) and copying. LLVM's containers are designed around them: inline storage for small sizes, flat open-addressing tables, views instead of copies, and bits instead of words where possible [Car14]. The price is sharper invalidation rules than the standard library's, and several ways to create dangling views.

SmallVector¶

SmallVector<T, N> stores up to $N$ elements inside the object and moves to the heap only when it grows past $N$. APIs take SmallVectorImpl<T> &, which erases $N$ from the type, so callers choose their own inline size [LLVM-PM, LLVM-SmallVector].

DenseMap¶

A hash table with open addressing: keys and values live in one flat array of buckets, so there is no per-entry allocation. DenseMapInfo<K> supplies the hash and equality. Up to LLVM 22 the table used quadratic probing, with reserved empty and tombstone key values. LLVM 23 switched to linear probing with a separate "used" bit per bucket and deletion by backward shifting (Knuth's Algorithm R [TAOCP3]), which removes tombstones and the reserved keys (llvm/include/llvm/ADT/DenseMap.h, file comment) [LLVM-DenseMap].

SetVector¶

A vector plus a set: $O(1)$ expected membership tests, and iteration in insertion order. Iterating a DenseSet<T *> follows hash order, which depends on pointer values and so changes from run to run. A compiler whose output depends on that order is non-deterministic. SetVector is the standard fix and the standard worklist [LLVM-PM].

StringRef, ArrayRef and Twine¶

StringRef and ArrayRef<T> are (pointer, length) views that make string and array parameters free to pass. Twine is a lazy concatenation tree for building names (Base + "." + Twine(N)) without allocating intermediate strings. All three are non-owning. They are the most common source of use-after-free in LLVM client code [LLVM-PM, LLVM-Twine].

StringMap¶

A hash table from strings to values where each entry is allocated together with a copy of its key. It is used for symbol tables (a module's ValueSymbolTable is one). Because entries never move, a StringRef to a key stays valid while the entry exists [LLVM-PM].

Bit sets¶

BitVector is a dense bit array: one bit per possible element, with word-parallel union and intersection. It is the representation of choice for dataflow sets (Ch 14). SparseBitVector stores only the non-zero 128-bit chunks in a sorted list, for sparse sets over huge universes (points-to sets, Ch 19).

Pointer packing¶

Heap objects are aligned, so the low bits of their addresses are always zero. PointerIntPair<T *, k, I> stores a $k$-bit integer there, and PointerUnion<T1 *, T2 *, …> stores a type tag there. One word does the job of two [LLVM-PM].

APInt and APFloat¶

Constants in IR have arbitrary width (i1, i7, i128, i4096) and follow IEEE floating-point semantics exactly, whatever the host. APInt implements two's-complement arithmetic modulo $2^w$, with signed and unsigned operations kept separate. APFloat implements IEEE 754 formats (and a few others) in software, with explicit rounding modes [LLVM-APInt, IEEE754].

2. Definitions and algorithms¶

SmallVector¶

Definition 10.6.1 (SmallVector)

A SmallVector<T, N> has a size $s$, a capacity $c \ge s$ and a buffer pointer $\beta$. Initially $\beta$ points to the inline storage of $N$ elements, and $c = N$. SmallVectorImpl<T> is the base class holding $(\beta, s, c)$ without $N$. Growth to hold $m > c$ elements allocates a heap buffer of capacity

\[ c' = \max(2c + 1,\ m) \]

(getNewCapacity in llvm/lib/Support/SmallVector.cpp), moves the $s$ elements, frees the old buffer if it was on the heap, and sets $\beta$ to the new one.

Algorithm 10.6.2 (push_back with geometric growth)

Input: a SmallVector $(\beta, s, c)$ and an element $x$.
Output: $x$ appended.
Precondition: $x$ does not refer into the vector (or the implementation copies it first).
Postcondition: $s' = s + 1$, and the elements are the old ones followed by $x$.
Invariant: $s \le c$; $\beta$ is the inline storage iff no growth has happened since the last clear/shrink.

function PushBack(V, x):
    if V.s = V.c:
        Grow(V, V.s + 1)          # c ← max(2c+1, s+1); move s elements; invalidates all pointers
    construct x at V.β[V.s]
    V.s ← V.s + 1

SmallVector's sizes and growth sequence

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 smallvec.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o smallvec && ./smallvec

Output (complete):

sizeof(SmallVector<int, 0>) = 16
sizeof(SmallVector<int, 8>) = 48
sizeof(std::vector<int>)    = 24
push_back# size capacity storage
  1  1  4  inline
  5  5  9  heap
  10  10  19  heap
  20  20  39  heap
  40  40  79  heap
sum via SmallVectorImpl: 820

What to notice: capacities 4 → 9 → 19 → 39 → 79 are $c' = 2c + 1$ (Definition 10.6.1). The header is 16 bytes (a pointer and two 32-bit counters), smaller than std::vector's 24, and N = 8 adds 32 inline bytes. The first 4 pushes allocate nothing. total(SmallVectorImpl<int> &) accepts the vector whatever its $N$.

DenseMap¶

Definition 10.6.3 (Open-addressing table, load factor, probe sequence)

A table has $B = 2^b$ buckets, each used (holding a key–value pair) or empty. A hash $h(k)$ gives the home bucket $h(k) \bmod B$. A probe sequence is a map $\pi_k : \{0, 1, \dots\} \to \{0, \dots, B - 1\}$ with $\pi_k(0) = $ home. The load factor is $\alpha = n / B$ for $n$ used buckets. DenseMap grows (doubles $B$, reinserting everything) before an insertion would make $4(n+1) \ge 3B$, so after every insertion $\alpha < 3/4$. The first allocation has 64 buckets; SmallDenseMap<K, V, N> starts with $N$ inline buckets.

LLVM 23: linear probing, $\pi_k(i) = (\mathrm{home} + i) \bmod B$, and a bitmap of used buckets.
LLVM ≤ 22: quadratic (triangular) probing, $\pi_k(i) = (\mathrm{home} + i(i+1)/2) \bmod B$, with two reserved key values from DenseMapInfo, getEmptyKey() and getTombstoneKey().

Definition 10.6.4 (DenseMapInfo)

DenseMapInfo<K> provides getHashValue(const K &) → unsigned and isEqual(a, b). Pre-23 it also provided the two reserved keys, which no real key may equal. LLVM 23 hashes integers of at most 32 bits (and signed wider ones) as $k \cdot 37 \bmod 2^{32}$, and pointers and unsigned integers wider than 32 bits with a multiply–xorshift mixer (densemap::detail::mix, from splitmix64). Pairs are combined through the same mixer.

Algorithm 10.6.5 (LLVM 23 DenseMap: lookup, insert, erase)

Input: a table (Definition 10.6.3, linear probing) and a key $k$.
Output: the bucket of $k$, or $k$ inserted, or $k$ erased.
Precondition: the cluster invariant (Theorem 10.6.14) holds.
Postcondition: the cluster invariant holds, and the multiset of stored pairs changed as requested.
Invariant (erase loop): the hole $I$ is empty, and every key between the start of the cluster and $I$ can reach its bucket from home without crossing $I$.

function Find(T, k):
    j ← home(k)
    while used(j):
        if key(j) = k: return j
        j ← (j + 1) mod B
    return none                                   # an empty bucket ends every search
function Insert(T, k, v):
    if Find(T, k) ≠ none: return
    if 4(n + 1) ≥ 3B: Grow(T, 2B)                 # rehash every key into 2B buckets
    j ← home(k); while used(j): j ← (j + 1) mod B
    store (k, v) in j; used(j) ← true; n ← n + 1
function Erase(T, k):                             # Knuth, Algorithm R
    I ← Find(T, k); if I = none: return
    destroy bucket I; n ← n − 1                   # I is now a hole
    J ← I
    loop:
        J ← (J + 1) mod B
        if not used(J): break                     # end of the cluster
        H ← home(key(J))
        if (I − H) mod B < (J − H) mod B:         # the hole lies on key(J)'s probe path
            move bucket J into I; I ← J           # the hole moves forward
    used(I) ← false

DenseMap in LLVM 23: erase moves other entries; growth moves everything

Reproduce (clang 23.1.2 with compiler-rt 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 -g -fsanitize=address densemap.cpp \
  $(llvm-config --ldflags --libs) -Wl,-rpath,$(llvm-config --libdir) -o densemap
./densemap          # SmallDenseMap<unsigned, unsigned, 8>: keys 0, 8 (home 0) and 3 (home 7)
./densemap grow     # unsigned &R = M[1]; insert 98 more keys; R = 5

Output (the second run is abridged after the first stack frames):

after inserts: 0->100 8->108 3->103
after erase(0): 8->108 3->103
old pointer still at key 8's value? 0

==ERROR: AddressSanitizer: heap-use-after-free on address 0x7ca57b1e04ac …
WRITE of size 4 at 0x7ca57b1e04ac thread T0
    #0 … in main …/examples/densemap.cpp:15:7

What to notice: iteration visits buckets in order, so key 8 sat in bucket 1 (its home 0 was taken by key 0). erase(0) moved it back to bucket 0 (Algorithm 10.6.5), so a pointer taken to key 8's value before the erase no longer points at it, and no sanitizer notices, because bucket 1 is still valid memory. The second run is the classic growth bug: a reference into the bucket array written after the table was reallocated.

SetVector¶

Definition 10.6.6 (SetVector)

SetVector<T, Vector, Set> is a pair $(V, S)$ of a sequence and a set. Invariant: $S = \mathrm{elems}(V)$ and $V$ has no duplicates. insert(x): if $x \notin S$, append $x$ to $V$ and add it to $S$. Iteration is over $V$. remove(x) erases from both, which is $O(\lvert V \rvert)$ in $V$. Small SetVectors (SmallSetVector) search the vector linearly while it is small and build the set only past a threshold.

Hash order changes between runs; insertion order does not

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64 with ASLR):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 setvec.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o setvec
for i in 1 2 3; do ./setvec; done

Output (complete):

DenseSet order: 5 2 1 0 3 4 
SetVector order: 3 1 4 5 0 2
SetVector size 6, pop_back_val -> 2
DenseSet order: 2 5 1 3 4 0 
SetVector order: 3 1 4 5 0 2
SetVector size 6, pop_back_val -> 2
DenseSet order: 2 5 1 3 4 0 
SetVector order: 3 1 4 5 0 2
SetVector size 6, pop_back_val -> 2

What to notice: the same insertions 3 1 4 1 5 0 2 into a DenseSet<Block *> iterate in an order that depends on the heap addresses (first run vs the next two). The SetVector always iterates 3 1 4 5 0 2: insertion order, with the duplicate 1 dropped (Theorem 10.6.17).

StringRef, ArrayRef and Twine¶

Definition 10.6.7 (View, validity)

A view is a pair $(p, \ell)$ denoting the memory $[p, p + \ell)$, without owning it. A view is valid at time $t$ if that memory belongs to a live object at $t$ and has not been reallocated. StringRef and ArrayRef<T> are views. A Twine is a node with up to two children. Each child is empty, a C string, a std::string *, a (pointer, length) leaf, a number, a character, or a pointer to another Twine. Twine::concat stores a pointer to an operand Twine unless that operand is unary (a single leaf), in which case it copies the leaf (llvm/include/llvm/ADT/Twine.h).

Algorithm 10.6.8 (Rendering a Twine)

Input: a Twine $T$ and an output buffer.
Output: the concatenation of $T$'s leaves, left to right.
Precondition: every node and leaf reachable from $T$ is alive (Theorem 10.6.18).
Postcondition: the buffer holds the string; str() returns an owning std::string, and toStringRef(Buf) returns a view into Buf (or into a single leaf).
Invariant: children are printed before the right sibling (in-order traversal).

function Print(T, out):
    PrintChild(T.lhs, out); PrintChild(T.rhs, out)
function PrintChild(c, out):
    case kind(c):
        TwineKind: Print(*c.twine, out)        # follows a pointer: must be alive
        CString, PtrAndLength, StdString: append the characters
        Dec*, Char: format the number or character
        Empty: nothing

Dangling StringRef and Twine under AddressSanitizer

Reproduce (clang 23.1.2 with compiler-rt 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 -g -O0 -fsanitize=address dangle.cpp \
  $(llvm-config --ldflags --libs) -Wl,-rpath,$(llvm-config --libdir) -o dangle
./dangle ok; ./dangle stringref; ./dangle twine

Output (abridged: stacks after the frame in main, and the shadow-byte dumps, are cut; paths shortened):

dangle.cpp:11:22: warning: object backing the pointer will be destroyed at the end of the full-expression [-Wdangling-gsl]
   11 |     StringRef Name = makeName(7);            // the std::string temporary dies at the ';'
block.42
==ERROR: AddressSanitizer: heap-use-after-free on address 0x7b30019e04c0 …
READ of size 29 at 0x7b30019e04c0 thread T0
    #1 … in llvm::raw_ostream::operator<<(llvm::StringRef) …/include/llvm/Support/raw_ostream.h:234:7
    #2 … in main …/examples/dangle.cpp:12:34
0x7b30019e04c0 is located 0 bytes inside of 31-byte region [0x7b30019e04c0,0x7b30019e04df)
==ERROR: AddressSanitizer: stack-use-after-scope on address 0x7be31fef0180 …
READ of size 6 at 0x7be31fef0180 thread T0
    #3 … in llvm::Twine::str[abi:cxx11]() const (…/libLLVM.so.23.1+0xb5f574)
    #4 … in main …/examples/dangle.cpp:16:17
    [368, 400) 'ref.tmp' (line 15) <== Memory access at offset 384 is inside this variable

What to notice:

Warning (compile time): clang warns about the StringRef bound to a temporary std::string (-Wdangling-gsl).
ok: a Twine used inside one full-expression prints block.42.
stringref: reads the freed 31-byte string buffer, all 29 characters of it.
twine: const Twine T = Base + "." + Twine(42) stored a pointer to the temporary std::string "block.", created by std::string's own operator+ at line 15 (6 bytes read). T.str() on line 16 renders a leaf whose object died at the end of line 15 (Theorem 10.6.18).

StringMap¶

Definition 10.6.9 (StringMap)

A StringMap<V> is an open-addressing table of pointers to entries. Each entry is allocated as [StringMapEntry<V> header (key length, value)][key bytes][\0] in one block, and the table also stores each key's full hash to skip most string comparisons. Growing the table reallocates the pointer array only; entries are never moved.

StringMap keys live right after their entry

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 misc.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o misc && ./misc stringmap

Output (complete):

add=3 (key bytes start at entry+16)
mul=1 (key bytes start at entry+16)
load=1 (key bytes start at entry+16)
sizeof(StringMapEntry<int>)=16

What to notice: the key bytes start immediately after the 16-byte entry (Definition 10.6.9): one allocation per entry, key included. Because the table holds pointers, rehashing never moves an entry, which is why a StringRef to a key survives insertions (Proposition 10.6.19).

Bit sets¶

Definition 10.6.10 (BitVector, SparseBitVector)

A BitVector over a universe $\{0, \dots, U-1\}$ stores $\lceil U/64 \rceil$ 64-bit words. Bit $i$ is bit $i \bmod 64$ of word $\lfloor i/64 \rfloor$. A SparseBitVector<E> stores a list, sorted by index, of elements $(q, w)$ where $w$ is an $E$-bit mask covering bits $[qE, (q+1)E)$ and $w \ne 0$, plus a cursor to the last element accessed.

Dense vs sparse bit sets

Reproduce (same binary as above):

cd chapters/10-llvm-cpp-api/examples && ./misc bits

Output (complete):

BitVector: size=1000 count=3 first=3 next(4)=64 heap bytes=128
SparseBitVector: count=3 elements: 3 64 999
BV & {64,500}: count=1 first=64

What to notice: the dense set pays $\lceil 1000/64 \rceil = 16$ words (128 bytes) for three members. The sparse one holds two 128-bit elements ($\lfloor 3/128 \rfloor = \lfloor 64/128 \rfloor = 0$ and $\lfloor 999/128 \rfloor = 7$). The intersection is a word-wise AND (Definition 10.6.10).

Pointer packing¶

Definition 10.6.11 (Free low bits, PointerIntPair, PointerUnion)

If $\mathrm{alignof}(T) = 2^{a}$, every T * to a live object has its $a$ low bits zero. PointerLikeTypeTraits<T *>::NumLowBitsAvailable is $a$ (for known-complete types). PointerIntPair<T *, k, I> requires $k \le a$ and stores $\mathit{ptr} \mid (i \ll (a - k))$ for a $k$-bit integer $i$ (the highest of the free bits), masking on access. PointerUnion<T_1 *, \dots, T_m *> stores a $\lceil \log_2 m \rceil$-bit tag the same way and requires every $T_j$ to have enough free bits.

Two words in one

Reproduce (same binary):

cd chapters/10-llvm-cpp-api/examples && ./misc pointers

Output (complete):

sizeof(PointerIntPair<Node*,2,unsigned>)=8 ptr ok=1 int=3
sizeof(PointerUnion<Node*,Leaf*>)=8 isa<Leaf*>=1 value=2

What to notice: Node and Leaf are declared alignas(8), which gives 3 free bits. A 2-bit integer and a 1-bit tag both fit in the pointer's 8 bytes, and isa<Leaf *>/cast<Leaf *> work on the union through the CastInfo machinery of Lesson 10.4.

APInt and APFloat¶

Definition 10.6.12 (APInt semantics)

An APInt of width $w$ is a bit pattern $a \in \{0, 1\}^w$, read as $\mathrm{u}(a) = \sum_i a_i 2^i \in [0, 2^w)$ or as $\mathrm{s}(a) = \mathrm{u}(a) - a_{w-1} 2^w \in [-2^{w-1}, 2^{w-1})$. add, sub, mul and shl compute the result modulo $2^w$. udiv/urem use $\mathrm{u}$, and sdiv/srem use $\mathrm{s}$ (truncating toward zero). lshr shifts in zeros and ashr copies bit $w-1$. The *_ov variants (uadd_ov, sadd_ov, umul_ov, …) also report whether the mathematical result was out of range. Widths up to 64 use one inline word; wider values use a heap array. An APFloat holds a value of a given IEEE 754 (or other) format, and every operation takes a rounding mode and returns a status (opInexact, opOverflow, …) [IEEE754, LLVM-APInt].

APInt and APFloat compute what the target would

Reproduce (same binary):

cd chapters/10-llvm-cpp-api/examples && ./misc apint

Output (complete):

i8: 200 + 100 = 44 (unsigned overflow=1)
i8 200 as signed = -56, udiv 200/7 = 28, sdiv 200/7 = -8
i128 2^100+1 = 1267650600228229401496703205377, popcount=2
double 0.1+0.2 = 0.30000000000000004
half "0.1" = 9.9976E-2 = 0.0999755859375 as double

What to notice:

Wrap-around: $300 \bmod 256 = 44$, with the unsigned overflow reported.
Two readings of one pattern: the bits of 200 read signed are $-56$. Unsigned division gives $\lfloor 200/7 \rfloor = 28$, and signed division gives $-56/7 = -8$ (Definition 10.6.12).
Wide integers: i128 arithmetic is exact at any width.
Host-independent floating point: the familiar IEEE double sum $0.1 + 0.2$, and half's nearest value to 0.1, computed in software, independently of the host's FP unit.

3. Worked example¶

SmallVector¶

SmallVector<int, 4> receiving 40 push_backs (Algorithm 10.6.2). Growth happens at push 5 (4 → 9, moving 4 elements), push 10 (9 → 19, moving 9), push 20 (19 → 39, moving 19) and push 40 (39 → 79, moving 39). That is $4 + 9 + 19 + 39 = 71$ moves for 40 pushes, below the bound $2n = 80$ of Theorem 10.6.13.

DenseMap¶

Operations insert 58, insert 52, insert 1, insert 20, insert 17, erase 52, insert 41 on 8 buckets, with $\mathrm{home}(k) = 5k \bmod 8$. The homes are 2, 4, 5, 4, 5, 5 for $k = 58, 52, 1, 20, 17, 41$.

LLVM 23 (Algorithm 10.6.5):

step	operation	probes / moves	buckets 0..7
1	insert 58	home 2; probes [2]	`- - 58 - - - - -`
2	insert 52	home 4; probes [4]	`- - 58 - 52 - - -`
3	insert 1	home 5; probes [5]	`- - 58 - 52 1 - -`
4	insert 20	home 4; probes [4, 5, 6]	`- - 58 - 52 1 20 -`
5	insert 17	home 5; probes [5, 6, 7]	`- - 58 - 52 1 20 17`
6	erase 52	hole 4; J=5: home(1)=5, (4−5) mod 8 = 7 ≥ (5−5)=0, stays; J=6: home(20)=4, 0 < 2, move 20: 6→4, hole 6; J=7: home(17)=5, (6−5)=1 < (7−5)=2, move 17: 7→6, hole 7; J=0 empty: stop	`- - 58 - 20 1 17 -`
7	insert 41	home 5; probes [5, 6, 7]	`- - 58 - 20 1 17 41`

LLVM 22 (quadratic probing, tombstones), same operations:

step	operation	probes	buckets 0..7
1–3	insert 58, 52, 1	homes	`- - 58 - 52 1 - -`
4	insert 20	home 4; 4, 4+1=5, 5+2=7	`- - 58 - 52 1 - 20`
5	insert 17	home 5; 5, 6	`- - 58 - 52 1 17 20`
6	erase 52	[4]: tombstone	`- - 58 - T 1 17 20`
7	insert 41	home 5; 5, 6, 6+2=0 (empty, and no tombstone was seen)	`41 - 58 - T 1 17 20`

The designs disagree on every position that involved a collision. LLVM 23's table stays compact after the erase, while LLVM 22's keeps the tombstone until a rehash.

SetVector¶

Inserting 3 1 4 1 5 0 2 (Definition 10.6.6): $V$ goes $\langle 3 \rangle, \langle 3, 1 \rangle, \langle 3, 1, 4 \rangle$; the second 1 is found in $S$ and skipped; then $\langle 3, 1, 4, 5 \rangle, \langle 3,1,4,5,0 \rangle, \langle 3,1,4,5,0,2 \rangle$. pop_back_val returns 2 (the box's output).

StringRef, ArrayRef and Twine¶

Twine T = A + "." + "exit" with StringRef A = "block":

A + "." is operator+(StringRef, const char *), which builds a temporary Twine $X$ with leaves (ptr/len of "block", cstring ".").
X + "exit" converts "exit" to a unary Twine $Y$ and calls X.concat(Y). $X$ is binary, so the new node stores &X. $Y$ is unary, so its leaf is copied.
At the ;, $X$ is destroyed and T.lhs points to a dead object.

With only two pieces (Twine T = A + ".exit") the single node has two value leaves and nothing dangles, but one more + breaks it. That is why the rule is never to store a Twine.

StringMap¶

Inserting add, mul, add, load, add into a StringMap<int> creates three entries: add = 3, mul = 1, load = 1. Each is one allocation of $16 + \lvert\mathit{key}\rvert + 1$ bytes. A later insertion that grows the pointer table rehashes the three pointers, and the entries stay where they are.

Bit sets¶

The set $\{3, 64, 999\}$: BitVector(1000) sets word 0 bit 3, word 1 bit 0 and word 15 bit 39. SparseBitVector<128> creates element $q = 0$ with bits 3 and 64 set, and element $q = 7$ with bit $999 - 896 = 103$ set.

Pointer packing¶

PointerIntPair<Node *, 2, unsigned>(&N, 3) with alignof(Node) = 8 ($a = 3$): the stored word is $\mathit{addr}(N) \mid (3 \ll 1)$, since LLVM places the integer in the highest of the free bits. Reading masks with $\sim 7$ for the pointer and shifts right by 1 (then masks 2 bits) for the integer.

APInt and APFloat¶

In i8, $200 = 11001000_2$. $\mathrm{s} = 200 - 256 = -56$. $200 + 100 = 300 = 100101100_2$, truncated to 8 bits $= 00101100_2 = 44$, and the carry out means uadd_ov reports true. sdiv(200, 7) $= -56 / 7 = -8$ $= 11111000_2$, which reads as 248 unsigned.

Try it

./course drill densemap-probe --seed 5 --difficulty hard for the LLVM 22 table, --difficulty medium for LLVM 23; ./course drill adt-costs for capacities, bucket counts and APInt; ./course drill view-lifetime for Twine and StringRef lifetimes.

4. Invariants and correctness¶

SmallVector¶

Theorem 10.6.13 (Amortized O(1) push_back)

Starting from an empty SmallVector<T, N>, any sequence of $n$ push_back calls moves fewer than $2n$ elements in total during growth. So push_back is amortized $O(1)$.

Proof

Growths happen exactly when $s = c$ (Algorithm 10.6.2). With only single pushes the new capacity is $2c + 1$ (it is always at least $s + 1$), so the capacities are $c_0 = N$ and $c_{j+1} = 2c_j + 1$, that is $c_j = (N + 1)2^{j} - 1$. Growth $j$ moves $c_j$ elements (the full buffer). If growths $0, \dots, J$ occur, the last one was triggered by push number $c_J + 1 \le n$. The total number of moves is

\[ \sum_{j=0}^{J} c_j = (N+1)(2^{J+1} - 1) - (J + 1) < 2\big((N+1)2^{J} - 1\big) + 2 = 2 c_J + 2 \le 2n. \]

The last step uses $c_J + 1 \le n$. Each push also does $O(1)$ other work, so $n$ pushes cost $O(n)$ in total.

Invalidation: any growth moves every element, so every pointer, reference and iterator into the vector is invalidated. The iterator-invalidation drill's push_back-in-a-range-for case follows directly.

DenseMap¶

Theorem 10.6.14 (Linear probing's cluster invariant is kept by Algorithm R)

Call a linear-probing table well formed if every stored key $k$ in bucket $j$ has all buckets $\mathrm{home}(k), \mathrm{home}(k)+1, \dots, j$ (mod $B$) used. Then Find returns $k$'s bucket exactly when $k$ is stored, and Insert and Erase of Algorithm 10.6.5 preserve well-formedness.

Proof

Find. If $k$ is stored in $j$, the probe from $\mathrm{home}(k)$ meets only used buckets up to $j$ (well-formedness) and stops there. If $k$ is not stored, the probe stops at an empty bucket, which exists because $\alpha < 1$. Insert places $k$ in the first empty bucket after $\mathrm{home}(k)$, so every bucket from $\mathrm{home}(k)$ to its slot is used. Other keys only gain used buckets, so their conditions still hold. Erase. Emptying bucket $I$ can break the condition only for keys $k$ in buckets $J$ after $I$ in the same cluster whose path from $\mathrm{home}(k)$ to $J$ crosses $I$. That path crosses $I$ iff $I$ lies cyclically in $[\mathrm{home}(k), J)$, i.e. $(I - H) \bmod B < (J - H) \bmod B$ with $H = \mathrm{home}(k)$, which is exactly the test in the algorithm. Such a key is moved into $I$. Its new bucket is on its path, and every bucket from $H$ to $I$ is used, because they were used before and none of them was emptied. Then $J$ becomes the hole, and the same argument repeats for later keys. Keys whose path does not cross the current hole are left in place and remain valid. The loop ends at the first empty bucket, beyond which no key's path crosses the hole (a path would have to pass that empty bucket). So the invariant holds at the end.

Lemma 10.6.15 (Triangular probing visits every bucket)

For $B = 2^{b}$, the offsets $T_i = i(i+1)/2 \bmod B$ for $i = 0, \dots, B-1$ are pairwise distinct. So LLVM 22's probe sequence reaches every bucket, and an insertion always finds an empty or tombstone bucket when $n < B$.

Proof

Suppose $T_i \equiv T_j \pmod{2^b}$ with $0 \le j < i < 2^b$. Then $2^{b+1}$ divides $i(i+1) - j(j+1) = (i - j)(i + j + 1)$. The factors $i - j$ and $i + j + 1$ have opposite parity (their sum $2i + 1$ is odd), so one of them is odd and $2^{b+1}$ divides the other. But $0 < i - j < 2^b$ and $0 < i + j + 1 < 2^{b+1}$, a contradiction.

Proposition 10.6.16 (Expected probes under the load cap)

Under the uniform-hashing assumption, linear probing at load factor $\alpha$ needs about $\frac{1}{2}(1 + \frac{1}{1 - \alpha})$ probes for a successful search and $\frac{1}{2}(1 + \frac{1}{(1 - \alpha)^2})$ for an unsuccessful one. With DenseMap's cap $\alpha < 3/4$ these are below $2.5$ and $8.5$.

Proof sketch (full proof: [TAOCP3, §6.4, Theorem K])

Knuth counts, over all hash sequences, the expected length of the run of used buckets that a new key's home falls into. That gives the unsuccessful-search cost as $\frac{1}{2}(1 + (1 - \alpha)^{-2})$ asymptotically. The successful-search cost is the average of the unsuccessful costs at the times each key was inserted, $\frac{1}{\alpha}\int_0^\alpha \frac{1}{2}(1 + (1-x)^{-2})\,dx = \frac{1}{2}(1 + \frac{1}{1-\alpha})$. Substituting $\alpha = 3/4$ gives $2.5$ and $8.5$. For quadratic probing, [CLRS4, §11.4] shows that with uniform probing the unsuccessful bound improves to $1/(1 - \alpha) = 4$ at $\alpha = 3/4$.

The price of LLVM 23's design is visible in the real-world box: erase moves entries, so references to other entries are invalidated by erasure. In the tombstone design they were not, and only growth invalidated them. DenseMap::remove_if is the documented way to delete while scanning.

SetVector¶

Theorem 10.6.17 (Deterministic iteration)

The iteration order of a SetVector is determined by the sequence of insert/remove calls alone. It is independent of the hash function and of the values' addresses.

Proof

Iteration follows $V$ (Definition 10.6.6). By induction on the operations: insert(x) appends $x$ to $V$ iff $x \notin S$, and $S = \mathrm{elems}(V)$ by the invariant, so the decision depends only on which elements were inserted before, not on hash order. remove(x) deletes $x$ from $V$ at its position. Hence $V$ is a function of the call sequence, and the invariant $S = \mathrm{elems}(V)$ is maintained by updating both together.

StringRef, ArrayRef and Twine¶

Theorem 10.6.18 (When views and Twines are safe)

(a) A view $(p, \ell)$ obtained from an object $o$ is valid until $o$ is destroyed or $o$ reallocates $[p, p+\ell)$. (b) A Twine built in a full-expression and consumed (rendered, or passed to a function that renders or copies it) within the same full-expression never reads dead memory, provided its leaves' objects outlive that expression. (c) A Twine stored past the end of its full-expression is safe only if it is unary, or has two leaves stored by value whose objects are alive. Any node that concat stored as a pointer refers to a temporary that has died.

Proof

(a) is the definition of validity (Definition 10.6.7). (b) C++ destroys temporaries at the end of the full-expression that created them ([class.temporary]). Every intermediate Twine node in a + b + c is such a temporary, and so is every temporary std::string a leaf points to. Consumption within the expression happens before any of them is destroyed. (c) By Definition 10.6.7, concat stores &operand for a non-unary operand. That operand is an intermediate result of the same expression, hence a temporary destroyed at the ;, and a later render dereferences it. Leaves stored by value (C strings, (pointer, length), numbers) hold no pointer to the temporary node itself, so a node consisting only of them stays valid as long as the objects the pointers refer to are alive. The box's two-leaf example stores pointers to string literals, which live forever.

StringMap¶

Proposition 10.6.19 (Keys never move)

A StringRef to an entry's key (getKey()) remains valid across any insertions and across erasure of other keys. It is invalidated only by erasing that entry or destroying the map.

Proof

The table stores pointers to separately allocated entries (Definition 10.6.9). Rehashing copies the pointers into a new table and does not touch the entries. Erasing another key frees only that key's entry. The key bytes are part of their own entry's allocation, so they live exactly as long as the entry.

Bit sets¶

The correctness of a bit set is that the bit-to-word mapping of Definition 10.6.10 is a bijection between elements and (word, bit) positions (dense), or between elements and (element index, bit) pairs with only non-zero elements stored (sparse). Union and intersection are then word-wise OR and AND on corresponding words, because both mappings are position-preserving.

Pointer packing¶

Lemma 10.6.20 (Alignment gives zero bits)

If T has alignment $2^{a}$, every address of a T object is divisible by $2^{a}$, so its $a$ low bits are zero. Therefore, for $k \le a$, $\mathit{ptr} \mid (i \ll (a - k))$ with $0 \le i < 2^{k}$ is decoded exactly by masking: $\mathit{ptr} = w \mathbin{\&} {\sim}(2^{a} - 1)$ and $i = (w \gg (a - k)) \mathbin{\&} (2^{k} - 1)$.

Proof

Divisibility by the alignment is the meaning of alignment in C++ (an object of type T occupies an address that is a multiple of alignof(T)). The low $a$ bits of $\mathit{ptr}$ are zero, and $i \ll (a - k) < 2^{a}$ occupies only those bits, so OR-ing does not disturb the pointer bits, and the two masks recover each part.

APInt and APFloat¶

Theorem 10.6.21 (One adder for signed and unsigned)

For bit patterns $a, b$ of width $w$: $\mathrm{u}(a + b) = (\mathrm{u}(a) + \mathrm{u}(b)) \bmod 2^{w}$ and $\mathrm{s}(a + b) \equiv \mathrm{s}(a) + \mathrm{s}(b) \pmod{2^{w}}$, and the same holds for $-$ and $\times$. Division and comparison are not sign-agnostic: udiv and sdiv (and ult and slt) differ on patterns with the top bit set.

Proof

$\mathrm{s}(a) \equiv \mathrm{u}(a) \pmod{2^w}$ because they differ by $a_{w-1} 2^w$. Reduction modulo $2^w$ is a ring homomorphism $\mathbb{Z} \to \mathbb{Z}/2^w$, so sums, differences and products of congruent values are congruent. The single bit-level operation "add modulo $2^w$" therefore computes both readings' results. For division, $200 = 11001000_2$ gives $\mathrm{udiv}(200, 7) = 28$ but $\mathrm{sdiv}(200, 7) = -8$ ($248$ unsigned), and $28 \not\equiv 248$ — the box's output.

For APFloat, correctness means correct rounding: each basic operation returns the representable value that the rounding mode selects from the exact real result, as IEEE 754 requires [IEEE754]. APFloat computes the exact result with extra precision in software and then rounds, which is what makes constant folding host-independent.

5. Complexity¶

Variables: $n$ = number of elements, $N$ = inline capacity, $B$ = buckets, $\alpha = n/B$, $\lvert k \rvert$ = key length, $U$ = universe size, $E = 128$, $w$ = bit width.

Technique	Main operations	Time	Space	Invalidated by
SmallVector	`push_back`, index, iterate	amortized $O(1)$ (Theorem 10.6.13); $O(1)$	$N$ inline elements + 16-byte header; heap $\le 2n + 1$	growth (all), insert/erase (at and after the position)
DenseMap (LLVM 23)	find, insert, erase	expected $O(1)$: $< 2.5$ / $< 8.5$ probes (Proposition 10.6.16); erase $O(\text{cluster})$	$B \cdot \mathrm{sizeof}(K, V) + B/8$ bytes; $B \le 8n/3$ after growth	insert (if it grows): all; erase: all (entries move)
DenseMap (LLVM 22)	same	expected $O(1)$; tombstones lengthen probes until rehash	$B \cdot \mathrm{sizeof}(K, V)$, reserved keys	insert (if it grows or rehashes): all
SetVector	insert, contains; remove	$O(1)$ expected; $O(n)$	vector + set	as the underlying vector/set
StringRef / ArrayRef	construct, slice, compare	$O(1)$; compare $O(\ell)$	16 bytes	the viewed object
Twine	build; render	$O(1)$ per `+`; $O(\text{total length})$	two child slots per node, on the stack	end of the full-expression
StringMap	find, insert	expected $O(\lvert k \rvert)$ (hashing the key)	one entry allocation + a pointer per bucket	erase of that entry only
BitVector	test/set; union/intersection; count	$O(1)$; $O(U/64)$; $O(U/64)$ popcounts	$U/8$ bytes	resize
SparseBitVector	test/set; union/intersection	$O(\#\text{elements})$ (cursor makes sequential access $O(1)$)	$\approx 24 + 16$ bytes per non-zero element	—
Pointer packing	get/set	$O(1)$ (mask/shift)	one word	—
APInt / APFloat	add/mul/div at width $w$	$O(w/64)$ / $O((w/64)^2)$ / $O((w/64)^2)$	inline if $w \le 64$	—

Pathological inputs.

Bad hashes under linear probing. A custom DenseMapInfo with a poor hash, for example the identity on pointers aligned to 64 bytes, lands every key of a table with $B \le 64$ in the same few buckets. Every operation then becomes $\Theta(n)$ and a fill costs $\Theta(n^2)$. LLVM 23's pointer mixer exists precisely to spread such keys.
Tombstone build-up in the LLVM 22 design. An alternating insert/erase workload fills the table with tombstones until the "fewer than ⅛ empty" rule forces an $O(B)$ in-place rehash. LLVM 23's backward shift avoids this.
Dense bit sets over sparse data. A BitVector over $U = 10^6$ pointer IDs with 10 members pays 125 KB and $\Theta(U/64)$ per union. That is the case for SparseBitVector.

At scale: "Efficiency with Algorithms, Performance with Data Structures" [Car14] makes the case, with LLVM's own measurements, that cache misses from node-based containers dominate compiler time, and that flat, inline, open-addressing structures pay off.

SmallVector¶

SmallVector<T> with no $N$: LLVM picks $N$ so that sizeof stays at most 64 bytes (CalculateSmallVectorDefaultInlinedElements).
SmallString<N>: a SmallVector<char, N> with string helpers, the usual toStringRef buffer.
std::vector::reserve: the standard alternative when the final size is known, but it still pays one allocation.

DenseMap¶

SmallDenseMap<K, V, N>: $N$ inline buckets and no allocation while small. The drill uses it.
DenseSet; SmallPtrSet, a small unsorted array that becomes a linear-probed table with the same Algorithm R deletion, empty buckets marked by the illegal pointer $-1$ and growth at ⅔ load (llvm/include/llvm/ADT/SmallPtrSet.h, LLVM 23); MapVector, the insertion-ordered map and map analogue of SetVector.
Other designs: Swiss tables (Abseil, std::unordered_map replacements) use SIMD group probing with control bytes; robin-hood hashing bounds probe-length variance. LLVM 23's used-bit array plus Algorithm R is a simple point in this space.

SetVector¶

SmallSetVector<T, N>: linear search while small.
UniqueVector: assigns dense IDs in insertion order.

StringRef, ArrayRef and Twine¶

std::string_view / std::span: the standard equivalents. StringRef converts implicitly to and from std::string_view (StringRef.h).
MutableArrayRef, OwningArrayRef: a writable view, and an owning variant.
formatv (llvm/Support/FormatVariadic.h): type-safe formatting when a Twine is not enough.

StringMap¶

StringSet<>, and UniqueStringSaver (interning strings into a BumpPtrAllocator) for stable string storage without values.
ValueSymbolTable: a StringMap<Value *> (ValueName = StringMapEntry<Value *>) with uniquing suffixes (%x1, %x2).

Bit sets¶

SmallBitVector: up to 57 bits in the object's pointer word (on 64-bit hosts), a heap BitVector beyond.
CoalescingBitVector: intervals instead of bits, for long runs.

Pointer packing¶

PointerEmbeddedInt, PointerSumType (a tagged union of pointer-like types with user-chosen tags).
Clang's QualType: a PointerIntPair<PointerUnion<const Type *, const ExtQuals *>, FastWidth> that keeps the const, volatile and restrict qualifiers in the low bits (clang/include/clang/AST/TypeBase.h in LLVM 23).

APInt and APFloat¶

APSInt: an APInt that carries its signedness, used by Clang's constant evaluator.
DynamicAPInt (llvm/include/llvm/ADT/DynamicAPInt.h, used by MLIR's Presburger library): arbitrary-precision integers without a fixed width.
APFixedPoint: fixed-point arithmetic for Embedded-C types.

7. In real compilers¶

SmallVector¶

LLVM

llvm/include/llvm/ADT/SmallVector.h (SmallVectorImpl, SmallVectorTemplateBase::grow), llvm/lib/Support/SmallVector.cpp (getNewCapacity: 2 * OldCapacity + 1) [LLVM-SmallVector].

GCC gcc/vec.h has auto_vec<T, N>, the same small-size idea. rustc uses the smallvec crate (SmallVec<[T; N]>) throughout.

Find where LLVM does it. In SmallVector.cpp, find getNewCapacity. Question: what is the new capacity of a full SmallVector with capacity 9 after one push_back? (Quiz smallvector-growth.)

DenseMap¶

LLVM

llvm/include/llvm/ADT/DenseMap.h at llvmorg-23.1.2: the file comment ("linear-probing open addressing with tombstone-free deletion (Knuth TAOCP 6.4 Algorithm R) … a 0.75 maximum load factor. No sentinel key"), LookupBucketFor, eraseFromFilledBucket, remove_if; llvm/include/llvm/ADT/DenseMapInfo.h (densemap::detail::mix, the k * 37 integer hash). The earlier design: the same file at llvmorg-22.1.0 (ProbeAmt, getTombstoneKey) [LLVM-DenseMap, LLVM-DenseMap22].

Abseil flat_hash_map (Swiss tables) and rustc's FxHashMap (hashbrown, also a Swiss table) are the open-addressing tables of other large C++ and Rust code bases.

Find where LLVM does it. In LLVM 23's DenseMap.h, find eraseFromFilledBucket. Question: which condition decides whether the key in bucket J is moved into the hole I? (Quiz llvm-where-algorithm-r.)

SetVector¶

LLVM

llvm/include/llvm/ADT/SetVector.h (insert, remove, the small-size linear search), used for deterministic worklists in many passes, e.g. SetVector<BasicBlock *> in loop and SROA utilities [LLVM-PM].

GCC uses auto_bitmap and hash_set with explicit sorting where output order matters. rustc uses FxIndexSet (the indexmap crate), which is the same "set with insertion order" design.

StringRef, ArrayRef and Twine¶

LLVM

llvm/include/llvm/ADT/StringRef.h, llvm/include/llvm/ADT/ArrayRef.h, llvm/include/llvm/ADT/Twine.h (Twine::concat, the TwineKind child, the "never store a Twine" warning in the class comment) [LLVM-Twine].

Clang warns (-Wdangling-gsl, -Wdangling) because StringRef is annotated [[gsl::Pointer]] (LLVM_GSL_POINTER in StringRef.h), which is the source of the warning in the box.

StringMap¶

LLVM

llvm/include/llvm/ADT/StringMap.h, llvm/include/llvm/ADT/StringMapEntry.h (StringMapEntry::create allocates key and entry together), llvm/lib/Support/StringMap.cpp (LookupBucketFor with the stored full hashes) [LLVM-PM].

GCC's preprocessor interns identifiers in its own string hash table (libcpp/symtab.cc, ht_lookup), and Clang in IdentifierTable (llvm::StringMap<IdentifierInfo *, llvm::BumpPtrAllocator> in clang/include/clang/Basic/IdentifierTable.h).

Bit sets¶

LLVM

llvm/include/llvm/ADT/BitVector.h, llvm/include/llvm/ADT/SparseBitVector.h (SparseBitVectorElement, the cursor CurrElementIter), llvm/include/llvm/ADT/SmallBitVector.h [LLVM-PM].

GCC's bitmap (gcc/bitmap.h) is a sparse linked-list-of-chunks bitmap, the analogue of SparseBitVector, and sbitmap the dense one.

Pointer packing¶

LLVM

llvm/include/llvm/ADT/PointerIntPair.h, llvm/include/llvm/ADT/PointerUnion.h, llvm/include/llvm/Support/PointerLikeTypeTraits.h (NumLowBitsAvailable) [LLVM-PM].

Clang QualType (clang/include/clang/AST/TypeBase.h in LLVM 23): the fast qualifiers packed into the low bits of a PointerUnion<const Type *, const ExtQuals *>, itself a packed pointer.

APInt and APFloat¶

LLVM

llvm/include/llvm/ADT/APInt.h (uadd_ov, sdiv, ashr, the inline/heap U union), llvm/include/llvm/ADT/APFloat.h (IEEEhalf(), add(…, roundingMode), opStatus), used by the constant folder llvm/lib/Analysis/ConstantFolding.cpp [LLVM-APInt].

GCC wide-int.h (wide_int, widest_int) and real.cc: the same two jobs.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
SmallVector	a vector; inline up to $N$	amortized $O(1)$, no allocation while $\le N$	growth invalidates everything	drop-in for `std::vector`	operand lists, worklists, temporary buffers
DenseMap	hash map for small, trivially copyable keys	expected $O(1)$; $< 2.5$ probes on success at $\alpha < 3/4$	LLVM 23: erase moves entries; iteration order is unspecified	provide `DenseMapInfo` for new key types	pointer-keyed side tables everywhere
SetVector	set with insertion-order iteration	$O(1)$ expected insert/find, $O(n)$ remove	deterministic output (Theorem 10.6.17)	none	worklists, ordered uniquing
StringRef/ArrayRef/Twine	free string/array parameters; lazy concatenation	$O(1)$ to pass	dangling views are silent without ASan	discipline, not code	API parameters, names
StringMap	string-keyed map with stable keys	expected $O(\lvert k \rvert)$	keys stable (Proposition 10.6.19)	none	symbol tables, name interning
Bit sets	exact sets over integer universes	dense: $O(U/64)$ ops; sparse: $O(\#\text{elements})$	—	none	dataflow (dense), points-to (sparse)
Pointer packing	a pointer plus $\le a$ bits in one word	$O(1)$	wrong alignment assumptions assert	a traits specialization for new types	tagged pointers, `QualType`, `PointerUnion` operands
APInt/APFloat	exact integer and IEEE semantics at any width	$O(w/64)$–$O((w/64)^2)$	host-independent results	none	constant folding, known bits, ranges

Choose SmallVector for any sequence that is usually short. Choose DenseMap for pointer or integer keys, StringMap for string keys, and SetVector/MapVector whenever iteration order reaches the output. Choose views for parameters and never for members, and render Twines before the ;. Choose BitVector for dense small universes and SparseBitVector for huge sparse ones. Choose APInt/APFloat whenever you compute what the target computes.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch10.yaml`)	Drill	Flashcard tag	Exercises
SmallVector	`smallvector-growth`, `smallvector-moves`	`./course drill adt-costs`	`smallvector`	Lab 10.2 (use it for buffers)
DenseMap	`densemap23-trace`, `densemap22-tombstone`, `llvm-where-algorithm-r`	`./course drill densemap-probe`	`densemap`	Lab 10.2 R3 (position map)
SetVector	`setvector-order`, `setvector-determinism`	`./course drill iterator-invalidation` (worklist cases)	`setvector`	—
StringRef/ArrayRef/Twine	`twine-dangling`, `stringref-lifetime`	`./course drill view-lifetime`	`views`	—
StringMap	`stringmap-stable`, `stringref-lifetime`	`./course drill view-lifetime --difficulty hard`	`stringmap`	—
Bit sets	`bitvector-words`, `bitset-choice`	`./course drill adt-costs --difficulty hard`	`bitsets`	—
Pointer packing	`pointer-bits`, `pointer-packing-limit`	`./course drill adt-costs --difficulty hard`	`pointer-packing`	—
APInt/APFloat	`apint-sdiv`, `apint-overflow`	`./course drill adt-costs`	`apint`	Lab 10.2 (`APInt::getLowBitsSet` for the mask)

Pitfall

In LLVM 23, DenseMap::erase can move other entries (Algorithm R). A pointer or reference to any value in a DenseMap is valid only until the next insertion or erasure. Code written for the tombstone design, which assumed that erasing a different key was harmless, can now read the wrong entry, silently, as the first real-world box shows.

References¶

See the chapter references.

Technique	Main operations	Time	Space	Invalidated by
SmallVector	`push_back`, index, iterate	amortized \(O(1)\) (Theorem 10.6.13); \(O(1)\)	\(N\) inline elements + 16-byte header; heap \(\le 2n + 1\)	growth (all), insert/erase (at and after the position)
DenseMap (LLVM 23)	find, insert, erase	expected \(O(1)\): \(< 2.5\) / \(< 8.5\) probes (Proposition 10.6.16); erase \(O(\text{cluster})\)	\(B \cdot \mathrm{sizeof}(K, V) + B/8\) bytes; \(B \le 8n/3\) after growth	insert (if it grows): all; erase: all (entries move)
DenseMap (LLVM 22)	same	expected \(O(1)\); tombstones lengthen probes until rehash	\(B \cdot \mathrm{sizeof}(K, V)\), reserved keys	insert (if it grows or rehashes): all
SetVector	insert, contains; remove	\(O(1)\) expected; \(O(n)\)	vector + set	as the underlying vector/set
StringRef / ArrayRef	construct, slice, compare	\(O(1)\); compare \(O(\ell)\)	16 bytes	the viewed object
Twine	build; render	\(O(1)\) per `+`; \(O(\text{total length})\)	two child slots per node, on the stack	end of the full-expression
StringMap	find, insert	expected \(O(\lvert k \rvert)\) (hashing the key)	one entry allocation + a pointer per bucket	erase of that entry only
BitVector	test/set; union/intersection; count	\(O(1)\); \(O(U/64)\); \(O(U/64)\) popcounts	\(U/8\) bytes	resize
SparseBitVector	test/set; union/intersection	\(O(\#\text{elements})\) (cursor makes sequential access \(O(1)\))	\(\approx 24 + 16\) bytes per non-zero element	—
Pointer packing	get/set	\(O(1)\) (mask/shift)	one word	—
APInt / APFloat	add/mul/div at width \(w\)	\(O(w/64)\) / \(O((w/64)^2)\) / \(O((w/64)^2)\)	inline if \(w \le 64\)	—

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
SmallVector	a vector; inline up to \(N\)	amortized \(O(1)\), no allocation while \(\le N\)	growth invalidates everything	drop-in for `std::vector`	operand lists, worklists, temporary buffers
DenseMap	hash map for small, trivially copyable keys	expected \(O(1)\); \(< 2.5\) probes on success at \(\alpha < 3/4\)	LLVM 23: erase moves entries; iteration order is unspecified	provide `DenseMapInfo` for new key types	pointer-keyed side tables everywhere
SetVector	set with insertion-order iteration	\(O(1)\) expected insert/find, \(O(n)\) remove	deterministic output (Theorem 10.6.17)	none	worklists, ordered uniquing
StringRef/ArrayRef/Twine	free string/array parameters; lazy concatenation	\(O(1)\) to pass	dangling views are silent without ASan	discipline, not code	API parameters, names
StringMap	string-keyed map with stable keys	expected \(O(\lvert k \rvert)\)	keys stable (Proposition 10.6.19)	none	symbol tables, name interning
Bit sets	exact sets over integer universes	dense: \(O(U/64)\) ops; sparse: \(O(\#\text{elements})\)	—	none	dataflow (dense), points-to (sparse)
Pointer packing	a pointer plus \(\le a\) bits in one word	\(O(1)\)	wrong alignment assumptions assert	a traits specialization for new types	tagged pointers, `QualType`, `PointerUnion` operands
APInt/APFloat	exact integer and IEEE semantics at any width	\(O(w/64)\)–\(O((w/64)^2)\)	host-independent results	none	constant folding, known bits, ranges

Lesson 10.6 — ADTs and why they exist¶

1. Problem and motivation¶

SmallVector¶

DenseMap¶

SetVector¶

StringRef, ArrayRef and Twine¶

StringMap¶

Bit sets¶

Pointer packing¶

APInt and APFloat¶

2. Definitions and algorithms¶

SmallVector¶

DenseMap¶

SetVector¶

StringRef, ArrayRef and Twine¶

StringMap¶

Bit sets¶

Pointer packing¶

APInt and APFloat¶

3. Worked example¶

SmallVector¶

DenseMap¶

SetVector¶

StringRef, ArrayRef and Twine¶

StringMap¶

Bit sets¶

Pointer packing¶

APInt and APFloat¶

4. Invariants and correctness¶

SmallVector¶

DenseMap¶

SetVector¶

StringRef, ArrayRef and Twine¶

StringMap¶

Bit sets¶

Pointer packing¶

APInt and APFloat¶

5. Complexity¶

6. Variants and refinements¶

SmallVector¶

DenseMap¶

SetVector¶

StringRef, ArrayRef and Twine¶

StringMap¶

Bit sets¶

Pointer packing¶

APInt and APFloat¶

7. In real compilers¶

SmallVector¶

DenseMap¶

SetVector¶

StringRef, ArrayRef and Twine¶

StringMap¶

Bit sets¶

Pointer packing¶

APInt and APFloat¶

8. Comparison¶

9. Assessment¶

References¶