How to ensure a 2D array is allocated contigously in memory

Question

I am sending a 2D array over MPI and for this to work correctly the array needs to be contiguously allocated in memory.

I am allocating it as follows:

int **array;
array = malloc(size1 * sizeof( *(array) );
for (int k = 0; k < size1; k++)
    array[k] = malloc(size2 * sizeof(**(array));

Then I would like to use:

MPI_Send(array, size1*size2, MPI_INT, target_pe, tag, MPI_COMM_WORLD);

How can I ensure the array is allocated contiguously?

Currently I am trying this:

for (int k = 0; k < size1; k++)
    MPI_Send(array[k], size2, MPI_INT, target_pe, tag, MPI_COMM_WORLD);

which leads to a seg fault later in an unrelated part of the program. However if I send the elements 1 by 1 it works.

You can't do that. BTW this is not a 2D array but an array of pointers — Jabberwocky, Sep 17 '19 at 13:29
With `*(int)` do you really mean `*array`? Otherwise it doesn't make much sense. — Some programmer dude, Sep 17 '19 at 13:30
Also, what you're attempting to create is a [*jagged array*](https://en.wikipedia.org/wiki/Jagged_array). You could allocate a single array of `size1 * size2` elements and use simple arithmetic to access the elements. — Some programmer dude, Sep 17 '19 at 13:32
Possible duplicate of [Correctly allocating multi-dimensional arrays](https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays). — Lundin, Sep 17 '19 at 13:45
Indeed it should have been `*(array)`, I fixed that. So if I `malloc (size*size2 * sizeof int)` that would be a 1D array and behave as expected with MPI, but my program accesses array[i][j] all throughout so it would require major refactoring. I added some additional issues with my current approach. — jsb, Sep 17 '19 at 13:47
[Question 6.16](http://c-faq.com/aryptr/dynmuldimary.html) in the [C FAQ list](http://c-faq.com) is all about this. — Steve Summit, Sep 17 '19 at 14:45
@jsb *but my program accesses array[i][j] all throughout so it would require major refactoring* If you set things up right you can have your cake and eat it too: a contiguous array but with no refactoring. Study the answers here carefully. — Steve Summit, Sep 17 '19 at 14:47

score 1 · Answer 1 · answered Sep 17 '19 at 15:22

How to ensure a 2D array is allocated contiguously in memory

Allocate in one step.

Example uses C99 code which supports variable length arrays. Here a pointer to a VLA is used.

// ptr is a pointer to a 2D array
int (*ptr)[size1][size2] = malloc(sizeof *ptr); 
(*ptr)[0][0] = 1;            // One corner of the 2D array
(*ptr)[size-1][size-1] = 2;  // Opposite corner of the 2D array

I'll look into sample MPI() code later.

score 0 · Accepted Answer · answered Sep 17 '19 at 13:43

0

Use:

int (*array)[size2] = malloc(size1 * sizeof *array);
if (!array) Handle error…

If size2 is not a constant and your C implementation does not support variable length arrays, then use:

int *array = malloc(size1 * size2 * sizeof *array);
if (!array) Handle error…

In this case, you will have to use manual address arithmetic to access array elements. Instead of array[i][j], use array[i*size2 + j].

answered Sep 17 '19 at 13:43

Eric Postpischil

195,579
13
168
312

I think I might end up refactoring the code to implement it as a 1D array and index it with the proper arithmetic. Since it is likely the "safest" way to send it through MPI – jsb Sep 17 '19 at 16:12

score 0 · Answer 3 · answered Sep 17 '19 at 13:43

You can not ensure that by using sequential calls to malloc(). What you can do instead, you can allocate from the beginning malloc(size1 * size2) space in the memory, then you can split your allocated buffer how you desire. You can now say that array[i] is in fact array[i * size2] in the memory.

Serge Ballesta · Answer 4 · 2019-09-17T21:55:51.960

0

The correct way is to allocate the memory for the 2D array in on single operation. Then as arrays are not really first class citizens in C, not speaking of multi-dimensional arrays, you will have to allocate memory for an array of pointers and make its elements points to the beginning of each row:

int *mem = malloc(sizeof(*mem) * size1 * size2);
int **array = malloc(size1 * sizeof(*array));
for (int k = 0; k < size1; k++) {
    array[k] = mem + k * size2 * sizeof(*mem);
}

This will ensure contiguous allocation when it matters for passing the array to routine expecting that, and still allow to access the elements as array[i][j];

edited Sep 17 '19 at 21:55

answered Sep 17 '19 at 13:46

Serge Ballesta

143,923
11
122
252

I'm having issues freeing memory after this. free(array[k]) within a loop leads to errors, and I do not have access to int *mem in the freeing routine. – jsb Sep 17 '19 at 14:03
@jsb: Just use `free(array [0]);`. By construction, `array[0]` **is** `mem`. – Serge Ballesta Sep 17 '19 at 14:42
`sizeof(*mem) * size1 * size2` have advantages over `size1 * size2 * sizeof(*mem)`. Should `size1,size2` be `int`, `size1 * size2` may overflow the 2nd and may not the first as the first uses at least `size_t` math. – chux - Reinstate Monica Sep 17 '19 at 15:15
In general, It's not a good idea to make a pointer array. While this allows to write `array[col][row]`, it can have decremental performance and the fact that memory is contiguous is not implicitly guaranteed. Instead, you should just use `mem[col * size2 + row]`. – Zulan Sep 17 '19 at 15:34
it should be `array[k] = mem + k * size2;` (long story short, pointer arithmetic). – Gilles Gouaillardet Sep 18 '19 at 00:03

How to ensure a 2D array is allocated contigously in memory

4 Answers4