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).但是,CODE BLOCK#2比CODE BLOCK#1快得多.

代码块#1:3,580,000个循环(我只是将中断添加到CODE BLOCK#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),其他的也存在并且不那么明显.
编译器知道很多这些小技巧,并且在第二个代码块中可能能够优化大多数(如果不是全部)这些可分性检查(因为它们是由你直接写出的),而在第一个代码块中它必须决定展开首先循环,然后用常量替换循环变量,甚至可以推断出不同的检查.
这可能与块1中的块2中的优化代码有所不同.