OffsetAllocator
Classes
Fast hard realtime O(1) offset allocator with minimal fragmentation.
Uses 256 bins with 8 bit floating point distribution (3 bit mantissa + 5 bit exponent) and a two level bitfield to find the next available bin using 2x LZCNT instructions to make all operations O(1). Bin sizes following the floating point distribution ensures hard bounds for memory overhead percentage regardless of size class. Pow2 bins would waste up to +100% memory (+50% on average). Our float bins waste up to +12.5% (+6.25% on average).
The allocation metadata is stored in a separate data structure, making this allocator suitable for sub-allocating any resources, such as GPU heaps, buffers and arrays. Returns an offset to the first element of the allocated contiguous range.
Constants
- NODE_INDEX_DATA_TYPE :
BinaryDataType
Can potentially use u16, but number of allocation slots will be limited to 65k, so a severe limitation for little gain
- NODE_TABLE_SPEC :
RowFirstTableSpec
Functions
NODE_INDEX_DATA_TYPE : BinaryDataType
Can potentially use u16, but number of allocation slots will be limited to 65k, so a severe limitation for little gain
Kind: global constant
NODE_TABLE_SPEC : RowFirstTableSpec
Kind: global constant
See: https://github.com/sebbbi/OffsetAllocator/blob/3610a7377088b1e8c8f1525f458c96038a4e6fc0/offsetAllocator.hpp#L70
findLowestSetBitAfter(bitMask, startBitIndex) ⇒ number
Kind: global function
| Param | Type |
|---|---|
| bitMask | number |
| startBitIndex | number |