Library Reference

version 2.111.0

Internal API

If you spot a problem with this page, click here to create a Bugzilla issue.

Quickly fork, edit online, and submit a pull request for this page.Requires a signed-in GitHub account. This works well for small changes.If you'd like to make larger changes you may want to consider usinga local clone.

std.experimental.allocator.building_blocks

Assembling Your Own Allocator

This package also implementsuntyped composable memory allocators. They areuntyped because they dealexclusively invoid[] and have no notion of what type the memory allocatedwould be destined for. They arecomposable because the included allocatorsare building blocks that can be assembled in complex nontrivial allocators.

Unlike the allocators for the C and C++ programming languages, which managethe allocated size internally, these allocators require that the clientmaintains (or knowsa priori) the allocation size for each piece of memoryallocated. Put simply, the client must pass the allocated size upondeallocation. Storing the size in the allocator has significant negativeperformance implications, and is virtually always redundant because client codeneeds knowledge of the allocated size in order to avoid buffer overruns. (Seemore discussion in aproposal for sizeddeallocation in C++.) For this reason, allocators herein traffic invoid[]as opposed tovoid*.

In order to be usable as an allocator, a type should implement thefollowing methods with their respective semantics. Onlyalignment andallocate are required. If any of the other methods is missing, the allocatoris assumed to not have that capability (for example some allocators do not offermanual deallocation of memory). Allocators should NOT implementunsupported methods to always fail. For example, an allocator that lacks thecapability to implementalignedAllocate should not define it at all (asopposed to defining it to always returnnull or throw an exception). Themissing implementation statically informs other components about theallocator's capabilities and allows them to make design decisions accordingly.


Method name	Semantics
`uint alignment;` Post:`result > 0`	Returns the minimumalignment of all data returned by the allocator. An allocator may implementalignment as a statically-knownenum value only. Applications that needdynamically-chosen alignment values should use thealignedAllocate andalignedReallocate APIs.
`size_t goodAllocSize(size_t n);` Post:`result >= n`	Allocatorscustomarily allocate memory in discretely-sized chunks. Therefore, a request forn bytes may result in a larger allocation. The extra memory allocated goesunused and adds to the so-calledinternal fragmentation.The functiongoodAllocSize(n) returns the actual number of bytes that wouldbe allocated upon a request forn bytes. This module defines a defaultimplementation that returnsn rounded up to a multiple of the allocator'salignment.
`void[] allocate(size_t s);` Post:`result is null \|\|result.length ==s`	Ifs == 0, the call may return any empty slice (includingnull). Otherwise, the call allocatess bytes of memory and returns theallocated block, ornull if the request could not be satisfied.
`void[] alignedAllocate(size_t s, uint a);` Post:`result is null \|\|result.length == s`	Similar toallocate, with the additionalguarantee that the memory returned is aligned to at leasta bytes.amust be a power of 2.
`void[] allocateAll();`	Offers all of allocator's memory to thecaller, so it's usually defined by fixed-size allocators. If the allocator iscurrently NOT managing any memory, thenallocateAll() shall allocate andreturn all memory available to the allocator, and subsequent calls to allallocation primitives should not succeed (e.g.allocate shall returnnull etc). Otherwise,allocateAll only works on a best-effort basis, andthe allocator is allowed to returnnull even if does have available memory.Memory allocated withallocateAll is not otherwise special (e.g. can bereallocated or deallocated with the usual primitives, if defined).
`bool expand(ref void[] b, size_t delta);` Post:`!result \|\| b.length==old(b).length + delta`	Expandsb bydelta bytes. Ifdelta == 0, succeeds without changingb. Ifb is null, returnsfalse (the null pointer cannot be expanded in place). Otherwise,b must be a buffer previously allocated with the same allocator. If expansionwas successful,expand changesb's length tob.length + delta andreturnstrue. Upon failure, the call effects no change upon the allocatorobject, leavesb unchanged, and returnsfalse.
`bool reallocate(ref void[] b, size_t s);` Post:`!result \|\| b.length== s`	Reallocatesb to sizes, possibly moving memory around.b must benull or a buffer allocated with the same allocator. Ifreallocation was successful,reallocate changesb appropriately andreturnstrue. Upon failure, the call effects no change upon the allocatorobject, leavesb unchanged, and returnsfalse. An allocator shouldimplementreallocate if it can derive some advantage from doing so;otherwise, this module defines areallocate free function implemented interms ofexpand,allocate, anddeallocate.
`bool alignedReallocate(ref void[] b, size_t s, uint a);` Post:`!result \|\| b.length == s`	Similar toreallocate, but guarantees thereallocated memory is aligned ata bytes. The buffer must have beenoriginated with a call toalignedAllocate.a must be a power of 2greater than(void*).sizeof. An allocator should implementalignedReallocate if it can derive some advantage from doing so; otherwise,this module defines aalignedReallocate free function implemented in termsofexpand,alignedAllocate, anddeallocate.
`Ternary owns(void[] b);`	ReturnsTernary.yes ifb has beenallocated with this allocator. An allocator should define this method only if itcan decide on ownership precisely and fast (in constant time, logarithmic time,or linear time with a low multiplication factor). Traditional allocators such asthe C heap do not define such functionality. Ifb is null, the allocatorshall returnTernary.no, i.e. no allocator owns thenull slice.
`Ternary resolveInternalPointer(void* p, ref void[] result);`	Ifp is a pointer somewhere inside a block allocated with this allocator,result holds a pointer to the beginning of the allocated block and returnsTernary.yes. Otherwise,result holdsnull and returnsTernary.no.If the pointer points immediately after an allocated block, the result isimplementation defined.
`bool deallocate(void[] b);`	Ifb is null, doesnothing and returnstrue. Otherwise, deallocates memory previously allocatedwith this allocator and returnstrue if successful,false otherwise. Animplementation that would not support deallocation (i.e. would always returnfalse should not define this primitive at all.)
`bool deallocateAll();` Post:`empty`	Deallocates all memoryallocated with this allocator. If an allocator implements this method, it mustspecify whether its destructor calls it, too.
`Ternary empty();`	ReturnsTernary.yes if and only if theallocator holds no memory (i.e. no allocation has occurred, or all allocationshave been deallocated).
`static Allocator instance;` Post:`instanceis a validAllocatorobject`	Some allocators aremonostate, i.e. have onlyan instance and hold only global state. (Notable examples are C's ownmalloc-based allocator and D's garbage-collected heap.) Such allocators mustdefine a staticinstance instance that serves as the symbolic placeholderfor the global instance of the allocator. An allocator should not hold stateand defineinstance simultaneously. Depending on whether the allocator isthread-safe or not, this instance may beshared.

