23

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

由于 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 分析）当数据集变大时，最好迭代动态数组以避免行主要索引？

4

5 回答 5

31

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

首先让我们澄清一些术语

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

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

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

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

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

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

引入更多维度

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

如果您通过索引访问，请注意内存是线性的。如果真实数组的后面维度不是 2 的倍数，编译器将需要生成乘法。例如，在数组int arr[4][12];中，第二维是 12。如果您现在将其作为arr[i][j]wherei和jare index 变量访问，则线性内存必须被索引为12 * i + j。所以编译器必须生成代码来与一个常量相乘。复杂性取决于常数与 2 的幂的“距离”。这里生成的代码可能看起来有点像计算(i<<3) + (i<<2) + j访问数组中的元素。

如果您从指针构建二维“数组”，则维度的大小无关紧要，因为结构中有引用指针。在这里，如果您可以编写arr[i][j]，则意味着您将其声明为 example int* arr[4]，然后将malloc()四个 12int秒的内存块写入其中。请注意，您的四个指针（编译器现在可以将其用作基础）也会消耗内存，如果它是一个真正的数组，则不会占用这些内存。另请注意，此处生成的代码将包含双重间接：首先代码通过ifrom加载一个指针arr，然后它将int从该指针加载一个 by j。

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

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

地点很重要

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

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

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

于 2013-07-21T19:15:17.113 回答
4

至于哪种选择提供更好的性能，那么答案将在很大程度上取决于您的具体情况。了解一种方法是否更好或它们是否大致等效的唯一方法是测量应用程序的性能。

一些可能是一个因素的因素是：您执行此操作的频率、数组/数据的实际大小、系统有多少内存以及系统管理内存的能力。

如果您有幸在这两种选择之间做出选择，那一定意味着尺寸已经确定。然后，您不需要您说明的多重分配方案。您可以对二维数组执行单个动态分配。在 C 中：

int (*array)[COLUMNS];
array = malloc(ROWS * sizeof(*array));

在 C++ 中：

std::vector<std::array<int, COLUMNS>> array(ROWS);

只要COLUMNS确定了，您就可以执行一次分配来获得您的二维数组。如果两者都没有确定，那么无论如何您都无法选择使用静态数组。

于 2013-07-21T17:57:11.913 回答
4

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

于 2013-07-21T18:02:56.290 回答
1

通常在内存消耗和速度之间进行权衡。根据经验，我见证了在堆栈上创建数组比在堆上分配更快。随着数组大小的增加，这变得更加明显。

您始终可以减少内存消耗。例如，您可以使用 short 或 char 代替 int 等。

随着数组大小的增加，尤其是在使用 realloc 的情况下，可能会有更多的页面替换（向上和向下）以保持项目的连续位置。

您还应该考虑到可以存储在堆栈中的东西的大小有一个下限，对于堆，这个限制更高，但正如我所说的性能成本。

于 2013-07-21T17:57:33.637 回答
-4

Stalk 内存分配提供比堆更快的数据访问。如果没有，CPU 会在缓存中查找地址，如果在缓存中找不到地址，则会在主存中查找。Stalk 是缓存后的首选位置。

于 2013-07-22T00:56:05.467 回答