1

考虑一些需要重复执行 1-1,000,000 次的代码，并且在编译时不知道重复次数。据我了解，考虑到大量循环，循环展开将是一个可以忽略不计的优化，并且只会优化到编译时指定的 max_unrolls。我想出的想法是实现一个二进制（或基数 2）部分循环展开器，它基本上重复执行 some_function 在运行时指定的次数。我想出了一些代码来演示这个想法，下面显示了一个浓缩版本。从可用性的角度来看，以下代码中使用的方法存在许多问题。

  1. 它需要编码人员手动复制出 base 2 unroll 基本上复制出 unroll 2^n-1 次。
  2. 对于需要使用此方法的每个新功能，也需要重新执行此操作。

我的问题是三方面的。首先，我是否遗漏了一些东西，编译器是否已经足够智能，可以自己做这件事？for其次，什么是实现这一点的有效方法，以便在解决上述问题的同时将其与标准循环进行基准测试变得可行。第三，据您所知，有一个库已经实现了这一点。

请注意：我这样做纯粹是为了好玩，但没有专业知识知道这是否有效。我已经对代码进行了测试，但只发现了非常小的改进，但是我相信我无法手动展开足够远的距离来进行公平的比较。我也知道这种方法有可能创建大量的二进制大小，但是我相信这将是一个值得的时间内存权衡。此外，如果您发布任何程序集，我可能需要一年左右的时间才能理解它。

inline void some_reapeated_function(int &function_parameter_1, int &function_parameter_2)
{
    function_parameter_1 /= function_parameter_2;
}

// Function to be called when you need it to be unrolled.
int runtime_unroll(unsigned int &no_of_loops, int &function_parameter_1, int &function_parameter_2)
{
    std::vector<bool> binary_vector;

    // Stores the number of loops in a binary representation in a vector.
    binary_function.reserve(no_of_loops);
     while(no_of_loops) 
    {
        if (no_of_loops&1)
          binary_vector.push_back(false);
        else
          binary_vector.push_back(true);
        no_of_loops>>=1;
    } 

    // If binary of no_of_loops contains a 2^0 execute once.
    if (binary_vector[0])
    {
        some_reapeated_function(function_parameter_1,function_parameter_2);
    }
    // If binary of no_of_loops contains a 2^1 execute twice.
    if (binary_vector[1])
    {
        some_reapeated_function(function_parameter_1,function_parameter_2);
        some_reapeated_function(function_parameter_1,function_parameter_2);
    }
    //If binary of no_of_loops contains a 2^2 execute 4 times.
    if (binary_vector[2])
    {
        some_reapeated_function(function_parameter_1,function_parameter_2);
        some_reapeated_function(function_parameter_1,function_parameter_2);
        some_reapeated_function(function_parameter_1,function_parameter_2);
        some_reapeated_function(function_parameter_1,function_parameter_2);
    }


    /* This example only covers from 1 to 2^3-1 or up to 7 unrolls. 
    This can continue depending on the number of repetitions needed and 
    could incorporate a for loop to continue after the loop has fully unrolled */
}
4

1 回答 1

2

您可以使用 C++ 模板轻松实现类似的功能。请注意，您仍然受制于编译器：不能保证所有函数调用都会被内联。如果不是，您可以尝试使用__forceinline关键字（或其等效项）。

首先，您需要一个展开器，它以函数为参数并在完全展开的循环中执行K次。函数调用必须是内联的，所以你必须使用函子对象而不是函数指针或std::function-s，函子的类型必须是模板。展开器本身可以通过整数模板参数实现为递归循环。由于 C++ 中的函数不能有部分模板特化，我们必须使我们的展开器成为模板类。这是示例代码：

// execute UnrollCnt times in unrolled fashion
template<int UnrollCnt, class Functor> struct Unroller {
    static inline void Run(int base, const Functor &func) {
        func(base);
        Unroller<UnrollCnt - 1, Functor>::Run(base + 1, func);
    }
};
template<class Functor> struct Unroller<0, Functor> {
    static inline void Run(int base, const Functor &func) {
    }
};

给定展开器，我们可以轻松实现展开循环。如果我们有N次迭代，那么我们可以调用我们的展开器[N/K]次，然后像往常一样执行一些剩余的调用。请注意，函子的类型在这里仍然必须是模板。这是代码：

// execute with argument in range [begin, end)
template<int UnrollCnt, class Functor>
void UnrolledFor(int begin, int end, const Functor &func) {
    // iterations with unrolling
    int iter = begin;
    for (; iter <= end - UnrollCnt; iter += UnrollCnt)
        Unroller<UnrollCnt, Functor>::Run(iter, func);
    // last iterations without unrolling
    for (; iter < end; iter++)
        func(iter);
}

现在我们可以UnrolledFor为任何接受单个参数的函数调用循环，即循环的迭代次数。例如，我们可以计算从0到N-1的数字之和：

long long ans = 0;
int main() {
    int cnt = 0;
    scanf("%d", &cnt);
    int start = clock();
    // note: passing a lambda function here, requesting 8x unrolling
    UnrolledFor<8>(0, cnt, [](int i) {
        ans += i;
    });
    int elapsed = clock() - start;
    printf("%lld   (%d pg)\n", ans, elapsed);
    return 0;
}

但是请注意，手动展开可能会工作得更快，因为这里的厚抽象级别对于编译器来说并非易事。例如，以下是我观察到的示例代码的一些时序（N = 2000000000）：

With MSVC 2013 x64:
1999999999000000000   (421 pg)   // 8x unrolling, ans is global
1999999999000000000   (1389 pg)  // 1x unrolling, ans is global
1999999999000000000   (4664 pg)  // 8x unrolling, ans is local
1999999999000000000   (1388 pg)  // 1x unrolling, ans is local
With MinGW GCC 5.1.0 x64:
1999999999000000000   (1388 pg)  // 1x unrolling, ans is global
1999999999000000000   (1404 pg)  // 8x unrolling, ans is global
1999999999000000000   (1389 pg)  // 1x unrolling, ans is local
1999999999000000000   (1393 pg)  // 8x unrolling, ans is local

如您所见，只有具有全局ans变量的 MSVC 确实从展开中获胜。但是对于局部ans变量（通过引用捕获），它反而慢了好几倍。

因此，如果您真的对性能很着迷，我建议您使用宏来展开循环，它们绝对不会增加任何开销。

于 2015-11-27T14:16:37.887 回答