How much memory does this program allocate?
int main(int ac, char *av)
for(i=0; i<(1<<20); i++)
p[i] = malloc(sizeof(int));
Well, let's estimate. I'm running on a box
ints, so I'm allocating 4MB
for the ints. I'm also allocating pointer
s 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?
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.
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
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 allocator
s" for small fixed-size blocks.