Struct std.experimental.allocator.building_blocks.kernighan_ritchie.KRRegion
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.
struct KRRegion(ParentAllocator)
;
KRRegion
= Region
+ Kernighan-Ritchie Allocator
Initially, KRRegion
starts in "region" mode: allocations are served from
the memory chunk in a region fashion. Thus, as long as there is enough memory
left, KRRegion
has 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.
Once the region cannot serve an allocate
request, KRRegion
switches
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.
The recommended use of KRRegion
is as a region with deallocation. If the
KRRegion
is 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.
If the chunk of memory managed is large, it may be desirable to switch
management to free list from the beginning. That way, memory may be used in a
more compact manner than region mode. To force free list mode, call switchToFreeList
shortly after construction or when deemed appropriate.
The smallest size that can be allocated is two words (16 bytes on 64-bit systems, 8 bytes on 32-bit systems). This is because the free list management needs two words (one for the length, the other for the next pointer in the singly-linked list).
The ParentAllocator
type parameter is the type of the allocator used to
allocate the memory chunk underlying the KRRegion
object. Choosing the
default (NullAllocator
) means the user is responsible for passing a buffer
at construction (and for deallocating it if necessary). Otherwise, KRRegion
automatically deallocates the buffer during destruction. For that reason, if
ParentAllocator
is not NullAllocator
, then KRRegion
is not
copyable.
Implementation Details
In free list mode, KRRegion
embeds 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.
Similarities of KRRegion
(in free list mode) with the
Kernighan-Ritchie allocator:
- Free blocks have variable size and are linked in a singly-linked list.
- The freelist is maintained in increasing address order, which makes coalescing easy.
- The strategy for finding the next available block is first fit.
- The free list is circular, with the last node pointing back to the first.
- Coalescing is carried during deallocation.
Differences from the Kernighan-Ritchie allocator:
- Once the chunk is exhausted, the Kernighan-Ritchie allocator allocates
another chunk using operating system primitives. For better composability,
KRRegion
just gets full (returnsnull
on new allocation requests). The decision to allocate more blocks is deferred to a higher-level entity. For an example, see the example below usingAllocatorList
in conjunction withKRRegion
. - Allocated blocks do not hold a size prefix. This is because in D the size information is available in client code at deallocation time.
Constructors
Name | Description |
---|---|
this
(b)
|
Create a KRRegion . If ParentAllocator is not NullAllocator ,
KRRegion 's destructor will call parent .
|
Fields
Name | Type | Description |
---|---|---|
parent
|
ParentAllocator | If ParentAllocator holds state, parent is a public member of type
KRRegion . Otherwise, parent is an alias for
ParentAllocator .
|
Methods
Name | Description |
---|---|
allocate
(n)
|
Allocates 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.
|
allocateAll
()
|
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.
|
deallocate
(b)
|
Deallocates 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.
|
deallocateAll
()
|
Deallocates all memory currently allocated, making the allocator ready for
other allocations. This is a Ο(1 ) operation.
|
empty
()
|
|
goodAllocSize
(n)
|
Adjusts n to a size suitable for allocation (two words or larger,
word-aligned).
|
owns
(b)
|
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.
|
switchToFreeList
()
|
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. |
Example
KRRegion
is preferable to Region
as a front for a general-purpose
allocator if deallocate
is needed, yet the actual deallocation traffic is
relatively low. The example below shows a KRRegion
using 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
Example
The code below defines a scalable allocator consisting of 1 MB (or larger) blocks fetched from the garbage-collected heap. Each block is organized as a KR-style heap. More blocks are allocated and freed on a need basis.
This is the closest example to the allocator introduced in the K&R book. It should perform slightly better because instead of searching through one large free list, it searches through several shorter lists in LRU order. Also, it actually returns memory to the operating system when possible.
import std .algorithm .comparison : max;
import std .experimental .allocator .building_blocks .allocator_list
: AllocatorList;
import std .experimental .allocator .mmap_allocator : MmapAllocator;
AllocatorList!(n => KRRegion!MmapAllocator(max(n * 16, 1024 * 1024))) alloc;