在C中,访问我的数组索引更快或通过指针访问更快?
在C中,访问数组索引更快或通过指针访问更快? 我的意思是更快,哪一个会占用更少的时钟周期。 该数组不是常量数组。
templatetypedef总结了它。 为他的回应增加一些支持。 以这些示例函数为例:
unsigned int fun1(unsigned int * x) { unsigned int ra,rb; RB = 0; for(ra = 0; ra <1000; ra ++)rb + = * x ++; 返回(RB); } unsigned int fun2(unsigned int * x) { unsigned int ra,rb; RB = 0; for(ra = 0; ra <1000; ra ++)rb + = x [ra]; 返回(RB); }
现在gcc产生了这个:
00000000 fun1: 0:e52d4004 push {r4}; (str r4,[sp,#-4]!) 4:e1a03000 mov r3,r0 8:e2804efa添加r4,r0,#4000; 0xfa0 c:e3a00000 mov r0,#0 10:e1a02003 mov r2,r3 14:e492c004 ldr ip,[r2],#4 18:e5931004 ldr r1,[r3,#4] 1c:e2823004添加r3,r2,#4 20:e080000c添加r0,r0,ip 24:e1530004 cmp r3,r4 28:e0800001添加r0,r0,r1 2c:1afffff7 bne 10 30:e49d4004 pop {r4}; (ldr r4,[sp],#4) 34:e12fff1e bx lr 00000038 fun2: 38:e3a03000 mov r3,#0 3c:e1a02003 mov r2,r3 40:e790c003 ldr ip,[r0,r3] 44:e2833004添加r3,r3,#4 48:e7901003 ldr r1,[r0,r3] 4c:e2833004添加r3,r3,#4 50:e082200c添加r2,r2,ip 54:e3530efa cmp r3,#4000; 0xfa0 58:e0822001添加r2,r2,r1 5c:1afffff7 bne 40 60:e1a00002 mov r0,r2 64:e12fff1e bx lr
代码是不同的,但我很遗憾错过了优化的机会。
Clang / llvm制作了这个:
00000000 fun1:0:e3a01000 mov r1,#0 4:e3a02ffa mov r2,#1000; 0x3e8 8:e1a03001 mov r3,r1 c:e2522001 subs r2,r2,#1 10:e490c004 ldr ip,[r0],#4 14:e08c3003 add r3,ip,r3 18:e2c11000 sbc r1,r1,#0 1c :e182c001 orr ip,r2,r1 20:e35c0000 cmp ip,#0 24:1afffff8 bne c 28:e1a00003 mov r0,r3 2c:e12fff1e bx lr 00000030 fun2:30:e3a01000 mov r1,#0 34:e3a02ffa mov r2, #1000; 0x3e8 38:e1a03001 mov r3,r1 3c:e2522001 subs r2,r2,#1 40:e490c004 ldr ip,[r0],#4 44:e08c3003 add r3,ip,r3 48:e2c11000 sbc r1,r1,#0 4c :e182c001 orr ip,r2,r1 50:e35c0000 cmp ip,#0 54:1afffff8 bne 3c 58:e1a00003 mov r0,r3 5c:e12fff1e bx lr
您可能会注意到编译器生成了完全相同的代码,指针或偏移量。 通过更改编译器,我比改变指针与数组索引更好。 我认为llvm本可以做得更好一些,我需要更多地研究一下,以了解我的代码导致了什么。
编辑:
我希望让编译器至少使用有利于指针的ldr rd,[rs],#4指令,并希望编译器会看到它可以破坏数组地址,从而将其视为指针而非偏移到一个数组(并使用上面的指令,这基本上是clang / llvm所做的)。 或者,如果它使用ldr rd,[rm,rn]指令执行数组操作。 基本上希望其中一个编译器能够生成以下解决方案之一:
FUNA: mov r1,#0 mov r2,#1000 funa_loop: ldr r3,[r0],#4 添加r1,r1,r3 subs r2,r2,#1 bne funa_loop mov r0,r1 bx lr funb: mov r1,#0 mov r2,#0 funb_loop: ldr r3,[r0,r2] 添加r1,r1,r3 添加r2,r2,#4 cmp r2,#0x4000 有趣的funb_loop mov r0,r1 bx lr FUNC: mov r1,#0 mov r2,#4000 subs r2,r2,#4 func_loop: beq func_done ldr r3,[r0,r2] 添加r1,r1,r3 subs r2,r2,#4 b func_loop func_done: mov r0,r1 bx lr
没有完全到达那里,但非常接近。 这是一个有趣的练习。 注意以上是ARM汇编程序。
一般来说,(不是我特定的C代码示例,不一定是ARM),一些流行的体系结构,你将从基于寄存器的地址(ldr r0,[r1])和带有寄存器索引/偏移量的负载加载(ldr r0,[r1,r2])其中地址是两个寄存器的总和。 理想情况下,一个寄存器是数组的基址,第二个是索引/偏移量。 寄存器的前一个加载适用于指针,后者适用于数组。 如果你的C程序不会改变或移动指针或索引,那么在这两种情况下,这意味着计算的静态地址然后使用正常加载,数组和指针都应该产生相同的指令。 对于更改指针/索引的更有趣的情况。
指针 ldr r0,[r1] ... 添加r1,r1,一些数字 数组索引 ldr r0,[r1,r2] ... 添加r2,r2,一些数字
(用商店替换负载,根据需要用子添加)
有些架构没有三个寄存器寄存器索引指令,因此您必须执行类似的操作
数组索引: mov r2,r1 ... ldr r0,[r2] ... 添加r2,r2,一些数字
或者根据编译器它可能会变得非常糟糕,尤其是如果你编译调试或没有优化,并假设你没有三个寄存器添加
数组索引: mov r2,#0 ... mov r3,r1 添加r3,r2 ldr r4,[r3] ... 添加r2,一些数字
所以这两种方法很可能是相同的。 正如在ARM上看到的,它可以将两个(在立即限制内)指针指令合并为一个,使得速度更快一些。 数组索引解决方案会烧掉更多的寄存器,并且取决于架构的可用寄存器数量,这些寄存器会促使您更快更频繁地将寄存器交换到堆栈(比指针更多),从而减慢您的速度。 如果你不介意破坏基地址,那么底线是指针解决方案可能会从性能角度给你一个优势。 它与您的代码和编译器有很大关系。 对我来说,它的可读性发挥作用,我觉得数组更容易阅读和遵循,其次我需要保留该指针以释放malloc或再次通过该内存,等等。如果是这样,我可能会使用一个数组与一个索引,如果它是一次通过而我不关心破坏基地址我将使用指针。 正如您在上面看到的编译器生成的代码,如果性能至关重要,那么无论如何都要在汇编程序中手动编写解决方案(基于建议的方法,让编译器首先尝试它)。
它完全取决于系统,哪一个更快,但两者在function上是相同的,如果一个实际上更快,我会感到非常惊讶。 也就是代码
myArr[index]
完全等同于
*(&myArr[0] + index)
同样,写作
*ptr
相当于写作
ptr[0]
大多数编译器都很聪明,可以解决这个问题,所以如果一个比另一个更快,我会感到惊讶。
但更重要的是,你可能不应该太担心这一点。 在其他所有工作之后担心优化。 如果您发现数组访问确实在扼杀您,那么请考虑寻找更快的替代方案。 否则,不要担心; 除非您迫切需要优化,否则拥有干净,可读,可维护的代码比拥有优化代码更有价值。
简单的索引操作在我曾经触及的每个编译器上编译为相同的机器代码。 通常建议使用索引以提高可读性。
需要根据具体情况检查涉及指针访问与数组索引的不同逻辑的更复杂情况。 如果您有疑问,请一如既往地描述您的代码。
你的问题没有任何有意义的答案。 语言级操作没有与之关联的特定“速度”。 它们本身不能“更快”或“更慢”。
只有CPU指令可以更快或更慢,只有CPU指令可以消耗CPU周期。 为了以某种方式将“速度”的概念从CPU指令转移回语言级操作[这些CPU指令是从…生成的],一般情况下你需要知道上下文。 这是因为相同的语言级操作可以在不同的上下文中生成完全不同的CPU指令(甚至没有提到它可能还取决于编译器设置等)
换句话说,发布实际代码。 作为一个抽象的无上下文问题,它根本没有意义。
在最低级别,这些操作大多倾向于编译为同一个东西。 如果你真的感兴趣,你应该让你的C编译器生成汇编输出(例如使用gcc -S
),这样你就可以检查,特别是因为它至少依赖于:
- 你的目标平台。
- 你的编译器。
- 你的优化水平。
你会发现,即使存在差异(这是值得怀疑的),微观优化的水平大多不值得投入其中。 你最好做宏观优化,比如改进算法,因为这样可以提供更多的投资回报。
在这种情况下,效果可能很小,我总是优化可读性。
明确消除常见的子表达式可能对您有用。 如果您使用的是x86或RISC架构和优化程序质量,则可能会有所不同。
当我编写一个必须运行数组或索引结构的例程时,我计算一个指向数组/结构成员基础的指针并使用它来解决。 基本情况
struct SOMETHING list[100]; int find_something (...) { int i; i=0; while (i<(sizeof(list)/sizeof(struct SOMETHING))) { if (list[i].active && list[i].last_access+60
可以改进(即帮助编译器生成更好的代码):
int find_something (...) { int i; struct SOMETHING *pList; i=0; while (i<(sizeof(list)/sizeof(struct SOMETHING))) { pList=&list[i]; if (pList->active && pList->last_access+60
这只是为了说明,代码的简单性可能会隐式生成指针,但如果例程更复杂,则可能不是这种情况。 使用“list [i]。” 就像在第一个例子中一样,您运行(在x86上)编译器的风险(RISC haha)没有足够的寄存器来生成和存储地址一次,而是为每个引用生成它。 对于x86情况,需要一个局部变量来存储指针,除非明确指向,否则很少有编译器会创建堆栈变量。 在RISC上,编译器可以使用大量寄存器,并且通常会决定为每次迭代创建(并保持)指针一次是值得的。
循环可以进一步细化:
pList=list; i=0; while (i<(sizeof(list)/sizeof(struct SOMETHING))) { if (pList->active && pList->last_access+60
这种结构没有任何地址计算开销。 “pList + = 1”(其他人可能更喜欢“++ pList”)导致将常量值(等于单个行/成员的大小)添加到pList。
并进一步:
pList=list; pEndList=&list[sizeof(list)/sizeof(struct SOMETHING)]; while (pList!=pEndList) { if (pList->active && pList->last_access+60
这消除了索引增量并用循环内的一个乘法和循环内的一个除法替换它(在返回构造中只执行一次)。
现在,在所有你没有 - 优化者之前,开始尖叫血腥谋杀我的观点是什么结构是可接受的取决于它们所在的函数的大小和复杂性。 我可能不会在300行函数中考虑这个构造,这个函数复杂到足以开始,但在上述情况下? 如果搜索是整体处理的重要部分? 如果加速足够大?
为什么不呢? 优点和缺点。 它总是有利有弊。 充分利用它们。 绝对? 很少(如果有的话)。
相同。 它都是O(1),时钟时间可以忽略不计。 你基本上是在访问内存地址。
通过索引访问数组时,实际上是在执行两个操作: 添加 (将索引添加到基本数组地址),然后是内存访问 (实际读取或写入结果地址的内容)。 我想当你在谈论“通过指针访问”时,你的意思是你已经拥有了指向目标元素的指针。 因此,从逻辑上讲,使用指针保存“添加”部分,因此应该更快,或者至少不会更慢。
然而…
作为一种粗略的近似,在现代计算机中,内存访问比添加更加昂贵(特别是如果它从缓存中掉出来),所以差异(如果有的话)将是轻微的。 在某些体系结构(例如x86或PowerPC)上,可以将添加和内存访问组合到单个操作码中。 事情也会有所不同,这取决于数组地址是否是编译时常量(即数组不是常量数据,而是声明为全局变量, 而不是使用malloc()
获得的块)。 对于通用指针(特别是在使用restrict
关键字时),使用数组可以帮助编译器找到更好的代码。 上下文有很大的影响(例如,那时有多少个自由寄存器?)。
所以:
- 你的问题没有绝对的答案。 你必须尝试采取措施。
- 如果存在可检测的差异(很可能没有),则很难预测哪个方向,并且它取决于大量的外部因素,包括特定的编译器版本和优化标志,处理器架构和模型,内存布局等。
- 如果没有一些相当深入的汇编知识和一些编译理论,你将无法获得任何可靠的优化增益。
- 你应该专注于首先制作正确的代码,然后只关心优化; 除非在现实条件下进行适当的测量,否则没有性能问题。