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

我使用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)).