1

1 ～ 1,000,000 回の範囲で繰り返し実行する必要があり、コンパイル時には繰り返し回数がわからないコードがあるとします。ループの展開は、多数のループを考えると無視できる最適化であり、コンパイル時に指定された max_unrolls までしか最適化されないことを理解しています。私が思いついたアイデアは、実行時に指定された回数だけ some_function を本質的に繰り返し実行するバイナリ (または基数 2) 部分ループ アンローラーを実装することです。私はアイデアを実証するためにいくつかのコードを考え出しました。要約版を以下に示します。以下のコードで使用されているメソッドには、使いやすさの観点から多くの問題があります。

  1. 基本的に 2^n-1 回アンロールをコピーするために、コーダーはベース 2 アンロールを手動でコピーする必要があります。
  2. これは、このメソッドを使用する必要がある新しい関数ごとに再実行する必要もあります。

私の質問は 3 つあります。まず、私は何かが欠けています.コンパイラはすでにこれを行うのに十分なほどインテリジェントですか? for第二に、上記の問題を解決しながら、これを標準ループに対してベンチマークすることが可能になるように、これを実装する効率的な方法は何ですか。第三に、あなたの知る限り、これを既に実装しているライブラリがあります。

注意:私は純粋に楽しみのためにこれを行っていますが、これが効果的かどうかを知る専門知識はありません。コードのテストを行いましたが、非常に小さな改善しか見られませんでしたが、公正な比較を行うには、手動で展開することが十分ではなかったと思います。また、この方法が巨大なバイナリ サイズを作成する可能性があることは承知していますが、これは時間とメモリのトレードオフとして価値があると思います。また、アセンブリを投稿すると、それを理解するのにさらに1年ほどかかるでしょう.

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回実行するアンローラーが必要です。関数呼び出しはインライン化する必要があるため、関数ポインターまたは-s の代わりにファンクター オブジェクトを使用する必要があり、ファンクターの型はテンプレートである必要があります。アンローラー自体は、整数テンプレート引数による再帰ループとして実装できます。C++ の関数は部分的なテンプレートの特殊化を行うことができないため、アンローラーをテンプレート クラスにする必要があります。サンプルコードは次のとおりです。std::function

// 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 に答える