当性能对应用程序至关重要时,是否应该考虑是在堆栈上还是在堆上声明数组?请允许我概述一下为什么会想到这个问题。
由于 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 + (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 分析一样)当数据集变大时,最好遍历动态数组以避免行主要索引?
最佳答案
这些将适用于“普通”C(不是 C++)。
首先让我们明确一些术语
"static"是 C 中的一个关键字,如果它应用于函数内声明的变量,它将彻底改变分配/访问变量的方式。
变量(包括数组)可以在 3 个地方(关于 C):
static
的函数局部变量. static
,关键字与可见性相关),以及声明为 static
的任何函数局部变量。 . malloc()
& free()
)。您只能通过指针访问此数据。 现在让我们看看如何访问一维数组
如果您访问具有常量索引的数组(可能是
#define
d,但在普通 C 中不是 const
),则该索引可以由编译器计算。如果在 Data 部分中有一个真正的数组,则无需任何间接访问即可访问它。如果堆栈上有指针(堆)或数组,则始终需要间接寻址。因此,具有这种访问类型的 Data 部分中的数组可能会快一点。但这不是一件非常有用的事情,可以改变世界。如果您访问一个带有索引变量的数组,它基本上总是衰减为一个指针,因为索引可能会改变(例如在 for 循环中递增)。对于此处的所有类型,生成的代码可能非常相似甚至相同。
引入更多维度
如果你声明一个二维或更多维数组,并通过常量部分或全部访问它,智能编译器很可能会像上面一样优化这些常量。
如果按索引访问,请注意内存是线性的。如果真实数组的后面维度不是 2 的倍数,则编译器将需要生成乘法。例如在数组
int arr[4][12];
中第二个维度是 12。如果您现在访问它为 arr[i][j]
哪里i
和 j
是索引变量,线性内存必须被索引为 12 * i + j
.所以编译器必须在这里生成与常数相乘的代码。复杂性取决于常量与 2 的幂的“远”。这里的结果代码可能看起来有点像计算 (i<<3) + (i<<2) + j
访问数组中的元素。如果您从指针构建二维“数组”,则维度的大小无关紧要,因为您的结构中有引用指针。如果你可以在这里写
arr[i][j]
,这意味着您将其声明为例如 int* arr[4]
,然后 malloc()
编辑了四块内存为 12 int
每一个都投入其中。请注意,您的四个指针(编译器现在可以用作基数)也会消耗内存,如果它是真正的数组,则不会占用这些内存。另请注意,此处生成的代码将包含双重间接寻址:首先,代码通过 i
加载一个指针。来自 arr
,然后它会加载一个 int
从该指针 j
.如果长度与 2 的幂“相距甚远”(因此必须生成复杂的“乘以常数”代码来访问元素),那么使用指针可能会生成更快的访问代码。
如 James Kanze在他的回答中提到,在某些情况下,编译器可能能够优化对真正多维数组的访问。对于由指针组成的数组,这种优化是不可能的,因为在这种情况下,“数组”实际上不是线性内存块。
地点很重要
如果您正在为通常的台式机/移动架构(英特尔/ARM 32/64 位处理器)进行开发,则本地化也很重要。这就是缓存中可能存在的内容。如果您的变量由于某种原因已经在缓存中,它们将被更快地访问。
就局部性而言,堆栈始终是赢家,因为堆栈是如此频繁地使用,以至于它很可能总是位于缓存中。所以小阵列最好放在那里。
使用真正的多维数组而不是从指针组合一个也可能在这方面有所帮助,因为真正的数组始终是一块线性内存,因此它通常可能需要较少的缓存块来加载。分散的指针组合(即如果单独使用
malloc()
ed 块)相反可能需要更多的缓存块,并且可能会增加缓存线冲突,具体取决于块在物理上最终在堆上的方式。
关于c++ - 静态数组与动态数组的 C/C++ 性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17775066/