std.experimental.allocator.building_blocks.aligned_block_list

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.

Source

std/experimental/allocator/building_blocks/aligned_block_list.d

struct AlignedBlockList(Allocator, ParentAllocator, ulong theAlignment = 1 << 21);

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.

Parameters:

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

Examples:

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);

void[] allocate(size_t n);

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.

Parameters:

size_t n

bytes to allocate

Returns:

A chunk of memory of the required length or null on failure or

bool deallocate(void[] b);

Deallocates 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.

Parameters:

void[] b

buffer candidate for deallocation

Returns:

true on success and false on failure

Ternary owns(void[] b);

Returns Ternary.yes if the buffer belongs to the parent allocator and Ternary.no otherwise.

Parameters:

void[] b

buffer tested if owned by this allocator

Returns:

Ternary.yes if owned by this allocator and Ternary.no otherwise

struct SharedAlignedBlockList(Allocator, ParentAllocator, ulong theAlignment = 1 << 21);

SharedAlignedBlockList is the threadsafe version of AlignedBlockList. The Allocator template parameter must refer a shared allocator. Also, ParentAllocator must be a shared allocator, supporting alignedAllocate.

Parameters:

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

Examples:

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();

void[] allocate(size_t n);

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.

Parameters:

size_t n

bytes to allocate

Returns:

A chunk of memory of the required length or null on failure or

bool deallocate(void[] b);

Deallocates 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.

Parameters:

void[] b

buffer candidate for deallocation

Returns:

true on success and false on failure

Ternary owns(void[] b);

Returns Ternary.yes if the buffer belongs to the parent allocator and Ternary.no otherwise.

Parameters:

void[] b

buffer tested if owned by this allocator

Returns:

Ternary.yes if owned by this allocator and Ternary.no otherwise