Struct Span 

#[repr(packed(4))]
pub struct Span(u64);

A compressed span.

[SpanData] is 16 bytes, which is too big to stick everywhere. Span is only 8 bytes. A large majority 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.

An earlier version of this code used only 4 bytes for Span, but that was slower because many fewer spans could be stored inline and the interner was used a lot more. That version of the code also predated the storage of parents.

Experiments with uncompressed spans yielded worse performance in most cases because memory usage and cache miss rates are significantly higher without compression.

There are four different span formats and each packs data into the 8 bytes in a different way. A variable-length prefix in the high bits identifies which format is being used. It is an invariant that we always use the first listed format whose requirements are satisfied. len is hi - lo.

• Inline-context format (requires 15-bit length, 16-bit context, and no parent):

  [ prefix=0 | len:15 | ctxt:16 | lo:32 ]

• Inline-parent format (requires 14-bit length, root context, and 15-bit parent):

  [ prefix=110 | len:14 | parent:15 | lo:32 ]

• Inline-pair format (requires 24-bit lo, 7-bit length, 15-bit context, 16-bit parent):

  [ prefix=10 | len:7 | ctxt:15 | parent:16 | lo:24 ]

• Interned format (all cases not covered above):

  [ prefix=111 | ctxt:29 | index:32 ]

Notes about this design.

• This configuration was the best one found after many measurements of real-world crates, and replaced an earlier 8-byte design.

• The size of lo depends on the size of the crate and its dependencies. Crates whose lo size exceeds 24-bits are extremely rare.

• The most common numbers of bits needed for len are from 0 to 7, with a peak usually at 3 or 4, and then it drops off quickly from 8 onwards. Lengths larger than 14 bits are rare, but many crates will have a small number of such lengths (sometimes 20+ bits).

• The number of bits needed for ctxt and parent values depend partly on the crate size and partly on the form of the code. For both fields, values needing more than 15 bits are very rare, and most crates won’t hit these limits.

• The ctxt is stored inline in every format (Every ctxt must fit in 29 bits; if we ever hit that we’d have many gigabytes of contexts, and certainly would have OOM’d anyway.) This means reading the ctxt never requires checking the interner. This is good because the ctxt is often consulted by itself. It also means we don’t need to store the ctxt in the interner table, which we achieve by using SpanDataNoCtxt, which minimizes the number of unique values that need to be interned.

• The use of repr(packed(4)) means Span has an alignment of 4 bytes, which keeps many types that contain spans (e.g. AST nodes) smaller. repr(packed(1)) isn’t worth it; it only shrinks a few types and performance is a tiny bit worse.

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

Tuple Fields

0: u64