| HN Mirror

My thinking is this:

To access an array via index, you basically have to take the reference to the array, the index (i), and generally multiply (i) by the space set aside for each element (e).

i * e

If you've offset the array, you have to take the offset index (o), and call a mapping function (m) that maps (o) to (i), so the result can be multiplied by (e). Though it should be said there is another theoretical alternative: you can figure out a way to map (o) directly to (i * e) without the intermediate operation or mapping (o) to (i).

Where (i) and (o), and the relationship between them, is known at compile time, you can theoretically get the compiler to magic that operation away.

But where (o) is only known at run time, you have to first fetch/generate (o), apply (m) to map it back to (i), then multiply (i) by (e) before knowing how to access an array.

If you know fetch/generate (i) at run-time, you don't need the map operation (m), you just multiple (i) by (e) and there's your array reference. But otherwise there's an operation (m) sitting around whose cost must be paid.

You can't handwave it away via reliance on cpu parallel instructions or anything like that because its by definition a serial operation: you can't multiply by (e) until after you've got (i), you can't get (i) until you've applied (m), and you can't apply (m) until after you've fetched (o).

Now where the cost of (m) is sufficiently low relative to other operations, or where the number of array accesses are low, the two may appear sufficiently similar and offset array access might appear practically costless. But the point where we generally care about these things is because we're doing them a very very large number of times on a sufficiently large number of indexes that can't be known or optimised away ahead of time.

And it is worth pointing out that addition operations and things are remarkably cheap in general. But if you're accessing these arrays themselves in order to do addition operations or something similar on their contents, then it may still take up a relatively high proportional amount of time relative to the entirety of the program/operation.

Avoiding theoretical discussion on the possibility of functions (m) that map (o) directly to (i * e) while being equal or cheaper than (i * e) in cost, there is another possibility that might appear in practice...

If the original array access operations are not optimal, (or slowed down due to other issues, such as in-optimal caching or memory access, then it may be possible for both offsets and array access to be equal in practice. If indexing by both (i) and indexing by (o) are both seeing an additional step between the getting of the index and multiplying by element size, or if there is sufficient lag because the CPU isn't doing work optimally, then in profiling and practice, both would appear to be running to the same speed. But this wouldn't imply you've optimised offset indexes, it implies your regular indexes and operations aren'y optimised enough already....that's why it appears you can get something for free.