Four Shapes of Cache: How rustc Picks the Right Data Structure for Each Query

TL;DR: rustc has roughly 330 queries, and their keys range from () to (DefId, DefId, DefId). Using one hash map for all of them wastes most of the time. Instead each query picks a cache shape from its key type: a single OnceLock for unit keys, a dense bucketed vector for local DefIds, a hybrid that keeps locals dense and foreigners hashed, and a sharded map for everything else. The cleverest bit is the VecCache slot, which packs the “initialized?” flag and the dependency-node index into one atomic u32.

Every compiler is a caching system, and every caching system eventually asks the same question: what data structure do I use for the lookup table? The answer is usually “one hash map”, and the answer is usually wrong, because the distribution of keys matters more than the average cost of a lookup.

rustc’s query system makes the choice explicit and per-query.

The four shapes

// compiler/rustc_middle/src/query/caches.rs:52-80

pub struct DefaultCache<K, V> {
    cache: ShardedHashMap<K, (V, DepNodeIndex)>,
}
...
#[inline]
fn complete(&self, key: K, value: V, index: DepNodeIndex) {
    self.cache.insert_unique(key, (value, index));
}

That is the general case: a sharded hash map with write-once semantics (insert_unique — if the key is already there, it is a bug, not a race to resolve). Write-once is what lets the map be sharded without locks on the read path.

Then there is the unit-key case:

// compiler/rustc_middle/src/query/caches.rs:95-133

/// In-memory cache for queries whose key type only has one value (e.g. `()`).
/// The cache therefore only needs to store one query return value.
pub struct SingleCache<V> {
    cache: OnceLock<(V, DepNodeIndex)>,
}
...
#[inline(always)]
fn lookup(&self, _key: &()) -> Option<(V, DepNodeIndex)> {
    self.cache.get().copied()
}

#[inline]
fn complete(&self, _key: (), value: V, index: DepNodeIndex) {
    self.cache.set((value, index)).ok();
}

A query keyed by () is a global variable. It gets a global variable.

And then the interesting one:

// compiler/rustc_middle/src/query/caches.rs:135-144

/// In-memory cache for queries whose key is a [`DefId`].
///
/// Selects between one of two internal caches, depending on whether the key
/// is a local ID or foreign-crate ID.
pub struct DefIdCache<V> {
    /// Stores the local DefIds in a dense map. Local queries are much more often dense, so this is
    /// a win over hashing query keys at marginal memory cost (~5% at most) compared to FxHashMap.
    local: VecCache<DefIndex, V, DepNodeIndex>,
    foreign: DefaultCache<DefId, V>,
}

Read that comment like a punchline. The hybrid cache says out loud that it spends 5% more memory to make the common case faster. Local DefIds are dense — item 0, item 1, item 2 — so hashing them is wasted work; foreign DefIds are sparse and arbitrary, so they need a hash map. The struct picks between the two with a branch on whether the id is local.

The VecCache slot: one word, two jobs

// compiler/rustc_data_structures/src/vec_cache.rs:19-28

struct Slot<V> {
    // We never construct &Slot<V> so it's fine for this to not be in an UnsafeCell.
    value: V,
    // This is both an index and a once-lock.
    //
    // 0: not yet initialized.
    // 1: lock held, initializing.
    // 2..u32::MAX - 2: initialized.
    index_and_lock: AtomicU32,
}

index_and_lock is doing two jobs at once: it is the initialization state and the DepNodeIndex of the entry, which the query system needs so it can wire up the dependency graph. Since the index is only meaningful once the slot is initialized, the states and the payload do not conflict:

• 0 — not yet initialized;
• 1 — somebody is initializing it right now (the loser of the race waits);
• 2..=u32::MAX - 2 — initialized, and the value is the dep-node index.

That means the “am I initialized?” test is one relaxed atomic load, and there is no separate Option discriminant, no padding, and no second atomic to keep in sync.

Buckets, so growth never copies

// compiler/rustc_data_structures/src/vec_cache.rs:224-244

pub struct VecCache<K: Idx, V, I> {
    // Entries per bucket:
    // Bucket  0:       4096 2^12
    // Bucket  1:       4096 2^12
    // Bucket  2:       8192
    // Bucket  3:      16384
    // ...
    // Bucket 19: 1073741824
    // Bucket 20: 2147483648
    // The total number of entries if all buckets are initialized is 2^32.
    buckets: [AtomicPtr<Slot<V>>; BUCKETS],
}

A single Vec would have to be resized as the crate grows, which means copying every entry and coordinating between threads that are inserting at the same time. The bucketed scheme sidesteps that entirely: each bucket is allocated once (lazily, under a cold global mutex) and never moved. The flat index is split into a bucket number and an offset with an ilog2-based calculation.

The presence of a present side array means iteration touches only live entries instead of scanning 2^32 slots:

// compiler/rustc_data_structures/src/vec_cache.rs:236-240

The compile-time size budgets

The other thing rustc does is forbid the slow shapes. Query keys must fit in 88 bytes and values in 64 bytes, checked at compile time, with the offending query named in the panic message:

// compiler/rustc_middle/src/query/query_api.rs:95-124

// Ensure that keys grow no larger than 88 bytes by accident.
// Increase this limit if necessary, but do try to keep the size low if possible
#[cfg(target_pointer_width = "64")]
const _: () = {
    if size_of::<Key<'static>>() > 88 {
        panic!("{}", concat!(
            "the query `",
            stringify!($name),
            "` has a key type `",
            stringify!($($K)*),
            "` that is too large"
        ));
    }
};

Values are stored by value in the cache, so a value that does not fit has to be arena-allocated and returned by reference instead. The check even mentions the escape hatch:

// compiler/rustc_middle/src/query/arena_cached.rs:17-30

And the value check is compiled out under the randomized-layout feature, because shuffling struct fields makes size_of unstable:

#[cfg(not(feature = "rustc_randomized_layouts"))]

One list, four expansions

Every cache shape, every modifier, every provider struct is generated from a single list of query declarations in compiler/rustc_middle/src/queries.rs. The list is turned into a higher-order macro that four different macros consume:

// compiler/rustc_macros/src/query.rs:465-490

/// Higher-order macro that invokes the specified macro with (a) a list of all query
/// signatures (including modifiers), and (b) a list of non-query names. This allows
/// multiple simpler macros to each have access to these lists.
#[rustc_macro_transparency = "semiopaque"] // Use `macro_rules!` hygiene.
pub macro rustc_with_all_queries {
    (
        // The macro to invoke once, on all queries and non-queries.
        $macro:ident!
    ) => {
        $macro! {
            queries { #query_stream }
            non_queries { #non_query_stream }
        }
    }
}

The four consumers are the public query API, the per-query vtable, the dependency-kind vtable, and the DepKind enum itself. The modifiers list has a fixed syntactic shape with a grep anchor comment — “Search for (QMODLIST) to find all occurrences of this query modifier list” — so that adding a modifier cannot silently leave one of the four expansions behind.

Where it lives

• compiler/rustc_middle/src/query/caches.rs — SingleCache, DefIdCache, DefaultCache.
• compiler/rustc_data_structures/src/vec_cache.rs — the bucketed cache and the packed slot.
• compiler/rustc_data_structures/src/sharded.rs — the sharded map.
• compiler/rustc_middle/src/query/query_api.rs — the size assertions.
• compiler/rustc_macros/src/query.rs — the one-list-four-expansion macro.

The lesson: cache design is not one decision, it is a distribution decision. rustc measured that local DefIds are dense, spent 5% more memory, and got a hash-free lookup for the common case.