使用数组偏移和指针递增有什么区别?

5

假设有两个函数,如果有任何差异,哪一个更快?假设输入数据非常大。

void iterate1(const char* pIn, int Size)
{
   for ( int offset = 0; offset < Size; ++offset )
   {
      doSomething( pIn[offset] );
   }
}

vs

void iterate2(const char* pIn, int Size)
{
   const char* pEnd = pIn+Size;
   while(pIn != pEnd)
   {
      doSomething( *pIn++ );
   }
}

在采用任一方法时,是否还有其他问题需要考虑?

11个回答

10

很有可能,您的编译器优化器会为第一种情况创建一个循环归纳变量,将其转换为第二种情况。我预计在优化后不会有任何区别,所以我倾向于使用第一种风格,因为我觉得它更易于阅读。


是的 - 指出细节级别的实现是编译器的细节/关注点。(尽管我发现次要风格更易读 :-)) - user166390

8

Boojum是正确的 - 如果你的编译器有一个良好的优化器并且你已启用它。如果不是这种情况,或者你对数组的使用不是连续的且难以优化,使用数组偏移量可能会慢得多。

这里有一个例子。大约在1988年,我们在Mac II上实现了一个带有简单电传打字机接口的窗口。它由24行80个字符组成。当你从股票中获得新的一行时,你将前23行向上滚动,并在底部显示新的一行。当电传打字机上有东西时(并不是一直有),它以300波特率进入,加上串行协议开销,大约每秒30个字符。所以我们谈论的并不是应该完全耗尽16 MHz 68020的东西!

但是写这篇文章的人却像这样写:

char screen[24][80];

并使用二维数组偏移量来滚动字符,就像这样:

int i, j;
for (i = 0; i < 23; i++)
  for (j = 0; j < 80; j++)
    screen[i][j] = screen[i+1][j];

这样六个窗口就把机器搞崩了!

为什么? 因为在那个时代编译器比较低能,所以在机器语言中,每个内部循环赋值的实例,screen[i][j] = screen[i+1][j],看起来有点像这样(Ax和Dx是CPU寄存器);

Fetch the base address of screen from memory into the A1 register
Fetch i from stack memory into the D1 register
Multiply D1 by a constant 80
Fetch j from stack memory and add it to D1
Add D1 to A1
Fetch the base address of screen from memory into the A2 register
Fetch i from stack memory into the D1 register
Add 1 to D1
Multiply D1 by a constant 80
Fetch j from stack memory and add it to D1
Add D1 to A2
Fetch the value from the memory address pointed to by A2 into D1
Store the value in D1 into the memory address pointed to by A1

所以,对于1840个内循环迭代,我们需要13个机器语言指令,总共需要23920个指令,其中包括3680个CPU密集型整数乘法。

我们对C源代码进行了一些更改,然后它看起来像这样:

int i, j;
register char *a, *b;
for (i = 0; i < 22; i++)
{
  a = screen[i];
  b = screen[i+1];
  for (j = 0; j < 80; j++)
    *a++ = *b++;
}

仍有两个机器语言乘法,但它们在外循环中,因此只有46个整数乘法而不是3680个。而内部循环的 *a++ = *b++ 语句只包含两个机器语言操作。

Fetch the value from the memory address pointed to by A2 into D1, and post-increment A2
Store the value in D1 into the memory address pointed to by A1, and post-increment A1.

考虑到有1840个内部循环迭代,这总共需要3680个CPU廉价指令——少了6.5倍——而且没有整数乘法。在此之后,我们再也没有遇到过6个电传窗口的死机问题,因为我们先用完了电传数据源。还有更多的优化方法可以进一步提高效率。
现代编译器可以为你做这种优化——但是,只有当你要求它这样做,而且你的代码结构允许时才会这样。
但是,在某些情况下,编译器无法为您完成优化——例如,如果您在数组中执行非顺序操作。
因此,我发现尽可能使用指针而不是数组引用对我很有帮助。性能肯定不会更差,而且通常会更好。

等待分析器告诉你哪个循环导致了减速,这样不是更好吗? - Steve Rowe
1
@Steve Rowe:性能分析器并不总是可用的。1987年的Mac上没有任何性能分析器,今天在Linux ARM处理器上也没有真正好用的性能分析器。此外,精通指针确实是从C/C++初学者到大师之路的第一步。如果你不能在面试中编写基于指针的代码,许多硅谷的公司将不会雇用你。如果你不能阅读它,你将在包括Linux和Mac OS内核、X服务器和许多设备驱动程序的代码中彻底迷失。 - Bob Murphy
2
@Steve Rowe:另外,我可以从经验中说:每当您有两个或更多嵌套的循环时,最内层的代码很可能至少是潜在的性能瓶颈。 - Bob Murphy

3

使用现代编译器,两种方法的性能应该没有任何区别,尤其是在这样简单易懂的例子中。此外,即使编译器无法识别它们的等价性,即逐字翻译每个代码,也不应该在典型的现代硬件平台上出现任何明显的性能差异。(当然,在某些更专业的平台上可能会有明显的差异。)

至于其他考虑因素...从概念上讲,当你使用索引访问实现算法时,你对底层数据结构施加了一项随机访问要求。当你使用指针(“迭代器”)访问时,你只对底层数据结构施加了一个顺序访问要求。随机访问比顺序访问要求更强。因此,在我的代码中,我更喜欢尽可能使用指针访问,并仅在必要时使用索引访问。

