Memphisd Memphisd - 4 months ago 13
C Question

Multidimensional Arrrays Memory Usage in C (Heap)

I have a problem to understand the memory usage of the following Code:

typedef struct list{
uint64_t*** entrys;
int dimension;
uint64_t len;
} list;

void init_list(list * t, uint64_t dim, uint64_t length, int amount_reg)
{
t->dimension = dim;
t->len=length;
t->entrys = (uint64_t ***) malloc(sizeof(uint64_t**)*length);
uint64_t i;
for(i=0;i<length;i++)
{
t->entrys[i] = (uint64_t **) malloc(sizeof(uint64_t *)*dim);
int j;
for(j=0;j<dim;j++)
{
t->entrys[i][j]=(uint64_t *) malloc(sizeof(uint64_t)*amount_reg);
}
}
}

int main()
{
list * table = (list *) malloc(sizeof(list));
init_list(table,3,2048*2048,2);
_getch();
}


What i want to do is allocating a 3d-Array of uint64_t elements like table[4194304][3][2].

The taskmanager shows a memory usage of 560MB. cO

If i try to calculate the memory usage on my own i can't comprehend that value.


Here is my calculation (for a x64 System):



2^20 * 8 Byte (first dimension pointers)
+ 2^20 * 3 * 8 Byte (second dimension pointers)
+ 2^20 * 3 * 2 * 8 Byte (for the values itsself)

= 2^20 * 8 Byte * 10 = 80MB


Maybe I'm totaly wrong with that calculation or my code generates a huge amount of overhead?!

If so, is there a way, to make this program more memory efficent?
I can't imagine that for something like
~2^23 uint64_t
values so much memory is needed (cause
2^23*8Byte
are just
64MB
)

Answer

Your code does 2²² · 4 + 1 = 16777217 calls to malloc(). For each allocated memory region, malloc() does a little bookkeeping. This adds up when you do that many calls to malloc(). You can reduce the overhead by calling malloc() fewer times like this:

void init_list(list * t, int dim, uint64_t length, int amount_reg)
{
    uint64_t ***entries = malloc(sizeof *entries * length);
    uint64_t **seconds = malloc(sizeof *seconds * length * dim);
    uint64_t *thirds = malloc(sizeof *thirds * length * dim * amount_reg);

    uint64_t i, j;

    t->entrys = entries;

    for (i = 0; i < length; i++) {
        t->entrys[i] = seconds + dim * i;
        for (j = 0; j < dim; j++)
            t->entrys[i][j] = thirds + amount_reg * j + amount_reg * dim * i;
    }
}

Here we call malloc() only three times, and memory usage goes down from 561272 KiB to 332020 KiB. Why is the memory usage still so high? Because you made a mistake in your computations. The allocations allocate this much memory:

  • entries: sizeof(uint64_t**) * length = 8 · 2²²
  • seconds: sizeof(uint64_t*) * length * dim = 8 · 2²² · 3
  • thirds: sizeof(uint64_t) * length * dim * amount_reg = 8 · 2²² · 3 · 2

All together we have (1 + 3 + 6) · 8 · 2²² = 335544320 bytes (327680 KiB or 320 MiB) of RAM which closely matches the amount of memory observed.

How can you reduce this amount further? Consider transposing your array so the axes are sorted in ascending order of size. This way you waste much less memory in pointers. You could also consider allocating space for the values only and doing index computations manually. This can speed up the code a lot (less memory accesses) and saves memory but is tedious to program.