KRRegion draws inspiration from the region allocation strategy and also the famed allocator described by Brian Kernighan and Dennis Ritchie in section 8.7 of the book "The C Programming Language", Second Edition, Prentice Hall, 1988.
Region+ Kernighan-Ritchie Allocator
KRRegionstarts in "region" mode: allocations are served from the memory chunk in a region fashion. Thus, as long as there is enough memory left,
KRRegion.allocatehas the performance profile of a region allocator. Deallocation inserts (in Ο(
1) time) the deallocated blocks in an unstructured freelist, which is not read in region mode.
KRRegionswitches to "free list" mode. It sorts the list of previously deallocated blocks by address and serves allocation requests off that free list. The allocation and deallocation follow the pattern described by Kernighan and Ritchie.
KRRegionis as a region with deallocation. If the
KRRegionis dimensioned appropriately, it could often not enter free list mode during its lifetime. Thus it is as fast as a simple region, whilst offering deallocation at a small cost. When the region memory is exhausted, the previously deallocated memory is still usable, at a performance cost. If the region is not excessively large and fragmented, the linear allocation and deallocation cost may still be compensated for by the good locality characteristics.
switchToFreeListshortly after construction or when deemed appropriate.
ParentAllocatortype parameter is the type of the allocator used to allocate the memory chunk underlying the
KRRegionobject. Choosing the default (
NullAllocator) means the user is responsible for passing a buffer at construction (and for deallocating it if necessary). Otherwise,
KRRegionautomatically deallocates the buffer during destruction. For that reason, if
KRRegionis not copyable.
KRRegionembeds a free blocks list onto the chunk of memory. The free list is circular, coalesced, and sorted by address at all times. Allocations and deallocations take time proportional to the number of previously deallocated blocks. (In practice the cost may be lower, e.g. if memory is deallocated in reverse order of allocation, all operations take constant time.) Memory utilization is good (small control structure and no per-allocation overhead). The disadvantages of freelist mode include proneness to fragmentation, a minimum allocation size of two words, and linear worst-case allocation and deallocation times.
KRRegion(in free list mode) with the Kernighan-Ritchie allocator:
KRRegionjust gets full (returns
nullon new allocation requests). The decision to allocate more blocks is deferred to a higher-level entity. For an example, see the example below using
AllocatorListin conjunction with
KRRegionis preferable to
Regionas a front for a general-purpose allocator if
deallocateis needed, yet the actual deallocation traffic is relatively low. The example below shows a
KRRegionusing stack storage fronting the GC allocator.
import std.experimental.allocator.building_blocks.fallback_allocator : fallbackAllocator; import std.experimental.allocator.gc_allocator : GCAllocator; import std.typecons : Ternary; // KRRegion fronting a general-purpose allocator ubyte[1024 * 128] buf; auto alloc = fallbackAllocator(KRRegion!()(buf), GCAllocator.instance); auto b = alloc.allocate(100); writeln(b.length); // 100 writeln(( () pure nothrow @safe @nogc => alloc.primary.owns(b))()); // Ternary.yes
import std.algorithm.comparison : max; import std.experimental.allocator.building_blocks.allocator_list : AllocatorList; import std.experimental.allocator.gc_allocator : GCAllocator; import std.experimental.allocator.mmap_allocator : MmapAllocator; AllocatorList!(n => KRRegion!MmapAllocator(max(n * 16, 1024 * 1024))) alloc;
ParentAllocator holds state,
parent is a public member of type
parent is an
ParentAllocator is not
KRRegion's destructor will call
|ubyte ||Block of memory to serve as support for the allocator. Memory must be larger than two words and word-aligned.|
|size_t ||Capacity desired. This constructor is defined only if
Forces free list mode. If already in free list mode, does nothing. Otherwise, sorts the free list accumulated so far and switches strategy for future allocations to KR style.
n bytes. Allocation searches the list of available blocks until a free block with
n or more bytes is found (first fit strategy). The block is split (if larger) and returned.
|size_t ||number of bytes to allocate|
b, which is assumed to have been previously allocated with this allocator. Deallocation performs a linear search in the free list to preserve its sorting order. It follows that blocks with higher addresses in allocators with many free blocks are slower to deallocate.
|void ||block to be deallocated|
Allocates all memory available to this allocator. If the allocator is empty, returns the entire available block of memory. Otherwise, it still performs a best-effort allocation: if there is no fragmentation (e.g.
allocate has been used but not
deallocate), allocates and returns the only available block of memory.
The operation takes time proportional to the number of adjacent free blocks at the front of the free list. These blocks get coalesced, whether
allocateAll succeeds or fails due to fragmentation.
import std.experimental.allocator.gc_allocator : GCAllocator; auto alloc = KRRegion!GCAllocator(1024 * 64); const b1 = alloc.allocate(2048); writeln(b1.length); // 2048 const b2 = alloc.allocateAll; writeln(b2.length); // 1024 * 62
Deallocates all memory currently allocated, making the allocator ready for other allocations. This is a Ο(
Checks whether the allocator is responsible for the allocation of
b. It does a simple Ο(
1) range check.
b should be a buffer either allocated with
this or obtained through other means.
n to a size suitable for allocation (two words or larger, word-aligned).
Ternary.yesif the allocator is empty,
Ternary.nootherwise. Never returns
© 1999–2019 The D Language Foundation
Licensed under the Boost License 1.0.