38 Bytes and a Mask: Inside rustc's Incremental File Format

TL;DR: rustc’s dependency graph file is a sequence of fixed-size 38-byte node headers, each followed by an edge list whose byte width is decided per node. The edge lists stay varint-encoded in memory too, and are read back with a 4-byte load plus a mask. The encoder streams: threads claim node indices in blocks of 256 and write into 64 KiB private buffers, and the file is finalized with trailing count words so the reader can preallocate exactly.

Incremental compilation writes a dependency graph to disk and reads it back on the next build. That file is read hot: every node of the previous session’s graph is visited during red/green marking. Its layout matters.

The header

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:434-448

/// A packed representation of all the fixed-size fields in a `NodeInfo`.
///
/// This stores in one byte array:
/// * The value `Fingerprint` in the `NodeInfo`
/// * The key `Fingerprint` in `DepNode` that is in this `NodeInfo`
/// * The `DepKind`'s discriminant (a u16, but not all bits are used...)
/// * The byte width of the encoded edges for this node
/// * In whatever bits remain, the length of the edge list for this node, if it fits
struct SerializedNodeHeader {
    // 2 bytes for the DepNode
    // 4 bytes for the index
    // 16 for Fingerprint in DepNode
    // 16 for Fingerprint in NodeInfo
    bytes: [u8; 38],
}

One fixed-size read gets you the kind, the key fingerprint, the value fingerprint and the edge metadata. The bit layout is hand-packed:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:461-495

