C++ 循环展开性能差异(Project Euler)

Question

我有一个关于 Project Euler 问题和使用循环展开优化的问题。

问题描述:2520是能被1到10的每一个数整除而没有余数的最小数。能被 1 到 20 的所有数字整除的最小正数是多少？

解决方法:

#include <iostream>
#include <limits.h>
#include <stdio.h>
#include <time.h>

using namespace std;

int main() {

    clock_t startTime = clock();

    for (int i = 1; i < INT_MAX; i++)
    {
        bool isDivisible = true;

        //CODE BLOCK #1
        /*for (int j = 2; j <= 20; j++)
        {
                if ( i % j != 0)
                {
                        isDivisible = false;
                        break;
                {
        }*/

        //CODE BLOCK #2
        /*if (i % 2 != 0 || i % 3 != 0 ||
                i % 4 != 0 || i % 5 != 0 ||
                i % 6 != 0 || i % 7 != 0 ||
                i % 8 != 0 || i % 9 != 0 ||
                i % 10 != 0 || i % 11 != 0 ||
                i % 12 != 0 || i % 13 != 0 ||
                i % 14 != 0 || i % 15 != 0 ||
                i % 16 != 0 || i % 17 != 0 ||
                i % 18 != 0 || i % 19 != 0 ||
                i % 20 != 0 )
                isDivisible = false;*/

        if (isDivisible)
        {
                cout << "smallest: " << i << endl;

                cout << "Ran in: " << clock() -  startTime  << " cycles" << endl;
                break;
        }
    }

return 0;
}

现在，注释掉 CODE BLOCK #1 或 CODE BLOCK #2 会给出正确答案 (232792560)。然而，代码块 #2 比代码块 #1 快得多。

代码块 #1:3,580,000 次循环(我刚刚将中断添加到代码块 #1 中，它运行得更快。但是仍然比复合 IF 语句慢得多。)

代码块 #2:970,000 个周期

有谁知道为什么会出现这种巨大的性能差异？

Answer 1

使用 || 意味着只要有一个为真，就不会计算其余条件。这相当于循环:

    for (int j = 2; j <= 20; j++)
    {
        if ( i % j != 0){
            isDivisible = false;
            break;
        }
    }

如果您尝试这样做，您可能会发现运行时间的差距已经缩小。任何其他差异都可能归因于循环开销，但在您的编译器中启用优化后，我怀疑它们会以相同的速度运行(或者至少有更多相似的时间)。

编辑 关于新的性能差异:
有许多优化的方法来检查数字是否被常量整除，例如对于 N 任何 2 的幂 i % N != 0 可以替换为 i & (N-1)，其他的也存在，但不是很明显。
编译器知道很多这些小技巧，并且在第二个代码块中可能能够优化大部分(如果不是全部)这些可除性检查(因为它们是由您直接写出来的)，而在第一个代码块中它必须决定展开首先循环，然后用常量替换循环变量，然后才能推断出不同的检查。
这种差异可能会导致 block 2 中的代码比 block 1 中的代码优化得更好。