4.6 The SmallObjAllocator Class

The third layer in our allocator architecture consists of SmallObjAllocator, a class capable of allocating objects of any size. SmallObjAllocator does so by aggregating several FixedAllocator objects. When SmallObjAllocator receives an allocation request, it either forwards it to the best matching FixedAllocator object or passes it to the default ::operator new.

The following is a synopsis of SmallObjAllocator. Explanations follow the code.

class SmallObjAllocator


{


public:


   SmallObjAllocator(


      std::size_t chunkSize,


      std::size_t maxObjectSize);


   void* Allocate(std::size_t numBytes);


   void Deallocate(void* p, std::size_t size);


   ...


private:


   std::vector<FixedAllocator> pool_;


   ...


};

The constructor takes two parameters that configure SmallObjAllocator. The chunkSize parameter is the default chunk size (the length in bytes of each Chunk object), and maxObjectSize is the maximum size of objects that must be considered to be "small." SmallObjAllocator forwards requests for blocks larger than maxObjectSize directly to ::operator new.

Oddly enough, Deallocate takes the size to deallocate as an argument. Deallocations are much faster this way. Otherwise, SmallObjAllocator::Deallocate would have to search through all FixedAllocators in pool_ to find the one to which the pointer belongs. This is too expensive, so SmallObjAllocator requires you to pass the size of the block to deallocate. As you'll see in the next section, this task is graciously handled by the compiler itself.

What's the mapping between the block size of FixedAllocator and pool_? In other words, given a size, what's the FixedAllocator that handles allocations and deallocations for blocks of that size?

A simple and efficient idea is to have pool_[i] handle objects of size i. You initialize pool_ to have a size of maxObjectSize, and then initialize each FixedAllocator accordingly. When an allocation request of size numBytes comes, SmallObjAllocator forwards it either to pool_[numBytes]—a constant-time operation—or to ::operator new.

However, this solution is not as clever as it seems. "Efficient" is not always "effective." The problem is, you might need allocators only for certain sizes, depending on your application. For instance, maybe you create only objects of size 4 and 64—nothing else. In this case, you allocate 64 or more entries for pool_ although you use only 2.

Alignment and padding issues further contribute to wasting space in pool_. For instance, many compilers pad all user-defined types up to a multiple of a number (2, 4, or more). If the compiler pads all structures to a multiple of 4, for instance, you can count on using only 25% of pool_—the rest is wasted.

A better approach is to sacrifice a bit of lookup speed for the sake of memory conservation.^[3] We store FixedAllocators only for sizes that are requested at least once. This way pool_ can accommodate various object sizes without growing too much. To improve lookup speed, pool_ is kept sorted by block size.

^[3] Actually, on modern systems, you can count on an increase in speed when you use less memory. This is due to the big difference in speed between the main memory (large and slow) and the cache memory (small and fast).

To improve lookup speed, we can rely on the same strategy as in FixedAllocator. SmallObjAllocator keeps a pointer to the last FixedAllocator used for allocation and a pointer to the last FixedDeallocator used for deallocation. The following is the complete set of member variables in SmallObjAllocator.

class SmallObjAllocator


{


   ...


private:


   std::vector<FixedAllocator> pool_;


   FixedAllocator* pLastAlloc_;


   FixedAllocator* pLastDealloc_;


};

When an allocation request arrives, pLastAlloc_ is checked first. If it is not of the correct size, SmallObjAllocator::Allocate performs a binary search in pool_. Deal location requests are handled in a similar way. The only difference is that SmallObjAllocator::Allocate can end up inserting a new FixedAllocator object in pool_.

As discussed with FixedAllocator, this simple caching scheme favors bulk allocations and deallocations, which take place in constant time.