logo标签列表

效率：数组 vs 指针

carrayspointersperformancememory-access
67

通过指针进行内存访问比通过数组进行内存访问效率更高。我正在学习C语言，K&R中提到了上述内容。具体来说，他们说：

  

可以通过数组下标实现的任何操作也可以用指针完成。一般来说，指针版本会更快。

我使用Visual C++反汇编了以下代码。（我的处理器是686。我已禁用了所有优化。）

int a[10], *p = a, temp;

void foo()
{
    temp = a[0];
    temp = *p;
}

令我惊讶的是，通过指针进行内存访问需要3条指令，而通过数组访问内存只需要2条指令。以下是相应的代码。

; 5    : temp = a[0];

    mov eax, DWORD PTR _a
    mov DWORD PTR _temp, eax

; 6    : temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

请帮助我理解。我错过了什么？

正如许多答案和评论所指出的那样，我已经将编译时常量用作数组索引，因此通过数组访问可能更容易。下面是使用变量作为索引的汇编代码。现在通过指针和数组进行访问有相同数量的指令。我的更广泛的问题仍然存在。通过指针进行内存访问并没有更有效率。

; 7    :        temp = a[i];

    mov eax, DWORD PTR _i
    mov ecx, DWORD PTR _a[eax*4]
    mov DWORD PTR _temp, ecx

; 8    : 
; 9    :    
; 10   :        temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx
7
虽然我对汇编语言不太熟悉，但我认为你应该尝试使用“temp = a[k];”，其中k是一个在编译时不知道的变量。 - Drakosha
@Drakosha，谢谢。我没有意识到这一点。按照您的建议进行操作会导致通过数组访问内存的3条指令（获取索引，获取数组元素的值，存储在临时变量中）。但是我仍然无法看到效率。 :-( - Abhijith Madhav
2
有人提到K＆R在长迭代的情况下说过这句话。也就是说，在a[i++]与*p++之间。我认为那时候与你的问题所问的是完全不同的。 - Johannes Schaub - litb
@Johannes，K＆R在迭代的上下文中并没有真正说明这一点。它已经在子主题“5.3数组和指针”的介绍部分中提到。然而，缺乏这种上下文并不妨碍从长迭代角度进行讨论。此外，正如您下面所看到的，讨论也已经转向了该角度。 - Abhijith Madhav
你在这里生成汇编时用的是什么工具？ - david_adler
14个回答
1

由于0被定义为一个常量，a[0]也是一个常量，编译器在编译时知道它的位置。在“正常”的情况下，编译器需要根据基址+偏移量（偏移量根据元素大小进行缩放）计算元素地址。

另一方面，p是一个变量，间接寻址需要额外的移动操作。

总的来说，数组索引在内部处理时都被视为指针算术运算，因此我不确定K&R试图表达的观点。

1

由于许多人已经给出了详细的答案，因此我只会给出一个直观的例子。如果您在更大的规模上使用数组和指针，那么使用指针的效率将更加显著。例如，如果您要通过将其排序为几个子集然后将它们合并来对大型长整型数据集进行排序。

long int * testData = calloc(N, sizeof(long int));

对于2017年日常8G内存的计算机，我们可以将N设置为400000000左右，这意味着您将为这个原始数据集使用约1.5G的内存。如果您正在使用MPI，则可以通过使用

MPI_Scatterv(testData, partitionLength, partitionIndex, MPI_LONG, MPI_IN_PLACE, N/number_of_thread, MPI_LONG, 0, MPI_COMM_WORLD);

您可以将partitionLength简单地视为指针，它存储每个相同部分的N/number_of_thread长度，并将partitionIndex视为指针，它按增量存储N/number_of_threads起始索引。假设您有一个4核CPU，并且只将作业分成4个线程。MPI肯定会通过参考快速完成作业。但是，如果您正在使用数组，则此例程必须在数组上运行指针算术以找到分区点。这不像指针那样直接。此外，在合并分区数据集时，您可能希望使用K路合并来加速。您需要一个临时空间来存储四个排序后的数据集。在这里，如果您使用指针，您只需要存储4个地址。但是，如果您使用数组，则会存储4个完整的子数组，这是不高效的。有时，如果您没有使用MPI_Barrier确保程序是线程安全的，MPI甚至可能抱怨您的内存实现不好。我用数组方法和指针方法对32G机器上的400000000长值进行排序，分别获得11.054980秒和13.182739秒。如果我将大小增加到1000000000，则如果我使用数组，我的排序程序将无法成功执行。这就是为什么很多人在C中除标量之外的每个数据结构都使用指针的原因。
0

我对指针比数组更快的讨论感到有些惊讶，Abhijith 的汇编代码最初给出了证据。

mov eax, dord ptr _a; // 直接从地址 _a 加载值

与

mov eax, dword ptr _p; // 将 p 的地址/值加载到 eax 中

and

mov ecx, dword ptr [eax]; // 使用加载的地址访问值并将其放入 ecx 中

数组表示固定地址，因此 CPU 可以直接访问它，但是对于指针，CPU 需要对其进行解引用才能访问该值！

第二批代码不可比较，因为必须计算数组偏移量，为了对指针进行计算，您还需要至少 1/2 个以上的指令！

编译器在编译时可以推断出的任何内容（固定地址、偏移量等）都是实现高性能代码的关键。比较迭代代码和变量赋值：

数组：

; 2791 : tmp = buf_ai[ l ];

mov eax, DWORD PTR _l$[ebp]
mov ecx, DWORD PTR _buf_ai$[ebp+eax*4]
mov DWORD PTR _tmp$[ebp], ecx

vs

PTR

; 2796 : tmp2 = *p;

mov eax, DWORD PTR _p$[ebp]
mov ecx, DWORD PTR [eax]
mov DWORD PTR _tmp2$[ebp], ecx

加

; 2801 : ++p;

mov eax, DWORD PTR _p$[ebp]
add eax, 4
mov DWORD PTR _p$[ebp], eax

这只是为了先加载指针地址再使用它，与数组使用地址并同时获取值相比更加简单！

最好的问候

0

数组与指针的效率：向量化的情况

如果您正在使用像gcc这样的编译器，那么使用数组而不是指针可以从auto-vectorization的收益中获得很多好处：

基本块向量化（也称为SLP）由标志-ftree-slp-vectorize启用，并需要与循环向量化相同的平台相关标志。在-O3和启用-ftree-vectorize时，默认启用基本块SLP。

无法向量化的循环

目前无法进行向量化的循环示例：

示例1：不可计数的循环：


while (*p != NULL) {
  *q++ = *p++;
}

可向量化循环

“功能”表示该示例展示的向量化能力。

示例1：

int a[256], b[256], c[256];
foo () {
  int i;

  for (i=0; i<256; i++){
    a[i] = b[i] + c[i];
  }
}

底线

所以，虽然很多人会告诉你指针或数组哪个更好，但最好的方法始终是：

  • 使用最佳的编译标志来编译代码
  • 使用编译器探索器检查生成的字节码
  • 最后对实际运行速度进行基准测试。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接