如何在运行时间实现 base 2 循环展开以进行优化

Question

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

它需要编码人员手动复制出 base 2 unroll 实质上复制出 unroll 2^n-1 次。
这也需要为每个需要使用此方法的新功能重新完成。

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

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

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 */
}

Answer 1

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

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

// 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 次迭代，那么我们可以调用我们的 unroller [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 变量（通过引用捕获）它反而慢了好几倍。

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

如何在运行时间实现 base 2 循环展开以进行优化

How to implement base 2 loop unrolling at run-time for optimization purposes

c++

loops

optimization

loop-unrolling

如何在 运行 时间实现 base 2 循环展开以进行优化

How to implement base 2 loop unrolling at run-time for optimization purposes

c++

loops

optimization

loop-unrolling

如何在运行时间实现 base 2 循环展开以进行优化