Memory required to store 2d array

Question

I've been reading about 2d memory allocation in C at https://www.geeksforgeeks.org/dynamically-allocate-2d-array-c/. In the 4th example they set

len = sizeof(int *) * r + sizeof(int) * c * r;

Intuitively I would have thought that the last term was sufficient as the array has c*r dimensionality. Can anyone explain to me why the first term is necessary?

It is like the 3rd example, but all malloc calls combined to one call `sizeof(int *) * r` + `r` times `sizeof(int) * c` and splitted manually afterwards. The page also does not mention the best method `int (*arr)[c] = malloc( r * sizeof *arr);`. — mch, Apr 20 '21 at 11:19
The code does **not** allocate a 2D array (aka array of array). The code allocates an array with `r` int-pointers and a memory block with `r*c` ints. With proper initialization of the `r` pointers, the allocated memory can be accessed just like a 2D array. But still... it's **not** a 2D array — Support Ukraine, Apr 20 '21 at 11:34
@mch Thank you, that makes sense actually! I cannot upvote you, but this was definitely helpful. The method you suggest looks very sleek and concise, and seems much more intuitive. Again, thank you. — hodjafrapjort, Apr 20 '21 at 11:37
@4386427 This seems beyond the scope of the article I read, but if you have some litterature you can reference me I would very much like to read about it. — hodjafrapjort, Apr 20 '21 at 11:43
@hodjafrapjort This could be helpful: https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays — Support Ukraine, Apr 20 '21 at 11:47

score 0 · Answer 1 · answered Apr 20 '21 at 11:51

len = sizeof(int *) * r + sizeof(int) * c * r;

You need stock all pointers of all rows:

lenRow = sizeof(int *) * r

You need stock all data of the 2d array:

lenArray = sizeof(int) * c * r

Sum of lenRow and lenArray is the total size you need in allocation.

First data in array is reserved to place the pointer

// ptr is now pointing to the first element in of 2D array
ptr = (int *)(arr + r);

// for loop to point rows pointer to appropriate location in 2D array
for(i = 0; i < r; i++)
    arr[i] = (ptr + c * i);

Done

Eric Postpischil · Answer 2 · 2021-04-20T12:25:33.450

The code implements a two-dimensional array as a pointer to pointers to int, so it allocates space both for an array of r pointers to int and for the r•c int objects. (This is generally bad practice as using pointers-to-pointers commonly has bad performance practice. In C implementations that support variable-length arrays, they are generally a better choice. Otherwise, calculating the indices into a one-dimensional array, as with i*c + j to map indices [i][j] to one dimension, is better for performance.)

Thus it needs sizeof (int *) * r bytes for the pointers and sizeof (int) * c * r bytes for the int objects. However, it may also need padding between these to ensure proper alignment for the int objects. In common C implementations, the amount of padding needed is zero, since the alignment of int is commonly less than or equal to that of int *. However, within the requirements of the C standard, it can be non-zero. So a proper amount of memory to allocate is:

sizeof (int *) * r + _Alignof (int) - 1 - (sizeof (int *) * r - 1) % _Alignof (int) + sizeof (int) * c * r

In this, _Alignof (int) - 1 is the maximum number of bytes we might need to pad (if we end just one byte after the designed multiple, we need to add _Alignof (int) - 1 to get to the next multiple), and (sizeof (int *) * r - 1) % _Alignof (int) is how many bytes beyond one byte the space for the int * goes, modulo _Alignof (int), so subtracting that from the maximum gives the number of bytes we need to get to the next multiple.

Memory required to store 2d array

2 Answers2