为什么我的数组索引比指针更快

Question

为什么数组索引比指针更快？ 难道指针不应该比数组索引更快吗？ 我使用time.h的clock_t来测试了两个函数，每个函数循环了200万次。

Pointer time : 0.018995

Index time : 0.017864

void myPointer(int a[], int size)
{
     int *p;
     for(p = a; p < &a[size]; p++)
     {
         *p = 0;
     }
}


void myIndex(int a[], int size)
{
     int i;
     for(i = 0; i < size; i++)
     {
         a[i] = 0;
     }
}

- user977648

---

我会尝试翻译这句话：我预计指针版本的代码应该是 int * end = a + size; for(p=a; a<end; p++)。 - hugomg

这些时间看起来非常接近，很容易被操作系统的多线程等因素所影响。建议分别运行它们两亿次甚至十亿次以减少系统误差。 - Callum Rogers

稍微更改标签，直接摘自《计算机体系结构与设计》（Patterson/henrssy）。您的答案（除下面之外）在示例的“详细说明”中：... - gnometorule

C语言部分很有趣，但汇编才是关键。在下面的VC 2008示例中，编译器使用REP STOSB循环渲染，实际上是使用汇编指令（寄存器中的参数）来覆盖内存。也就是说，编译器并没有完全按照你要求的方式执行，因此询问这两个实现之间的差异没有意义。 - hughdbrown

你应该使用特定于平台的函数来更准确地测量时间。例如，在Windows上使用 QueryPerformanceCounter。 - Ameen

Answer 1

不，指针绝对不应该比数组索引更快。如果其中一个代码比另一个快，那么这很可能是因为某些地址计算可能不同。问题还应提供编译器和优化标志的信息，因为它们会严重影响性能。

在您的上下文中（未知数组边界），数组索引与指针操作完全相同。从编译器的角度来看，它只是指针算术的不同表达式。以下是使用Visual Studio 2010进行完全优化和无内联的优化x86代码示例。

     3: void myPointer(int a[], int size)
     4: {
013E1800  push        edi  
013E1801  mov         edi,ecx  
     5:      int *p;
     6:      for(p = a; p < &a[size]; p++)
013E1803  lea         ecx,[edi+eax*4]  
013E1806  cmp         edi,ecx  
013E1808  jae         myPointer+15h (13E1815h)  
013E180A  sub         ecx,edi  
013E180C  dec         ecx  
013E180D  shr         ecx,2  
013E1810  inc         ecx  
013E1811  xor         eax,eax  
013E1813  rep stos    dword ptr es:[edi]  
013E1815  pop         edi  
     7:      {
     8:          *p = 0;
     9:      }
    10: }
013E1816  ret 

    13: void myIndex(int a[], int size)
    14: {
    15:      int i;
    16:      for(i = 0; i < size; i++)
013E17F0  test        ecx,ecx  
013E17F2  jle         myIndex+0Ch (13E17FCh)  
013E17F4  push        edi  
013E17F5  xor         eax,eax  
013E17F7  mov         edi,edx  
013E17F9  rep stos    dword ptr es:[edi]  
013E17FB  pop         edi  
    17:      {
    18:          a[i] = 0;
    19:      }
    20: }
013E17FC  ret 

一眼看上去，myIndex 看起来更快，因为指令数量较少，然而这两段代码本质上是相同的。两者最终都使用了 rep stos，这是 x86 的重复（循环）指令。唯一的区别在于循环边界的计算方式。在 myIndex 中的 for 循环使用 size 作为迭代次数（即不需要计算）。但是，myPointer 需要进行一些计算才能得到 for 循环的迭代次数。这是唯一的区别。重要的循环操作是完全相同的。因此，差异可以忽略不计。

总之，在优化后的代码中，myPointer 和 myIndex 的性能应该是相同的。

---

如果数组边界在编译时已知，例如int A[constant_expression]，则对该数组的访问可能比指针更快。这主要是因为数组访问不受指针分析问题的影响。编译器可以完美地计算固定大小数组上的计算和访问的依赖信息，因此可以进行高级优化，包括自动并行化。

然而，如果计算是基于指针的，则编译器必须执行指针分析以进行进一步的优化，这在C/C++中非常有限。它通常以保守的指针分析结果结束，并导致少数优化机会。

- minjang

---

如果您不使用for循环，而是使用一个索引数组（而不是指针数组），那么索引是否仍然更快呢？例如：arr [indices [i]]与pointers_to_arr [i]。 - Tara

Answer 2

数组取值操作 p[i] 等同于 *(p + i)。编译器利用数学运算和指针取值的组合来优化速度（例如 x86 的 LEA 指令需要1-2个时钟周期）。

而使用指针循环时，访问和偏移被分成了两个独立的部分，编译器无法进行优化。

- moshbear

---

