Slice Bounds Checks and the Conditions for Eliding Them

A pointer and a length are two values that must agree. Nothing in the machine model forces the agreement, so a function that receives them separately can index past the end by computing a valid address. A slice, a descriptor pairing a pointer with a length, makes the agreement an invariant of the value rather than a convention between functions. Every index into it then has a fact to check against, and the check is cheap: one comparison of the index against the length.

The cost is a branch on the hot path. The design question for a language is therefore not whether to check but where the check is redundant, because a check that the compiler can prove unnecessary costs nothing at run time. The engineering is in making that proof possible.

The descriptor makes the check possible

A slice value is two machine words on a 64-bit target: a pointer to the first element and an integer length. Indexing computes ptr + i * sizeof(T) and compares i against the length. The comparison is against an unsigned value in the languages that do this well, which is what makes a negative index safe without a second check: a signed negative index converted to unsigned is enormous, so the single unsigned comparison rejects it.

// A slice header, and the check the compiler emits for s[i].
type slice struct {
    data uintptr
    len  int
    cap  int
}

func at(s []byte, i int) byte {
    // 0 <= i < len(s), evaluated as one unsigned compare
    if uint(i) >= uint(len(s)) {
        panic("index out of range")
    }
    return s[i]
}

Three words rather than two when capacity is tracked separately, which Go does: len is the number of addressable elements, cap is the number the backing array has room for, and slicing operations may extend a slice up to cap. The distinction is what makes append able to write past len in its own implementation while user code cannot. Rust’s slice is a pointer and a length only, and capacity belongs to the owning Vec rather than to the borrowed view.

The check is per index expression. A loop that indexes the same slice on every iteration checks on every iteration unless the compiler removes the check, and a nested loop over two slices checks twice per inner iteration. That is the cost being traded against.

What the check actually protects

Bounds checks protect the address computation, not the object graph. They guarantee that the access lands inside the region the slice describes. They do not guarantee that the region is still the one the program intended: a slice that was created from a buffer which has since been freed, or a slice whose backing array has been reallocated, passes every bounds check while pointing at memory that no longer belongs to it. A slice makes spatial errors checkable and leaves temporal errors to ownership.

The language’s type system supplies the rest of the temporal guarantee differently in each case. In Rust, a slice borrows from an owner, and the borrow checker prevents the owner from being freed or mutated while the borrow is live; the bounds check is the runtime half of a guarantee whose other half is static. In Go, the garbage collector keeps the backing array alive as long as any slice refers to it, so the temporal question is answered by reachability rather than by a static rule, and the check is the whole of the spatial guarantee.

Bounds checks also do not protect against an incorrect length. A slice constructed with a length larger than its backing array, which a safe language’s standard library will not do but unsafe code and foreign-function interfaces can, makes the check agree with a false invariant. The descriptor is only as trustworthy as the code that built it.

The branch, and what it costs when it stays

On the common architectures a bounds check is a compare and a conditional branch, and the branch is almost never taken. The direct cost is therefore small in throughput terms and larger in code size: each check is a few instructions, and a function with many indexing expressions grows accordingly. Instruction cache pressure is the reason heavily inlined numeric code sometimes performs worse with checks than without, even though each individual check is cheap.

The indirect cost is the one that matters for optimisation. A bounds check is a potential trap, and a potential trap is a barrier to reordering. The compiler cannot move a load that might trap across another side effect without proving the trap cannot occur, and it cannot vectorise a loop whose iterations might each trap. A loop that would otherwise become a four-wide vector operation with a single tail may stay scalar because each iteration carries a branch. Removing the checks is therefore often worth more than the branches themselves.

There is a further asymmetry: the panic path is cold code that the compiler must keep somewhere. In a function with a dozen checks, the failure paths add up, and they are not shared unless the compiler is willing to route them through a common call. Implementations usually do exactly that, emitting one out-of-line call per function that takes the index and length as arguments.

Proving a check away

The conditions under which a check can be removed are narrow, and each corresponds to a fact the compiler can establish about the values involved.

The simplest is a constant index into a fixed-size array. If the index is a literal and the array’s length is known at compile time, the comparison is evaluated during compilation, and an out-of-range literal is rejected rather than checked. Languages that treat fixed-size arrays as distinct from slices get this for free; a slice whose length the compiler can constant-fold does too.

The second is a loop whose induction variable is bounded by the length the check uses. A canonical loop over a slice compares the counter against len(s) and increments by one, so every iteration’s index is provably less than the length, and the check inside the body is redundant. Recognising this requires the compiler to relate the loop condition to the check’s operands, which is why the optimisation is described as a data-flow analysis over range facts rather than a peephole rule.

// The check in the body is redundant: the loop condition already bounds i.
for i in 0..v.len() {
    total += v[i];
}

The third is a length comparison hoisted out of a loop. If the code checks i + n <= len before a loop that indexes i..i+n, the compiler can use that fact to discharge each of the n checks inside, provided nothing in the loop can change the length. Mutation is the obstacle: a call that might append to the slice, or take a mutable reference to it, invalidates the fact. This is why the optimisation survives in tight numeric loops and vanishes in code that touches containers.

The fourth is a shared prefix. Two slices derived from the same allocation have related lengths, and when one is a prefix of the other, a fact established for the shorter slice holds for the longer one: an index below the shorter length is also below the longer length, though not the reverse. That is rare outside inlined code, because the derivation usually crosses a function boundary.

When the branch cannot go away

The cases where the proof fails are as informative as the ones where it succeeds.

A length loaded from memory is not a constant. If the slice descriptor is a field of a struct the compiler cannot track, each check must reload the length, and no fact survives across a call that might write to the struct. Aliasing defeats the analysis: in a language with raw pointers, a store through a pointer might have changed the length, so the compiler must assume it did.

Index arithmetic defeats the range analysis when it is not affine. An index computed as a hash, a table lookup, or a value returned from a function has no interval the compiler can bound, and the check stays. The same applies to an index whose upper bound is derived from a length that is itself computed, since the two computations are not related in the intermediate representation.

Dynamic languages and runtimes with a JIT take a different route: the check is compiled in, and the runtime specialises the loop after observing that a particular length is used, then recompiles with the check removed for that case and a guard that falls back if the length changes. The guard is a check, but it is one per loop rather than one per element, which is the same trade the static analysis makes with a proof.

Manual elision and its cost

The escape hatch is an unchecked accessor. Rust exposes one as an unsafe method on slices, so the call site is marked and the obligation is visible; Go has no language-level equivalent and leaves the decision entirely to the compiler’s analysis. Where an unchecked access is available the index is not verified, and a wrong claim produces exactly the out-of-bounds write the checks exist to prevent.

The honest way to use the escape hatch is to place it where the proof is trivial and local: an index just computed from a length, a loop counter bounded by the same expression. The dishonest way is to place it where the check is hot and the reasoning is vague, which converts a measurable cost into an unmeasurable bug. Languages that report which checks remain after optimisation make the first pattern easy to audit, because the surviving checks are exactly the places where the compiler could not see a reason to trust the index.