静态数组与动态数组的 C/C 性能

Question

当性能对应用程序至关重要时，是否应该考虑是否在堆栈和堆上声明数组？请允许我概述一下为什么会想到这个问题。

由于 C/C++ 中的数组不是对象并且衰减为指针，因此编译器使用提供的索引来执行指针算术以访问元素。我的理解是，当超过第一个维度时，此过程 不同于 静态声明的数组和动态声明的数组。

如果我要在堆栈上声明一个数组，如下所示；

   int array[2][3] = { 0, 1, 2, 3, 4, 5 }
  //In memory        { row1 } { row2 }

该数组将以 Row Major 格式存储在内存中，因为它存储在连续的内存块中。这意味着当我尝试访问数组中的元素时，编译器必须执行一些加法和乘法来确定正确的位置。

因此，如果我要执行以下操作

  int x = array[1][2]; // x = 5

然后编译器将使用此公式，其中：

i = 行索引 j = 列索引 n = 单行的大小（这里 n = 2）

数组 = 指向第一个元素的指针

  *(array + (i*n) + j)
  *(array + (1*2) + 2)

这意味着如果我要遍历这个数组来访问它的每个元素，那么每次按索引访问都会执行一个额外的乘法步骤。

现在，在堆上声明的数组中，范式不同，需要多阶段解决方案。注意：我也可以在这里使用 C++ new 运算符，但我相信数据的表示方式没有区别。

   int ** array;
  int rowSize = 2;
  // Create a 2 by 3 2d array on the heap
  array = malloc(2 * sizeof(int*));
  for (int i = 0; i < 2; i++) {
      array[i] = malloc(3 * sizeof(int));
  }

  // Populating the array
  int number = 0;
  for (int i = 0; i < 2; i++) {
      for (int j = 0l j < 3; j++) {
          array[i][j] = number++;
      }
  }

由于数组现在是动态的，它的表示是一维数组的一维数组。我会尝试画一张ascii图片…

               int *        int int int
int ** array-> [0]          0   1   2
               [1]          3   4   5

这意味着不再涉及乘法，对吗？如果我要执行以下操作

int x = array[1][1];

然后这将在 array[1] 上执行间接/指针算术以访问指向第二行的指针，然后再次执行此操作以访问第二个元素。我这样说对吗？

现在有了一些上下文，回到问题。如果我正在为需要清晰性能的应用程序编写代码，例如渲染帧大约需要 0.016 秒的游戏，我是否应该三思而后行在堆栈和堆上使用数组？现在我意识到使用 malloc 或 new 运算符有一次性成本，但是在某个点（就像 Big O 分析）当数据集变大时，最好迭代动态数组以避免行主要索引？

原文由 Paul Renton 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这些将适用于“普通”C（不是 C++）。

首先让我们澄清一些术语

“static”是 C 中的一个关键字，如果将其应用于函数内声明的变量，它将彻底改变分配/访问变量的方式。

变量（包括数组）可能位于 3 个位置（关于 C）：

• 堆栈：这些是没有 static 的函数局部变量。
• 数据部分：程序启动时为这些分配空间。这些是任何全局变量（无论是 static 与否，关键字都与可见性有关），以及声明的任何函数局部变量 static 。
• 堆：由指针引用的动态分配的内存（ malloc() & free() ）。您只能通过指针访问这些数据。

现在让我们看看如何访问一维数组

如果您访问具有常量索引的数组（可能是 #define d，但不是 const 在纯 C 中），该索引可以由编译器计算。如果 Data 部分 中有一个真正的数组，它将被无任何间接访问。如果您在 Stack 上有一个指针 ( Heap ) 或数组，则始终需要间接寻址。因此，具有这种访问类型的 Data 部分 中的数组可能会快一点。但这并不是一件可以改变世界的非常有用的事情。

如果您使用索引变量访问数组，它本质上总是衰减为指针，因为索引可能会更改（例如，在 for 循环中递增）。对于此处的所有类型，生成的代码可能非常相似甚至相同。

