Why is memory size doubled when allocating a large number of char*?

Question

I allocate a 2D array of char * and every string length is 12.
50 rows and 2000000 columns.

Lets calculate it: 50*2000000 * (12(length)+8(for pointer)). I use 64 bit.

50*2000000 * 20 =2000000000 bits .. -> 2 GB.

When I check the memory monitor it shows that the process takes 4 GB.
(All that happened after allocation)

This is the code:

int col=2000000,row=50,i=0,j=0;
char *** arr;
arr=(char***)malloc(sizeof(char**)*row);
for(i=0;i<row;i++)
{
arr[i]=(char ** )malloc(sizeof(char*)*col);
    for(j=0;j<col;j++)
     {
         arr[i][j]=(char*)malloc(12);
         strcpy(arr[i][j],"12345678901");
         arr[i][j][11]='\0';
     }
}

May that be from the paging in Linux?

Answer 1

Each call of malloc is taking more memory than you ask. Malloc needs to store somewhere its internal info about allocated place, like size of allocated space, some info about neighbors chunks, etc. Also (very probably) each returned pointer is aligned to 16 bytes. In my estimation each allocation of 12 bytes takes 32 bytes of memory. If you want to save memory allocate all strings in one malloc and split them into sizes per 12 at your own. Try the following:

int col=2000000,row=50,i=0,j=0;
char *** arr;
arr= malloc(sizeof(*arr)*row);
for(i=0;i<row;i++)
{ 
  arr[i]= malloc(sizeof(*arr[i])*col);
  char *colmem = malloc(12 * col);
  for(j=0;j<col;j++)
  {
     arr[i][j] = colmem + j*12;
     strcpy(arr[i][j],"12345678901");
  }
}

Answer 2

I would re-write the code from scratch. For some reason, around 99% of all C programmers don't know how to correctly allocate true 2D arrays dynamically. I'm not even sure I'm one of the 1% who do, but lets give it a shot:

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

int main()
{
  const int COL_N = 2000000;
  const int ROW_N = 50;

  char (*arr)[ROW_N] = malloc( sizeof(char[COL_N][ROW_N]) );

  if(arr == NULL)
  {
    printf("Out of memory");
    return 0;
  }

  for(int row=0; row<ROW_N; row++)
  {
    strcpy(arr[row], "12345678901");
    puts(arr[row]);
  }

  free(arr);

  return 0;
}

The important parts here are:

• You should always allocate multi-dimensional arrays in adjacent memory cells or they are not arrays, but rather pointer-based lookup tables. Thus you only need one single malloc call.
• This should save a bit of memory since you only need one pointer and it is allocated on the stack. No pointers are allocated on the heap.
• Casting the return value of malloc is pointless (but not dangerous on modern compilers).
• Ensure that malloc actually worked, particularly when allocating ridiculous amounts of memory.
• strcpy copies the null termination, you don't need to do it manually.
• There is no need for nested loops. You want to allocate a 2D array, not a 3D one.
• Always clean up your own mess with free(), even though the OS might do it for you.