Opensource internals

Tables That Pick Their Own Integer Width: How rustc Encodes Crate Metadata

8 min read Jay Hubbert

rustc's metadata tables choose their element width at encode time by dropping trailing zero bytes, and byte-interleave integer pairs so both halves compress at once.

TL;DR: rustc’s crate metadata is a set of tables whose element width is decided at encode time: the encoder strips trailing zero bytes from each element and takes the maximum, so a table of small values is stored in one byte per entry. And when an element is a pair of integers, the bytes are interleaved so that trailing zeros in both halves line up and one stripping pass compresses both.

The table header

rust 
// compiler/rustc_metadata/src/rmeta/mod.rs:156-164

struct LazyTable<IdxEncode, IdxDecode, T> {
    position: NonZero<usize>,
    /// The encoded size of the elements of a table is selected at runtime to drop
    /// trailing zeroes. This is the number of bytes used for each table element.
    width: usize,
    /// How many elements are in the table.
    len: usize,
    _marker: PhantomData<fn(IdxEncode, IdxDecode) -> T>,
}

The width is per table, not per element. The decoder knows the stride and reads width bytes at position + width * index.

Choosing the width

rust 
// compiler/rustc_metadata/src/rmeta/table.rs:453-505

pub(crate) fn set(&mut self, i: Ie, value: T) {
    ...
    if !value.is_default() {
        // FIXME(eddyb) investigate more compact encodings for sparse tables.
        // ...
        let block = self.blocks.ensure_contains_elem(i, || [0; N]);
        value.write_to_bytes(block);
        if self.width != N {
            let width = N - trailing_zeros(block);
            self.width = self.width.max(width);
        }
    }
}

pub(crate) fn encode(&self, buf: &mut FileEncoder<'_>) -> LazyTable<Ie, Id, T> {
    let pos = buf.position();

    let width = self.width;
    for block in &self.blocks {
        buf.write_with(|dest| {
            *dest = *block;
            width
        });
    }
    ...
}

fn trailing_zeros(x: &[u8]) -> usize {
    x.iter().rev().take_while(|b| **b == 0).count()
}

The mechanism:

  • each element has a maximum width N (1, 8 or 16 bytes);
  • when an element is written, the encoder computes how many of its trailing bytes are zero and remembers the maximum over all elements;
  • at encode time, only that many bytes per element are written.

So a table of DefKinds — one byte each — whose values all happen to be below 16 encodes in one byte per entry, and the same table with one large value encodes in the full width.

The is_default() check is a second optimisation: default values are simply not written, leaving zeros. (The comment notes that metadata tables never need to reset a value to default, which is what makes this safe.)

Byte-interleaving the pairs

Here is the genuinely clever part. Many metadata elements are a pair of integers — a position and a length, or a crate index and a local index. If you store them as [pos_bytes | len_bytes], then the high bytes of len (which are usually non-zero) shield the trailing zeros of pos, and the element can never shrink below 8 bytes.

The fix is to interleave:

rust 
// compiler/rustc_metadata/src/rmeta/table.rs:362-390

// Interleaving the bytes of the two integers exposes trailing bytes in the first integer
// to the varint scheme that we use for tables.
#[inline]
fn decode_interleaved<const N: usize, const M: usize>(encoded: &[u8; N]) -> ([u8; M], [u8; M]) {
    assert_eq!(M * 2, N);
    let mut first = [0u8; M];
    let mut second = [0u8; M];
    for i in 0..M {
        first[i] = encoded[2 * i];
        second[i] = encoded[2 * i + 1];
    }
    (first, second)
}

// Element width is selected at runtime on a per-table basis by omitting trailing
// zero bytes in table elements. This works very naturally when table elements are
// simple numbers but sometimes we have a pair of integers. If naively encoded, the second element
// would shield the trailing zeroes in the first. Interleaving the bytes exposes trailing zeroes in
// both to the optimization.
//
// Prefer passing a and b such that `b` is usually smaller.
#[inline]
fn encode_interleaved<const N: usize, const M: usize>(a: [u8; M], b: [u8; M], dest: &mut [u8; N]) {
    assert_eq!(M * 2, N);
    for i in 0..M {
        dest[2 * i] = a[i];
        dest[2 * i + 1] = b[i];
    }
}

Interleaving pos[0], len[0], pos[1], len[1], ... puts the significant bytes of both integers at the same offsets, so the trailing zeros of both line up at the end of the element and one “strip trailing zeros” pass compresses both halves at once.

The comment “Prefer passing a and b such that b is usually smaller” is the follow-on advice: the smaller number’s high bytes become zeros, which is where the savings come from.

Used for LazyArray<T>:

rust 
// compiler/rustc_metadata/src/rmeta/table.rs:346-360

