0

I am currently implementing an N x 2 matrix of floats on the heap as follows:

float **matrix = malloc(sizeof(float*) * n_cols);

for (int i = 0; i < n_cols; ++i) {
    matrix[i] = malloc(sizeof(float) * 2);
}

The elements of matrix are not contiguous in memory, making this data structure cache unfriendly (as I understand it). I am trying to re-write the above to create a genuine 2D array on the heap. Based on some previous SO posts, I tried the following:

float (*matrix)[2] = malloc(sizeof(float) * n_cols * 2);

However, this lead to a segmentation fault when I ran my code.

Alessandro Power
  • 2,395
  • 2
  • 19
  • 39
  • What do u mean by contiguous? You can allocate it in one chuck but how you access it will determine the cache friendliness. – Pemdas Apr 09 '16 at 00:26
  • @Pemdas By contiguous I mean similar to how a 2D array is stored on the stack ie all elements are connected to one another, so that going from the end of one row to the beginning of another does not require a jump in memory. – Alessandro Power Apr 09 '16 at 00:29
  • 2
    See this post.. http://stackoverflow.com/questions/17584215/how-does-c-allocate-space-for-a-2d-3d-array-when-using-malloc – Harry Apr 09 '16 at 00:30
  • Your example is correct, you haven't shown the code that reproduces the problem. – 2501 Apr 09 '16 at 08:14

2 Answers2

2

If you want the whole array to be contiguous then you need to declare it as follows.

  float *matrix = malloc(n1 * n2 * sizeof(float));

Does this help. Note the second way the matrix has been allocated. 

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
  size_t r = 0;
  size_t c = 0;
  int rows    = 82;
  int columns = 30;
  float *matrix = malloc(rows * columns * sizeof(float));
  for(r = 0; r < rows; r++) {
    printf("%zu - ", r); 
    for(c = 0; c < columns; c++) {
      printf("%zu|", c); 
      matrix[r + r*c] = 1.0;
    }   
    printf("\n"); 
  }

  float **matrix2 = malloc(rows * sizeof(float*));

  for(r = 0; r < rows; r++) {
    matrix2[r]    = malloc(columns * sizeof(float));
  }
  for(r = 0; r < rows; r++) {
    printf("%zu - ", r); 
    for(c = 0; c < columns; c++) {
      printf("%zu|", c); 
      matrix2[r][c] = 1.0;
    }   
    printf("\n"); 
  }
  free(matrix);
  for(r = 0; r < rows; r++) {
    free(matrix2[r]);    
  }
  free(matrix2);
  return 0;
}

You can find a benchmark with the code here...

https://github.com/harryjackson/doc/blob/master/c/cache_locality_2d_array_test.c

Harry
  • 11,298
  • 1
  • 29
  • 43
0

I think you want something like this. 

float ** matrix = malloc(sizeof(float) * ((n_col * 2) + (n_col * sizeof(float*));

for(i = 0; i < n_col; i++)
{
    matrix[i] = matrix + (n_col *sizeof(float*)) + ((i * 2) *sizeof(float)); 
}

The size of your matrix is 2* n_col, however the first index into your matrix is going to be a pointer to a column. You have to allocate additional space for these pointers. This is where the (n_col * sizeof(float *)) comes into play. Each row is of size (2 * sizeof(float)), so each of the first indexed in the matrix need to point to an array of memory (2 * sizeof(float)) bytes away from the last one.

It looks something like this.

m[0] m[1] m[2] matrix matrix + 1 * (2 * sizeof(float)) matrix + 2 * (2 * sizeof(float))

The second index deference a location into the memory pointed to by m[x].

Pemdas
  • 543
  • 2
  • 9