std.experimental.allocator.building_blocks.bitmapped_block

BitmappedBlock implements a simple heap consisting of one contiguous area of memory organized in blocks, each of size theBlockSize. A block is a unit of allocation. A bitmap serves as bookkeeping data, more precisely one bit per block indicating whether that block is currently allocated or not.

Passing NullAllocator as ParentAllocator (the default) means user code manages allocation of the memory block from the outside; in that case BitmappedBlock must be constructed with a ubyte[] preallocated block and has no responsibility regarding the lifetime of its support underlying storage. If another allocator type is passed, BitmappedBlock defines a destructor that uses the parent allocator to release the memory block. That makes the combination of AllocatorList, BitmappedBlock, and a back-end allocator such as MmapAllocator a simple and scalable solution for memory allocation.

There are advantages to storing bookkeeping data separated from the payload (as opposed to e.g. using AffixAllocator to store metadata together with each allocation). The layout is more compact (overhead is one bit per block), searching for a free block during allocation enjoys better cache locality, and deallocation does not touch memory around the payload being deallocated (which is often cold).

Allocation requests are handled on a first-fit basis. Although linear in complexity, allocation is in practice fast because of the compact bookkeeping representation, use of simple and fast bitwise routines, and caching of the first available block position. A known issue with this general approach is fragmentation, partially mitigated by coalescing. Since BitmappedBlock does not need to maintain the allocated size, freeing memory implicitly coalesces free blocks together. Also, tuning blockSize has a considerable impact on both internal and external fragmentation.

If the last template parameter is set to No.multiblock, the allocator will only serve allocations which require at most theBlockSize. The BitmappedBlock has a specialized implementation for single-block allocations which allows for greater performance, at the cost of not being able to allocate more than one block at a time.

The size of each block can be selected either during compilation or at run time. Statically-known block sizes are frequent in practice and yield slightly better performance. To choose a block size statically, pass it as the blockSize parameter as in BitmappedBlock!(4096). To choose a block size parameter, use BitmappedBlock!(chooseAtRuntime) and pass the block size to the constructor.

The threadsafe version of the BitmappedBlock. The semantics of the SharedBitmappedBlock are identical to the regular BitmappedBlock.

A BitmappedBlock with additional structure for supporting resolveInternalPointer. To that end, BitmappedBlockWithInternalPointers adds a bitmap (one bit per block) that marks object starts. The bitmap itself has variable size and is allocated together with regular allocations.

The time complexity of resolveInternalPointer is k, where k is the size of the object within which the internal pointer is looked up.