Boost::multi_array のパフォーマンスに関する質問
-
22-07-2019 - |
質問
次のテスト プログラムを使用して、boost::multi_array のパフォーマンスをネイティブに動的に割り当てられた配列と比較しようとしています。
#include <windows.h>
#define _SCL_SECURE_NO_WARNINGS
#define BOOST_DISABLE_ASSERTS
#include <boost/multi_array.hpp>
int main(int argc, char* argv[])
{
const int X_SIZE = 200;
const int Y_SIZE = 200;
const int ITERATIONS = 500;
unsigned int startTime = 0;
unsigned int endTime = 0;
// Create the boost array
typedef boost::multi_array<double, 2> ImageArrayType;
ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]);
// Create the native array
double *nativeMatrix = new double [X_SIZE * Y_SIZE];
//------------------Measure boost----------------------------------------------
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
boostMatrix[x][y] = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Boost] Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
//------------------Measure native-----------------------------------------------
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
nativeMatrix[x + (y * X_SIZE)] = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Native]Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
return 0;
}
次の結果が得られます。
[Boost] Elapsed time: 12.500 seconds
[Native]Elapsed time: 0.062 seconds
multi_array がそれほど遅いとは信じられません。誰か私が間違っていることを見つけられますか?
メモリへの書き込みを行っているため、キャッシュは問題ないと思います。
編集:これはデバッグ ビルドでした。Laserallan の提案に従って、リリース ビルドを実行しました。
[Boost] Elapsed time: 0.266 seconds
[Native]Elapsed time: 0.016 seconds
はるかに近いです。しかし、私にとって 16 対 1 はまだ高いように思えます。
そうですね、明確な答えはありませんが、今のところネイティブ配列を使用した実際のコードをそのままにして先に進みます。
それが私のテストの最大の欠陥だったので、Laserallan の答えを受け入れました。
ありがとうございます。
解決
リリースまたはデバッグを構築していますか?
デバッグモードで実行している場合、テンプレートマジックが適切にインライン化されず、関数呼び出しで多くのオーバーヘッドが発生するため、ブーストアレイは本当に遅い可能性があります。しかし、マルチ配列がどのように実装されているのかはわかりませんので、これは完全にオフになる可能性があります:)
保存順序にも多少の違いがあるので、列ごとに画像を保存し、行ごとに書き込むことができます。これにより、キャッシュの動作が低下し、速度が低下する可能性があります。
XループとYループの順序を切り替えて、何かが得られるかどうかを確認してください。 ストレージの注文に関する情報がここにあります: http://www.boost.org/doc/libs /1_37_0/libs/multi_array/doc/user.html
編集: 画像処理に2次元配列を使用しているように見えるので、ブースト画像処理ライブラリ gil 。
オーバーヘッドが少ない配列があり、状況に最適です。
他のヒント
使用しているマシンで
g++ -O3 -march=native -mtune=native --fast-math -DNDEBUG test.cpp -o test && ./test
わかります
[Boost] Elapsed time: 0.020 seconds
[Native]Elapsed time: 0.020 seconds
ただし、const int ITERATIONS
を5000
に変更する
[Boost] Elapsed time: 0.240 seconds
[Native]Elapsed time: 0.180 seconds
次にITERATIONS
を500
に戻しますが、X_SIZE
およびY_SIZE
を400
に設定すると、はるかに大きな違いが得られます
[Boost] Elapsed time: 0.460 seconds
[Native]Elapsed time: 0.070 seconds
最終的に[Boost]
の場合の内部ループを反転し、次のようになります
for (int x = 0; x < X_SIZE; ++x)
{
for (int y = 0; y < Y_SIZE; ++y)
{
および[Native]
、gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
および<=>を<=>、<=>および<=>に保持
[Boost] Elapsed time: 0.060 seconds
[Native]Elapsed time: 0.080 seconds
<=>の場合にも内側のループを反転させると(その場合、それは間違った順序になります)、当然のことながら、
[Boost] Elapsed time: 0.070 seconds
[Native]Elapsed time: 0.450 seconds
Ubuntu 10.10で<=>を使用しています
つまり、結論:
- 適切な最適化を使用すると、boost :: multi_arrayは期待どおりに動作します
- データにアクセスする順序重要
テストに欠陥があります。
- DEBUGビルドでは、boost :: MultiArrayに必要な最適化パスがありません。 (ネイティブ配列よりもはるかに多く)
- RELEASEビルドでは、コンパイラは完全に削除できるコードを探し、ほとんどのコードはそのカテゴリにあります。
おそらく見られるのは、最適化コンパイラが<!> quot; native array <!> quot;の大部分またはすべてを見たことの結果です。ループを削除できます。 boost :: MultiArrayループについても同じことが理論的には当てはまりますが、MultiArrayはおそらくオプティマイザーを無効にするのに十分なほど複雑です。
テストベッドにこの小さな変更を加えると、より実物に近い結果が表示されます。<!> quot; = 2.345
<!> quot; with <!> quot; *= 2.345
<!> quot;最適化して再度コンパイルします。これにより、コンパイラは各テストの外側のループが冗長であることを発見できなくなります。
やったのですが、速度比較は2:1に近づきました。
2つのことを考えています:
1)境界チェック: アプリケーションにmulti_array.hppを含める前に、BOOST_DISABLE_ASSERTSプリプロセッサマクロを定義します。これにより、境界チェックがオフになります。これがNDEBUGのときに無効になっているかどうかはわかりません。
2)ベースインデックス: MultiArrayは、0以外のベースから配列にインデックスを付けることができます。つまり、multi_arrayはベース番号(各次元)を格納し、より複雑な式を使用してメモリ内の正確な位置を取得します。 >
そうでなければ、なぜマルチアレイがCアレイよりも遅いのか理解できません。
代わりに Blitz++ の使用を検討してください。Blitz を試してみましたが、そのパフォーマンスは C スタイルの配列と同等でした。
以下に Blitz を追加したコードを確認してください。
#include <windows.h>
#define _SCL_SECURE_NO_WARNINGS
#define BOOST_DISABLE_ASSERTS
#include <boost/multi_array.hpp>
#include <blitz/array.h>
int main(int argc, char* argv[])
{
const int X_SIZE = 200;
const int Y_SIZE = 200;
const int ITERATIONS = 500;
unsigned int startTime = 0;
unsigned int endTime = 0;
// Create the boost array
typedef boost::multi_array<double, 2> ImageArrayType;
ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]);
//------------------Measure boost----------------------------------------------
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
boostMatrix[x][y] = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Boost] Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
//------------------Measure blitz-----------------------------------------------
blitz::Array<double, 2> blitzArray( X_SIZE, Y_SIZE );
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
blitzArray(x,y) = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Blitz] Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
//------------------Measure native-----------------------------------------------
// Create the native array
double *nativeMatrix = new double [X_SIZE * Y_SIZE];
startTime = ::GetTickCount();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
nativeMatrix[x + (y * X_SIZE)] = 2.345;
}
}
}
endTime = ::GetTickCount();
printf("[Native]Elapsed time: %6.3f seconds\n", (endTime - startTime) / 1000.0);
return 0;
}
デバッグとリリースの結果は次のとおりです。
デバッグ:
Boost 2.093 secs
Blitz 0.375 secs
Native 0.078 secs
リリース:
Boost 0.266 secs
Blitz 0.016 secs
Native 0.015 secs
これには MSVC 2008 SP1 コンパイラを使用しました。
これで C スタイル アレイに別れを告げることができるでしょうか?=p
同じ質問があったので、この質問を見ていました。より厳密なテストを行うためにいくつかの考えがありました。
- rodrigob が指摘したように、ループ順序に欠陥があるため、最初にアタッチしたコードに結果が生じる誤解を招くデータを提供します
- また、定数を使用して設定されているかなり小さなサイズの配列があります。コンパイラーは、実際にはコンパイラーが配列のサイズを知らない場合、ループを最適化できます。配列のサイズと反復回数は、念のためランタイム入力にする必要があります。
Macでは、より意味のある回答を提供するために次のコードが構成されています。ここには4つのテストがあります。
#define BOOST_DISABLE_ASSERTS
#include "boost/multi_array.hpp"
#include <sys/time.h>
#include <stdint.h>
#include<string>
uint64_t GetTimeMs64()
{
struct timeval tv;
gettimeofday( &tv, NULL );
uint64_t ret = tv.tv_usec;
/* Convert from micro seconds (10^-6) to milliseconds (10^-3) */
ret /= 1000;
/* Adds the seconds (10^0) after converting them to milliseconds (10^-3) */
ret += ( tv.tv_sec * 1000 );
return ret;
}
void function1( const int X_SIZE, const int Y_SIZE, const int ITERATIONS )
{
double nativeMatrix1add[X_SIZE*Y_SIZE];
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix1add[y + ( x * Y_SIZE )] = rand();
}
}
// Create the native array
double* __restrict const nativeMatrix1p = new double[X_SIZE * Y_SIZE];
uint64_t startTime = GetTimeMs64();
for( int i = 0 ; i < ITERATIONS ; ++i )
{
for( int xy = 0 ; xy < X_SIZE*Y_SIZE ; ++xy )
{
nativeMatrix1p[xy] += nativeMatrix1add[xy];
}
}
uint64_t endTime = GetTimeMs64();
printf( "[Native Pointer] Elapsed time: %6.3f seconds\n", ( endTime - startTime ) / 1000.0 );
}
void function2( const int X_SIZE, const int Y_SIZE, const int ITERATIONS )
{
double nativeMatrix1add[X_SIZE*Y_SIZE];
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix1add[y + ( x * Y_SIZE )] = rand();
}
}
// Create the native array
double* __restrict const nativeMatrix1 = new double[X_SIZE * Y_SIZE];
uint64_t startTime = GetTimeMs64();
for( int i = 0 ; i < ITERATIONS ; ++i )
{
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix1[y + ( x * Y_SIZE )] += nativeMatrix1add[y + ( x * Y_SIZE )];
}
}
}
uint64_t endTime = GetTimeMs64();
printf( "[Native 1D Array] Elapsed time: %6.3f seconds\n", ( endTime - startTime ) / 1000.0 );
}
void function3( const int X_SIZE, const int Y_SIZE, const int ITERATIONS )
{
double nativeMatrix2add[X_SIZE][Y_SIZE];
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix2add[x][y] = rand();
}
}
// Create the native array
double nativeMatrix2[X_SIZE][Y_SIZE];
uint64_t startTime = GetTimeMs64();
for( int i = 0 ; i < ITERATIONS ; ++i )
{
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
nativeMatrix2[x][y] += nativeMatrix2add[x][y];
}
}
}
uint64_t endTime = GetTimeMs64();
printf( "[Native 2D Array] Elapsed time: %6.3f seconds\n", ( endTime - startTime ) / 1000.0 );
}
void function4( const int X_SIZE, const int Y_SIZE, const int ITERATIONS )
{
boost::multi_array<double, 2> boostMatrix2add( boost::extents[X_SIZE][Y_SIZE] );
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
boostMatrix2add[x][y] = rand();
}
}
// Create the native array
boost::multi_array<double, 2> boostMatrix( boost::extents[X_SIZE][Y_SIZE] );
uint64_t startTime = GetTimeMs64();
for( int i = 0 ; i < ITERATIONS ; ++i )
{
for( int x = 0 ; x < X_SIZE ; ++x )
{
for( int y = 0 ; y < Y_SIZE ; ++y )
{
boostMatrix[x][y] += boostMatrix2add[x][y];
}
}
}
uint64_t endTime = GetTimeMs64();
printf( "[Boost Array] Elapsed time: %6.3f seconds\n", ( endTime - startTime ) / 1000.0 );
}
int main( int argc, char* argv[] )
{
srand( time( NULL ) );
const int X_SIZE = std::stoi( argv[1] );
const int Y_SIZE = std::stoi( argv[2] );
const int ITERATIONS = std::stoi( argv[3] );
function1( X_SIZE, Y_SIZE, ITERATIONS );
function2( X_SIZE, Y_SIZE, ITERATIONS );
function3( X_SIZE, Y_SIZE, ITERATIONS );
function4( X_SIZE, Y_SIZE, ITERATIONS );
return 0;
}
-
整数演算と二重ループを伴う[]を使用して、1次元配列のみを持つもの
-
ポインターのインクリメントを使用した同じ1次元配列を持つもの
-
多次元C配列
-
ブーストmulti_array
コマンドラインから実行、実行
./test_array xsize ysize iterations"
これらのアプローチがどのように機能するかについての良いアイデアを得ることができます。これは、次のコンパイラフラグで得たものです。
g++4.9.2 -O3 -march=native -funroll-loops -mno-avx --fast-math -DNDEBUG -c -std=c++11
./test_array 51200 1 20000
[Native 1-Loop ] Elapsed time: 0.537 seconds
[Native 1D Array] Elapsed time: 2.045 seconds
[Native 2D Array] Elapsed time: 2.749 seconds
[Boost Array] Elapsed time: 1.167 seconds
./test_array 25600 2 20000
[Native 1-Loop ] Elapsed time: 0.531 seconds
[Native 1D Array] Elapsed time: 1.241 seconds
[Native 2D Array] Elapsed time: 1.631 seconds
[Boost Array] Elapsed time: 0.954 seconds
./test_array 12800 4 20000
[Native 1-Loop ] Elapsed time: 0.536 seconds
[Native 1D Array] Elapsed time: 1.214 seconds
[Native 2D Array] Elapsed time: 1.223 seconds
[Boost Array] Elapsed time: 0.798 seconds
./test_array 6400 8 20000
[Native 1-Loop ] Elapsed time: 0.540 seconds
[Native 1D Array] Elapsed time: 0.845 seconds
[Native 2D Array] Elapsed time: 0.878 seconds
[Boost Array] Elapsed time: 0.803 seconds
./test_array 3200 16 20000
[Native 1-Loop ] Elapsed time: 0.537 seconds
[Native 1D Array] Elapsed time: 0.661 seconds
[Native 2D Array] Elapsed time: 0.673 seconds
[Boost Array] Elapsed time: 0.708 seconds
./test_array 1600 32 20000
[Native 1-Loop ] Elapsed time: 0.532 seconds
[Native 1D Array] Elapsed time: 0.592 seconds
[Native 2D Array] Elapsed time: 0.596 seconds
[Boost Array] Elapsed time: 0.764 seconds
./test_array 800 64 20000
[Native 1-Loop ] Elapsed time: 0.546 seconds
[Native 1D Array] Elapsed time: 0.594 seconds
[Native 2D Array] Elapsed time: 0.606 seconds
[Boost Array] Elapsed time: 0.764 seconds
./test_array 400 128 20000
[Native 1-Loop ] Elapsed time: 0.536 seconds
[Native 1D Array] Elapsed time: 0.560 seconds
[Native 2D Array] Elapsed time: 0.564 seconds
[Boost Array] Elapsed time: 0.746 seconds
したがって、boost multi_arrayのパフォーマンスはかなり良いと言っても安全だと思います。シングルループ評価に勝るものはありませんが、配列の次元によっては、boost :: multi_arrayがダブルループで標準c-arrayに勝る場合があります。
別の試みは、ブースト配列にストレートインデックスの代わりにイテレータを使用することです。
マルチアレイも同様に効率的であると期待していました。しかし、gccを使用するPPC Macでも同様の結果が得られます。また、multiarrayrefを試してみたので、両方のバージョンが同じストレージを使用し、違いはありませんでした。私のコードの一部でマルチアレイを使用しているため、これは知っておくと便利です。また、それがハンドコーディングに似ていると仮定しただけです。
問題が何であるかを知っていると思います...たぶん。
ブースト実装の構文がmatrix [x] [y]のようになるため。つまり、matrix [x]は1D配列 column のように機能するオブジェクトへの参照を返す必要があり、その時点でreference [y]が要素を提供します。
ここでの問題は、行メジャーの順序で反復していることです(ネイティブ配列は行メジャーIIRCであるため、c / c ++で一般的です。コンパイラは、マトリックス[x]をこの場合、各y。ブーストマトリックスを使用するときに列の主要な順序で反復した場合、パフォーマンスが向上する可能性があります。
理論だけです。
編集:Linuxシステムで(若干の変更を加えて)理論をテストし、xとyを切り替えることでいくらかのパフォーマンスの改善を示しましたが、ネイティブアレイよりも依然として低速でした。これは、コンパイラーが一時的な参照型を最適化することができないという単純な問題である可能性があります。
リリースモードでビルドし、objdumpを使用して、アセンブリを確認します。それらはまったく異なることをしている可能性があり、コンパイラが使用している最適化を確認できます。
同様の質問がここで尋ねられ、回答されました:
http://www.codeguru.com/forum /archive/index.php/t-300014.html
簡単な答えは、コンパイラが単純な配列を最適化するのが最も簡単であり、Boostバージョンを最適化するのはそれほど簡単ではないということです。したがって、特定のコンパイラーはBoostバージョンにすべて同じ最適化の利点を与えない場合があります。
コンパイラーは、最適化の程度と保守性の度合い(テンプレートコードやその他の複雑な問題など)が異なる場合があります。
gcc 4.2.1
Debug:
[Boost] Elapsed time: 2.268 seconds
[Native]Elapsed time: 0.076 seconds
Release:
[Boost] Elapsed time: 0.065 seconds
[Native]Elapsed time: 0.020 seconds
コードは次のとおりです(Unixでコンパイルできるように変更されています):
#define BOOST_DISABLE_ASSERTS
#include <boost/multi_array.hpp>
#include <ctime>
int main(int argc, char* argv[])
{
const int X_SIZE = 200;
const int Y_SIZE = 200;
const int ITERATIONS = 500;
unsigned int startTime = 0;
unsigned int endTime = 0;
// Create the boost array
typedef boost::multi_array<double, 2> ImageArrayType;
ImageArrayType boostMatrix(boost::extents[X_SIZE][Y_SIZE]);
// Create the native array
double *nativeMatrix = new double [X_SIZE * Y_SIZE];
//------------------Measure boost----------------------------------------------
startTime = clock();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
boostMatrix[x][y] = 2.345;
}
}
}
endTime = clock();
printf("[Boost] Elapsed time: %6.3f seconds\n", (endTime - startTime) / (double)CLOCKS_PER_SEC);
//------------------Measure native-----------------------------------------------
startTime = clock();
for (int i = 0; i < ITERATIONS; ++i)
{
for (int y = 0; y < Y_SIZE; ++y)
{
for (int x = 0; x < X_SIZE; ++x)
{
nativeMatrix[x + (y * X_SIZE)] = 2.345;
}
}
}
endTime = clock();
printf("[Native]Elapsed time: %6.3f seconds\n", (endTime - startTime) / (double)CLOCKS_PER_SEC);
return 0;
}
g ++ 4.8.2で-O3 -DBOOST_DISABLE_ASSERTS
を使用して生成されたアセンブリを見て、operator()
と[][]
の両方の方法で要素にアクセスすると、ネイティブ配列および手動のインデックス計算と比較して、余分な操作はベースの追加。ただし、このコストは測定しませんでした。
Visual Studio 2008 v9.0.21022で上記のコードを変更し、CおよびC ++の数値レシピルーチンからコンテナールーチンを適用しました
http://www.nrbook.com/nr3/ のライセンスルーチンdmatrixおよびそれぞれMatDoub
dmatrixは古い構文malloc演算子を使用するため、推奨されません... MatDoubはNewコマンドを使用します
秒単位の速度はリリースバージョンです:
ブースト:0.437
ネイティブ:0.032
数値レシピC:0.031
数値レシピC ++:0.031
したがって、上記の電撃戦からは最高の無料の代替手段のように見えます。
VC ++ 2010で最適化をオン(<!> quot; Maximize Speed <!> quot;とインライン<!> quot; Any適切な<!> quot;関数を使用してコードをコンパイルしました(わずかな変更を加えました)および<!> quot; Favoring fast code <!> quot;)および0.015 / 0.391の時間を取得しました。アセンブリリストを生成しましたが、私はひどいアセンブリ初心者ですが、ブースト測定ループ内には見た目が良くない行が1つあります:
call ??A?$multi_array_ref@N$01@boost@@QAE?AV?$sub_array@N$00@multi_array@detail@1@H@Z ; boost::multi_array_ref<double,2>::operator[]
[]演算子の1つがインライン化されませんでした!呼び出されたプロシージャは、今度はmulti_array::value_accessor_n<...>::access<...>()
:
call ??$access@V?$sub_array@N$00@multi_array@detail@boost@@PAN@?$value_accessor_n@N$01@multi_array@detail@boost@@IBE?AV?$sub_array@N$00@123@U?$type@V?$sub_array@N$00@multi_array@detail@boost@@@3@HPANPBIPBH3@Z ; boost::detail::multi_array::value_accessor_n<double,2>::access<boost::detail::multi_array::sub_array<double,1>,double *>
全体として、2つのプロシージャは、配列内の1つの要素に単純にアクセスするための非常に多くのコードです。私の一般的な印象は、ライブラリが非常に複雑で高レベルであるため、Visual Studioが望むほど最適化できないことです(gccを使用する投稿者は、より良い結果を得ているようです)。
IMHO、優れたコンパイラーは、2つのプロシージャーをインライン化および最適化する必要があります-どちらも非常に短くて簡単で、ループなどは含まれません。引数と結果を渡すだけで多くの時間が浪費される可能性があります。
rodrigobが答えたように、適切な最適化(GCCのデフォルトは-O0)を有効にすることが、良好なパフォーマンスを得るための鍵です。さらに、 Blaze DynamicMatrix でもテストしました。まったく同じ最適化フラグを使用して、ファクター2のパフォーマンスが向上します。 https://bitbucket.org/account/user/blaze-lib/projects/ブレーズ