impl<T> LazyArray<T> {
    #[inline]
    fn write_to_bytes_impl(self, dest: &mut [u8; 16]) {
        let position = (self.position.get() as u64).to_le_bytes();
        let len = (self.num_elems as u64).to_le_bytes();

        encode_interleaved(position, len, dest)
    }

and for DefIds, where the crate number goes second:

rust 
// compiler/rustc_metadata/src/rmeta/table.rs:272-288

fn write_to_bytes(self, dest: &mut [u8; 8]) {
    match self {
        None => unreachable!(),
        Some(id) => {
            let (krate, index) = id.decompose();
            debug_assert!(krate < u32::MAX);
            // CrateNum is less than `CrateNum::MAX_AS_U32`.
            let krate = (krate + 1).to_le_bytes();
            let index = index.to_le_bytes();

            // CrateNum is usually much smaller than the index within the crate, so put it in
            // the second slot.
            encode_interleaved(index, krate, dest);
        }
    }
}

A DefId element is 8 bytes: a u32 index and a u32 crate number. The crate number is usually small (a handful of dependencies), so putting it second means the element usually compresses to 5 bytes or fewer.

Decoding straight out of the mmap

rust 
// compiler/rustc_metadata/src/rmeta/table.rs:507-535

pub(super) fn get<'a, 'tcx, M: MetaBlob<'a>>(&self, metadata: M, i: Id) -> T::Value<'tcx> {
    // Access past the end of the table returns a Default
    if i.index() >= self.len {
        return Default::default();
    }

    let width = self.width;
    let start = self.position.get() + (width * i.index());
    let end = start + width;
    let bytes = &metadata.blob()[start..end];

    if let Ok(fixed) = bytes.try_into() {
        FixedSizeEncoding::from_bytes(fixed)
    } else {
        let mut fixed = [0u8; N];
        fixed[..width].copy_from_slice(bytes);
        FixedSizeEncoding::from_bytes(&fixed)
    }
}

The element is read by indexing the metadata blob directly — no decompression step, no intermediate structure, no copy (in the common case where the width matches the fixed size exactly). And the blob is an mmap:

rust 
// compiler/rustc_metadata/src/locator.rs:936-953

fn get_rmeta_metadata_section<'a, 'p>(filename: &'p Path) -> Result<OwnedSlice, MetadataError<'a>> {
    // mmap the file, because only a small fraction of it is read.
    let file = std::fs::File::open(filename).map_err(|_| {
        MetadataError::LoadFailure(format!(
            "failed to open rmeta metadata: '{}'",
            filename.display()
        ))
    })?;
    let mmap = unsafe { Mmap::map(file) };
    ...

The comment is the point: only a small fraction of the file is ever read, so the OS only faults in the pages that are touched.

Lazy values and post-order encoding

The table above stores offsets, and those offsets point into a post-order-encoded tree:

rust 
// compiler/rustc_metadata/src/rmeta/mod.rs:93-118

/// A value of type T referred to by its absolute position
/// in the metadata, and which can be decoded lazily.
///
/// Metadata is effective a tree, encoded in post-order,
/// and with the root's position written next to the header.
/// That means every single `LazyValue` points to some previous
/// location in the metadata and is part of a larger node.
///
/// The first `LazyValue` in a node is encoded as the backwards
/// distance from the position where the containing node
/// starts and where the `LazyValue` points to, while the rest
/// use the forward distance from the previous `LazyValue`.
/// Distances start at 1, as 0-byte nodes are invalid.
/// Also invalid are nodes being referred in a different
/// order than they were encoded in.
#[must_use]
struct LazyValue<T> {
    position: NonZero<usize>,
    _marker: PhantomData<fn() -> T>,
}

A LazyValue is one machine word — an offset, nothing else. The value T is decoded only when somebody asks for it.

And the offsets are encoded as distances, not absolute positions:

rust 
// compiler/rustc_metadata/src/rmeta/encoder.rs:497-518

fn emit_lazy_distance(&mut self, position: NonZero<usize>) {
    let pos = position.get();
    let distance = match self.lazy_state {
        LazyState::NoNode => bug!("emit_lazy_distance: outside of a metadata node"),
        LazyState::NodeStart(start) => {
            let start = start.get();
            assert!(pos <= start);
            start - pos
        }
        LazyState::Previous(last_pos) => {
            assert!(
                last_pos <= position,
                "make sure that the calls to `lazy*` \
                 are in the same order as the metadata fields",
            );
            position.get() - last_pos.get()
        }
    };
    self.lazy_state = LazyState::Previous(NonZero::new(pos).unwrap());
    self.emit_usize(distance);
}

The first LazyValue in a node is a backwards distance from the node’s start; the rest are forward distances from the previous one. Because post-order encoding puts children right next to their parent, these distances are small — typically one to three varint bytes instead of eight for an absolute offset.

The effect: loading a dependency crate’s metadata costs one mmap plus a handful of page faults for the header and the tables. Only the definitions actually referenced get decoded.

Where it lives

  • compiler/rustc_metadata/src/rmeta/table.rs — TableBuilder::set, encode_interleaved, LazyTable::get.
  • compiler/rustc_metadata/src/rmeta/mod.rs — LazyTable, LazyValue.
  • compiler/rustc_metadata/src/rmeta/encoder.rs — emit_lazy_distance.
  • compiler/rustc_metadata/src/locator.rs — the mmap.

Takeaway

Two reusable ideas. First: choose the encoding width at runtime, when the data is in front of you — the encoder knows the actual values and can pick the smallest width that fits, which a fixed-width format cannot do. Second: interleave to expose common structure — when two numbers are packed together, laying their bytes out alternately lets a single trailing-zero-stripping rule compress both. Neither trick is specific to rustc; both are good tricks for any binary format.

RustInternalsCompilerMetadataFile formatPerformance