效率：数组 vs 指针

Question

通过指针进行内存访问比通过数组进行内存访问效率更高。我正在学习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

- Abhijith Madhav

---

虽然我对汇编语言不太熟悉，但我认为你应该尝试使用“temp = a[k];”，其中k是一个在编译时不知道的变量。 - Drakosha

@Drakosha，谢谢。我没有意识到这一点。按照您的建议进行操作会导致通过数组访问内存的3条指令（获取索引，获取数组元素的值，存储在临时变量中）。但是我仍然无法看到效率。 :-( - Abhijith Madhav

有人提到K＆R在长迭代的情况下说过这句话。也就是说，在a[i++]与*p++之间。我认为那时候与你的问题所问的是完全不同的。 - Johannes Schaub - litb

@Johannes，K＆R在迭代的上下文中并没有真正说明这一点。它已经在子主题“5.3数组和指针”的介绍部分中提到。然而，缺乏这种上下文并不妨碍从长迭代角度进行讨论。此外，正如您下面所看到的，讨论也已经转向了该角度。 - Abhijith Madhav

你在这里生成汇编时用的是什么工具？ - david_adler

Answer 1

使用指针进行内存访问比使用数组访问更有效率，但在编译器变得相对愚笨的过去可能是真的。只需查看高优化模式下gcc输出的一些代码就可以知道这不再成立了。有些代码很难理解，但一旦掌握，它的杰出之处就显而易见了。一个好的编译器将为指针和数组访问生成相同的代码，你应该不必担心那个级别的性能。编写编译器的人对目标架构的了解远远超过我们凡人。在优化代码时更应集中注意宏观层面（如算法选择等），并相信你的工具制造商会尽职尽责。

事实上，我很惊讶编译器没有优化整个

temp = a[0];

由于在下一行中用不同的值覆盖了temp，并且a没有以任何方式标记为volatile，因此该行代码将被优化而消失。

我还记得很久以前有一个城市传说，关于最新的VAX Fortran编译器的基准测试（表明我很老），它比其竞争对手快出数个数量级。

原来是因为编译器发现基准计算结果在任何地方都没有使用，所以它将整个计算循环优化成不存在。因此运行速度大幅提高。

---

更新：优化后的代码之所以在您的特定情况下更有效率，是因为您找到位置的方式。 a将在链接/加载时决定固定位置，并且对它的引用将同时被确定。因此，a [0] 或者 a [任何常量] 将在固定位置。

由于相同的原因，p本身也将处于固定位置。但是，*p（p的内容）是可变的，因此需要额外的查找来找到正确的内存位置。

您可能会发现，拥有另一个变量x（不是const），并使用a [x]也会引入额外的计算。

---

在您的评论中，您声明：

按照您的建议操作会导致通过数组进行内存访问的3条指令（获取索引，获取数组元素值，存储在临时变量中）。但我仍然看不到效率。:-(

我的回答是：您很可能无法通过使用指针来提高效率。现代编译器足以确定数组操作和指针操作可以转换为相同的底层机器代码。

实际上，在未启用优化的情况下，指针代码可能会更低效。请考虑以下转换：

int *pa, i, a[10];

for (i = 0; i < 10; i++)
    a[i] = 100;
/*
    movl    $0, -16(%ebp)              ; this is i, init to 0
L2:
    cmpl    $9, -16(%ebp)              ; from 0 to 9
    jg      L3
    movl    -16(%ebp), %eax            ; load i into register
    movl    $100, -72(%ebp,%eax,4)     ; store 100 based on array/i
    leal    -16(%ebp), %eax            ; get address of i
    incl    (%eax)                     ; increment
    jmp     L2                         ; and loop
L3:
*/

for (pa = a; pa < a + 10; pa++)
    *pa = 100;
/*
    leal    -72(%ebp), %eax
    movl    %eax, -12(%ebp)            ; this is pa, init to &a[0]
L5:
    leal    -72(%ebp), %eax
    addl    $40, %eax
    cmpl    -12(%ebp), %eax            ; is pa at &(a[10])
    jbe     L6                         ; yes, stop
    movl    -12(%ebp), %eax            ; get pa
    movl    $100, (%eax)               ; store 100
    leal    -12(%ebp), %eax            ; get pa
    addl    $4, (%eax)                 ; add 4 (sizeof int)
    jmp     L5                         ; loop around
L6:
*/

从那个例子中，你可以看到指针示例更长，而且是不必要的。它多次将pa加载到%eax中，尽管pa没有改变，实际上在%eax中交替使用pa和&(a[10])。这里的默认优化基本上根本不存在。

当你升级到优化级别2时，你得到的代码是:

    xorl    %eax, %eax
L5:
    movl    $100, %edx
    movl    %edx, -56(%ebp,%eax,4)
    incl    %eax
    cmpl    $9, %eax
    jle     L5

对于数组版本：

    leal    -56(%ebp), %eax
    leal    -16(%ebp), %edx
    jmp     L14
L16:
    movl    $100, (%eax)
    addl    $4, %eax
L14:
    cmpl    %eax, %edx
    ja      L16

对于指针版本，我不会进行时钟周期分析（因为这太麻烦了，而且我基本上很懒），但我会指出一件事情。就汇编指令而言，两个版本的代码之间没有太大区别，考虑到现代CPU的运行速度，除非您要执行数十亿次此类操作，否则您不会注意到任何差异。我总是倾向于编写易读的代码，并且只在性能成为问题时才担心性能。

顺便说一句，您引用的那个声明：

5.3 指针和数组：指针版本通常会更快，但至少对于初学者来说，有些难以立即理解。

可以追溯到最早的K&R版本，包括我的古老的1978年版本，其中函数仍然是这样编写的：

getint(pn)
int *pn;
{
    ...
}

自从那时候以来，编译器已经走了很长的路。

- paxdiablo

---

这并不是一个都市传说，这件事情发生在我身上：我们进行了一项平台端口测试，该测试是已发布的一套符合性测试的一部分，旨在通过进行一定数量的递归调用来展示可用的“调用栈深度”。然而，GCC进行了尾递归优化。哎呀。编写优化证明基准测试并不像你想象的那样容易... - Steve Jessop

我特意禁用了所有优化，以便在汇编中看到指针更有效的方式。 我将此信息添加到我的问题中，以防万一。 - Abhijith Madhav

事实上，我对K＆R显然所说的话感到惊讶。总的来说，无论优化级别如何，数组访问始终至少与其同等快速。 - Johannes Schaub - litb

@Johannes：K＆R将会考虑迭代，其中在天真的实现中，使用*p++所需的操作比使用a[i++]更少。 - Porculus

我明白，@Abhijith。我的观点是你不会看到这一点，因为它已经不再正确了。这只对那些在数组中计算每个索引访问的基址和偏移量的编译器是正确的，而这些编译器应该立即被扔进废品堆。 :-) - paxdiablo

Answer 2

如果你在编写嵌入式平台程序，你很快就会发现使用指针方法比使用索引要快得多。

struct bar a[10], *p;

void foo()
{
    int i;

    // slow loop
    for (i = 0; i < 10; ++i)
        printf( a[i].value);

    // faster loop
    for (p = a; p < &a[10]; ++p)
        printf( p->value);
}

慢速循环需要每次计算 a + (i * sizeof(struct bar))，而第二个循环只需要每次将 sizeof(struct bar) 添加到 p 上。在许多处理器上，乘法操作使用的时钟周期比加法操作多。

如果在循环内部多次引用a[i]，您将真正看到改进。一些编译器不会缓存该地址，因此可能会在循环内多次重新计算。

尝试更新示例以使用结构并引用多个元素。

- tomlogic

---

这实际上取决于编译器，而不是目标环境。任何好的编译器都会将第一个循环转换为与第二个相同的代码。当然，如果您使用旧的8051编译器（例如），它不执行gcc能够执行的疯狂级别的优化，那么第一个循环可能会慢一些。 - paxdiablo

在某些情况下，指针会更快；在其他情况下，数组访问会更快。例如，适用于8位微处理器的编译器可能知道特定数组永远不会跨越256字节边界，并生成利用此特性的代码。使用指针的代码必须在每一步中处理指针的上半部分和下半部分。 - supercat

这是多么真实啊。我在8051上编写了一个数据缓冲区，无意中编写了一个带有变量的数组。在x86处理器上似乎并不是什么大问题。整个缓冲区过程要求我将MCU处理器速度加倍，以适应使用变量的数组语法。最终我只是硬编码值而不是使用for循环，结果将处理器速度降低了100%....与为PC编写C语言相比，嵌入式开发是一种奇怪的野兽... - Leroy105

Answer 3

指针自然地表达简单的归纳变量，而下标在某种程度上需要更复杂的编译器优化。

---

在许多情况下，仅使用下标表达式需要向问题添加额外的层级。一个增加下标 i 的循环可以被视为状态机，而表达式a [i]在技术上每次使用时都要求将 i 乘以每个元素的大小并加到基地址上。

为了将访问模式转换为使用指针，编译器必须分析整个循环，并确定例如正在访问每个元素。然后编译器可以用前一个循环值的简单增量替换多个实例将下标乘以元素大小的操作。此过程结合了称为 公共子表达式消除 和 归纳变量强度降低 的优化。

当使用指针编写时，不需要整个优化过程，因为程序员通常只需从数组中逐步进行。

有时编译器可以进行优化，有时则不能。近年来拥有先进编译器已经很普遍，所以基于指针的代码并不总是更快。

由于数组通常必须是连续的，指针在创建逐步分配的复合结构时具有另一个优势。

- DigitalRoss

Answer 4

第一种情况下，编译器直接知道数组的地址（也就是第一个元素的地址），并且可以访问它。在第二种情况下，它只知道指针的地址，并且读取指针的值，该值指向内存位置。这实际上是额外的一次间接寻址，因此可能会更慢。

- Alexander Gessler

---

只有当编译器没有像Paxdiablo的回答中所述的那样“优化掉”它时，这才是真的。 - dangerstat

或者，如果处理器没有数组访问寻址模式，因为如果有的话，它可以在任何情况下同时进行数学计算。此时，您只需要额外存储基指针和偏移量所带来的寄存器压力。 - Andrew McGregor

@dangerstat，但这恰恰证明了K＆R所声称的“一般情况下”数组访问速度更快是错误的。所以实际情况恰恰相反。 - Johannes Schaub - litb

Answer 5

速度最大程度上通过循环获得。当使用数组时，您将使用一个计数器来进行递增。为了计算位置，系统将此计数器乘以数组元素的大小，然后加上第一个元素的地址以获取地址。

使用指针时，只需通过增加当前指针与元素大小来获取下一个元素，假设所有元素都在内存中相邻。

因此，在循环中执行指针运算所需的计算量要少一些。而且，拥有正确元素的指针比在数组中使用索引更快。

然而，现代开发正在逐渐摆脱许多指针操作。处理器变得越来越快，并且数组比指针更易于管理。此外，数组往往会减少代码中的错误。数组将允许索引检查，确保您未访问数组外部的数据。

- Wim ten Brink

---

为了计算位置，该系统将此计数器乘以数组元素的大小，然后加上第一个元素的地址以获取地址。在x86中，这整个步骤序列通过单个汇编指令（mov ecx，DWORD PTR _a [eax*4]）实现，因此我认为与通过指针访问没有任何优势。 - Abhijith Madhav

在其他平台（非x86），您将不得不将索引乘以数组元素的大小作为单独操作。如果大小是2的幂，则可以简单地左移，但在其他情况下必须进行乘法运算。 - tomlogic

Alex，你能用例子解释一下这是如何发生的吗？ - Vishwanath Dalvi

Answer 6

如paxdiablo所说，任何新编译器都会使它们非常相似。

更进一步，我看到过数组比指针更快的情况。这是在使用矢量运算的DSP处理器上。

在这种情况下，使用数组类似于使用“restrict”指针。因为通过使用两个数组，编译器隐含地知道它们不指向同一位置。 但如果你处理两个指针，编译器可能会认为它们指向相同的位置，并跳过流水线。

例如：

int a[10],b[10],c[10];
int *pa=a, *pb=b, *pc=c;
int i;

// fill a and b.
fill_arrays(a,b);

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

// set *pc++ = *pa++ + *pb++;
for (i = 0; i<10; i++)
{
   *pc++ = *pa++ + *pb++;
}

在情况1中，编译器将轻松地对a和b进行流水线处理，并将值存储到c中。

在情况2中，编译器将不会进行流水线处理，因为它可能在保存到C时覆盖a或b。

- Yousf

---

关于使用restrict的好处也说得很好——指针别名几乎是一个“大象在房间里”。我认为，在C++0x中，restrict现在是一个关键字，这是一个非常出色的决定。 - zebrabox

Answer 7

这是一个非常古老的问题，已经有了答案，因此我不需要回答！不过，我没有注意到一个简单的答案，所以提供一个。

答案：间接访问（指针/数组）“可能”会增加一条额外的指令来加载（基）地址，但所有后续访问（在数组中为元素，在指向结构体的指针中为成员）应该只需一条指令，因为它仅是将偏移量添加到已经加载的（基）地址。因此，在某种程度上，它将与直接访问一样好。因此，在大多数情况下，通过数组/指针访问等效，并且元素访问也与直接访问变量一样好。

例如，如果我有一个有10个元素的数组（或指针）或一个有10个成员的结构体（通过指向结构体的指针访问），并且我正在访问一个元素/成员，则可能只需要一条额外的指令。之后，所有的元素/成员访问应该只需一条指令。

- RcnRcf

Answer 8

你在这里得到了很好的回答，但是由于你正在学习，值得指出的是，在那个级别上的效率很少能被察觉到。

当你为程序的最大性能进行调整时，你应该至少给予同样多的注意力来发现和修复程序结构中更大的问题。在这些问题被解决后，低级优化可以进一步提高性能。 以下是一个如何实现这一点的示例。

- Mike Dunlavey

Answer 9

指针曾经比数组更快。当 C 语言设计时，指针确实要快得多。但是现在，优化器通常可以更好地优化数组，因为数组更受限制。现代处理器的指令集也被设计用于帮助优化数组访问。因此，总体来说，这些天数组往往更快，特别是在与索引变量一起使用循环时。当然，您仍然希望将指针用于诸如链表之类的事情，但是通过数组遍历指针而不是使用索引变量的旧式优化现在可能会导致不优化。

- John Knoeller

Answer 10

“指针版本通常会更快”意味着在大多数情况下，编译器生成更高效的代码更容易使用指针（只需解除引用），而不是使用数组和下标（这意味着编译器需要从数组开头移动地址）。然而，随着现代处理器和优化编译器的出现，典型情况下数组访问并不比指针访问慢。

具体来说，在您的情况下，您需要打开优化才能获得相同的结果。

- Vlad