Heap memory allocation

The bitmap

We can split memory into 'allocation units', and store an array with one bit for  every allocation unit, to determine whether or not it is free:

Say that we use 0 to indicate free memory, and 1 for allocated units. To allocate a block of memory, we must search for a run of n 0's, then when we have found them, set them to 1 to indicate that they have been allocated.

To deallocate a block of memory, we must set all the bits corresponding to its allocation units to 0.

This system is quite efficient in memory terms. Even if the allocation unit is as small as 8 bytes, the overhead for the bitmap is only 1.6% (smaller allocation units mean more overhead, larger units less overhead but more internal fragmentation).

Trouble is that searching the bitmap for a run of 0's is very slow, so in practice it is not a common technique.


last updated 18 March 1998