Multiplying large matrices is much slower with contiguous memory allocation

Question

While implementing a neural network, I noticed that if I allocate memory as a single contiguous block for the data set arrays, execution time increases several times.

Compare these two methods of memory allocation:

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

Here are the results when compiling with -march=native -Ofast (tried gcc and 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

Here's the code: https://github.com/michaelklachko/NN/blob/master/test.c

Note that both initializing and dot product are much slower for contiguous memory.

I expected the opposite - a contiguous block of memory should be more cache friendly than a large number of separate small blocks. Or at least they should be similar in performance (this machine has 64GB of RAM, and 90% of it is unused).

EDIT: Here's the compressed self-contained code (I still recommend using the github version instead, which has measuring and formatting statements):

#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

Looks like you've run into ability or disability of your compiler to run some vectorisation of your code. I've tried to repeat your experiment with no succeed -

mick@mick-laptop:~/Загрузки$ ./a.out 100 1 0

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

Initializing arrays...

Multiplying arrays...

Execution Time: Allocating memory: 0.1 seconds Initializing arrays: 0.9 seconds Dot product: 44.8 seconds

mick@mick-laptop:~/Загрузки$ ./a.out 100 1 1

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

Initializing arrays...

Multiplying arrays...

Execution Time: Allocating memory: 0.0 seconds Initializing arrays: 1.0 seconds Dot product: 46.3 seconds