5

我有一个关于 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 次循环

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

4

2 回答 2

7

使用这样||一种方法，即只要一个为真，其余的条件就不会被计算。这相当于循环：

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

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

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

于 2013-11-08T19:27:29.510 回答
0

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

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

在您的内部循环中，当前循环使用上一轮计算的数据。并行化这样的循环并不是一件容易的事，有时它根本无法完成。在您的情况下，一个简单的解决方案是使用原子运算符来增加 Up 和 Down 计数器，但这不会有效，因为原子运算符会导致操作的隐式序列化。

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

于 2013-11-08T20:26:23.403 回答