c++ - C++ 2 次元配列の最適化

Question

C++ で double の 2 次元配列 (密な行列) を表現する方法が必要で、アクセスオーバーヘッドを最小限に抑える必要があります。

さまざまな linux/unix マシンと gcc バージョンでタイミングを計りました。次のように宣言された、ベクトルの STL ベクトル。

vector<vector<double> > matrix(n,vector<double>(n));

経由でアクセスするmatrix[i][j]と、次のように宣言された配列よりもアクセスが 5% から 100% 遅くなります。

double *matrix = new double[n*n];

i+n*jmatrix[index(i,j)]に評価されるインラインインデックス関数を介してアクセスされます。index(i,j)STL を使用せずに 2 次元配列を配置する他の方法 (各行の先頭への n 個のポインターの配列、またはスタック上の全体を一定サイズとして定義するmatrix[n][n]方法) は、インデックス関数メソッドとほぼ同じ速度で実行されます。

最近の GCC バージョン (> 4.0) では、最適化がオンになっている場合、STL ベクトルのベクトルを非 STL コードとほぼ同じ効率でコンパイルできるようですが、これは多少マシンに依存します。

可能であれば STL を使用したいのですが、最速のソリューションを選択する必要があります。GCC で STL を最適化した経験のある人はいますか?

score 8 · Accepted Answer

GCC を使用している場合、コンパイラは行列アクセスを分析し、場合によってはメモリ内の順序を変更できます。マジックコンパイラフラグは次のように定義されます。

-fipa-matrix-reorg

行列の平坦化と転置を実行します。行列の平坦化は、m 次元の行列をそれに相当する n 次元の行列 (n < m) に置き換えようとします。これにより、マトリックスの要素にアクセスするために必要な間接的なレベルが減少します。2 番目の最適化は、キャッシュの局所性を改善するために行列の次元の順序を変更しようとする行列の転置です。両方の最適化には、fhole-program フラグが必要です。転置は、プロファイリング情報が利用可能な場合にのみ有効になります。

このオプションは -O2 または -O3 では有効にならないことに注意してください。自分で渡す必要があります。

score 8 · Accepted Answer

私の推測では、行列の場合、1D STL 配列を使用し、() 演算子をオーバーライドして 2D 行列として使用するのが最速です。

ただし、STL では、サイズ変更不可の数値配列専用の型である valarray も定義されています。インプレース操作のためのさまざまな最適化もあります。

valarray は引数として数値型を受け入れます:

valarray<double> a;

次に、スライス、間接配列などを使用できます...そしてもちろん、valarray を継承して、2D 配列に対して独自の operator()(int i, int j) を定義できます...

score 7 · Accepted Answer

これは参照の局所性の問題である可能性が非常に高いです。vector内部配列を割り当てるために使用newするため、各行は各ブロックのヘッダーのためにメモリ内で少なくとも少し離れています。それらを割り当てるときにメモリがすでに断片化されている場合、距離が離れている可能性があります。配列の異なる行は、少なくともキャッシュラインフォールトを発生させる可能性が高く、ページフォールトを発生させる可能性があります。本当に不運な場合は、2 つの隣接する行が TLB スロットを共有するメモリライン上にある可能性があり、1 つにアクセスするともう 1 つが追い出されます。

対照的に、他のソリューションは、すべてのデータが隣接していることを保証します。可能な限り少ないキャッシュラインを横切るように構造を調整すると、パフォーマンスが向上する可能性があります。

vectorサイズ変更可能な配列用に設計されています。配列のサイズを変更する必要がない場合は、通常の C++ 配列を使用してください。STL 操作は通常、C++ 配列で操作できます。

配列を正しい方向、つまり (連続するメモリアドレス) を下ではなく横に移動するようにしてください。これにより、キャッシュ障害が減少します。

score 6 · Accepted Answer

高速な行列/ベクトルクラスを提供する Boost.UBLAS を使用することをお勧めします。

score 1 · Accepted Answer

http://eigen.tuxfamily.org/にあるEigenC++テンプレートライブラリを確認することをお勧めします。AltiVecまたはsse2コードを生成して、ベクトル/行列の計算を最適化します。

score 1 · Accepted Answer

公平を期すためには、マトリックスで使用しているアルゴリズムによって異なります。

double name[n*m] 形式は、乗算と加算以外のオーバーヘッドがほとんどなく、行がキャッシュ内で一貫性のあるパックされたデータであるため、行単位でデータにアクセスする場合に非常に高速です。

アルゴリズムが列の順序付けされたデータにアクセスする場合、他のレイアウトの方がキャッシュの一貫性がはるかに優れている可能性があります。アルゴリズムがマトリックスの象限のデータにアクセスする場合、他のレイアウトの方が優れている場合があります。

使用方法と使用しているアルゴリズムのタイプに向けた調査を行うようにしてください。マトリックスが非常に大きい場合、これは特に重要です。キャッシュミスは、各アドレスにアクセスするために 1 つまたは 2 つの追加の数学演算を必要とするよりもパフォーマンスに悪影響を与える可能性があるためです。

score 1 · Accepted Answer

1

vector< double >( n*m ); と同じくらい簡単に実行できます。

于 2008-09-30T17:37:05.943 に答える

score 0 · Accepted Answer

Boost には uBLAS の実装があります。一見の価値ありです。

http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/matrix.htm

score 0 · Accepted Answer

独自の 2 次元配列クラスを宣言することで、生の画像に対してこれを行ったことがあります。

通常の 2D 配列では、次のような要素にアクセスします。

配列[2][3]。その効果を得るには、オーバーロードされた [] 配列アクセサーを持つクラス配列が必要です。ただし、これは本質的に別の配列を返すため、2 番目の次元が得られます。

このアプローチの問題は、関数呼び出しのオーバーヘッドが 2 倍になることです。

私がやった方法は、() スタイルのオーバーロードを使用することでした。

したがって、array[2][3] の代わりに、このスタイルの array(2,3) を変更してもらいました。

その () 関数は非常に小さく、インライン化されていることを確認しました。

その一般的な概念については、このリンクを参照してください: http://www.learncpp.com/cpp-tutorial/99-overloading-the-parenthesis-operator/

必要に応じて、型をテンプレート化できます。
私が持っていた違いは、私の配列が動的だったことです。宣言するcharメモリのブロックがありました。また、列キャッシュを使用したので、次の行がバイトシーケンスのどこから始まるかがわかりました。アクセスは、画像処理に使用していたため、隣接する値にアクセスするために最適化されました。

コードなしで説明するのは難しいですが、基本的に結果は C と同じくらい速く、理解しやすく使いやすいものでした。

score 0 · Accepted Answer

別の関連ライブラリは Blitz++ です: http://www.oonumerics.org/blitz/docs/blitz.html

Blitz++ は、配列操作を最適化するように設計されています。

c++ - C++ 2 次元配列の最適化

10 に答える 10

Related

Reference