C 循环展开优化性能

Question

首先：我知道什么是循环优化以及它是如何工作的，但我发现了一个我无法解释结果的情况。

我创建了一个素数检查器，它对从 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 primen", 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 倍以上？ 由于我用 100M 调用它，我希望它至少执行 100M - 3(w/o 0、1、n(模或和否定运算，但它只需要每个元素 1.37 个周期(并且 afaik 模不是一个便宜的操作(。

Answer 1

!(n % i + 1)似乎是奇数，n%i会产生0或正数，1相加将导致正数，计算!将导致0。因此，每个!(n % i + XX)都可以优化。

应该是!(n % (i + 1)).

Answer 2

这个发布的代码：

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;
}
}

找到答案后正在执行许多循环建议

int is_prime(natural n)
{
for(natural i = 2; i < n; i += 1)
{
if( !(n&i) )
return 0;
}
return 1
}