Struct std.experimental.allocator.building_blocks.bitmapped_block.BitmappedBlock
BitmappedBlock implements a simple heap consisting of one contiguous area
of memory organized in blocks, each of size theBlockSize. 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.
struct BitmappedBlock(ulong theBlockSize, uint theAlignment = platformAlignment, ParentAllocator)
;
Passing NullAllocator as ParentAllocator (the default) means user code
manages allocation of the memory block from the outside; in that case
BitmappedBlock must be constructed with a void[] preallocated block and
has no responsibility regarding the lifetime of its support underlying storage.
If another allocator type is passed, BitmappedBlock defines a destructor that
uses the parent allocator to release the memory block. That makes the combination of AllocatorList, BitmappedBlock, and a back-end allocator such as MmapAllocator 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 AffixAllocator 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 BitmappedBlock does
not need to maintain the allocated size, freeing memory implicitly coalesces
free blocks together. Also, tuning blockSize 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 blockSize parameter as in BitmappedBlock!(4096). To choose a block
size parameter, use BitmappedBlock!(chooseAtRuntime) and pass the
block size to the constructor.
Constructors
| Name | Description |
|---|---|
this
|
Constructs a block allocator given a hunk of memory, or a desired capacity in bytes. |
Fields
| Name | Type | Description |
|---|---|---|
parent
|
ParentAllocator | The parent allocator. Depending on whether ParentAllocator holds state
or not, this is a member variable or an alias for
ParentAllocator.
|
Methods
| Name | Description |
|---|---|
alignedAllocate
|
Allocates a block with specified alignment a. The alignment must be a
power of 2. If a <= alignment, function forwards to allocate.
Otherwise, it attempts to overallocate and then adjust the result for
proper alignment. In the worst case the slack memory is around two blocks.
|
alignedReallocate
|
Reallocates a block previously allocated with alignedAllocate. Contractions do not occur in place.
|
allocate
|
Allocates s bytes of memory and returns it, or null if memory
could not be allocated.
|
allocateAll
|
If the BitmappedBlock object is empty (has no active allocation), allocates
all memory within and returns a slice to it. Otherwise, returns null
(i.e. no attempt is made to allocate the largest available block).
|
allocateFresh
|
Allocates s bytes of memory and returns it, or null if memory
could not be allocated.
|
deallocate
|
Deallocates a block previously allocated with this allocator. |
deallocateAll
|
Forcibly deallocates all memory allocated by this allocator, making it
available for further allocations. Does not return memory to ParentAllocator.
|
empty
|
Returns Ternary if no memory is currently allocated with this
allocator, otherwise Ternary. This method never returns
Ternary.
|
expand
|
Expands an allocated block in place. |
goodAllocSize
|
Returns the actual bytes allocated when n bytes are requested, i.e.
n.
|
owns
|
Returns Ternary if b belongs to the BitmappedBlock object,
Ternary otherwise. Never returns Ternary. (This
method is somewhat tolerant in that accepts an interior slice.)
|
reallocate
|
Reallocates a previously-allocated block. Contractions occur in place. |
Aliases
| Name | Description |
|---|---|
alignment
|
The alignment offered is user-configurable statically through parameter
theAlignment, defaulted to platformAlignment.
|
blockSize
|
If blockSize == chooseAtRuntime, BitmappedBlock offers a read/write
property blockSize. It must be set before any use of the allocator.
Otherwise (i.e. theBlockSize is a legit constant), blockSize is
an alias for theBlockSize. Whether constant or variable, must also be
a multiple of alignment. This constraint is asserted statically
and dynamically.
|
Example
// Create a block allocator on top of a 10KB stack region.
import std