stdx.allocator.building_blocks.bitmapped_block
-
Declaration
struct
BitmappedBlock
(size_t theBlockSize, uint theAlignment = platformAlignment, ParentAllocator = NullAllocator);implements a simple heap consisting of one contiguous area of memory organized in blocks, each of size . A block is a unit of allocation. A bitmap serves as bookkeeping data, more precisely one bit per block indicating whether that block is currently allocated or not.
Discussion
Passing as (the default) means user code manages allocation of the memory block from the outside; in that case must be constructed with a preallocated block and has no responsibility regarding the lifetime of its support underlying storage. If another allocator type is passed, defines a destructor that uses the parent allocator to release the memory block. That makes the combination of , , and a back-end allocator such as a simple and scalable solution for memory allocation.
There are advantages to storing bookkeeping data separated from the payload (as opposed to e.g. using to store metadata together with each allocation). The layout is more compact (overhead is one bit per block), searching for a free block during allocation enjoys better cache locality, and deallocation does not touch memory around the payload being deallocated (which is often cold).
Allocation requests are handled on a first-fit basis. Although linear in complexity, allocation is in practice fast because of the compact bookkeeping representation, use of simple and fast bitwise routines, and caching of the first available block position. A known issue with this general approach is fragmentation, partially mitigated by coalescing. Since does not need to maintain the allocated size, freeing memory implicitly coalesces free blocks together. Also, tuning has a considerable impact on both internal and external fragmentation.
The size of each block can be selected either during compilation or at run time. Statically-known block sizes are frequent in practice and yield slightly better performance. To choose a block size statically, pass it as the parameter as in . To choose a block size parameter, use and pass the block size to the constructor.Examples
// Create a block allocator on top of a 10KB stack region. import stdx.allocator.building_blocks.region : InSituRegion; import std.traits : hasMember; InSituRegion!(10_240, 64) r; auto a = BitmappedBlock!(64, 64)(cast(ubyte[])(r.allocateAll())); static assert(hasMember!(InSituRegion!(10_240, 64), "allocateAll")); const b = a.allocate(100); assert(b.length == 100);
-
Declaration
alias
blockSize
= theBlockSize;If , offers a read/write property . It must be set before any use of the allocator. Otherwise (i.e. is a legit constant), is an alias for . Whether constant or variable, must also be a multiple of . This constraint is ed statically and dynamically.
-
Declaration
alias
alignment
= theAlignment;The alignment offered is user-configurable statically through parameter , defaulted to .
-
Declaration
ParentAllocator
parent
;The parent allocator. Depending on whether holds state or not, this is a member variable or an alias for
ParentAllocator.instance
. -
Declaration
this(ubyte[]
data
);
this(size_tcapacity
);Constructs a block allocator given a hunk of memory, or a desired
capacity
in bytes.Discussion
- If is , only the constructor taking is defined and the user is responsible for freeing if desired.
- Otherwise, both constructors are defined. The -based constructor assumes memory has been allocated with the parent allocator. The -based constructor uses to allocate an appropriate contiguous hunk of memory. Regardless of the constructor used, the destructor releases the memory by using .
-
Declaration
size_t
goodAllocSize
(size_tn
);Returns the actual bytes allocated when bytes are requested, i.e. .
-
Declaration
@trusted void[]
allocate
(const size_ts
);Allocates bytes of memory and returns it, or if memory could not be allocated.
Discussion
The following information might be of help with choosing the appropriate block size. Actual allocation occurs in sizes multiple of the block size. Allocating one block is the fastest because only one 0 bit needs to be found in the metadata. Allocating 2 through 64 blocks is the next cheapest because it affects a maximum of two
s
in the metadata. Allocations greater than 64 blocks require a multiword search through the metadata. -
Declaration
void[]
alignedAllocate
(size_tn
, uinta
);Allocates
a
block with specified alignment . The alignment must bea
power of 2. If , function forwards to . Otherwise, it attempts to overallocate and then adjust the result for proper alignment. In the worst case the slack memory is around two blocks. -
Declaration
void[]
allocateAll
();If the object is empty (has no active allocation), allocates all memory within and returns a slice to it. Otherwise, returns (i.e. no attempt is made to allocate the largest available block).
-
Declaration
const Ternary
owns
(void[]b
);Returns
Ternary.yes
if
belongs to theb
BitmappedBlock
object,Ternary.no
otherwise. Never returnsTernary.unkown
. (This method is somewhat tolerant in that accepts an interior slice.) -
Declaration
@trusted bool
expand
(ref void[]b
, immutable size_tdelta
);Expands an allocated block in place.
-
Declaration
@system bool
reallocate
(ref void[]b
, size_tnewSize
);Reallocates a previously-allocated block. Contractions occur in place.
-
Declaration
@system bool
alignedReallocate
(ref void[]b
, size_tnewSize
, uinta
);Reallocates
a
block previously allocated with . Contractions do not occur in place. -
Declaration
bool
deallocate
(void[]b
);Deallocates a block previously allocated with this allocator.
-
Declaration
bool
deallocateAll
();Forcibly deallocates all memory allocated by this allocator, making it available for further allocations. Does not return memory to .
-
Declaration
Ternary
empty
();Returns
Ternary.yes
if no memory is currently allocated with this allocator, otherwiseTernary.no
. This method never returnsTernary.unknown
.
-
Declaration
struct
BitmappedBlockWithInternalPointers
(size_t theBlockSize, uint theAlignment = platformAlignment, ParentAllocator = NullAllocator);A with additional structure for supporting . To that end, adds a bitmap (one bit per block) that marks object starts. The bitmap itself has variable size and is allocated together with regular allocations.
Discussion
The time complexity of is , where is the size of the object within which the internal pointer is looked up.
-
Declaration
this(ubyte[]
data
);
this(size_tcapacity
);Constructors accepting desired
capacity
or a preallocated buffer, similar in semantics to those of . -
Declaration
alias
alignment
= theAlignment;
size_tgoodAllocSize
(size_tn
);
void[]allocate
(size_tbytes
);
void[]allocateAll
();
boolexpand
(ref void[]b
, size_tbytes
);
booldeallocate
(void[]b
);
TernaryresolveInternalPointer
(const void*p
, ref void[]result
);
Ternaryempty
();Allocator primitives.
-