C++循环展开性能差异（欧拉计划）

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快得多。

CODE BLOCK #1：3,580,000个周期（我刚刚在CODE BLOCK #1中添加了break，它运行得更快。然而，仍然比复合IF语句慢得多。）

CODE BLOCK #2：970,000个周期

有人知道为什么会出现如此巨大的性能差异吗？

- Blaine

Answer 1

使用 || 表示一旦其中一个条件为真，其余条件就不会被计算。这相当于以下循环：

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

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

编辑关于新的性能差异： 有许多优化的方法来检查数字是否可被常数整除，例如对于任何2的幂N，i％N！= 0可以替换为i＆（N-1），还有其他不那么明显的方法。 编译器知道很多这些小技巧，在第二个代码块中，它可能能够优化大部分甚至所有这些可除性检查（因为它们是由您直接写出的），而在第一个代码块中，它必须先决定展开循环，然后将循环变量替换为常量，然后才能推理出不同的检查。 这种差异可能导致块2中的代码比块1中的代码更好地优化。

- SirGuy

---

啊，这很有道理。我刚把break语句加到代码块#1中，现在运行速度快多了。但是仍然比复合IF语句慢得多。 使用break语句：3,580,000个周期 - Blaine

Answer 2

3,580,000与970,000不仅仅是循环开销...

在您的最后一个内核中，看起来您打算让Up、Down和square块在其他循环之间保持不变，但这些块是“简洁”的本地块，因此它们包含的数据不会在分支之间共享。不幸的是，即使它们在分支之间共享，您的方法也不起作用。

在您的内部循环中，当前循环的轮次使用了在上一轮计算出的数据。并行化这样的循环并不完全简单，有时甚至无法完成。在您的情况下，一个简单的解决方案是使用原子操作符来增加Up和Down计数器，但这并不高效，因为原子操作符会导致操作的隐式串行化。

您应该考虑使用现有的并行原语来解决这个问题，例如已经过优化的前缀和，例如CUB或Thrust中的原语。

- zluk in the flesh

---

这个回答是否属于不同的问题？我在发布的代码中没有看到任何数组或线程。 - Blastfurnace

不确定你指的是什么。我在回复欧拉计划的帖子。 - zluk in the flesh

即使您进行了编辑，我仍然不确定这个答案如何适用。什么是“上、下和正方形的块”？此外，与其尝试并行化此代码，不如使用最小公倍数的微不足道（且快速）解决方案。 - Blastfurnace

请详细说明最小公倍数方法。我认为循环开销无法解释原帖中4倍的加速问题。我的例子是臭名昭著的普遍算法，运行时间为Θ(n!)。我已经探索了新颖的LCM方法来理解冗余，并且校验和无法实现这个目的。我认为使用启发式循环阻塞来控制INT搜索是没有问题的。 - zluk in the flesh

你可以在 ideone.com 上看到我的解决方案。它简单而快速。 - Blastfurnace