Module offset_allocator 

A fast, hard-real-time sub-allocator over one contiguous range.

An Allocator owns a single block of size units — units being whatever the caller needs, such as bytes, vertices or indices — and hands out contiguous sub-ranges of it. It knows nothing about the resource behind the range, which is what makes it usable for packing many small ranges into one GPU buffer: allocate the range, then write the data at offset * unit_size.

The algorithm is the two-level segregated fit used by Sebastian Aaltonen’s OffsetAllocator: free ranges (“nodes”) are filed into 256 bins whose boundaries follow an 8-bit float distribution (a 3-bit mantissa and a 5-bit exponent), so that the relative overhead of rounding to a bin stays under 12.5% for every size class. Two bitfields — one per top-level bin, one per leaf bin — make the search for the next fitting bin two trailing_zeros instructions, so Allocator::allocate and Allocator::free are O(1) and never allocate.

Every allocation starts at a multiple of the alignment fixed at construction, which is what a GPU buffer sub-allocation needs: the size charged for an allocation is the requested size rounded up to that alignment.

Known limitation

A free range is filed under the bin of its rounded-down size, while an allocation searches from the bin of its rounded-up size. A range whose size is not exactly representable by a bin is therefore never found by an allocation of exactly that size, even though it would fit — so Allocator::new(size).allocate(size) fails for most size values. Size the allocator with min_allocator_size (and, for aligned allocators, pass the same alignment) to make the initial free range representable:

use unlit_wgpu::offset_allocator::{Allocator, min_allocator_size};
use core::num::NonZeroU32;

let mut allocator = Allocator::new(min_allocator_size(1000, NonZeroU32::MIN));
assert!(allocator.allocate(1000).is_some());

Re-exports

use core::fmt::Debug; 🔒

use core::fmt::Debug; 🔒

use core::fmt::Formatter; 🔒

use core::fmt::Result as FmtResult; 🔒

use core::num::NonZeroU32; 🔒

Modules

small_float 🔒

The 8-bit float size distribution the bins follow.

Structs

Allocation

A single allocation, handed out by Allocator::allocate.

Allocator

An allocator that manages a single contiguous chunk of space and hands out portions of it as requested.

Node 🔒

A range of the managed chunk: either an allocation or the free space around one.

NodeIndex 🔒

The index of a Node.

StorageReport

Provides a summary of the state of the allocator, including space remaining.

Constants

BINS_PER_LEAF 🔒

The number of leaf bins per top-level bin.

DEFAULT_MAX_NODES 🔒

The number of nodes an allocator tracks unless the caller says otherwise.

LEAF_BINS_INDEX_MASK 🔒

The mask of the leaf bin index within a leaf bin index.

NUM_LEAF_BINS 🔒

The number of leaf bins, i.e. of distinct size classes.

NUM_TOP_BINS 🔒

The number of top-level bins.

TOP_BINS_INDEX_SHIFT 🔒

The bit position of a top-level bin index within a leaf bin index.

Functions

align_up 🔒

Rounds size up to the next multiple of alignment.

find_lowest_bit_set_after 🔒

Returns the index of the lowest set bit of bit_mask at or after start_bit_index, or None if there is none.

min_allocator_size

The smallest allocator size that can hold an allocation of size units at the given alignment.