Why array indices start at zero

Every programmer meets this on day one. The first element of an array is a[0], the last is a[length - 1], and somewhere in that first week you write a loop that runs one step too far and hit an off-by-one error you don’t yet have the vocabulary for. Most of us shrug, memorise the rule, and move on.

The rule isn’t arbitrary. But the reason usually given for it, that it saves an arithmetic operation, is wrong. I believed that one for years and only found out otherwise while writing this.

An index is a distance, not a position

An index doesn’t say which element. It says how far from the start.

When you write a[i] in C, the compiler isn’t counting elements. It’s doing arithmetic on an address:

a[i]  ≡  *(a + i)

a is where the array begins, i is how far to travel from there. The first element sits right at the beginning, zero steps away, so its index is 0 — that falls out of the arithmetic rather than being chosen.

Both rows are the same memory; only the labels changed. In the top row the label already equals the distance, so there’s nothing to work out. In the bottom row it’s always one more, so every access has to undo it.

This is the usual explanation for C and BCPL before it. BCPL, written by Martin Richards in 1967, treated an array as a pointer to a block of words where V!0 meant “the word at V”, and C inherited the memory model along with the numbering. The history is contested, though: Mike Hoye went looking for a primary source and couldn’t find one, arguing that the pointer-arithmetic story is post-facto and that the real saving was in 1960s compile times rather than run times. That turns out to matter later. (Zero-based numbering has the longer history.)

The same logic runs through ranges. Write them half-open — include the bottom, exclude the top — and the length is simply b - a with no +1, while adjacent ranges share a number: [0, k) and [k, n) tile [0, n) exactly, with k written once. Which is why nobody has to think about this loop:

for (int i = 0; i < n; i++) { ... }

The bound is n, which is also the length. No n - 1, no <= to get wrong. Dijkstra made this case in 1982 and reached zero from the opposite end, with no hardware in the argument at all — only which range convention behaves best. He ends up where the diagram does: a subscript “equals the number of elements preceding it in the sequence.”

So is it faster? I was certain it was

This is the part I got wrong for years, and the reasoning is almost too tidy to question: a[i - 1] has one more arithmetic operation than a[i], so one-based indexing must cost a subtraction on every access. It sounds right, and I never checked it until I sat down to write this.

One clarification first, since Big O gets dragged into this a lot:

Big O doesn’t measure instruction counts. It measures how cost grows with input size. Indexing is O(1) under either convention — one step, whatever the array’s size. A subtraction is a constant, and Big O deliberately discards constants.

So the question is only about that constant. gcc 13.3, x86-64, -O2:

int get0(const int *a, long i) { return a[i];     }   // zero-based
int get1(const int *a, long i) { return a[i - 1]; }   // one-based

get0:  mov  eax, DWORD PTR [rdi+rsi*4]
get1:  mov  eax, DWORD PTR -4[rdi+rsi*4]

One instruction each. If you haven’t read x86 before: rdi holds the pointer a and rsi holds i, because that’s where the two arguments arrive, and [rdi+rsi*4] means start at a and move i lots of 4 bytes, 4 being the width of an int. The - 1 never became a subtraction. It became the -4 in front of the brackets — shift the whole calculation back by one int — and the chip works that last term into the address in the same step as the read. There was nowhere for the operation I was so sure about to happen. (Same result at -O1 through -O3 and -Os.) Loops are starker still: gcc emits byte-identical machine code for a zero-based and a one-based sum, walking a pointer from one end of the array to the other and never tracking i at all (strength reduction).

Two dimensions is where I expected to be vindicated, because the row correction gets multiplied rather than added. Write a[(r-1)*cols + (c-1)] exactly like that and you do pay — 200 million random accesses into a 64×64 matrix, best of five:

That middle row is a real 20% penalty. (The folded row came out a shade faster than zero-based, reproducibly — with identical instruction counts that’s code layout rather than arithmetic, but it does make the direction of the result hard to argue with.) Now look at that third row, and then at what the two sides of this line have in common:

base + ((r-1)·cols + (c-1))·4   ==   [base − (cols+1)·4] + (r·cols + c)·4

Both sides land on the same byte. The right-hand version has moved the correction off the per-access arithmetic and into the base pointer, and it can do that because the whole correction is (cols + 1) — no r in it, no c, the same number for every element in the array. Work it out once when the array is created and every access afterwards is ordinary zero-based arithmetic. That isn’t a trick I invented for the benchmark: it’s how one-based arrays are built. The standard addressing formula picks whatever base makes the indices come out right, one that “may not be the address of any element” at all.

So the middle row isn’t the cost of one-based indexing. It’s the cost of emulating one-based indexing by hand, in a zero-based language, never giving the compiler a chance to hoist a constant. I had been mistaking my own workaround for the language’s design.

At every dimension, then, no difference. The subtraction never survives to runtime, because it is always a constant, and constants live inside addresses instead of instructions. (All of this is gcc on x86-64; AArch64 has the same mechanism but I haven’t measured it there.) That also lines up with Hoye’s argument from earlier: whatever was being saved in the 1960s, it wasn’t cycles at run time.

The case for zero was never speed. It’s that the bias terms aren’t there to reason about. i % n lands in [0, n) on its own, ring buffers wrap with (head + 1) % capacity, hash buckets need no adjustment — modular arithmetic agreeing with your indices for free.

The other camp isn’t wrong

Fortran, MATLAB, R, Julia, Lua and others count from one, and they’re not oversights. They’re aimed at people transcribing mathematics, where matrix entries are conventionally written a₁₁ through aₘₙ. If your users turn published formulas into code, matching the notation on the page prevents more bugs than clean address arithmetic does — and as we’ve just seen, it costs nothing to do so.

The trade

Zero-based indexing will not make your code faster. What it does is make the arithmetic agree with itself: lengths, offsets, differences, moduli and range bounds all line up without correction terms.

The cost is that the fifth element is a[4], which never quite stops being awkward to say out loud. It looked arbitrary to me on day one, and stopped the first time I split a buffer at k and noticed there was nothing to adjust on either side.