引入更多维度

如果您声明一个二维或更多维数组，并通过常量部分或全部访问它，智能编译器可能会像上面那样优化这些常量。

如果您通过索引访问，请注意内存是线性的。如果真实数组的后面维度不是 2 的倍数，编译器将需要生成乘法。 For example in the array int arr[4][12]; the second dimension is 12. If you now access it as arr[i][j] where i and j are index variables ，线性内存必须被索引为 12 * i + j 。所以编译器必须生成代码来与一个常量相乘。复杂性取决于常数与 2 的幂的“距离”。这里生成的代码可能看起来有点像计算 (i<<3) + (i<<2) + j 以访问数组中的元素。

如果您从指针构建二维“数组”，则维度的大小无关紧要，因为结构中有引用指针。 Here if you can write arr[i][j] , that implies you declared it as for example int* arr[4] , and then malloc() ed four chunks of memory of 12 int 每个人都投入其中。请注意，您的四个指针（编译器现在可以将其用作基础）也会消耗内存，如果它是一个真正的数组，则不会占用这些内存。另请注意，此处生成的代码将包含双重间接：首先代码通过 i 从 arr 加载一个指针，然后它将加载一个 int 从那个指针由 j 。

如果长度与 2 的幂“相距甚远”（必须生成如此复杂的“乘以常数”代码来访问元素），那么使用指针可能会生成更快的访问代码。

正如 James Kanze 在他的回答中提到的，在某些情况下，编译器可能能够优化对真正多维数组的访问。这种优化对于由指针组成的数组是不可能的，因为在这种情况下，“数组”实际上不是线性内存块。

地点很重要

如果您正在为通常的桌面/移动架构（英特尔/ARM ³²⁄₆₄ 位处理器）进行开发，则位置也很重要。这可能是缓存中的内容。如果您的变量由于某种原因已经在缓存中，它们将被更快地访问。

就局部性而言， 堆栈 始终是赢家，因为 堆栈 被频繁使用以至于它很可能总是坐在缓存中。所以小阵列最好放在那里。

使用真正的多维数组而不是由指针组成一个数组也可能在这方面有所帮助，因为真正的数组总是一个线性的内存块，因此它通常可能需要更少的缓存块来加载。分散的指针组合（即如果单独使用 malloc() ed 块）相反，可能需要更多的缓存块，并且可能会增加缓存线冲突，具体取决于块在堆上的物理结束方式。

原文由 Jubatian 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

在 C++ 中实现二维数组的常用方法是将其包装在一个类中，使用 std::vector<int> 并具有计算索引的类访问器。然而：

任何有关优化的问题都只能通过测量来回答，即便如此，它们也仅对您正在使用的编译器、在您进行测量的机器上有效。

如果你写：

 int array[2][3] = { ... };

然后是这样的：

 for ( int i = 0; i != 2; ++ i ) {
    for ( int j = 0; j != 3; ++ j ) {
        //  do something with array[i][j]...
    }
}

很难想象一个编译器实际上不会生成以下内容：

 for ( int* p = array, p != array + whatever; ++ p ) {
    //  do something with *p
}

这是最根本的优化之一，并且已经持续了至少 30 年。

如果您按照您的建议动态分配，编译器将 无法 应用此优化。甚至对于单次访问：矩阵的局部性较差，并且需要更多的内存访问，因此性能可能会降低。

如果您使用 C++，通常会编写一个 Matrix 类，使用 std::vector<int> 作为内存，并使用乘法显式计算索引。 （改进的局部性可能会带来更好的性能，尽管有乘法。）这可能会使编译器更难进行上述优化，但如果这是一个问题，你总是可以提供专门的迭代器来处理这个问题一个特例。您最终会得到更具可读性和更灵活的代码（例如，维度不必是恒定的），而性能损失很小或没有损失。

原文由 James Kanze 发布，翻译遵循 CC BY-SA 3.0 许可协议