大きな行列を掛け合わせることは連続したメモリ割り当てでははるかに遅い

Question

ニューラルネットワークを実装している間、データセット配列に対して1つの連続したブロックとしてメモリを割り当てると、実行時間が数倍に増加することに気付きました。

メモリ割り当てのこれら2つの方法を比較：-march=native -Ofast（試みGCCと打ち鳴らす）でコンパイルするときにここ

float** alloc_2d_float(int rows, int cols, int contiguous) 
{ 
    int i; 
    float** array = malloc(rows * sizeof(float*)); 

    if(contiguous) 
    { 
     float* data = malloc(rows*cols*sizeof(float)); 
     assert(data && "Can't allocate contiguous memory"); 

     for(i=0; i<rows; i++) 
      array[i] = &(data[cols * i]); 
    } 
    else 
     for(i=0; i<rows; i++) 
     { 
      array[i] = malloc(cols * sizeof(float)); 
      assert(array[i] && "Can't allocate memory"); 
     } 

    return array; 
} 

結果である：

michael@Pascal:~/NN$ time ./test 300 1 0 

Multiplying (100000, 1000) and (300, 1000) arrays 1 times, noncontiguous memory allocation. 

Allocating memory: 0.2 seconds 
Initializing arrays: 0.8 seconds 
Dot product:   3.3 seconds 

real 0m4.296s 
user 0m4.108s 
sys  0m0.188s 

michael@Pascal:~/NN$ time ./test 300 1 1 

Multiplying (100000, 1000) and (300, 1000) arrays 1 times, contiguous memory allocation. 

Allocating memory: 0.0 seconds 
Initializing arrays: 40.3 seconds 
Dot product:   13.5 seconds  

real 0m53.817s 
user 0m4.204s 
sys  0m49.664s 

ここでは、コードは次のとおり https://github.com/michaelklachko/NN/blob/master/test.c

初期化とドット積の両方が連続したメモリの方がはるかに遅いことに注意してください。

私はその反対のことを期待しました。連続したメモリブロックは、多数の別々の小さなブロックよりキャッシュフレンドリでなければなりません。または、少なくともパフォーマンスは似ているはずです（このマシンのRAMは64GBで、その90％は使用されていません）。

編集：ここでは圧縮された自己完結型のコードは（私はまだ文を測定し、書式設定有し、代わりにgithubのバージョンを使用することをお勧めします）です：あなたはあなたの能力や障害に遭遇しているよう

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

float** alloc_2d_float(int rows, int cols, int contiguous){ 
    int i; 
    float** array = malloc(rows * sizeof(float*)); 
    if(contiguous){ 
     float* data = malloc(rows*cols*sizeof(float)); 
     for(i=0; i<rows; i++) 
      array[i] = &(data[cols * i]); 
    } 
    else 
    for(i=0; i<rows; i++) 
     array[i] = malloc(cols * sizeof(float)); 
    return array; 
} 

void initialize(float** array, int dim1, int dim2){ 
    srand(time(NULL)); 
    int i, j; 
    for(i=0; i<dim1; i++) 
     for(j=0; j<dim2; j++) 
      array[i][j] = rand()/RAND_MAX; 
} 

int main(){ 
    int i,j,k, dim1=100000, dim2=1000, dim3=300; 
    int contiguous=0; 
    float temp; 

    float** array1 = alloc_2d_float(dim1, dim2, contiguous); 
    float** array2 = alloc_2d_float(dim3, dim2, contiguous); 
    float** result = alloc_2d_float(dim1, dim3, contiguous); 

    initialize(array1, dim1, dim2); 
    initialize(array2, dim3, dim2); 

    for(i=0; i<dim1; i++) 
     for(k=0; k<dim3; k++){ 
      temp = 0; 
      for(j=0; j<dim2; j++) 
       temp += array1[i][j] * array2[k][j]; 
      result[i][k] = temp; 
    } 
} 

Answer 1

が見えますコンパイラはあなたのコードのベクトル化を実行します。 〜/Загрузки$ ./a.out 100 1 0

乗算（100000、1000）および（100、1000年：

ミック@のミック・ラップトップ - ノー成功すると、あなたの実験を繰り返すように試みた ）配列1回、非連続 メモリ割り当て。

配列を初期化しています...

配列を掛ける...

実行時間： 割り当てメモリ：0.1秒 初期化配列：0.9秒 ドット積：44.8秒

ミックする@ミック-laptop：〜/Загрузки$ ./a.out 100 1 1

（100000,1000）および（100,1000）の配列を1倍に連続して掛ける メモリ割り当て。配列の初期化

...

配列を掛ける...

実行時間： は、メモリの割り当て：配列の初期化0.0秒 ：1.0秒 ドット積：46.3秒