Sample Assembly

The example below features an allocator modeled afterjemalloc, which uses a battery of free-list allocators spaced so as to keepinternal fragmentation to a minimum. TheFList definitions specify nobounds for the freelist because theSegregator does all size selection inadvance.

Sizes through 3584 bytes are handled via freelists of staggered sizes. Sizesfrom 3585 bytes through 4072 KB are handled by aBitmappedBlock with ablock size of 4 KB. Sizes above that are passed direct to theGCAllocator.

import std.experimental.allocator;import std.algorithm.comparison : max;alias FList = FreeList!(GCAllocator, 0, unbounded);alias A = Segregator!(    8, FreeList!(GCAllocator, 0, 8),    128, Bucketizer!(FList, 1, 128, 16),    256, Bucketizer!(FList, 129, 256, 32),    512, Bucketizer!(FList, 257, 512, 64),    1024, Bucketizer!(FList, 513, 1024, 128),    2048, Bucketizer!(FList, 1025, 2048, 256),    3584, Bucketizer!(FList, 2049, 3584, 512),    4072 * 1024, AllocatorList!(n => Region!GCAllocator(max(n, 1024 * 4096))),    GCAllocator);A tuMalloc;auto b = tuMalloc.allocate(500);assert(b.length == 500);auto c = tuMalloc.allocate(113);assert(c.length == 113);assert(tuMalloc.expand(c, 14));tuMalloc.deallocate(b);tuMalloc.deallocate(c);

Allocating memory for sharing across threads

One allocation pattern used in multithreaded applications is to share memoryacross threads, and to deallocate blocks in a different thread than the one thatallocated it.

All allocators in this module accept and returnvoid[] (as opposed toshared void[]). This is because at the time of allocation, deallocation, orreallocation, the memory is effectively notshared (if it were, it wouldreveal a bug at the application level).

The issue remains of callinga.deallocate(b) from a different thread thanthe one that allocatedb. It follows that both threads must have access tothe same instancea of the respective allocator type. By definition of D,this is possible only ifa has theshared qualifier. It follows thatthe allocator type must implementallocate anddeallocate asshared methods. That way, the allocator commits to allowing usablesharedinstances.

