Quantizer

This allocator sits on top of ParentAllocator and quantizes allocation sizes, usually from arbitrary positive numbers to a small set of round numbers (e.g. powers of two, page sizes etc). This technique is commonly used to:

Preallocate more memory than requested such that later on, when reallocation is needed (e.g. to grow an array), expansion can be done quickly in place. Reallocation to smaller sizes is also fast (in-place) when the new size requested is within the same quantum as the existing size. Code that's reallocation-heavy can therefore benefit from fronting a generic allocator with a Quantizer. These advantages are present even if ParentAllocator does not support reallocation at all.
Improve behavior of allocators sensitive to allocation sizes, such as FreeList and FreeTree. Rounding allocation requests up makes for smaller free lists/trees at the cost of slack memory (internal fragmentation).

The following methods are forwarded to the parent allocator if present: allocateAll, owns, deallocateAll, empty.

Preconditions: roundingFunction must satisfy three constraints. These are not enforced (save for the use of assert) for the sake of efficiency.

roundingFunction(n) >= n for all n of type size_t;
roundingFunction must be monotonically increasing, i.e. roundingFunction(n1) <= roundingFunction(n2) for all n1 < n2;
roundingFunction must be nothrow, @safe, @nogc and pure, i.e. always return the same value for a given n.

struct Quantizer (

ParentAllocator

alias roundingFunction

) {

eponymoustemplate hasMember(T, string name) via import std.traits : hasMember;;

static if(stateSize!ParentAllocator)

ParentAllocator parent;

__gshared

static if(!(stateSize!ParentAllocator))

Quantizer instance;

size_t goodAllocSize(size_t n);

enum alignment;

void[] allocate(size_t n);

static if(hasMember!(ParentAllocator, "alignedAllocate"))

void[] alignedAllocate(size_t n, uint a);

bool expand(void[] b, size_t delta);

bool reallocate(void[] b, size_t s);

static if(hasMember!(ParentAllocator, "alignedAllocate"))

bool alignedReallocate(void[] b, size_t s, uint a);

static if(hasMember!(ParentAllocator, "deallocate"))

bool deallocate(void[] b);

}

Members

Functions

alignedAllocate void[] alignedAllocate(size_t n, uint a): Defined only if parent.alignedAllocate exists and works similarly to allocate by forwarding to parent.alignedAllocate(goodAllocSize(n), a).
alignedReallocate bool alignedReallocate(void[] b, size_t s, uint a): Defined only if ParentAllocator.alignedAllocate exists. Expansion occurs in place under the conditions required by expand. Shrinking occurs in place if goodAllocSize(b.length) == goodAllocSize(s).
allocate void[] allocate(size_t n): Gets a larger buffer buf by calling parent.allocate(goodAllocSize(n)). If buf is null, returns null. Otherwise, returns buf[0 .. n].
deallocate bool deallocate(void[] b): Defined if ParentAllocator.deallocate exists and forwards to parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)]).
expand bool expand(void[] b, size_t delta): First checks whether there's enough slack memory preallocated for b by evaluating b.length + delta <= goodAllocSize(b.length). If that's the case, expands b in place. Otherwise, attempts to use parent.expand appropriately if present.
goodAllocSize size_t goodAllocSize(size_t n): Returns roundingFunction(n).
reallocate bool reallocate(void[] b, size_t s): Expands or shrinks allocated block to an allocated size of goodAllocSize(s). Expansion occurs in place under the conditions required by expand. Shrinking occurs in place if goodAllocSize(b.length) == goodAllocSize(s).

Manifest constants

alignment enum alignment;: Alignment is identical to that of the parent.

Variables

parent ParentAllocator parent;: The parent allocator. Depending on whether ParentAllocator holds state or not, this is a member variable or an alias for ParentAllocator.instance.

Examples

import std.experimental.allocator.building_blocks.free_tree : FreeTree;
import std.experimental.allocator.gc_allocator : GCAllocator;

size_t roundUpToMultipleOf(size_t s, uint base)
{
    auto rem = s % base;
    return rem ? s + base - rem : s;
}

// Quantize small allocations to a multiple of cache line, large ones to a
// multiple of page size
alias MyAlloc = Quantizer!(
    FreeTree!GCAllocator,
    n => roundUpToMultipleOf(n, n <= 16_384 ? 64 : 4096));
MyAlloc alloc;
const buf = alloc.allocate(256);
assert(buf.ptr);

The OpenD Programming Language