15

Herb Sutter の説得力のある講義Not your Father's C++に触発されて、Microsoft の Visual Studio 2010 を使用して C++ の最新バージョンをもう一度見てみることにしました。パフォーマンスが重要なコード。

ベンチマークとして、同じ単純な FFT アルゴリズムをさまざまな言語で記述してみることにしました。

complex組み込みの型とvectorコレクションを使用する次の C++11 コードを思いつきました。

#include <complex>
#include <vector>

using namespace std;

// Must provide type or MSVC++ barfs with "ambiguous call to overloaded function"
double pi = 4 * atan(1.0);

void fft(int sign, vector<complex<double>> &zs) {
    unsigned int j=0;
    // Warning about signed vs unsigned comparison
    for(unsigned int i=0; i<zs.size()-1; ++i) {
        if (i < j) {
            auto t = zs.at(i);
            zs.at(i) = zs.at(j);
            zs.at(j) = t;
        }
        int m=zs.size()/2;
        j^=m;
        while ((j & m) == 0) { m/=2; j^=m; }
    }
    for(unsigned int j=1; j<zs.size(); j*=2)
        for(unsigned int m=0; m<j; ++m) {
            auto t = pi * sign * m / j;
            auto w = complex<double>(cos(t), sin(t));
            for(unsigned int i = m; i<zs.size(); i+=2*j) {
                complex<double> zi = zs.at(i), t = w * zs.at(i + j);
                zs.at(i) = zi + t;
                zs.at(i + j) = zi - t;
            }
        }
}

この関数は、 が 2 の整数乗であるn要素ベクトルに対してのみ機能することに注意してください。n高速な FFT コードを探している人は、 FFTWnを参照してください。

私が理解しているように、xs[i]a にインデックスを付けるための C の従来の構文vectorは境界チェックを行わないため、メモリ セーフではなく、非決定論的な破損やメモリ アクセス違反などのメモリ エラーの原因となる可能性があります。だからxs.at(i)代わりに使った。

さて、このコードを「安全で高速」にしたいのですが、私は C++11 の専門家ではないので、このコードをより慣用的または効率的にするための改善をお願いしたいと思います。

4

1 に答える 1

14

at() の使用において、過度に「安全」になっていると思います。ほとんどの場合、使用されるインデックスは、for ループ内のコンテナーのサイズによって制約されるため、簡単に検証できます。

例えば

  for(unsigned int i=0; i<zs.size()-1; ++i) { 
    ...
    auto t = zs.at(i);

at() として残すのは (i + j) だけです。それらが常に制約されるかどうかはすぐにはわかりません（ただし、本当に確信が持てない場合は、おそらく手動で確認しますが、この場合に意見を述べるほどFFTに精通していません）。

ループの反復ごとに繰り返されるいくつかの固定計算もあります。

int m=zs.size()/2;
pi * sign
2*j

zs.at(i + j) は 2 回計算されます。

オプティマイザーがこれらをキャッチする可能性はありますが、これをパフォーマンス クリティカルとして扱っていて、タイマーでテストしている場合は、それらをループから引き上げます (または、zs.at(i + j の場合)。 ）、最初の使用時に参照を取り、それがタイマーに影響するかどうかを確認してください。

オプティマイザーの第二の推測について言えば、.size() への呼び出しは、少なくとも内部メンバー変数への直接呼び出しとしてインライン化されると確信していますが、それを呼び出す回数を考えると、私も実験しますzs.size() および zs.size()-1 のローカル変数を事前に導入します。それらもそのようにレジスターに入れられる可能性が高くなります。

これらすべてが実行時間全体にどの程度の違いをもたらすか (もしあれば) はわかりません - そのうちのいくつかはオプティマイザによってすでに捕捉されている可能性があり、関連する計算に比べて違いは小さいかもしれませんが、価値があります。ショット。

慣用的な私の唯一のコメントは、実際には、size() が std::size_t を返すことです (これは通常、unsigned int の typedef ですが、代わりにその型を使用する方が慣用的です)。auto を使用したいが、警告を回避したい場合は、ul サフィックスを 0 に追加してみてください。ただし、それが慣用的であるとは言えません。ここでイテレータを使用しないことで、すでに慣用的ではなくなっていると思いますが、それができない理由はわかります (簡単に)。

アップデート

私はすべての提案を試してみましたが、i+j と 2*j の事前計算を除いて、すべて測定可能なパフォーマンスの改善がありましたが、実際にはわずかな速度低下を引き起こしました! コンパイラの最適化を妨げたか、何らかの目的でレジスタを使用できないようにしたのだと思います。

全体として、10% を超えるパフォーマンスが得られました。それらの提案で改善します。ループの 2 番目のブロックを少しリファクタリングしてジャンプを回避すれば、さらに多くのことができるのではないかと思います。そうすると、SSE2 命令セットを有効にすると大幅に向上する可能性があります (そのまま試してみたところ、わずかに遅くなりました)。

リファクタリングと、cos 呼び出しと sin 呼び出しに MKL のようなものを使用することで、より大きな改善が得られ、脆弱性が少なくなると思います。そして、どちらも言語に依存しません (これはもともと F# の実装と比較されていたことを知っています)。

更新 2

zs.size() を事前に計算すると違いが生じることを忘れていました。

アップデート 3

また、i < j チェックに続くブロックを std::swap に煮詰めることができることを (OP へのコメントで @xeo が思い出させるまで) 言うのを忘れていました。これはより慣用的であり、少なくともパフォーマンスは同じです。最悪の場合、記述されたのと同じコードにインライン化する必要があります。実際、私がそれを行ったとき、パフォーマンスに変化は見られませんでした。それ以外の場合、移動コンストラクターが使用可能であれば、パフォーマンスの向上につながる可能性があります。

于 2012-04-12T10:58:14.083 に答える