数组与记录，动态下标与静态字段

Question

因此，我使用 Robert W. Sebesta 的书“编程语言概念”学习了编程语言。有一个有趣的段落将 heterogeneous array 与 record 进行了比较。显然，与静态字段名称相比，数组的访问时间要慢得多，因为下标是动态的。

问题：那为什么会更快呢？跟Stack和Heap内存的利用率有关系吗？

第 265 页，第 6 章：

Records are used when the collection of data values is heterogeneous and the different fields are not processed in the same way. Also, the fields of a record often need not be processed in a particular order. Field names are like literal, or constant, subscripts. Because they are static, they provide very efficient access to the fields. Dynamic subscripts could be used to access record fields, but it would disallow type checking and would also be slower.

Answer 1

首先我想提一下，“性能”的概念并不真正脱离实际的硬件和低级实现。当本书讲述某种数据组织方式“更快”时，它对实际 compiler/interpreter 实现和硬件（von Neumann architecture、CPU 指令集、内存布局做出了一些假设).

说到这里，让我们谈谈静态记录、同构和异构数组的实现可能存在的差异。

1。静态记录

struct Point {
    int x;
    int y;
};

这是一个简单的 C++ 结构。当你这样做时：

Point *p = new Point();

内存分配器在堆上分配8个字节，并将该块的起始地址存储在p。

编译器预先知道 Point 的大小（8 字节），因为 Point 编译器的每个字段都知道它的大小和移位（即 y 的大小为 4，移位为 4）。

当你访问Point（p -> x）的一个字段时，编译器将其替换为计算字段x的实际内存地址（p的地址+[的移位=19=]) 并访问该地址。没有任何运行时开销。

2。齐次数组

int *arr = new int[10];

这是一个简单的 C++ 同构数组。与struct类似，allocator在堆上分配4 * 10字节，并将其起始地址存储在arr.

中

当你访问数组的元素时，arr[i]，编译器知道 arr 的地址，它的元素的大小（它们是相同的，因为数组是同类的），所以它可以将您访问的内存地址计算为 arr + i * element_size（大多数体系结构上的单个 CPU 指令）。

同样，如果您不计入访问 i 除了 arr.

，开销也不大

3。异构数组

现在，这就是事情变得有趣的地方。异构数组没有直接的低级表示。有多种可能的实现可以将这个高级概念映射到实际的内存和机器代码中。

让我们考虑其中之一。

enum ElType {
    INT, POINT
};

struct ArrEl {
    ElType type;
    char* elPtr;
};

ArrEl *arr = new ArrEl[10];

arr[1].type = POINT;
arr[1].elPtr = (char*)(new Point {3,4} );

arr[2].type = INT;
arr[2].elPtr = (char*)(new int {2} );

注意，由于数组现在可以存储任何类型的元素（仅针对此演示 int 或 Point）：

数组元素可以有不同的大小（Point是8个字节，int是4），所以实际元素必须分配在堆上，数组只存储指针（另一种方法是为每个元素分配等于最大可能元素大小的内存，在一般情况下这太浪费了；注意：请参阅下面的评论）。
要了解存储元素的实际类型，必须存储额外的元数据。这种方式选择了存储在数组中，但是大多数实际实现（包括python and java) store it together with the actual object, as an "object header". See the simplified implementation here.

现在要访问此类数组的元素，必须检查此元数据：

ArrEl el = arr[2];

if (el.type == INT) {
  int *value = (int *) el.elPtr;
  std::cout <<  *value;
} else if (el.type == POINT) {
  Point *p = (Point *) el.elPtr;
  std::cout <<  p->x;
}

访问异构数组的开销包括额外的indirection：首先你必须访问数组的元素，然后根据指针指向堆上的实际值，并检查元数据。

还有存储所有指针和元数据的额外内存开销。当您将“简单”类型的同类数组（例如 int）与可以存储的异构数组（例如 int 和 float 进行比较时，这一点尤为明显（注意：请参阅下面的评论）。

好的，现在，当我给出了为什么异构阵列在理论上会很慢的一般概念后，让我们来谈谈现实世界。

大多数具有异构数组的语言的现代 VM 都具有 JIT。与静态编译器（如 C++）相反，JIT 可以对执行的代码做出一些乐观的假设，如果这些假设失败，则在运行时将代码重新编译为更悲观的变体。

回到数组，虽然Javascript和Python等动态语言中的数组是异构的，但有可能当数组以同构方式使用时，JIT将其编译为同构在内部！例如，V8 certainly does that。我认为 Python 目前不会这样做，但将来可能会这样做。

此外，现代 optimizing compilers, including static compilers 可以以您意想不到的方式重写您的代码。例如，您的代码创建了一个对象并对其字段执行了一些操作，但实际上编译器会将字段访问替换为 CPU 寄存器。根本没有创建“实际”对象。

这就是为什么用实际基准验证关于性能的理论假设总是很重要的原因。

P.S。此演示中的所有 C++ 代码都不是惯用的、不安全的和糟糕的。不要在家里使用它。

数组与记录，动态下标与静态字段

Array vs Record, Dynamic Subscripts vs Static Field

arrays

performance

programming-languages

1。静态记录

2。齐次数组

3。异构数组