4.2 The Workings of a Memory Allocator

Studying memory usage trends of programs is a very interesting activity, as proven by Knuth's seminal work (Knuth 1998). Knuth established many fundamental memory allocation strategies, and even more were invented later.

How does a memory allocator work? A memory allocator manages a pool of raw bytes and is able to allocate chunks of arbitrary size from that pool. The bookkeeping structure can be a simple control block having a structure like the following:

struct MemControlBlock


{


   std::size_t size_;


   bool available_;


};

The memory managed by a MemControlBlock object lies right after it and has size_ bytes. After the chunk of memory, there is another MemControlBlock, and so on.

When the program starts, there is only one MemControlBlock at the beginning of the pool, managing the entire memory as a big chunk. This is the root control block, which will never move from its original location. Figure 4.1 shows the memory layout for a 1MB memory pool at startup.

For each allocation request, a linear search of memory blocks finds a suitable block for the requested size. Its size must be equal to or larger than the size requested. It is amazing just how many strategies for fitting requests with available blocks exist, and how oddly they perform. You can go for first fit, best fit, worst fit, or even a random fit. Interestingly, worst fit is better than best fit—how's that for an oxymoron?

Each deallocation incurs, again, a linear search for figuring out the memory block that precedes the block being deallocated, and an adjustment of its size.

As you can see, this strategy is not terribly time efficient. However, the overhead in size is quite small—only one size_t plus a bool per memory block. In most concrete cases, you can even give up a bit in size_ and store available_ there, thus squeezing MemControl Block to the ultimate:

// Platform- and compiler-dependent code


struct MemControlBlock


{


   std::size_t size_ : 31;


   bool available_ : 1;


};

If you store pointers to the previous and next MemControlBlock in each MemControlBlock, you can achieve constant-time deallocation. This is because a block that's freed can access the adjacent blocks directly and adjust them accordingly. The necessary memory control block structure is

struct MemControlBlock


{


   bool available_ ;


   MemControlBlock* prev_;


   MemControlBlock* next_;


};

Figure 4.2 shows the layout of a memory pool fostering such a doubly linked list of blocks. As you can see, the size_ member variable is not needed anymore because you can compute the size as this->next_ - this. Still, you have the overhead of two pointers and a bool for each allocated memory block. (Again, you can do some system-dependent tricks to pack that bool together with one of the pointers.)

Still, allocations take linear time. There are many neat techniques for mitigating that, each fostering a different set of trade-offs. Interestingly, there's no perfect memory allocation strategy; each of them has a memory use trend that makes it perform worse than others.

We don't need to optimize general allocators. Let's focus on specialized allocators—allocators that deal best with small objects.