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

Question

当性能对应用程序至关重要时,应该考虑是否在堆栈上声明一个数组而不是堆？请允许我概述为什么会出现这个问题.

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

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

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

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

所以如果我要做以下事情

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

然后编译器将使用以下公式:

i =行索引j =列索引n =单行的大小(此处n = 2)
array =指向第一个元素的指针

  *(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分析一样)当数据集变大时,最好通过动态数组迭代来避免行主索引？

Answer 1

这些将适用于"普通"C(不是C++).

首先让我们清楚一些术语

"static"是C中的关键字,如果将变量应用于函数内声明的变量,它将极大地改变变量的分配/访问方式.

有3个位置(关于C),其中一个变量(包括数组)可能位于:

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

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

如果访问具有常量索引的数组(可能是#defined,但不是const普通的C),则可以由编译器计算此索引.如果在" 数据"部分中有一个真实数组,则无需任何间接访问它.如果堆栈上有指针(Heap)或数组,则始终需要间接.因此,具有此类访问权限的数据部分中的数组可能会快得多.但这不是一个可以改变世界的非常有用的东西.

如果访问具有索引变量的数组,则它基本上总是衰减到指针,因为索引可能会更改(例如for循环中的增量).对于所有类型,生成的代码可能非常相似甚至相同.

带来更多尺寸

如果声明一个两维或更多维数组,并通过常量部分或完全访问它,智能编译器可能会如上所述优化这些常量.

如果您通过索引访问,请注意内存是线性的.如果真实数组的后续维度不是2的倍数,则编译器将需要生成乘法.例如,在数组中int arr[4][12];,第二个维度为12.如果现在将其作为arr[i][j]where i和jindex索引变量进行访问,则必须将线性内存索引为12 * i + j.因此编译器必须生成代码以在此处与常量相乘.复杂性取决于常数与2的幂的"远"程度.这里得到的代码看起来有点像计算(i<<3) + (i<<2) + j访问数组中的元素.

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

如果长度与2的幂"相差"(因此必须生成复杂的"乘以常数"代码以访问元素),则使用指针可以生成更快的访问代码.

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

地方很重要

如果您正在开发通常的桌面/移动架构(Intel/ARM 32/64位处理器),那么地方也很重要.这可能就是坐在缓存中.如果您的变量由于某种原因已经在缓存中,则可以更快地访问它们.

在局部性方面,Stack总是赢家,因为Stack经常被使用,因此很可能总是位于缓存中.所以小阵列最好放在那里.

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