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 prime\n", check);
    }

    return 0;
}

我用-O3编译了gcc的代码，以强制编译器完成所有的优化。由于在编译时不知道迭代数，所以我希望编译器不会展开循环。我创建了第二个版本，用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倍以上？因为我用100 m调用它，所以我希望它至少可以完成100米-3 (w/o，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
}