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

Answer 1

array[object] and array[int] are actually very similar, since an array of objects doesn't usually store the actual objects directly next to each other like this:

// [ _______Person________,  _____Pet_____,  _______Person_______ ]
   [ Name,    Age, Country,  Name,    Type,  Name,   Age, Country ]
   [ "Lucas", 37,  FRANCE,   "Misty", CAT,   "Emma", 22,  SWEDEN  ]    

Instead, the array just stores references (pointers to the objects), which are all of the same size (32 or 64-bit int):

// [ ______Person______,  ________Pet_______,  ______Person______ ]
   [ address of Person,   address of Pet,      address of Person  ]
   [ 0xaba11b8ae55fa4d2,  0xb8e4f4adea6be036,  0x5ce415a69ca50222 ]

Then the data for each object is found at the specific memory address and can occupy however many bytes is needed.

You might find this question about how object[] is stored in memory (in C#) useful.

Answer 2

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.}