c++ - 快速生成变量嵌套for循环的数字组合

Question

我有以下代码，它为嵌套的 for 循环生成数字/索引的组合

#include <iostream>
#include <array>

template<size_t ... Rest>
inline void index_generator() {
    constexpr int size = sizeof...(Rest);
    std::array<int,size> maxes = {Rest...};
    std::array<int,size> a;
    int i,j;
    std::fill(a.begin(),a.end(),0);

    while(1)
    { 
        for(i = 0; i<size; i++) {
            std::cout << a[i] << " ";
        }
        std::cout << "\n";

        for(j = size-1 ; j>=0 ; j--)
        {
            if(++a[j]<maxes[j])
                break;
            else
                a[j]=0;
        }
        if(j<0)
            break;
    }
}

int main()
{
    index_generator<2,3,3>();
    return 0;
}

输出如下

0 0 0 
0 0 1 
0 0 2 
0 1 0 
0 1 1 
0 1 2 
0 2 0 
0 2 1 
0 2 2 
1 0 0 
1 0 1 
1 0 2 
1 1 0 
1 1 1 
1 1 2 
1 2 0 
1 2 1 
1 2 2

这确实等同于拥有

for (int i=0; i<2; ++i)
    for (int j=0; j<3; ++j)
        for (int k=0; i<3; ++k)

我可以使用上述方法生成任意数量的 嵌套 for 循环 的等价物，但是我注意到随着循环数量的增加，与等效的代码相比，这段代码的执行速度越来越慢(即嵌套 for 循环)。我已经用 gcc 5.3 和 clang 3.8 检查过。也许这是因为处理器很难预测 while(true) 中的分支，或者可能是其他原因。

我在最内层循环中所做的通常是从两个数组访问数据并对它们进行乘法运算，例如 c_ptr[idx] +=a_ptr[idx]*b_ptr[idx]。由于使用嵌套 for 循环和使用上述技术生成的索引是相同的，因此内存访问模式保持不变。因此，就数据访问而言，我很确定这不是缓存未命中/命中问题。

所以我的问题是:

1. 有没有一种方法可以像嵌套 for 循环样式代码一样快地生成这些组合/索引，甚至可能更快？
2. 既然我们知道要设置的 for 循环的数量并且 for 循环的索引在编译时是已知的，那么可以不利用更好的优化机会吗？例如 SIMD？

Answer 1

您可以通过对所有维度进行乘法的单个循环来生成它，并对最终索引使用模数。

#include <iostream>
#include <array>

template<size_t ... Rest>
inline void index_generator( ) {
    constexpr int size = sizeof...( Rest );
    std::array<int, size> maxes = { Rest... };
    int total = 1;
    for (int i = 0; i<size; ++i) {
        total *= maxes[i];
    }

    for (int i = 0; i < total; ++i) {
        int remaining = total;
        for (int n = 0; n < size; ++n) {
            remaining /= maxes[n];
            std::cout << ( i / remaining ) % maxes[n] << " ";
        }
        std::cout << std::endl;
    }
}

或者只是生成递归模板来实际生成嵌套循环并让编译器为您优化它。这取决于索引的实际使用情况。现在你的功能不是很有用。

编辑:

对三个解决方案进行了基准测试，第一个是问题中的那个，第二个是没有数组的我的，第三个是递归模板。最后一个有一个缺点，那就是访问要使用的实际参数有点困难，但并非不可能。还必须添加一个求和计算以避免被优化，并且必须删除控制台输出以减少它在基准测试中的影响。结果来 self 的 i7 机器 Release模式(VS 2015 社区)和下面给定的设置。 LOG 和 PROFILE_SCOPE 是我的宏。

#include <array>

// Original from the question
template<size_t ... Rest>
inline void index_generator1( ) { 
    constexpr int size = sizeof...( Rest );
    std::array<int, size> maxes = { Rest... };
    std::array<int, size> a;
    int i, j;
    std::fill( a.begin( ), a.end( ), 0 );

    int x = 0;

    while (1) {
        for (i = 0; i < size; i++) {
            x += a[i];
        }

        for (j = size - 1; j >= 0; j--) {
            if (++a[j] < maxes[j])
                break;
            else
                a[j] = 0;
        }
        if (j < 0)
            break;
    }

    LOG( x )
}

// Initial try
template<size_t ... Rest>
inline void index_generator2( ) { 
    constexpr int size = sizeof...( Rest );

    int x = 0;

    std::array<int, size> maxes = { Rest... };
    int total = 1;
    for (int i = 0; i < size; ++i) {
        total *= maxes[i];
    }

    for (int i = 0; i < total; ++i) {
        int remaining = total;
        for (int n = 0; n < size; ++n) {
            remaining /= maxes[n];
            x += ( i / remaining ) % maxes[n];
        }
    }

    LOG(x)
}


// Recursive templates
template <int... Args>
struct Impl;

template <int First, int... Args>
struct Impl<First, Args...>
{
    static int Do( int sum )
    {
        int x = 0;
        for (int i = 0; i < First; ++i) {
            x += Impl<Args...>::Do( sum + i );
        }

        return x;
    }
};

template <>
struct Impl<>
{
    static int Do( int sum )
    {
        return sum;
    }
};

template <int... Args>
void index_generator3( )
{
    LOG( Impl<Args...>::Do( 0 ) );
}

执行代码

{
    PROFILE_SCOPE( Index1 )
    index_generator1<200, 3, 400, 20>( );
}
{
    PROFILE_SCOPE( Index2 )
    index_generator2<200, 3, 400, 20>( );
}
{
    PROFILE_SCOPE( Index3 )
    index_generator3<200, 3, 400, 20>( );
}

控制台结果:

[19:35:50]: 1485600000
[19:35:50]: 1485600000
[19:35:50]: 1485600000

[19:35:56]:          PerCall(ms)
[19:35:56]:   Index1     10.4016
[19:35:56]:   Index2     75.3770
[19:35:56]:   Index3      4.2299