谢谢！那么在这种情况下，指针总是较慢的吗？因为编译器无法对其进行优化。 - user977648

我正在查看gcc -O3的汇编输出，以查看仅在索引解除引用与普通解除引用之间存在差异时的区别。 - moshbear

我要说的是：编译器优化比索引解引用和普通解引用之间的差异对速度的影响更大。 - moshbear

我正在使用O0、O1、O2、O3的示例进行定时循环，对一个包含100万个元素的数组进行重复1百万次的操作。这将花费我几个小时来获取一些数据。 - moshbear

哇..非常感谢，但你不必这样做，这需要太多时间。我做了200万个元素，重复了1000次，索引打败了指针。 - user977648

尝试在指针one中进行以下修改：引入一个临时变量int *p_end = a + size，然后与p_end进行比较以隔离指针与索引。我对long[1000000]进行了1000次运行的时间如下：gcc -O0 P: 4420000 I: 5460000; gcc -O1 P: 2260000 I: 2250000; gcc -O2 P: 2300000 I: 2290000; gcc -O3 P: 2280000 I: 2290000。显然，最终没有真正的区别。您的开销在于&a[size]的计算。 - moshbear

Answer 3

可能是for循环中的比较导致了差异。终止条件在每次迭代时都会被测试，而您的“指针”示例具有稍微复杂的终止条件（取&a [size]的地址）。由于&a [size]不会改变，因此您可以尝试将其设置为变量以避免在循环的每次迭代中重新计算它。

- Ron

---

谢谢！它确实使指针更快，但仍然比数组索引慢一点。 - user977648

一个编译优化器可能会将一个寄存器临时化，其值为 a + (size * (sizeof *a))。 - moshbear

Answer 4

我建议您分别运行每个循环2亿次，然后每个循环跑10次，并记录最快的时间。这将消除操作系统调度等影响因素。

然后，我建议您对每个循环的代码进行反汇编。

- Anthony Blake

Answer 5

糟糕，在我的64位系统上，结果相当不同。我得到了这个：

 int i;

 for(i = 0; i < size; i++)
 {
     *(a+i) = 0;
 }

比这个慢了大约100倍！！

 int i;
 int * p = a;

 for(i = 0; i < size; i++)
 {
     *(p++) = 0;
 }

当使用-O3编译时。这提示我64位CPU更容易实现移动到下一个地址，而不是从某个偏移量计算目标地址。但我不确定。

编辑：
这确实与64位架构有关，因为相同的代码和相同的编译标志在32位系统上没有显示出任何实际性能差异。

- Agnius Vasiliauskas

---

也许在第二种情况下，编译器已经识别了这个模式并使用SSE/MMX指令将循环并行化。这些指令在64位架构上始终可用，而在32位架构上编译器无法假设其可用性（除非你在编译时提供一些明确的提示）。 - BeeOnRope

如果差异是100倍，那么你的代码显然是错误的。最慢的部分是内存访问，无论循环做什么都是一样的。（也许你先做了一个，然后再做另一个？）我会与std::fill进行比较，看看哪个是“奇怪的”。 - Tiger4Hire

Answer 6

编译器优化是模式匹配。

当编译器进行优化时，它会寻找已知的代码模式，然后根据一些规则转换代码。你的两个代码片段似乎触发了不同的转换，因此产生了略微不同的代码。

这就是为什么我们总是坚持在优化时实际测量结果的原因之一：除非测试过，否则你永远无法确定编译器将你的代码转换成什么样子。

---

如果你真的很好奇，可以尝试使用 gcc -S -Os 编译你的代码，这将生成最易读且经过优化的汇编代码。对于你的两个函数，我用这个命令得到了以下汇编代码：

pointer code:
.L2:
    cmpq    %rax, %rdi
    jnb .L5
    movl    $0, (%rdi)
    addq    $4, %rdi
    jmp .L2
.L5:

index code:
.L7:
    cmpl    %eax, %esi
    jle .L9
    movl    $0, (%rdi,%rax,4)
    incq    %rax
    jmp .L7
.L9:

差别很小，但确实可能会引起性能差异，最重要的是使用 addq 和 incq 的区别可能是显著的。

- cmaster - reinstate monica

Answer 7

这些时间非常接近，如果你重复执行它们，可能看不出太大的差异。两个代码段编译成了完全相同的汇编代码。根据定义，它们没有任何区别。

- djhaskin987

Answer 8

看起来索引解决方案可以在for循环中使用比较来节省一些指令。

- shenles

---

这是一个调试版本吗？优化后的发布版本输出结果会截然不同。 - Blastfurnace

是的，我刚刚意识到忘记获取发布文件了... @minjang已经发布了相同的汇编代码，所以我将删除调试构建。 - shenles

Answer 9

这是一个非常难以计时的事情，因为编译器非常擅长优化这些东西。不过最好尽可能地给编译器提供更多信息，这就是为什么在这种情况下我建议使用std :: fill，并让编译器选择。

