首先,我知道什么是循环优化以及它的工作原理,但我遇到了一个无法解释结果的情况。
我创建了一个素数检查器,对从2到n-1的每个数字调用了模操作,因此没有算法优化。
编辑:我知道素数可以更有效地计算,但这只是循环行为的一个示例。
然后我创建了一个普通版本和一个优化版本:
#include <stdlib.h>
#include <stdio.h>
typedef unsigned long long natural;
int is_prime(natural n){
int is_not_prime = 0;
for(natural i = 2; i < n; i += 1){
is_not_prime |= !!!(n % i);
}
if(is_not_prime){
return 0;
}else{
return 1;
}
}
//__attribute__((noinline))
int is_prime_opt(natural n){
int is_not_prime = 0;
for(natural i = 2; i < n; i += 8){
is_not_prime |= !!(
!(n % i) |
!(n % i + 1) |
!(n % i + 2) |
!(n % i + 3) |
!(n % i + 4) |
!(n % i + 5) |
!(n % i + 6) |
!(n % i + 7));
}
if(is_not_prime){
return 0;
}else{
return 1;
}
}
int main(int argc, char *argv[])
{
if(argc != 2)
return 1;
natural check = atoi(argv[1]);
if(is_prime(check)){
printf("%llu is prime\n", check);
}
return 0;
}
我使用gcc编译代码,并添加-O3
选项,以强制编译器进行所有优化。由于迭代次数在编译时未知,因此我期望编译器不会展开循环。
我创建了第二个版本,将同样的操作分为8个数字一组。由于某些输入不能被8整除,循环计算的最坏情况是多计算7个项目,但这是可接受的。
我使用valgrind --tool=callgrind ./prime 100000000
检查了循环周期,并得到以下结果:
未经优化的:
==983== Callgrind, a call-graph generating cache profiler
==983== Copyright (C) 2002-2015, and GNU GPL'd, by Josef Weidendorfer et al.
==983== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==983== Command: ./prime 100000000
==983==
==983== For interactive control, run 'callgrind_control -h'.
==983==
==983== Events : Ir
==983== Collected : 1000098047
==983==
==983== I refs: 1,000,098,047
优化:
==2307== Callgrind, a call-graph generating cache profiler
==2307== Copyright (C) 2002-2015, and GNU GPL'd, by Josef Weidendorfer et al.
==2307== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==2307== Command: ./prime 100000000
==2307==
==2307== For interactive control, run 'callgrind_control -h'.
==2307==
==2307== Events : Ir
==2307== Collected : 137598072
==2307==
==2307== I refs: 137,598,072
我原本预计循环速度会快10-20%,因为我节省了1/8的跳转和检查。另外,由于除了最后一个跳转之外,所有跳转都指向同一方向,所以分支预测应该已经加速了第一个版本。
但是我不清楚为什么这个版本要快7倍以上?因为我使用了1亿次调用,所以我至少希望它执行1亿-3(不包括0,1,n)次取模、或运算和否定操作,但实际上只需要每个元素1.37个周期就能完成这个任务(而且据我所知,取模不是一项廉价的操作)。
i < n
作为条件,而不是!is_not_prime && (i < n)
呢? - dbush!(n % i + 1)
看起来是奇数,n%i
的结果将会是0
或者一个正数,加上1
后将得到一个正数,对其进行逻辑非运算!
的结果将为0
。所以每个!(n % i + XX)
都可以被优化掉。 - mch!(n % (i + x))
,有了这个更改,我可以得到大约 6.75 亿个周期,这更符合实际(并且仍然比不展开循环要快约 30%)。如果你把这写成答案,我会接受的。 - jklmnn