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倍以上？因为我使用了1亿次调用，所以我至少希望它执行1亿-3（不包括0，1，n）次取模、或运算和否定操作，但实际上只需要每个元素1.37个周期就能完成这个任务（而且据我所知，取模不是一项廉价的操作）。

- jklmnn

---

你看过生成的代码，了解它的实际作用了吗？ - Some programmer dude

你为什么要使用 i < n 作为条件，而不是 !is_not_prime && (i < n) 呢？ - dbush

!(n % i + 1)看起来是奇数，n%i的结果将会是0或者一个正数，加上1后将得到一个正数，对其进行逻辑非运算!的结果将为0。所以每个!(n % i + XX)都可以被优化掉。 - mch

@mch 那就是问题所在！当然需要是 !(n % (i + x))，有了这个更改，我可以得到大约 6.75 亿个周期，这更符合实际（并且仍然比不展开循环要快约 30%）。如果你把这写成答案，我会接受的。 - jklmnn

你的CPU和架构是什么？即使在64位模式下，x86也是一个相对寄存器不足的CPU。如果我正确理解了你的问题，你的单循环实现比手动展开的实现表现更好。展开循环会增加所需的寄存器数量。我敢打赌，如果你检查编译器实际发出的指令，展开的实现将有很多寄存器溢出和填充。 - Andrew Henle

Answer 1

!(n % i + 1)似乎很奇怪，n%i的结果将会是0或正数，再加上1会得到一个正数，在它上面计算!将会得到0。所以每个!(n % i + XX)都可以被优化掉。

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

- mch

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
}

- user3629249