How much memory does this program allocate?

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

int main(int ac, char *av[])
  int i;
  int *p[1<<20];
  for(i=0; i<(1<<20); i++)
    p[i] = malloc(sizeof(int));

  system("top -n");
Well, let's estimate. I'm running on a box with 4-byte ints, so I'm allocating 4MB for the ints. I'm also allocating pointers of the same size for all of these, so I total another 4MB. The program "should" use 8MB.

On my computer, it uses 21MB. What's going on?

Remember malloc? Most C run time libraries put a small header block before each bit of allocated memory, so they know how to free it (things like "buddy system" allocators do without this extra block, though). We're allocating over a million bits of memory, and each gets its small header. A million small headers end up as quite a lot, in this instance.

While malloc is a good allocator for general-purpose codes, you can often do better, and sometimes you have to. When you have on the order of 106 small blocks of memory, your implementation is likely to give poor results (we saw here an overhead of over 100%). Instead of allocating each block separately, consider allocating one large block and splitting it yourself. A call of

int *q;
q = malloc((1<<20)*sizeof(int);
uses just one header for all the blocks. Of course, now your program may have to keep better track of allocated memory; consider writing additional "slab allocators" for small fixed-size blocks.