Why Assigning Array Elements from the End First Speeds Up Go Code

The author discovered the github.com/planetscale/vtprotobuf library, which claims to be the fastest Go protobuf implementation. Its marshal function writes to a byte slice by assigning the tail elements first and then moving backward toward the head.

Key snippet from MarshalToSizedBufferVT shows this pattern:

func (m *Child) MarshalToSizedBufferVT(dAtA []byte) (int, error) {
    if m == nil {
        return 0, nil
    }
    i := len(dAtA)
    if len(m.ChildName) > 0 {
        i -= len(m.ChildName)
        copy(dAtA[i:], m.ChildName)
        i = protohelpers.EncodeVarint(dAtA, i, uint64(len(m.ChildName)))
        i--
        dAtA[i] = 0x12
    }
    if m.ChildId != 0 {
        i = protohelpers.EncodeVarint(dAtA, i, uint64(m.ChildId))
        i--
        dAtA[i] = 0x8
    }
    return len(dAtA) - i, nil
}

The author hypothesised that writing the larger index first lets the compiler infer that later accesses with smaller indices are safe, thus removing the bounds‑check code.

Two equivalent functions illustrate the effect:

func f1(arr []byte) {
    arr[0] = 1
    arr[9] = 2
}

func f2(arr []byte) {
    arr[9] = 2
    arr[0] = 1
}

Running go tool compile -d=ssa/check_bce/debug=1 bce.go produces the following SSA output:

func f1(arr []byte) {
    arr[0] = 1 // still has bounds check
    arr[9] = 2 // still has bounds check
}

func f2(arr []byte) {
    arr[9] = 2 // still has bounds check
    arr[0] = 1 // no bounds check found, it was eliminated
}

The missing check in f2 demonstrates that when a larger index is accessed first, the compiler learns the relationship 0 <= index < len and can safely drop the subsequent check for the smaller index.

This behaviour is documented in the Go compiler source file cmd/compile/internal/ssa/prove.go. The OpIsInBounds operation records an index‑in‑bounds proof; when true, the compiler updates its knowledge that 0 <= a0 < a1 (signed) or a0 < a1 (unsigned), allowing later accesses to be proven safe.

Consequently, vtprotobuf’s strategy of assigning array elements from the tail first reduces the number of generated bounds‑check instructions, leading to measurable performance gains.