AlignedBlockList
represents a wrapper around a chain of allocators, allowing for fast deallocations and preserving a low degree of fragmentation by means of aligned allocations.
AlignedBlockList
represents a wrapper around a chain of allocators, allowing for fast deallocations and preserving a low degree of fragmentation. The allocator holds internally a doubly linked list of Allocator
objects, which will serve allocations in a most-recently-used fashion. Most recent allocators used for allocate
calls, will be moved to the front of the list.
Although allocations are in theory served in linear searching time, deallocate
calls take Ο(1
) time, by using aligned allocations. ParentAllocator
must implement alignedAllocate
and it must be able to allocate theAlignment
bytes at the same alignment. Each aligned allocation done by ParentAllocator
will contain metadata for an Allocator
, followed by its payload.
Allocator | the allocator which is used to manage each node; it must have a constructor which receives ubyte[] and it must not have any parent allocators, except for the NullAllocator
|
ParentAllocator | each node draws memory from the parent allocator; it must support alignedAllocate
|
theAlignment | alignment of each block and at the same time length of each node |
import std.experimental.allocator.building_blocks.ascending_page_allocator : AscendingPageAllocator; import std.experimental.allocator.building_blocks.segregator : Segregator; import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock; import std.typecons : Ternary; /* In this example we use 'AlignedBlockList' in conjunction with other allocators in order to create a more complex allocator. The 'SuperAllocator' uses a 'Segregator' to distribute allocations to sub-allocators, based on the requested size. Each sub-allocator is represented by an 'AlignedBlockList' of 'BitmappedBlocks'. Each 'AlignedBlockList' draws memory from a root allocator which in this case is an 'AscendingPageAllocator' Such an allocator not only provides good performance, but also a low degree of memory fragmentation. */ alias SuperAllocator = Segregator!( 32, AlignedBlockList!(BitmappedBlock!32, AscendingPageAllocator*, 1 << 12), Segregator!( 64, AlignedBlockList!(BitmappedBlock!64, AscendingPageAllocator*, 1 << 12), Segregator!( 128, AlignedBlockList!(BitmappedBlock!128, AscendingPageAllocator*, 1 << 12), AscendingPageAllocator* ))); SuperAllocator a; auto pageAlloc = AscendingPageAllocator(128 * 4096); // Set the parent allocator for all the sub allocators a.allocatorForSize!256 = &pageAlloc; a.allocatorForSize!128.parent = &pageAlloc; a.allocatorForSize!64.parent = &pageAlloc; a.allocatorForSize!32.parent = &pageAlloc; enum testNum = 10; void[][testNum] buf; // Allocations of size 32 will go to the first 'AlignedBlockList' foreach (j; 0 .. testNum) { buf[j] = a.allocate(32); writeln(buf[j].length); // 32 // This is owned by the first 'AlignedBlockList' writeln(a.allocatorForSize!32.owns(buf[j])); // Ternary.yes } // Free the memory foreach (j; 0 .. testNum) assert(a.deallocate(buf[j])); // Allocations of size 64 will go to the second 'AlignedBlockList' foreach (j; 0 .. testNum) { buf[j] = a.allocate(64); writeln(buf[j].length); // 64 // This is owned by the second 'AlignedBlockList' writeln(a.allocatorForSize!64.owns(buf[j])); // Ternary.yes } // Free the memory foreach (j; 0 .. testNum) assert(a.deallocate(buf[j])); // Allocations of size 128 will go to the third 'AlignedBlockList' foreach (j; 0 .. testNum) { buf[j] = a.allocate(128); writeln(buf[j].length); // 128 // This is owned by the third 'AlignedBlockList' writeln(a.allocatorForSize!128.owns(buf[j])); // Ternary.yes } // Free the memory foreach (j; 0 .. testNum) assert(a.deallocate(buf[j])); // Allocations which exceed 128, will go to the 'AscendingPageAllocator*' void[] b = a.allocate(256); writeln(b.length); // 256 a.deallocate(b);
Returns a chunk of memory of size n
It finds the first node in the AlignedBlockNode
list which has available memory, and moves it to the front of the list.
All empty nodes which cannot return new memory, are removed from the list.
size_t n
| bytes to allocate |
null
on failure orDeallocates the buffer b
given as parameter. Deallocations take place in constant time, regardless of the number of nodes in the list. b.ptr
is rounded down to the nearest multiple of the alignment
to quickly find the corresponding AlignedBlockNode
.
void[] b
| buffer candidate for deallocation |
true
on success and false
on failureReturns Ternary.yes
if the buffer belongs to the parent allocator and Ternary.no
otherwise.
void[] b
| buffer tested if owned by this allocator |
Ternary.yes
if owned by this allocator and Ternary.no
otherwiseSharedAlignedBlockList
is the threadsafe version of AlignedBlockList
. The Allocator
template parameter must refer a shared allocator. Also, ParentAllocator
must be a shared allocator, supporting alignedAllocate
.
Allocator | the shared allocator which is used to manage each node; it must have a constructor which receives ubyte[] and it must not have any parent allocators, except for the NullAllocator
|
ParentAllocator | each node draws memory from the parent allocator; it must be shared and support alignedAllocate
|
theAlignment | alignment of each block and at the same time length of each node |
import std.experimental.allocator.building_blocks.region : SharedRegion; import std.experimental.allocator.building_blocks.ascending_page_allocator : SharedAscendingPageAllocator; import std.experimental.allocator.building_blocks.null_allocator : NullAllocator; import core.thread : ThreadGroup; enum numThreads = 8; enum size = 2048; enum maxIter = 10; /* In this example we use 'SharedAlignedBlockList' together with 'SharedRegion', in order to create a fast, thread-safe allocator. */ alias SuperAllocator = SharedAlignedBlockList!( SharedRegion!(NullAllocator, 1), SharedAscendingPageAllocator, 4096); SuperAllocator a; // The 'SuperAllocator' will draw memory from a 'SharedAscendingPageAllocator' a.parent = SharedAscendingPageAllocator(4096 * 1024); // Launch 'numThreads', each performing allocations void fun() { foreach (i; 0 .. maxIter) { void[] b = a.allocate(size); writeln(b.length); // size } } auto tg = new ThreadGroup; foreach (i; 0 .. numThreads) { tg.create(&fun); } tg.joinAll();
Returns a chunk of memory of size n
It finds the first node in the AlignedBlockNode
list which has available memory, and moves it to the front of the list.
All empty nodes which cannot return new memory, are removed from the list.
size_t n
| bytes to allocate |
null
on failure orDeallocates the buffer b
given as parameter. Deallocations take place in constant time, regardless of the number of nodes in the list. b.ptr
is rounded down to the nearest multiple of the alignment
to quickly find the corresponding AlignedBlockNode
.
void[] b
| buffer candidate for deallocation |
true
on success and false
on failureReturns Ternary.yes
if the buffer belongs to the parent allocator and Ternary.no
otherwise.
void[] b
| buffer tested if owned by this allocator |
Ternary.yes
if owned by this allocator and Ternary.no
otherwise
© 1999–2019 The D Language Foundation
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_experimental_allocator_building_blocks_aligned_block_list.html