// Bit fields, where
// M: bits used to store the length of a node's edge list
// N: bits used to store the byte width of elements of the edge list
// are
// 0..M    length of the edge
// M..M+N  bytes per index
// M+N..16 kind
impl SerializedNodeHeader {
    const TOTAL_BITS: usize = size_of::<DepKind>() * 8;
    const LEN_BITS: usize = Self::TOTAL_BITS - Self::KIND_BITS - Self::WIDTH_BITS;
    const WIDTH_BITS: usize = DEP_NODE_WIDTH_BITS;
    const KIND_BITS: usize = Self::TOTAL_BITS - DepKind::MAX.leading_zeros() as usize;
    const MAX_INLINE_LEN: usize = (u16::MAX as usize >> (Self::TOTAL_BITS - Self::LEN_BITS)) - 1;

The edge length is stored inline when it fits, and the edge byte width is computed once per node from the largest index in the list:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:581-602

fn encode(&self, e: &mut MemEncoder, index: DepNodeIndex) {
    let NodeInfo { ref node, value_fingerprint, edges } = *self;
    // The largest index picks the byte width of the edge list.
    let edge_max = edges.iter().map(|e| e.as_u32()).max().unwrap_or(0);
    let header =
        SerializedNodeHeader::new(node, index, value_fingerprint, edge_max, edges.len());
    e.write_array(header.bytes);
    ...
    let bytes_per_index = header.bytes_per_index();
    for node_index in edges.iter() {
        e.write_with(|dest| {
            *dest = node_index.as_u32().to_le_bytes();
            bytes_per_index
        });
    }
}

A node with 200 dependencies gets 1-byte indices; a node with 200 000 gets 4-byte indices. One width for the whole list, not per edge.

The edges stay varint-encoded in memory

The surprising part: the in-memory representation after loading is the same byte array, not a decoded IndexVec<DepNodeIndex>.

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:15-28

//! The encoding of the dep-graph is generally designed around the fact that fixed-size
//! reads of encoded data are generally faster than variable-sized reads. Ergo we adopt
//! essentially the same varint encoding scheme used in the rmeta format; the edge lists
//! for each node on the graph store a 2-bit integer which is the number of bytes per edge
//! index in that node's edge list. We effectively ignore that an edge index of 0 could be
//! encoded with 0 bytes in order to not require 3 bits to store the byte width of the edges.
//! The overhead of calculating the correct byte width for each edge is mitigated by
//! computing the max of the edge list once per node instead of per edge.

and the decoder:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:210-231

#[inline]
pub fn edge_targets_from(
    &self,
    source: SerializedDepNodeIndex,
) -> impl Iterator<Item = SerializedDepNodeIndex> + Clone {
    let header = self.edge_list_indices[source];
    let mut raw = &self.edge_list_data[header.start()..];

    let bytes_per_index = header.bytes_per_index();

    // LLVM doesn't hoist EdgeHeader::mask so we do it ourselves.
    let mask = header.mask();
    (0..header.num_edges).map(move |_| {
        // Doing this slicing in this order ensures that the first bounds check suffices for
        // all the others.
        let index = &raw[..DEP_NODE_SIZE];
        raw = &raw[bytes_per_index..];
        let index = u32::from_le_bytes(index.try_into().unwrap()) & mask;
        SerializedDepNodeIndex::from_u32(index)
    })
}

Three micro-decisions in there:

The list is read as a fixed 4-byte load and then masked, rather than as a varint. Fixed-size reads are much faster than variable-size ones.
The comment “LLVM doesn’t hoist EdgeHeader::mask so we do it ourselves” is a note from a past optimization attempt: the mask is computed once, outside the closure, instead of per element.
The slicing order is deliberate: taking &raw[..4] first means the bounds check on the slice happens once and the subsequent raw = &raw[bytes_per_index..] is provably in range.

The last edge may read past the end of the array, which is why the buffer is padded:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:83-91
const DEP_NODE_SIZE: usize = size_of::<SerializedDepNodeIndex>();
/// Amount of padding we need to add to the edge list data so that we can retrieve every
/// SerializedDepNodeIndex with a fixed-size read then mask.
const DEP_NODE_PAD: usize = DEP_NODE_SIZE - 1;

Streaming out: blocks of 256

The encoder never builds the whole graph in memory. Threads claim node indices in blocks:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:663-681

#[inline]
fn next_index(&self, local: &mut LocalEncoderState) -> DepNodeIndex {
    if local.remaining_node_index == 0 {
        const COUNT: u32 = 256;

        // We assume that there won't be enough active threads to overflow `u64` from `u32::MAX` here.
        // This can exceed u32::MAX by at most `N` * `COUNT` where `N` is the thread pool count since
        // `try_into().unwrap()` will make threads panic when `self.next_node_index` exceeds u32::MAX.
        local.next_node_index =
            self.next_node_index.fetch_add(COUNT as u64, Ordering::Relaxed).try_into().unwrap();

        // Check that we'll stay within `u32`
        local.next_node_index.checked_add(COUNT).unwrap();

        local.remaining_node_index = COUNT;
    }

    DepNodeIndex::from_u32(local.next_node_index)
}

One atomic fetch_add per 256 nodes instead of per node — and because a thread owns the whole block, two threads can never allocate the same index and no lock is needed around allocation.

Each thread writes into its own buffer and flushes at 64 KiB:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:731-750

fn flush_mem_encoder(&self, local: &mut LocalEncoderState) {
    let data = &mut local.encoder.data;
    if data.len() > 64 * 1024 {
        self.file.lock().as_mut().unwrap().emit_raw_bytes(&data[..]);
        data.clear();
    }
}

That converts what would be hundreds of thousands of write(2) syscalls into a few thousand, and turns lock contention between all frontend threads into contention between threads that happen to flush at the same moment.

Trailing counts for exact preallocation

At the end of the run, the encoder writes three fixed-size counts at the end of the file:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:772-834

// Encode the number of each dep kind encountered
for count in kind_stats.iter() {
    count.encode(&mut encoder);
}

self.previous.session_count.checked_add(1).unwrap().encode(&mut encoder);
...
IntEncodedWithFixedSize(node_max.try_into().unwrap()).encode(&mut encoder);
IntEncodedWithFixedSize(node_count.try_into().unwrap()).encode(&mut encoder);
IntEncodedWithFixedSize(edge_count.try_into().unwrap()).encode(&mut encoder);

and the reader seeks backwards from the end to find them:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:309-327

let (node_max, node_count, edge_count) =
    d.with_position(d.len() - 3 * IntEncodedWithFixedSize::ENCODED_SIZE, |d| {
        let node_max = IntEncodedWithFixedSize::decode(d).0 as usize;
        let node_count = IntEncodedWithFixedSize::decode(d).0 as usize;
        let edge_count = IntEncodedWithFixedSize::decode(d).0 as usize;
        (node_max, node_count, edge_count)
    });

so the reader can allocate exactly the right amount:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:329-338

let mut nodes = IndexVec::from_elem_n(
    DepNode { kind: DepKind::Null, key_fingerprint: PackedFingerprint::from(Fingerprint::ZERO) },
    node_max,
);

Note node_max versus node_count: because indices are handed out in blocks of 256, there are gaps — the unused indices stay Null in the graph and are skipped by the decoder. The reader allocates for the index space but decodes only the populated nodes.

The reverse index is built lazily

If you need to look up “which node has this key fingerprint?”, you do not want to build that map for every DepKind:

rust
// compiler/rustc_middle/src/dep_graph/serialized.rs:145-170

/// The inverse of [`SerializedDepGraph::nodes`], built lazily per [`DepKind`].
///
/// Only few nodes are ever looked up here, and those cluster into a handful of
/// `DepKind`s. Building a map for every kind up front would be wasted work.
#[derive(Debug, Default)]
struct LazyNodeIndex {

and when it is built, it is built by a counting sort over the kinds, so the per-kind ranges are contiguous and the map is a flat slice lookup:

rust

// compiler/rustc_middle/src/dep_graph/serialized.rs:172-207

Where it lives

All of it is in compiler/rustc_middle/src/dep_graph/serialized.rs, with the color map in compiler/rustc_middle/src/dep_graph/graph.rs.

The design principle: the file format and the in-memory format are the same. There is no decode step that materializes a friendlier structure, because the friendly structure is bigger and slower to walk. The one thing that is materialized — the reverse index — is deferred until something actually asks for it.