How does compiler fetch elements from array of objects in constant time?

Question

Whenever we want to fetch elements based on index from an array, I learned that the compiler just does something like this to fetch the element in constant time:

array_addr + ele_size * (i - first_index) (where the ele_size depends on the type of the elements present in an array, e.g. for array[int] the ele_size will be 4 bytes)

So how does compiler fetch elements from array[object] in constant time, when each object could have a different size (in memory)?

PS: Question is not specific to any language

question from:https://stackoverflow.com/questions/65557392/how-does-compiler-fetch-elements-from-array-of-objects-in-constant-time

Answer 1

So how does compiler fetch elements from array[object] in constant time (as the size of the objects could vary)?

Well, the expression that is being evaluated is:

array_addr + ele_size * (i - first_index)

where ele_size is a constant that depends on the (compile time) type of the array, and first_index is also typically a constant; e.g. zero for C, C++, Java, etcetera.

That is one subtraction (when first_index is not the constant zero), one multiplication, one addition, and possibly a memory fetch or two.

Either way, the number of machine instructions required to perform the calculation is a constant. Hence (modulo quibbling about variable memory fetch times, pipeline effects, etc) the time taken for one such computation will be a constant ... irrespective of the values of the notional expression parameters.

---

^{Quibble: The compiler doesn't fetch the elements. It generates code that will fetch elements ... when the code is executed.}