更普遍地说,如果可以通过顺序访问有效地实现算法,最好这样做,而不涉及不必要的随机访问要求。这可能在未来证明是有用的,如果需要重构代码或更改算法。


2

几年前,我曾提出过这个问题。在一次面试中,有人因为使用数组符号而将候选人判定为失败,理由是它明显更慢。当时,我编译了两个版本并查看了反汇编代码。在数组符号中多了一个操作码。这是使用Visual C++ (.net?)得出的结论。根据我所见,我得出结论:没有明显的区别。

再次进行此操作,以下是我的发现:

    iterate1(arr, 400); // array notation
011C1027  mov         edi,dword ptr [__imp__printf (11C20A0h)] 
011C102D  add         esp,0Ch 
011C1030  xor         esi,esi 
011C1032  movsx       ecx,byte ptr [esp+esi+8] <-- Loop starts here
011C1037  push        ecx  
011C1038  push        offset string "%c" (11C20F4h) 
011C103D  call        edi  
011C103F  inc         esi  
011C1040  add         esp,8 
011C1043  cmp         esi,190h 
011C1049  jl          main+32h (11C1032h) 

    iterate2(arr, 400); // pointer offset notation
011C104B  lea         esi,[esp+8] 
011C104F  nop              
011C1050  movsx       edx,byte ptr [esi] <-- Loop starts here
011C1053  push        edx  
011C1054  push        offset string "%c" (11C20F4h) 
011C1059  call        edi  
011C105B  inc         esi  
011C105C  lea         eax,[esp+1A0h] 
011C1063  add         esp,8 
011C1066  cmp         esi,eax 
011C1068  jne         main+50h (11C1050h) 

3
如果候选人因为过于强调微观优化而使用指针偏移量来评估代码清晰度,我可能会不通过他(或者打折扣)。 - JohnMcG
@John,我也是这么想的。如果我必须选择一个,那就是更清晰易懂的代码。做其他任何事情都是过早优化。 - Steve Rowe
1
@JohnMcG: 如果一个候选人认为使用“滑动指针”技术的唯一原因是微优化,那我会判定他失败。实际上,这并不是必须的。有其他令人信服的理由选择指针而非索引。 - AnT stands with Russia
@Doug,这些天这可能是一个严重的问题。 - Steve Rowe

2
它们几乎是一样的。两种解决方案都涉及一个临时变量,一个在您系统上增加单词(int或ptr)的递增,以及一个逻辑检查,应该需要一个汇编指令。
我看到的唯一区别是数组查找 arr[idx] 可能需要指针算术,然后再进行提取,而解引用 *ptr 只需要提取。
我的建议是,如果真的很重要,请实现两者,并查看是否有任何节省。

2

需要确保的是,在您打算使用的目标环境中进行分析。

话虽如此,我的猜测是,任何现代编译器都会将它们优化为非常相似(如果不是相同)的代码。

如果您没有优化器,第二种方法有可能更快,因为您不需要在每次迭代中重新计算指针。但是,除非Size是一个非常大的数字(或该程序经常被调用),否则差异对您程序的整体执行速度不会产生影响。


1
英特尔有直接进行偏移指针的指令,因此您不需要显式重新计算指针。我看到第一个循环运行得更快。 - Mark Ransom

2

指针操作曾经速度非常快,现在稍微快了一些,但编译器可能会为您进行优化

历史上,通过*p++迭代比p[i]更快,这是使用指针的动机之一。

此外,p[i]通常需要较慢的乘法或至少需要移位操作,因此用指针替换循环中的乘法以进行加法优化非常重要,这被称为强度降低。下标也倾向于生成更大的代码。

然而,有两个事情已经改变:其一是编译器变得更加复杂,通常能够为您进行这种优化。

另一个是操作和内存访问之间的相对差异增加了。当*p++被发明时,内存和CPU操作的时间类似。今天,随机桌面机器可以执行30亿个整数操作/秒,但只能读取约1000万个随机DRAM。缓存访问更快,系统将预取和流式传输顺序内存访问,当您遍历数组时,但仍然需要付出很高的成本才能命中内存,一点点下标调整并不是那么重要。


1
为什么不试试两种并计时呢?我猜它们会被编译器优化成基本相同的代码。只需在比较时记得开启优化(-O3)。

如果性能对你很重要,测试你正在考虑的代码。有太多的变量不能依赖于网络陌生人的建议。 - Mark Ransom

1
在“其他考虑”栏中,我认为方法一更清晰。不过这只是我的个人意见。

1

你正在问错问题。 开发人员应该先追求可读性还是性能?

第一个版本在处理数组时是惯用语,而且对于以前使用过数组的任何人来说,你的意图都是清楚的,而第二个版本则严重依赖于数组名称和指针之间的等价性,迫使阅读代码的人多次切换比喻。

一些评论可能会说,只有值得信任的开发人员才能清楚地理解第二个版本。

如果你编写的程序运行缓慢并且你已经进行了分析,确定这个循环是瓶颈所在,那么看看哪个更快是有意义的。但是首先使用众所周知的惯用语言构造,让它清晰易懂地运行起来。


现在,我的经验法则是:如果对人类来说更容易理解,那么编译器也会更容易理解。 - Boojum

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接