float配列のより速いabs-max
https://stackoverflow.com/questions/817604
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
オーディオのピークメーターをリアルタイムで描画する必要があります。 1秒あたり最小44100サンプル、最小40ストリーム。各バッファは64〜1024サンプルです。各バッファーからabs maxを取得する必要があります。 （これらは、一種のローパスフィルターを介して供給され、約20ms間隔で描画されます。）
for(int i = 0; i < numSamples; i++)
{
absMaxOfBuffer = MAX( fabs( buffer[i] ), absMaxOfBuffer);
}
それが今のやり方です。もっと早くやりたいです。バッファーには-1から1の範囲の浮動小数点数があるため、fabsです。
質問、これをより速く行うためのいくつかのトリッキーなcomp-sciクイックソート風の方法はありますか？
失敗した場合、フロート用のブランチレスABSおよびMAX関数は存在しますか？
編集： プライマリプラットフォームはLinux / gccですが、Windowsポートが計画されています（おそらくmingwを使用）。
編集、2番目：
質問の中心となった実際のアルゴ構造に関するビットのため、私はonebyoneに同意しました。
ループをその時点で4に展開し、符号ビットをゼロにしてからSSE（maxps命令）で最大値を取得し、バナナが剥がれないかどうかを確認します。提案をありがとう、次点としてあなたの何人かを投票しました。 ：）
解決
fabと比較はどちらもIEEE浮動小数点数に対して非常に高速です（原則として、単一整数opの高速）。
コンパイラーが両方の操作をインライン化しない場合は、コンパイラーがそれまでインライン化するか、アーキテクチャーの実装を見つけて自分でインライン化します。
IEEE浮動小数点数が同じビットパターンの整数と同じ順序で移動するという事実から何かを得ることができます。つまり、
f > g iff *(int*)&f > *(int*)&g
そのため、一度fabsを作成したら、intのブランチフリーmaxはfloatでも機能すると思います（もちろん同じサイズであると仮定して）。これがなぜ機能するかの説明はここにあります： http：//www.cygnus-software .com / papers / comparingfloats / comparingfloats.htm 。ただし、コンパイラーはCPUと同様にこれらすべてをすでに知っているため、違いは生じない可能性があります。
それを行うための複雑な高速な方法はありません。アルゴリズムはすでにO（n）であり、これに勝てずにすべてのサンプルを見ることができます。
おそらく、プロセッサのSIMD（つまりIntelのSSE2）には、コードよりも多くのデータをクロックサイクルごとに処理するのに役立つ何かがあると思います。しかし、私は何を知りません。ある場合は、おそらく数倍高速になります。
とにかく40の独立したストリームを扱っているので、特にマルチコアCPUで並列化できます。それはせいぜいいくつかの要因により速くなります。 <！> quot;ちょうど<！> quot;適切な数の追加のスレッドを起動し、それらの間で作業を分割し、可能な限り軽量のプリミティブを使用して、それらがすべて完了したことを示します（スレッドバリアかもしれません）。 40ストリームすべての最大値をプロットするのか、それとも個別に最大値をプロットするのかは明確ではないので、結果が次の段階に確実に配信されることを除いて、実際にワーカースレッドを同期する必要はないデータ破損なし。
おそらくコンパイラがループを展開した量を確認するために、逆アセンブリを調べる価値があります。もう少し展開してみて、違いが出るかどうかを確認してください。
考慮すべきもう1つのことは、キャッシュミスの数と、キャッシュにいくつかの手がかりを与えて適切なページを事前にロードできるようにすることで、数を減らすことができるかどうかです。しかし、これについては経験がなく、あまり希望を抱きません。 __builtin_prefetchはgccの魔法の呪文であり、最初の実験は<！> quot;このブロックのループに入る前に次のブロックの先頭をプリフェッチすることだと思います<！> quot;。
現在、必要な速度の何パーセントですか？または、<！> quot;できるだけ速く<！> quot;？
の場合他のヒント
http：// wwwに文書化されているブランチレスファブがあります。 scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms
また、最新バージョンのGCCでは、MMX命令を使用してブランチレスfabsがインライン化されます。 fminとfmaxもありますが、GCCはそれらをインライン化しません（call fminを取得します）。
試すこと：
- fabs（）はインライン関数ではない可能性があります。
- 特別な組み立て手順が役立つ場合があります。 Intelでは、SSEに一度に最大4つのフロートを計算する命令があります。
- これに失敗すると、IEEE 754仕様では、aとbが非負の場合、a <！> lt; bは*（int *）<！> amp; a <！> lt;と同等です。 *（int *）<！> amp; b。さらに、任意のaに対して、MSBを反転することにより、aから-aを計算できます。一緒に、これらのプロパティは、いくつかのビットいじりハッキングを有効にする可能性があります。
- すべてのサンプルの最大値が本当に必要ですか？おそらく、最大値が複数回発生する可能性があり、すべての入力を検査しない可能性があります。
- ストリーミング方式で最大値を計算できますか？
Eigen をご覧ください。
これは、非ベクトル化コードへの適切なフォールバックを備えた SSE（2以降）およびAltiVec命令セットを使用するC ++テンプレートライブラリです。
高速。 （ベンチマークを参照）。
式テンプレートを使用すると、適切な場合に一時的にインテリジェントに削除し、遅延評価を有効にすることができます。Eigenはこれを自動的に処理し、ほとんどの場合エイリアスを処理します。
SSE（2以降）およびAltiVec命令セットに対して明示的なベクトル化が実行され、非ベクトル化コードへの適切なフォールバックが行われます。式テンプレートを使用すると、式全体に対してこれらの最適化をグローバルに実行できます。
固定サイズのオブジェクトを使用すると、動的なメモリ割り当てが回避され、それが理にかなったときにループが展開されます。
大きな行列の場合、キャッシュの使いやすさに特別な注意が払われます。
別の質問で質問に答えることは正確に答えているわけではありませんが、ちょっと...私もC ++開発者ではありません。
これをC ++で開発し、dspを実行しているため、matlab、またはオクターブ（オープンソース）に接続して数学を計算して結果を得ることができませんか？
これらのソフトウェアに実装されている関数（conv、fft、ifft、fir、freqz、stem、graph、plot、meshなどのutil関数のプロットなど）は既に実装されています。 Photoshopを見てみると、MATLABと呼ばれる大きなフォルダーがあります。アプリケーションから呼び出しを取得し、それを動的なmatlabに送信し、結果をアプリケーションに返す.mファイルがあります。
お役に立てば幸いです。
わかりやすい最適化：
- ループをポインター演算バージョンに変換します（コンパイラーがこれを認識しないと仮定）
- IEEE 754標準は、その表現を符号の大きさとして定義しています。したがって、最上位ビットを0に設定することは、fabs（）を呼び出すことと同じになります。たぶん、この関数はすでにこのトリックを使用しています。
あなたの目的のために、絶対値を取る代わりに二乗することができます。数学的に| a | <！> lt; | b | if a ^ 2 <！> lt; b ^ 2およびその逆。乗算は、一部のマシンではfabs（）より高速かもしれません（？）、私は知らない。
