编译器如何在恒定时间内从对象数组中获取元素？

Question

每当我们想根据索引从数组中获取元素时，我了解到编译器只是做这样的事情来在恒定时间内获取元素：

array_addr + ele_size * (i - first_index) （其中 ele_size 取决于数组中元素的类型，例如，对于 array[int]，ele_size 将是 4 个字节）

那么当每个 object 可能具有不同的大小（在内存中）时，编译器如何在恒定时间内从 array[object] 获取元素？

PS: 问题不特定于任何语言

Answer 1

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

嗯，正在评估的表达式是：

array_addr + ele_size * (i - first_index)

其中 ele_size 是一个常量，它取决于数组的（编译时）类型，并且 first_index 通常也是一个常量；例如C、C++、Java 等为零。

这是一次减法（当 first_index 不是常量零时），一次乘法，一次加法，可能还有一两次内存读取。

无论哪种方式，执行计算所需的 机器指令数 是一个常数。因此（关于可变内存获取时间、流水线效应等的模数争论）一次这样的计算所花费的时间将是一个常数……不管名义表达式参数的值如何。

^{Quibble：编译器不获取元素。它生成代码，将在执行代码时获取元素...。}

Answer 2

array[object] 和 array[int] 实际上非常相似，因为对象数组通常不会像这样将实际对象直接相邻存储：

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

相反，该数组仅存储引用（指向对象的指针），它们的大小都相同（32 位或 64 位 int）：

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

然后在特定的内存地址找到每个对象的数据，并且可以占用需要多少字节。

您可能会发现 this question about how object[] is stored in memory (in C#) 有用。

编译器如何在恒定时间内从对象数组中获取元素？

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

arrays

compiler-construction