数组索引与指针算术性能
本文关键字:性能 指针 索引 数组 | 更新日期: 2023-09-27 18:26:42
我今天读到了关于数组索引和指针算术的文章,并认为两者是相同的(例如,数组索引是指针算术的语法糖)。
除此之外,其他一些人说数组索引比指针算术更快。(??)
我提出了这两个代码片段来测试性能。我在C#中测试了它们,但我认为在C或C++中也是一样的。
数组索引
for (int i = 0; i < n; i++) // n is size of an array
{
sum += arr1[i] * arr2[i];
}
指针算术
for (int i = 0; i < n; i++) // n is size of an array
{
sum += *(arrP1 + i) * *(arrP2 + i);
}
我用数组运行了1000次代码,其中有数百万个整数。结果出乎我的意料。指针运算比数组索引稍微快一点(大约%10)。
结果看起来正确吗?有什么解释可以解释吗?
编辑
我想添加生成的程序集代码。
数组索引
sum += arr1[i] * arr2[i]; // C# Code
mov eax,dword ptr [ebp-14h]
cmp dword ptr [eax+4],0
ja 00E63195
call 73EDBE3A
mov eax,dword ptr [eax+8]
mov edx,dword ptr [ebp-0Ch]
cmp edx,dword ptr [eax+4]
jb 00E631A5
call 73EDBE3A
mov eax,dword ptr [eax+edx*4+8]
mov edx,dword ptr [ebp-18h]
cmp dword ptr [edx+4],0
ja 00E631B7
call 73EDBE3A
mov edx,dword ptr [edx+8]
mov ecx,dword ptr [ebp-0Ch]
cmp ecx,dword ptr [edx+4]
jb 00E631C7
call 73EDBE3A
imul eax,dword ptr [edx+ecx*4+8]
add dword ptr [ebp-8],eax
指针算术
sum += *(arrP1 + i) * *(arrP2 + i); // C# Code
mov eax,dword ptr [ebp-10h]
mov dword ptr [ebp-28h],eax
mov eax,dword ptr [ebp-28h]
mov edx,dword ptr [ebp-1Ch]
mov eax,dword ptr [eax+edx*4]
mov edx,dword ptr [ebp-14h]
mov dword ptr [ebp-2Ch],edx
mov edx,dword ptr [ebp-2Ch]
mov ecx,dword ptr [ebp-1Ch]
imul eax,dword ptr [edx+ecx*4]
add eax,dword ptr [ebp-18h]
mov dword ptr [ebp-18h],eax
基于指针的手动优化代码是:
int* arrP1 = arr1;
int* limitP1 = &arr1[n];
int* arrP2 = arr2;
for (; arrP1<limitP1; ++arrP1, ++arrP2)
{
sum += *arrP1 * *arrP2;
}
请注意,编译器优化的代码可能比手动优化的代码更好,手动优化可能会掩盖行为,阻止编译器进行优化,从而使情况变得更糟。
因此,使用一个足够愚蠢的编译器优化器,我们可以期望手动优化的指针版本比索引版本更好。但是,您需要更多的专业知识(加上检查生成的代码和分析),才能在实际代码中有效地执行这样的操作。
此外,如果读取任何一个输入数组都会导致缓存未命中,那么代码的整个优化(无论你是这样做还是编译器这样做)最终都是完全无用的,因为任何接近正常的版本都与任何其他具有匹配缓存未命中的接近正常版本具有相同的性能。
当然,在C++中,结果是相同的[在C中也是一样]:
#include <stdio.h>
extern int arr1[], arr2[];
const int n = 1000000;
int main()
{
int sum = 0;
for (int i = 0; i < n; i++) // n is size of an array
{
sum += arr1[i] * arr2[i];
}
printf("sum=%d'n", sum);
int* arrP1 = arr1;
int* arrP2 = arr2;
for (int i = 0; i < n; i++) // n is size of an array
{
sum += *(arrP1 + i) * *(arrP2 + i);
}
printf("sum=%d'n", sum);
}
用clang++ -O2 -S arrptr.cpp
编译第一个循环:
pxor %xmm0, %xmm0
movq $-4000000, %rax # imm = 0xFFFFFFFFFFC2F700
pxor %xmm1, %xmm1
.align 16, 0x90
.LBB0_1: # %vector.body
# =>This Inner Loop Header: Depth=1
movdqu arr1+4000000(%rax), %xmm3
movdqu arr1+4000016(%rax), %xmm4
movdqu arr2+4000000(%rax), %xmm2
movdqu arr2+4000016(%rax), %xmm5
pshufd $245, %xmm2, %xmm6 # xmm6 = xmm2[1,1,3,3]
pmuludq %xmm3, %xmm2
pshufd $232, %xmm2, %xmm2 # xmm2 = xmm2[0,2,2,3]
pshufd $245, %xmm3, %xmm3 # xmm3 = xmm3[1,1,3,3]
pmuludq %xmm6, %xmm3
pshufd $232, %xmm3, %xmm3 # xmm3 = xmm3[0,2,2,3]
punpckldq %xmm3, %xmm2 # xmm2 = xmm2[0],xmm3[0],xmm2[1],xmm3[1]
pshufd $245, %xmm5, %xmm6 # xmm6 = xmm5[1,1,3,3]
pmuludq %xmm4, %xmm5
pshufd $232, %xmm5, %xmm3 # xmm3 = xmm5[0,2,2,3]
pshufd $245, %xmm4, %xmm4 # xmm4 = xmm4[1,1,3,3]
pmuludq %xmm6, %xmm4
pshufd $232, %xmm4, %xmm4 # xmm4 = xmm4[0,2,2,3]
punpckldq %xmm4, %xmm3 # xmm3 = xmm3[0],xmm4[0],xmm3[1],xmm4[1]
paddd %xmm0, %xmm2
paddd %xmm1, %xmm3
movdqu arr1+4000032(%rax), %xmm1
movdqu arr1+4000048(%rax), %xmm4
movdqu arr2+4000032(%rax), %xmm0
movdqu arr2+4000048(%rax), %xmm5
pshufd $245, %xmm0, %xmm6 # xmm6 = xmm0[1,1,3,3]
pmuludq %xmm1, %xmm0
pshufd $232, %xmm0, %xmm0 # xmm0 = xmm0[0,2,2,3]
pshufd $245, %xmm1, %xmm1 # xmm1 = xmm1[1,1,3,3]
pmuludq %xmm6, %xmm1
pshufd $232, %xmm1, %xmm1 # xmm1 = xmm1[0,2,2,3]
punpckldq %xmm1, %xmm0 # xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
pshufd $245, %xmm5, %xmm6 # xmm6 = xmm5[1,1,3,3]
pmuludq %xmm4, %xmm5
pshufd $232, %xmm5, %xmm1 # xmm1 = xmm5[0,2,2,3]
pshufd $245, %xmm4, %xmm4 # xmm4 = xmm4[1,1,3,3]
pmuludq %xmm6, %xmm4
pshufd $232, %xmm4, %xmm4 # xmm4 = xmm4[0,2,2,3]
punpckldq %xmm4, %xmm1 # xmm1 = xmm1[0],xmm4[0],xmm1[1],xmm4[1]
paddd %xmm2, %xmm0
paddd %xmm3, %xmm1
addq $64, %rax
jne .LBB0_1
第二个循环:
pxor %xmm1, %xmm1
pxor %xmm0, %xmm0
movaps (%rsp), %xmm2 # 16-byte Reload
movss %xmm2, %xmm0 # xmm0 = xmm2[0],xmm0[1,2,3]
movq $-4000000, %rax # imm = 0xFFFFFFFFFFC2F700
.align 16, 0x90
.LBB0_3: # %vector.body45
# =>This Inner Loop Header: Depth=1
movdqu arr1+4000000(%rax), %xmm3
movdqu arr1+4000016(%rax), %xmm4
movdqu arr2+4000000(%rax), %xmm2
movdqu arr2+4000016(%rax), %xmm5
pshufd $245, %xmm2, %xmm6 # xmm6 = xmm2[1,1,3,3]
pmuludq %xmm3, %xmm2
pshufd $232, %xmm2, %xmm2 # xmm2 = xmm2[0,2,2,3]
pshufd $245, %xmm3, %xmm3 # xmm3 = xmm3[1,1,3,3]
pmuludq %xmm6, %xmm3
pshufd $232, %xmm3, %xmm3 # xmm3 = xmm3[0,2,2,3]
punpckldq %xmm3, %xmm2 # xmm2 = xmm2[0],xmm3[0],xmm2[1],xmm3[1]
pshufd $245, %xmm5, %xmm6 # xmm6 = xmm5[1,1,3,3]
pmuludq %xmm4, %xmm5
pshufd $232, %xmm5, %xmm3 # xmm3 = xmm5[0,2,2,3]
pshufd $245, %xmm4, %xmm4 # xmm4 = xmm4[1,1,3,3]
pmuludq %xmm6, %xmm4
pshufd $232, %xmm4, %xmm4 # xmm4 = xmm4[0,2,2,3]
punpckldq %xmm4, %xmm3 # xmm3 = xmm3[0],xmm4[0],xmm3[1],xmm4[1]
paddd %xmm0, %xmm2
paddd %xmm1, %xmm3
movdqu arr1+4000032(%rax), %xmm1
movdqu arr1+4000048(%rax), %xmm4
movdqu arr2+4000032(%rax), %xmm0
movdqu arr2+4000048(%rax), %xmm5
pshufd $245, %xmm0, %xmm6 # xmm6 = xmm0[1,1,3,3]
pmuludq %xmm1, %xmm0
pshufd $232, %xmm0, %xmm0 # xmm0 = xmm0[0,2,2,3]
pshufd $245, %xmm1, %xmm1 # xmm1 = xmm1[1,1,3,3]
pmuludq %xmm6, %xmm1
pshufd $232, %xmm1, %xmm1 # xmm1 = xmm1[0,2,2,3]
punpckldq %xmm1, %xmm0 # xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
pshufd $245, %xmm5, %xmm6 # xmm6 = xmm5[1,1,3,3]
pmuludq %xmm4, %xmm5
pshufd $232, %xmm5, %xmm1 # xmm1 = xmm5[0,2,2,3]
pshufd $245, %xmm4, %xmm4 # xmm4 = xmm4[1,1,3,3]
pmuludq %xmm6, %xmm4
pshufd $232, %xmm4, %xmm4 # xmm4 = xmm4[0,2,2,3]
punpckldq %xmm4, %xmm1 # xmm1 = xmm1[0],xmm4[0],xmm1[1],xmm4[1]
paddd %xmm2, %xmm0
paddd %xmm3, %xmm1
addq $64, %rax
jne .LBB0_3
除了循环标签和实际循环之前的几条指令之外,这是完全相同的。
g++ -O2 -S
给出了一组类似的相同循环,但不使用SSE指令和展开,因此循环更简单:
.L2:
movl arr1(%rax), %edx
addq $4, %rax
imull arr2-4(%rax), %edx
addl %edx, %ebx
cmpq $4000000, %rax
jne .L2
movl %ebx, %esi
movl $.LC0, %edi
xorl %eax, %eax
call printf
xorl %eax, %eax
.p2align 4,,10
.p2align 3
.L3:
movl arr1(%rax), %edx
addq $4, %rax
imull arr2-4(%rax), %edx
addl %edx, %ebx
cmpq $4000000, %rax
jne .L3
movl %ebx, %esi
movl $.LC0, %edi
xorl %eax, %eax
call printf
xorl %eax, %eax
popq %rbx
.cfi_def_cfa_offset 8
ret
您的两个示例非常相似。
arr[i]
这一行将i乘以sizeof decltype(*arr)并将其与arr相加。这意味着乘法和加法。
若你们想用指针运算来提高性能,下面这样的方法可能会更好:
for (auto p=&(arrP1[0]); p<&(arrP1[n]); p++) // n is size of an array
{
sum += *p; // removed arrP2 for simplification, but can be achieved too.
}
这种新方法消除了乘法运算的需要。
编辑以包括替代解决方案:
正如@SimpleVar所指出的,为了可读性,可以根据程序员的偏好选择几个几乎等效的解决方案。
auto p = arrP1;
for (var i=0; i<n; i++, p++) sum += *p;
甚至
for (auto p=arrP1; p<arrP1+n; p++) sum += *p;
使用C++11,还有另一种选择,允许编译器决定如何实现(我们可以假设其性能正确)
for (auto &p: arrP1) sum += p;
(最后,arrP1需要是标准容器,如std::array或声明的数组:它不能是指针,因为循环不知道数组大小)