Умножение больших матриц происходит гораздо медленнее с непрерывным распределением памяти

Question

При внедрении нейронной сети я заметил, что если я выделяю память как единый непрерывный блок для массивов данных, время выполнения увеличивается несколько раз.

Сравните эти два метода распределения памяти:

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; 
} 

Ниже приведены результаты при компиляции с -march=native -Ofast (попытался НКУ и лязгом):

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

Обратите внимание, что как для инициализации, так и для точечного продукта гораздо медленнее для непрерывной памяти.

Я ожидал обратного - непрерывный блок памяти должен быть более дружественным к кэшу, чем большое количество отдельных маленьких блоков. Или, по крайней мере, они должны быть одинаковыми по производительности (у этого аппарата 64 ГБ ОЗУ, а 90% его не используется).

EDIT: Вот сжатый самодостаточным код (я все еще рекомендую использовать версию 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 секунды Dot продукта: 44.8 секунд

Mick @ Мик -Ноутбуки: ~/Загрузки $ ./a.out 100 1 1

Многоразовые (100000, 1000) и (100, 1000) массивы 1 раз, смежные распределение памяти.

Инициализация массивов ...

Умножение массивы ...

Время выполнения: Выделение памяти: 0.0 секунд Инициализация массивов: 1.0 секунды Dot продукта: 46.3 секунд