difference b/w allocating memory to 2D array in 1 go or row by row

Question

what would be the impact in accessing of array or in memory allocation for these two cases:

1.

    int **arr;
    arr = malloc( sizeof(int) * row * column );

2.

    int **arr;
    arr = malloc( sizeof(*arr) * row);
    for(i=0; i<row; i++)
        arr[i] = malloc( sizeof( **arr) * column));

Answer 1

• Firstly, the "impact" is that your first method is broken. It will not work through an int ** pointer.

  In order to allocate a 2D array in one shot as you are trying to do it in your first method, you actually have to allocate a 1D array of sufficient size

  int *arr = malloc( row * column * sizeof *arr );
  // Note: `int *`, not `int **`
  

  and perform access by manual index re-calculation, e.g. instead of doing arr[i][j] you have to do arr[i * column + j].

  Trying to store the allocated pointer in int **arr and then access your array as arr[i][j] will simply lead to crashes.

• Secondly, your second method is OK. It is just that in the second method your are not really required to allocate the second-level memory by multiple independent malloc calls. You can allocate the whole second-level memory in one shot

  int **arr = malloc( row  * sizeof *arr );
  int *arr_data = malloc( row * column * sizeof *arr_data );
  

  and then just distribute that pre-allocated second-level memory between the rows

  for (i = 0; i < row; i++)
    arr[i] = arr_data + i * column;
  

  (Of course, you can allocate the rows independently, if you wish so. It will also work. The reason I wanted to allocate them in one shot is to better illustrate the similarity between the first and the second approach, as commented below.)

Now, by looking at these two methods you can easily see that both of them essentially do the same thing. The only difference is that in the first method you find the beginning of the row on-the-fly by calculating arr + i * column every time (note that arr[i * column + j] is equivalent to (arr + i * column)[j]). In the second method you pre-calculate all row beginnings in advance by using the same arr_data + i * column formula, and store them for further usage in a separate "row index" array arr.

So, it basically boils down to trade-off between memory usage (first method requires less memory) and speed (the second method is potentially, but not necessarily, faster). At the same time the second method supports the "natural" syntax for 2D array access - arr[i][j], while in the first method you have to use more convoluted 1D access syntax with index recalculation.