malloc abuse

"hi... i'm tftv256, and i have a problem. i'm a malloc abuser."

"all my strings are fixed-length but they're all dynamically allocated. the thought of declaring a char array boggles my mind. arrays? what are those? i even find myself doing malloc(1)'s twice a day. i look at myself in the mirror and i dont like what i see. so i do some more mallocs to escape reality. ENOMEM, ENOMEM, ENOMEM, damnit don't do this to me now. just one more hit. just one more hit, man!"

"'oh, sure', you could be thinking, 'that's not me. i only malloc a string here and there.' that was me too. but sooner or later character pointers weren't good enough. they say the char * is the gateway cast. damn straight; sooner or later i found myself casting mallocs to structs and pointers to pointers, and then so far as to pointers to struct pointer pointers. they asked me why i was doing all this; i told them all them asterisks look pretty. that's not cool. i passed out, almost dumped core, man. they sent me to rehab and now i'm here. it'll happen to you too..."

** fades to black **

This message from Partnership for a Malloc-Free America

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.