One u32, Three Colors: How rustc Packs Its Dependency Graph State Into Four Bytes

TL;DR: rustc’s incremental compiler has to answer two questions about every node of the previous session’s dependency graph: what color is it? and which node in the current session does it correspond to? The textbook design answers them with an enum plus a side table. rustc answers them with one u32 load, because the color’s payload is the index: values below u32::MAX - 1 mean “green, and here is the new index”, u32::MAX - 1 means “red”, and u32::MAX means “we haven’t decided yet”. The file lives in compiler/rustc_middle/src/dep_graph/graph.rs.

Incremental compilation in rustc is a red/green algorithm with a twist: the “green” state is not stored, it is recomputed. Every time rustc rebuilds a crate, it re-executes the queries, but if a query’s result fingerprint matches the fingerprint recorded in the previous session, the result is “green” and can be reused. The bookkeeping for that lives in DepNodeColorMap.

The obvious design

You would model this as an enum:

enum DepNodeColor {
    Green(DepNodeIndex),
    Red,
    Unknown,
}

which is 8 bytes: a discriminant plus a 4-byte payload with padding. And then, because the previous session’s node indices are not the current session’s node indices, you need a second map from “previous index” to “current index”. Two data structures, two lookups, and the second one has to be built before you can use the first.

rustc does it with one array of u32.

The encoding

// compiler/rustc_middle/src/dep_graph/graph.rs:1327-1345

/// A data structure that stores Option<DepNodeColor> values as a contiguous
/// array, using one u32 per entry.
pub(super) struct DepNodeColorMap {
    values: IndexVec<SerializedDepNodeIndex, AtomicU32>,
}

// All values below `COMPRESSED_RED` are green.
const COMPRESSED_RED: u32 = u32::MAX - 1;
const COMPRESSED_UNKNOWN: u32 = u32::MAX;

Read the comment carefully: all values below COMPRESSED_RED are green. That is the whole trick. The number 0xFFFE_FFFF and below are not a reserved range — they are 4 billion possible green states, and the value itself is the current-session index of the node.

Reading a color is therefore one load and two comparisons:

// compiler/rustc_middle/src/dep_graph/graph.rs:1370-1380

#[inline]
pub(super) fn get(&self, index: SerializedDepNodeIndex) -> DepNodeColor {
    let value = self.values[index].load(Ordering::Acquire);
    // Green is by far the most common case. Check for that first so we can succeed with a
    // single comparison.
    if value < COMPRESSED_RED {
        DepNodeColor::Green(DepNodeIndex::from_u32(value))
    } else if value == COMPRESSED_RED {
        DepNodeColor::Red
    } else {
        debug_assert_eq!(value, COMPRESSED_UNKNOWN);
        DepNodeColor::Unknown
    }
}

And current() — the “what is the new index?” question — reads the same word:

// compiler/rustc_middle/src/dep_graph/graph.rs:1339-1346

#[inline]
pub(super) fn current(&self, index: SerializedDepNodeIndex) -> Option<DepNodeIndex> {
    let value = self.values[index].load(Ordering::Relaxed);
    if value <= DepNodeIndex::MAX_AS_U32 { Some(DepNodeIndex::from_u32(value)) } else { None }
}

Two questions, one load, no side table.

Writing is a race, and that’s the point

Multiple threads may reach the same previous-session node at the same time — that is the entire point of a parallel compiler. So the write has to be atomic, and “first writer wins” has to be the arbitration rule. The color map does exactly that with a compare-exchange:

// compiler/rustc_middle/src/dep_graph/graph.rs:1349-1370

#[inline(always)]
pub(super) fn try_set_color(
    &self,
    prev_index: SerializedDepNodeIndex,
    color: DesiredColor,
) -> TrySetColorResult {
    match self.values[prev_index].compare_exchange(
        COMPRESSED_UNKNOWN,
        match color {
            DesiredColor::Red => COMPRESSED_RED,
            DesiredColor::Green { index } => index.as_u32(),
        },
        Ordering::Relaxed,
        Ordering::Relaxed,
    ) {
        Ok(_) => TrySetColorResult::Success,
        Err(COMPRESSED_RED) => TrySetColorResult::AlreadyRed,
        Err(index) => TrySetColorResult::AlreadyGreen { index: DepNodeIndex::from_u32(index) },
    }
}

Two things are worth noticing.

First, the loser of the race is told what the winner decided. If thread A marks a node green with index 8123 and thread B tried to mark it green with index 8124, B gets back AlreadyGreen { index: 8123 } and simply uses A’s answer. There is no “conflict” state to handle.

Second, the memory ordering is Relaxed on both sides. That is sound because the DepNode data itself is published through a different, synchronizing channel; this word only carries a decision, and the decision is idempotent. (The get path uses Acquire because the returned index is then used to look at node data.)

The invariant that makes it legal

The encoding only works while DepNodeIndex stays below u32::MAX - 1, and rustc asserts exactly that:

debug_assert!(COMPRESSED_RED > DepNodeIndex::MAX_AS_U32);

It is the sort of thing that breaks the day someone adds a billion nodes to a crate, and the debug assertion is there to make sure that day is a loud failure rather than a silent miscompile.

Why not use the top bit?

You could encode “red” as the top bit and “unknown” as the second, leaving 31 bits for the index. rustc instead spends two of the high values (u32::MAX - 1 and u32::MAX) on the exceptional states and gives the index the whole remaining range. The reason is the comparison order: the green check is value < COMPRESSED_RED, a single unsigned compare against a constant, and the branch predictor loves it because green is the overwhelmingly common case. The comment in the source says as much: “Green is by far the most common case. Check for that first so we can succeed with a single comparison.”

The smaller cousin

The same trick shows up elsewhere in the compiler’s data structures. The dependency node itself is shrunk with a packed fingerprint:

// compiler/rustc_data_structures/src/fingerprint.rs:184-203

/// `PackedFingerprint` wraps a `Fingerprint`.
/// Its purpose is to behave like a `Fingerprint` without alignment requirements.
///
/// This may be preferable to use in large collections of structs containing
/// fingerprints, as it can reduce memory consumption by preventing the padding
/// that the more strictly-aligned `Fingerprint` can introduce. An application
/// of this is in the query dependency graph, which contains a large collection
/// of `DepNode`s. As of this writing, the size of a `DepNode` decreases by 25%
/// (from 24 bytes to 18) by using the packed representation here, which
/// noticeably decreases total memory usage when compiling large crates.
#[repr(packed)]
pub struct PackedFingerprint(Fingerprint);

and the size is pinned by a compile-time assertion:

// compiler/rustc_middle/src/dep_graph/dep_node.rs:372-382
static_assert_size!(DepKind, 2);
static_assert_size!(DepNode, 18);

Six bytes saved per node, times a million nodes, is six megabytes of resident memory that the compiler does not have to page in. When you are mmap-ing a dependency graph off disk and walking it millions of times, that is not a micro-optimization; it is the difference between a compile that fits in cache and one that does not.

Where it lives

• compiler/rustc_middle/src/dep_graph/graph.rs — DepNodeColorMap, the encoding constants, and try_set_color.
• compiler/rustc_middle/src/dep_graph/dep_node.rs — the DepNode layout and its size assertions.
• compiler/rustc_data_structures/src/fingerprint.rs — PackedFingerprint.

The lesson is bigger than rustc: when a state machine has a “payload” in one of its states, and the payload happens to fit in the same integer, you can delete a data structure. Four bytes per node, one load, no side table.