I've been implementing Andrei Alexandrescu's allocators as an exercise, but I've gotten stuck on his
Freelist looks something like this:
std::size_t kMaxSize /* Actual size of each block on the freelist */,
Everything but the
kBatchSize has a clear implementation to me. Let's take a specific example:
Freelist<A, 8, 8, 8, someLargeNumber>
Basically, a freelist which stores blocks of size
8 on its list, but allocates
8*8=64 bytes from the parent allocator when asked to allocate
8, threading the remaining bytes onto the freelist.
Some of my thoughts for how to implement this are as follows (assume
n is the number of blocks on the freelist):
- Join adjacent memory blocks when adding free'd blocks to the freelist. This loses the
O(1)complexity that we previously had, and also has the problem that it's possible to join blocks that are actually from different allocations.
- I could modify the previous technique to always allocate memory aligned to the batch size. Then, I could use the alignment to determine if two blocks are from different allocations. This still has the complexity problem, and restricts
kBatchSizeto powers of two (as alignment must be a power of two)
- I could have a
std::vector<Batch, BaseAllocator>to store extra information about a given batch. I strongly dislike this idea because it changes the memory requirement from
O(n). Freelists without batch allocation can be implemented in almost no extra memory (a pointer to the start and maybe a size of the list)
- I could require
BaseAllocatorto be what I would call a "segmentable allocator"; that is, segments of a block can be deallocated separately, or joined together and deallocated together. Although this would make the
Freelistimplementation trivial, this seems like too big of a requirement to place on
None of these approaches feels right to me. If allocating in batches is a worthwhile optimization for a freelist, it seems that there ought to be a way to implement it in
O(1) space and time.