Struct Span

pub struct Span {
    lo_or_index: u32,
    len_with_tag_or_marker: u16,
    ctxt_or_parent_or_marker: u16,
}

A compressed span.

SpanData is 16 bytes, which is too big to stick everywhere. Span only takes up 8 bytes, with less space for the length, parent and context. The vast majority (99.9%+) of SpanData instances can be made to fit within those 8 bytes. Any SpanData whose fields don’t fit into a Span are stored in a separate interner table, and the Span will index into that table. Interning is rare enough that the cost is low, but common enough that the code is exercised regularly.

An earlier version of this code used only 4 bytes for Span, but that was slower because only 80–90% of spans could be stored inline (even less in very large crates) and so the interner was used a lot more. That version of the code also predated the storage of parents.

There are four different span forms.

Inline-context format (requires non-huge length, non-huge context, and no parent):

• span.lo_or_index == span_data.lo
• span.len_with_tag_or_marker == len == span_data.hi - span_data.lo (must be <= MAX_LEN)
• span.ctxt_or_parent_or_marker == span_data.ctxt (must be <= MAX_CTXT)

Inline-parent format (requires non-huge length, root context, and non-huge parent):

• span.lo_or_index == span_data.lo
• span.len_with_tag_or_marker & !PARENT_TAG == len == span_data.hi - span_data.lo (must be <= MAX_LEN)
• span.len_with_tag_or_marker has top bit (PARENT_TAG) set
• span.ctxt_or_parent_or_marker == span_data.parent (must be <= MAX_CTXT)

Partially-interned format (requires non-huge context):

• span.lo_or_index == index (indexes into the interner table)
• span.len_with_tag_or_marker == BASE_LEN_INTERNED_MARKER
• span.ctxt_or_parent_or_marker == span_data.ctxt (must be <= MAX_CTXT)

Fully-interned format (all cases not covered above):

• span.lo_or_index == index (indexes into the interner table)
• span.len_with_tag_or_marker == BASE_LEN_INTERNED_MARKER
• span.ctxt_or_parent_or_marker == CTXT_INTERNED_MARKER

The partially-interned form requires looking in the interning table for lo and length, but the context is stored inline as well as interned. This is useful because context lookups are often done in isolation, and inline lookups are quicker.

Notes about the choice of field sizes:

• lo is 32 bits in both Span and SpanData, which means that lo values never cause interning. The number of bits needed for lo depends on the crate size. 32 bits allows up to 4 GiB of code in a crate. Having no compression on this field means there is no performance cliff if a crate exceeds a particular size.
• len is ~15 bits in Span (a u16, minus 1 bit for PARENT_TAG) and 32 bits in SpanData, which means that large len values will cause interning. The number of bits needed for len does not depend on the crate size. The most common numbers of bits for len are from 0 to 7, with a peak usually at 3 or 4, and then it drops off quickly from 8 onwards. 15 bits is enough for 99.99%+ of cases, but larger values (sometimes 20+ bits) might occur dozens of times in a typical crate.
• ctxt_or_parent_or_marker is 16 bits in Span and two 32 bit fields in SpanData, which means intering will happen if ctxt is large, if parent is large, or if both values are non-zero. The number of bits needed for ctxt values depend partly on the crate size and partly on the form of the code. No crates in rustc-perf need more than 15 bits for ctxt_or_parent_or_marker, but larger crates might need more than 16 bits. The number of bits needed for parent hasn’t been measured, because parent isn’t currently used by default.

In order to reliably use parented spans in incremental compilation, the dependency to the parent definition’s span. This is performed using the callback SPAN_TRACK to access the query engine.

Fields

lo_or_index: u32

len_with_tag_or_marker: u16

ctxt_or_parent_or_marker: u16