C语言在访问数组时既可以使用如
a[i]
这样的下标方式,也可以使用*(a+i)
这样的指针方式,理论上完全等价。但是在编译器对循环作优化时,对于指针方式的索引很有可能分析不彻底,因此相比数组索引耗时有所增加
数组索引耗时
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
unsigned long get_start_ms() {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return (ts.tv_sec * 1000 + ts.tv_nsec / 1000000);
}
int main() {
unsigned long t = get_start_ms();
uint64_t* mem = malloc(1024*1024*128*sizeof(uint64_t));
register uint64_t sum = 0;
for(int i = 0; i < 1024*1024*128; i++) sum += mem[i];
printf("[%lums]0x%016llx\n", get_start_ms()-t, sum);
}
分别编译、运行后结果如下所示
可见随着优化等级提升,用时依次减少。
指针索引耗时
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
unsigned long get_start_ms() {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return (ts.tv_sec * 1000 + ts.tv_nsec / 1000000);
}
int main() {
unsigned long t = get_start_ms();
uint64_t* mem = malloc(1024*1024*128*sizeof(uint64_t));
uint64_t* end = mem + 1024*1024*128;
register uint64_t sum = 0;
while(mem<end) sum += *mem++;
printf("[%lums]0x%016llx\n", get_start_ms()-t, sum);
}
分别编译、运行后结果如下所示
同样,随着优化等级提升,用时依次减少。但是我们注意到,在-O1
时指针与数组用时大体相同,但是之后两级都是数组比指针快约10ms
,不是一个小数目。
编译器优化分析
对于出现这种现象的原因,我们需要从汇编代码作分析。
1. 优化等级-O1
在这一级,二者区别不明显。
- 数组索引
- 指针索引
2. 优化等级-O2
在这一级,引入了向量化,但是数组索引的向量化程度更高,指令条数也更少。
- 数组索引
- 指针索引
cmpq $4, %r9
jae LBB1_2
## %bb.1:
## implicit-def: $rbx
jmp LBB1_11
LBB1_2:
movq %r9, %r8
andq $-4, %r8
leaq -4(%r8), %rdi
movq %rdi, %rsi
shrq $2, %rsi
incq %rsi
movl %esi, %ebx
andl $3, %ebx
cmpq $12, %rdi
jae LBB1_4
## %bb.3:
pxor %xmm0, %xmm0
xorl %edi, %edi
pxor %xmm1, %xmm1
testq %rbx, %rbx
jne LBB1_7
jmp LBB1_9
LBB1_4:
movl $1, %edi
subq %rsi, %rdi
leaq -1(%rbx,%rdi), %rsi
pxor %xmm0, %xmm0
xorl %edi, %edi
pxor %xmm1, %xmm1
.p2align 4, 0x90
LBB1_5: ## =>This Inner Loop Header: Depth=1
movdqu 8(%rax,%rdi,8), %xmm2
paddq %xmm0, %xmm2
movdqu 24(%rax,%rdi,8), %xmm0
paddq %xmm1, %xmm0
movdqu 40(%rax,%rdi,8), %xmm1
movdqu 56(%rax,%rdi,8), %xmm3
movdqu 72(%rax,%rdi,8), %xmm4
paddq %xmm1, %xmm4
paddq %xmm2, %xmm4
movdqu 88(%rax,%rdi,8), %xmm2
paddq %xmm3, %xmm2
paddq %xmm0, %xmm2
movdqu 104(%rax,%rdi,8), %xmm0
paddq %xmm4, %xmm0
movdqu 120(%rax,%rdi,8), %xmm1
paddq %xmm2, %xmm1
addq $16, %rdi
addq $4, %rsi
jne LBB1_5
## %bb.6:
testq %rbx, %rbx
je LBB1_9
LBB1_7:
leaq 24(%rax,%rdi,8), %rax
negq %rbx
.p2align 4, 0x90
LBB1_8: ## =>This Inner Loop Header: Depth=1
movdqu -16(%rax), %xmm2
paddq %xmm2, %xmm0
movdqu (%rax), %xmm2
paddq %xmm2, %xmm1
addq $32, %rax
incq %rbx
jne LBB1_8
LBB1_9:
paddq %xmm1, %xmm0
pshufd $78, %xmm0, %xmm1 ## xmm1 = xmm0[2,3,0,1]
paddq %xmm0, %xmm1
movq %xmm1, %rbx
cmpq %r8, %r9
je LBB1_12
## %bb.10:
leaq (%rdx,%r8,8), %rdx
.p2align 4, 0x90
LBB1_11: ## =>This Inner Loop Header: Depth=1
addq (%rdx), %rbx
addq $8, %rdx
cmpq %rcx, %rdx
jb LBB1_11
LBB1_12:
3. 优化等级-O2 -march=native
在这一级引入了avx512
,仍然是数组索引的向量化程度更高,指令条数更少。
- 数组索引
- 指针索引
cmpq $16, %r9
jae LBB1_2
## %bb.1:
## implicit-def: $rbx
jmp LBB1_11
LBB1_2:
movq %r9, %r8
andq $-16, %r8
leaq -16(%r8), %rdi
movq %rdi, %rsi
shrq $4, %rsi
addq $1, %rsi
movl %esi, %ebx
andl $3, %ebx
cmpq $48, %rdi
jae LBB1_4
## %bb.3:
vpxor %xmm0, %xmm0, %xmm0
xorl %edi, %edi
vpxor %xmm1, %xmm1, %xmm1
vpxor %xmm2, %xmm2, %xmm2
vpxor %xmm3, %xmm3, %xmm3
testq %rbx, %rbx
jne LBB1_7
jmp LBB1_9
LBB1_4:
movl $1, %edi
subq %rsi, %rdi
leaq (%rbx,%rdi), %rsi
addq $-1, %rsi
vpxor %xmm0, %xmm0, %xmm0
xorl %edi, %edi
vpxor %xmm1, %xmm1, %xmm1
vpxor %xmm2, %xmm2, %xmm2
vpxor %xmm3, %xmm3, %xmm3
.p2align 4, 0x90
LBB1_5: ## =>This Inner Loop Header: Depth=1
vpaddq 8(%rax,%rdi,8), %ymm0, %ymm0
vpaddq 40(%rax,%rdi,8), %ymm1, %ymm1
vpaddq 72(%rax,%rdi,8), %ymm2, %ymm2
vpaddq 104(%rax,%rdi,8), %ymm3, %ymm3
vpaddq 136(%rax,%rdi,8), %ymm0, %ymm0
vpaddq 168(%rax,%rdi,8), %ymm1, %ymm1
vpaddq 200(%rax,%rdi,8), %ymm2, %ymm2
vpaddq 232(%rax,%rdi,8), %ymm3, %ymm3
vpaddq 264(%rax,%rdi,8), %ymm0, %ymm0
vpaddq 296(%rax,%rdi,8), %ymm1, %ymm1
vpaddq 328(%rax,%rdi,8), %ymm2, %ymm2
vpaddq 360(%rax,%rdi,8), %ymm3, %ymm3
vpaddq 392(%rax,%rdi,8), %ymm0, %ymm0
vpaddq 424(%rax,%rdi,8), %ymm1, %ymm1
vpaddq 456(%rax,%rdi,8), %ymm2, %ymm2
vpaddq 488(%rax,%rdi,8), %ymm3, %ymm3
addq $64, %rdi
addq $4, %rsi
jne LBB1_5
## %bb.6:
testq %rbx, %rbx
je LBB1_9
LBB1_7:
leaq (%rax,%rdi,8), %rax
addq $104, %rax
negq %rbx
.p2align 4, 0x90
LBB1_8: ## =>This Inner Loop Header: Depth=1
vpaddq -96(%rax), %ymm0, %ymm0
vpaddq -64(%rax), %ymm1, %ymm1
vpaddq -32(%rax), %ymm2, %ymm2
vpaddq (%rax), %ymm3, %ymm3
subq $-128, %rax
incq %rbx
jne LBB1_8
LBB1_9:
vpaddq %ymm3, %ymm1, %ymm1
vpaddq %ymm2, %ymm0, %ymm0
vpaddq %ymm1, %ymm0, %ymm0
vextracti128 $1, %ymm0, %xmm1
vpaddq %ymm1, %ymm0, %ymm0
vpshufd $78, %xmm0, %xmm1 ## xmm1 = xmm0[2,3,0,1]
vpaddq %xmm1, %xmm0, %xmm0
vmovq %xmm0, %rbx
cmpq %r8, %r9
je LBB1_12
## %bb.10:
leaq (%rdx,%r8,8), %rdx
.p2align 4, 0x90
LBB1_11: ## =>This Inner Loop Header: Depth=1
addq (%rdx), %rbx
addq $8, %rdx
cmpq %rcx, %rdx
jb LBB1_11
LBB1_12:
由此可见,编译器对for循环下的数组索引的向量化有一套成熟的优化手段,贸然改用指针索引反而会拖慢速度,一定要慎之又慎