C-通过连续的内存分配，大型矩阵的乘积要慢得多

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（尝试的GCC和Clang）编译时的结果：

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

请注意，初始化和点产品对于连续内存都要慢得多。

我期望的是相反的 - 连续的内存块应该比大量的单独的小块更友好。或者至少它们的性能应该相似（该机器具有64GB的RAM，其中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

看起来您遇到了编译器的能力或残疾，可以运行代码的某些矢量化。我试图重复您的实验，没有成功 -

mick@mick-laptop：〜/з/згзз$ $ ./a.out 100 1 0

乘以（100000，1000）和（100，1000）阵列1次，不连续 内存分配。

初始化数组...

乘以数组...

执行时间： 分配内存：0.1秒 初始化阵列：0.9秒 点产品：44.8秒

mick@mick-wastop：〜/з/згзз$ $ ./a.out 100 1 1

乘法（100000，1000）和（100，1000）阵列1次，连续 内存分配。

初始化数组...

乘以数组...

执行时间： 分配内存：0.0秒 初始化数组：1.0秒 点产品：46.3秒