安全で高速FFT

Question

ハーブ・サッターの説得力のある講義Not your father's C++に触発された私は、MicrosoftのVisual Studio 2010を使ってC++の最新バージョンをもう一度見直すことにしました。私は特に、C++は「安全で速い」と主張しました。パフォーマンスクリティカルなコードをたくさん書く。

ベンチマークとして、同じ単純なFFTアルゴリズムをさまざまな言語で作成しようと決めました。

Iは、内蔵complexタイプとvectorコレクションを使用して、次のC++ 11のコードを思い付いた：この関数は唯一nが不可欠であるn -elementベクトルのために働くことを

#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で動作する高速FFTコードをお探しの場合は、FFTWをご覧ください。

私が理解しているように、vectorを索引付けするためのCの構文では、境界チェックは行われないため、メモリに安全ではなく、非決定的な破損やメモリアクセス違反などのメモリエラーの原因になることがあります。だから代わりにxs.at(i)を使用しました。

私はこのコードを「安全で高速」にしたいと思いますが、私はC++ 11のエキスパートではありませんので、このコードを改善してより慣用的で効率的なものにしたいのですか？

Answer 1

あなたはat（）の使用で過度に安全であると思います。ほとんどの場合、使用されるインデックスは、forループ内のコンテナのサイズによって制約されていることを自明に検証できます。

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

at（）のように残すのは（i + j）sです。彼らが常に制約されているかどうかはすぐには分かりませんが（本当にわからない場合は手動でチェックしますが、この場合は十分に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はprecalcs除いて - 彼らは実際にはわずかな減速を引き起こしました！私は彼らがコンパイラの最適化を妨げているとか、いくつかのもののためにレジスタを使うことができないと推測しています。

全体的に私は10％を超えるパーフォーマンスを得ました。それらの提案による改善。 SSE2命令セットを有効にすることで、大幅に向上させることができます（私はそれを試してみて、わずかに減速を見せました）、ループの2番目のブロックが少しリファクタリングされてジャンプを回避すると、さらに多くの問題が発生する可能性があります。

リファクタリングは、cosとsin呼び出しにMKLのようなものを使用すると、より大きく、脆弱ではない改善が得られるはずです。そして、これらの事柄のどちらも言語依存ではありません（私はこれがもともとF＃実装と比較されていたことを知っています）。私は事前に計算zs.size（ことを言及するのを忘れ

アップデート2

）はは違いを作ることでした。 3

アップデートはまた（OPにコメントで@xeoによって思い出されるまで）は、i < jのチェック、次のブロックがSTD ::スワップに煮詰めすることができると言うのを忘れていました。これはより慣用的であり、少なくともパフォーマンス面では最悪の場合、書かれたコードと同じコードにインライン展開する必要があります。実際に私がそれをしたとき、私はパフォーマンスに変化は見ませんでした。他のケースでは、移動コンストラクタが利用可能な場合、パフォーマンスが向上する可能性があります。