0

ベクトルアクセスがマトリックスアクセスよりも速いかどうかを知るために、非常に単純なコードを作成しました。

私は3つのことを試しました：

1：intの100.000.000要素でベクトルを作成します。

int *matrix=(int*)malloc(sizeof(int)*100000*1000)
for(long int=x;x<100000*1000;x++)matrix[x]=1;

2：同じサイズのマトリックスを作成します。

int ** matrix=(int**)malloc(sizeof(int*)*100000);
for(long int=0; x<100000;x++){
   matrix[x]=(int*)malloc(sizeof(int*)*1000);
}
for(int x=0; x<100000;x++){
   for(int y=0;y<1000;y++){
     matrix[x][y]=1;
   }
}

3：同じベクトルを作成しますが、その中に行列として書き込みます

for(int x=0; x<100000;x++){
   for(int y=0;y<1000;y++){
     matrix[(x*1000)+y]=1;
   }
}

常にマトリックスアクセス（CASE 2）はケース1と3の2倍かかります。ケース3はケース1よりも少し高速です。C++コンパイラ（g ++）で-O2パラメータを使用しています。

ベクトルが行列よりも速い理由は理解できます:(しかし、説明が好きです）。しかし、なぜケース3がケース1よりも速いのか理解できません。乗算プロセスによって処理が大幅に遅くなり、速くならないことを想像しました。差が0.002であっても、理由がわかりません（時間とその時間のプロセッサ使用量である可能性があります（私は想像します））

最適化せずに3つのケースすべてをコンパイルすると、ケース2の方が遅くなります。ケース3はケース1よりも遅くなります。したがって、最適化プロセスがないと、ケース1の方が速くなります。

ベクトルは、通常、より高速ですか？

ありがとう

4

1 に答える 1

1

ケース2が最も遅い理由は、間接レベルがもう1つあるためです。

ケース1と3の場合、メモリから目的の要素をフェッチします。ケース2の場合、最初に行/列配列のアドレスをメモリからフェッチする必要がありますが、後で目的の要素からフェッチする必要があります。最近のコンピュータでは、メモリアクセスが（実行の観点から）はるかにコストのかかる操作であるため、それがはるかに遅いのも不思議ではありません。

1と3の違いは、予想どおりごくわずかです。最適化オプションをいじることはすでに違いを生むので、ここでは誰もあなたが使用している正確なマシンを知っていることであなたに明確な答えを与えることはできません。ここでの最良の（そして唯一の合理的な）アプローチは、生成されたアセンブラーコードを調べることです。1つの理由は、1つのバージョンではループ変数が長く、他のバージョンではそうではないことです（したがって、要素アドレスの計算を行います）。CPUによっては、これによって違いが生じる可能性があります。

編集：マトリックスメモリへのアクセスがないため、あなたの言い回しは非常に悪い選択になっています。メモリは常にフラットです。マトリックスアドレッシングは、（たとえば3で行ったように直接）または間接的に（たとえば、Fortranのように、それを行う別の言語を使用して）上に置く「仮想」アドレッシングです。したがって、行列のさまざまなメモリレイアウトを多かれ少なかれ区別する必要があります。3では、マトリックスはマトリックス内の1つの大きなチャンクとして存在しますが、2では、メモリ内に行ごと/列ごとにあります。これには、もう1レベルの間接参照があるという欠点があります（ただし、行へのスワップなどの特定の操作をより高速に実行できること、およびガベージコレクターに適していることの利点）。行列をメモリに格納する方法は他にもたくさんあります（特に、スパース行列を処理する必要がある場合）。

于 2012-07-30T15:33:11.153 に答える