Conversely, allocating memory with one non-shared allocator, passing itacross threads (by casting the obtained buffer toshared), and laterdeallocating it in a different thread (either with a different allocator objector with the same allocator object after casting it toshared) is illegal.

Building Blocks

The table below gives a synopsis of predefined allocator building blocks,with their respective modules. Eitherimport the needed modules individually,orimportstd.experimental.building_blocks, which imports them allpublicly. The building blocks can be assembled in unbounded ways and alsocombined with your own. For a collection of typical and useful preassembledallocators and for inspiration in defining more such assemblies, refer tostd.experimental.allocator.showcase.


Allocator	Description
NullAllocator `std.experimental.allocator.building_blocks.null_allocator`	Very good at doing absolutely nothing. A goodstarting point for defining other allocators or for studying the API.
GCAllocator `std.experimental.allocator.gc_allocator`	The system-provided garbage-collector allocator.This should be the default fallback allocator tapping into system memory. Itoffers manualfree and dutifully collects litter.
Mallocator `std.experimental.allocator.mallocator`	The C heap allocator, a.k.a.malloc/realloc/free. Use sparingly and only for code that is unlikelyto leak.
AlignedMallocator `std.experimental.allocator.mallocator`	Interface to OS-specific allocators thatsupport specifying alignment:posix_memalignon Posix and__aligned_xxx on Windows.
AlignedBlockList `std.experimental.allocator.building_blocks.aligned_block_list`	A wrapper around a list of allocatorswhich allow for very fast deallocations.
AffixAllocator `std.experimental.allocator.building_blocks.affix_allocator`	Allocator that allows and manages allocatingextra prefix and/or a suffix bytes for each block allocated.
BitmappedBlock `std.experimental.allocator.building_blocks.bitmapped_block`	Organizes one contiguous chunk of memory inequal-size blocks and tracks allocation status at the cost of one bit perblock.
FallbackAllocator `std.experimental.allocator.building_blocks.fallback_allocator`	Allocator that combines two other allocators - primary and fallback. Allocation requests are first tried with primary, and upon failure are passed to the fallback. Useful for small and fast allocators fronting general-purpose ones.
FreeList `std.experimental.allocator.building_blocks.free_list`	Allocator that implements afree list on top of any other allocator. Thepreferred size, tolerance, and maximum elements are configurable at compile- andrun time.
SharedFreeList `std.experimental.allocator.building_blocks.free_list`	Same features asFreeList, but packaged asashared structure that is accessible to several threads.
FreeTree `std.experimental.allocator.building_blocks.free_tree`	Allocator similar toFreeList that uses abinary search tree to adaptively store not one, but many free lists.
Region `std.experimental.allocator.building_blocks.region`	Region allocator organizes a chunk of memory as asimple bump-the-pointer allocator.
InSituRegion `std.experimental.allocator.building_blocks.region`	Region holding its own allocation, most often onthe stack. Has statically-determined size.
SbrkRegion `std.experimental.allocator.building_blocks.region`	Region usingsbrk for allocating memory.
MmapAllocator `std.experimental.allocator.mmap_allocator`	Allocator usingmmap directly.
StatsCollector `std.experimental.allocator.building_blocks.stats_collector`	Collect statistics about any otherallocator.
Quantizer `std.experimental.allocator.building_blocks.quantizer`	Allocates in coarse-grained quantas, thusimproving performance of reallocations by often reallocating in place. The drawback is higher memory consumption because of allocated and unused memory.
AllocatorList `std.experimental.allocator.building_blocks.allocator_list`	Given an allocator factory, lazily creates asmany allocators as needed to satisfy allocation requests. The allocators arestored in a linked list. Requests for allocation are satisfied by searching thelist in a linear manner.
Segregator `std.experimental.allocator.building_blocks.segregator`	Segregates allocation requests by sizeand dispatches them to distinct allocators.
Bucketizer `std.experimental.allocator.building_blocks.bucketizer`	Divides allocation sizes in discrete buckets anduses an array of allocators, one per bucket, to satisfy requests.
AscendingPageAllocator `std.experimental.allocator.building_blocks.ascending_page_allocator`	A memory safe allocatorwhere sizes are rounded to a multiple of the page size and allocations are satisfied at increasing addresses.