malloc abuse (idea)

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 10⁶ 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.