View source code

Display the source code in std/experimental/allocator/building_blocks/bitmapped_block.d from which this page was generated on github.

Report a bug

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

Improve this page

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 using local clone.

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, Flag!("multiblock") f = Yes.multiblock)
				;

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 ubyte[] 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.

If the last template parameter is set to No.multiblock, the allocator will only serve allocations which require at most theBlockSize. The BitmappedBlock has a specialized implementation for single-block allocations which allows for greater performance, at the cost of not being able to allocate more than one block at a time.

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

Name	Description
`this`	Constructs a block allocator given a hunk of memory, or a desired capacity in bytes. If `ParentAllocator` is `NullAllocator`, only the constructor taking `data` is defined and the user is responsible for freeing `data` if desired. Otherwise, both constructors are defined. The `data`-based constructor assumes memory has been allocated with the parent allocator. The `capacity`-based constructor uses `ParentAllocator` to allocate an appropriate contiguous hunk of memory. Regardless of the constructor used, the destructor releases the memory by using `ParentAllocator.deallocate`.

this

Constructs a block allocator given a hunk of memory, or a desired capacity in bytes.

If ParentAllocator is NullAllocator, only the constructor taking data is defined and the user is responsible for freeing data if desired.
Otherwise, both constructors are defined. The data-based constructor assumes memory has been allocated with the parent allocator. The capacity-based constructor uses ParentAllocator to allocate an appropriate contiguous hunk of memory. Regardless of the constructor used, the destructor releases the memory by using ParentAllocator.deallocate.

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.instance`.

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. `allocateFresh` behaves just like allocate, the only difference being that this always returns unused(fresh) memory. Although there may still be available space in the `BitmappedBlock`, `allocateFresh` could still return null, because all the available blocks have been previously deallocated.
`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.yes` if no memory is currently allocated with this allocator, otherwise `Ternary.no`. This method never returns `Ternary.unknown`.
`expand`	Expands in place a buffer previously allocated by `BitmappedBlock`. If instantiated with `No.multiblock`, the expansion fails if the new length exceeds `theBlockSize`.
`goodAllocSize`	Returns the actual bytes allocated when `n` bytes are requested, i.e. `n.roundUpToMultipleOf(blockSize)`.
`owns`	Returns `Ternary.yes` if `b` belongs to the `BitmappedBlock` object, `Ternary.no` otherwise. Never returns `Ternary.unkown`. (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 `assert`ed statically and dynamically.

Parameters

Name	Description
theBlockSize	the length of a block, which must be a multiple of `theAlignment`
theAlignment	alignment of each block
ParentAllocator	allocator from which the `BitmappedBlock` will draw memory. If set to `NullAllocator`, the storage must be passed via the constructor
f	`Yes.multiblock` to support allocations spanning across multiple blocks and `No.multiblock` to support single block allocations. Although limited by single block allocations, `No.multiblock` will generally provide higher performance.

Example

// Create a block allocator on top of a 10KB stack region.
import std.experimental.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);
writeln(b.length); // 100

Example

import std.experimental.allocator.mallocator : Mallocator;
import std.typecons : Flag, Yes;

enum blockSize = 64;
enum numBlocks = 10;

// The 'BitmappedBlock' is implicitly instantiated with Yes.multiblock
auto a = BitmappedBlock!(blockSize, 8, Mallocator, Yes.multiblock)(numBlocks * blockSize);

// Instantiated with Yes.multiblock, can allocate more than one block at a time
void[] buf = a.allocate(2 * blockSize);
writeln(buf.length); // 2 * blockSize
assert(a.deallocate(buf));

// Can also allocate less than one block
buf = a.allocate(blockSize / 2);
writeln(buf.length); // blockSize / 2

// Expands inside the same block
assert(a.expand(buf, blockSize / 2));
writeln(buf.length); // blockSize

// If Yes.multiblock, can expand past the size of a single block
assert(a.expand(buf, 3 * blockSize));
writeln(buf.length); // 4 * blockSize
assert(a.deallocate(buf));

Example

import std.experimental.allocator.mallocator : Mallocator;
import std.typecons : Flag, No;

enum blockSize = 64;
auto a = BitmappedBlock!(blockSize, 8, Mallocator, No.multiblock)(1024 * blockSize);

// Since instantiated with No.multiblock, can only allocate at most the block size
void[] buf = a.allocate(blockSize + 1);
assert(buf is null);

buf = a.allocate(blockSize);
writeln(buf.length); // blockSize
assert(a.deallocate(buf));

// This is also fine, because it's less than the block size
buf = a.allocate(blockSize / 2);
writeln(buf.length); // blockSize / 2

// Can expand the buffer until its length is at most 64
assert(a.expand(buf, blockSize / 2));
writeln(buf.length); // blockSize

// Cannot expand anymore
assert(!a.expand(buf, 1));
assert(a.deallocate(buf));

API Documentation

Struct `std.experimental.allocator.building_blocks.bitmapped_block.BitmappedBlock`

Constructors

Fields

Methods

Aliases

Parameters

Example

Example

Example

Authors

License

API Documentation

Struct std.experimental.allocator.building_blocks.bitmapped_block.BitmappedBlock

Constructors

Fields

Methods

Aliases

Parameters

Example

Example

Example

Authors

License

Struct `std.experimental.allocator.building_blocks.bitmapped_block.BitmappedBlock`