但是...如果你想深入了解：

a）CPU通常免费提供指针+值，例如：mov r1，r2（r3）。
b）这意味着索引操作仅需要：mul r3，r1，size
这只是每个循环额外的一个周期。
c）CPU通常提供停顿/延迟插槽，这意味着您通常可以隐藏单周期操作。

总的来说，即使您的循环非常大，访问成本与甚至几个缓存未命中的成本相比微不足道。在关心循环成本之前，最好先优化您的结构。例如，请尝试压缩您的结构以减少内存占用。

- Tiger4Hire

Answer 10

通过数组索引或指针访问数据是完全等效的。请跟我一起看下面的程序...

有一个循环，它持续100次，但当我们查看反汇编代码时，我们发现通过数组索引访问的数据比通过指针访问的数据具有更少的指令可比性。

但这并不意味着通过指针访问数据就快，实际上它取决于编译器执行的指令。指针和数组索引都使用地址数组访问偏移量中的值，并通过它进行增量操作，指针具有地址。

int a[100];
fun1(a,100);
fun2(&a[0],5);
}
void fun1(int a[],int n)
{
int i;
for(i=0;i<=99;i++)
{
a[i]=0;
printf("%d\n",a[i]);
}
}
void fun2(int *p,int n)
{
int i;
for(i=0;i<=99;i++)
{
*p=0;
printf("%d\n",*(p+i));
}
}


disass fun1
Dump of assembler code for function fun1:
   0x0804841a <+0>: push   %ebp
   0x0804841b <+1>: mov    %esp,%ebp
   0x0804841d <+3>: sub    $0x28,%esp`enter code here`
   0x08048420 <+6>: movl   $0x0,-0xc(%ebp)
   0x08048427 <+13>:    jmp    0x8048458 <fun1+62>
   0x08048429 <+15>:    mov    -0xc(%ebp),%eax
   0x0804842c <+18>:    shl    $0x2,%eax
   0x0804842f <+21>:    add    0x8(%ebp),%eax
   0x08048432 <+24>:    movl   $0x0,(%eax)
   0x08048438 <+30>:    mov    -0xc(%ebp),%eax
   0x0804843b <+33>:    shl    $0x2,%eax
   0x0804843e <+36>:    add    0x8(%ebp),%eax
   0x08048441 <+39>:    mov    (%eax),%edx
   0x08048443 <+41>:    mov    $0x8048570,%eax
   0x08048448 <+46>:    mov    %edx,0x4(%esp)
   0x0804844c <+50>:    mov    %eax,(%esp)
   0x0804844f <+53>:    call   0x8048300 <printf@plt>
   0x08048454 <+58>:    addl   $0x1,-0xc(%ebp)
   0x08048458 <+62>:    cmpl   $0x63,-0xc(%ebp)
   0x0804845c <+66>:    jle    0x8048429 <fun1+15>
   0x0804845e <+68>:    leave  
   0x0804845f <+69>:    ret    
End of assembler dump.
(gdb) disass fun2
Dump of assembler code for function fun2:
   0x08048460 <+0>: push   %ebp
   0x08048461 <+1>: mov    %esp,%ebp
   0x08048463 <+3>: sub    $0x28,%esp
   0x08048466 <+6>: movl   $0x0,-0xc(%ebp)
   0x0804846d <+13>:    jmp    0x8048498 <fun2+56>
   0x0804846f <+15>:    mov    0x8(%ebp),%eax
   0x08048472 <+18>:    movl   $0x0,(%eax)
   0x08048478 <+24>:    mov    -0xc(%ebp),%eax
   0x0804847b <+27>:    shl    $0x2,%eax
   0x0804847e <+30>:    add    0x8(%ebp),%eax
   0x08048481 <+33>:    mov    (%eax),%edx
   0x08048483 <+35>:    mov    $0x8048570,%eax
   0x08048488 <+40>:    mov    %edx,0x4(%esp)
   0x0804848c <+44>:    mov    %eax,(%esp)
   0x0804848f <+47>:    call   0x8048300 <printf@plt>
   0x08048494 <+52>:    addl   $0x1,-0xc(%ebp)
   0x08048498 <+56>:    cmpl   $0x63,-0xc(%ebp)
   0x0804849c <+60>:    jle    0x804846f <fun2+15>
   0x0804849e <+62>:    leave  
   0x0804849f <+63>:    ret    
End of assembler dump.
(gdb) 

- Varun Chhangani

---

你的例子有缺陷。编译器可以看到循环的大小，并理解它正在做什么，这就是为什么两个例子是相同的原因。如果你的循环足够小，编译器甚至可能会完全删除循环（谷歌循环展开）。要测试速度，你需要隐藏大小（就像原始问题所做的那样）。 - Tiger4Hire