README
¶
galloc
O(1) offset allocator for GPU memory sub-allocation. Pure Go, zero CGO, zero dependencies.
A Go port of Sebastian Aaltonen's OffsetAllocator (MIT, 1,051 stars C++). Manages a single contiguous range of offsets (e.g., a GPU heap or buffer) and hands out sub-regions with O(1) allocation, O(1) free, and automatic neighbor coalescing.
Features
- O(1) allocate and free -- two-level bitfield bin lookup, no linear scans
- Automatic coalescing -- adjacent free regions merge on free via doubly-linked neighbor list
- Zero heap allocations on hot path -- all node storage pre-allocated in
New() - 256 size classes -- SmallFloat encoding (3-bit mantissa + 5-bit exponent) covers the full 32-bit range with at most 12.5% overhead per allocation
- Thread-safe wrapper --
SyncAllocatoraddssync.Mutexfor concurrent use - Pure Go -- no unsafe, no CGO, no assembly, stdlib only
- Go 1.25+ -- matches gogpu ecosystem requirements
Installation
go get github.com/gogpu/galloc
Quick Start
package main
import (
"fmt"
"github.com/gogpu/galloc"
)
func main() {
// Manage a 64MB GPU heap with up to 4096 allocations.
a := galloc.New(64*1024*1024, 4096)
// Allocate 256 bytes.
alloc := a.Allocate(256)
if alloc.Failed() {
panic("out of memory")
}
fmt.Printf("Offset: %d\n", alloc.Offset) // 0
// Check free space.
report := a.StorageReport()
fmt.Printf("Free: %d, Largest: %d\n", report.TotalFreeSpace, report.LargestFreeRegion)
// Free the allocation.
a.Free(alloc)
}
Algorithm
The allocator is based on TLSF (Two-Level Segregated Fit) principles adapted for offset-only allocation (no actual memory management).
SmallFloat Binning
Sizes are mapped to 256 bins using a custom floating-point encoding with a 3-bit mantissa and 5-bit exponent:
Bin index = (exponent << 3) | mantissa
Sizes 0-7: exact (denormalized, exponent = 0)
Sizes 8+: normalized with hidden high bit (like IEEE 754)
Examples:
Size 1 -> bin 1 (exact)
Size 8 -> bin 8 (exact)
Size 1024 -> bin 64
Size 65536 -> bin 112
The maximum overhead per allocation is 12.5% (1/8), determined by the 3-bit mantissa.
Two-Level Bitfield
Free bins are tracked with a two-level bitfield for O(1) lookup:
usedBinsTop: uint32 -- 32 bits, one per top-level group
usedBins[32]: uint8 -- 8 bits each, one per leaf bin within a group
Total: 32 * 8 = 256 leaf bins
Finding the best-fit bin requires at most two TrailingZeros intrinsics.
Neighbor Coalescing
Every node maintains doubly-linked neighborPrev/neighborNext pointers to spatially adjacent regions. When a region is freed, the allocator checks both neighbors and merges contiguous free regions into a single larger block, eliminating fragmentation.
Node Pool
All nodes are pre-allocated in New(). A freelist stack provides O(1) node allocation and deallocation without any heap interaction on the hot path.
Thread Safety
Allocator is not safe for concurrent use. For multi-goroutine scenarios, use SyncAllocator:
a := galloc.NewSync(64*1024*1024, 4096)
// Safe to call from multiple goroutines:
alloc := a.Allocate(256)
a.Free(alloc)
Use Cases
- GPU buffer sub-allocation -- manage a single
VkBufferorID3D12Resourceheap - Ring buffer management -- track free regions in a staging belt
- Memory pool offset tracking -- any scenario requiring contiguous range sub-allocation
Credits
Based on OffsetAllocator by Sebastian Aaltonen. Also informed by offset-allocator (Rust port by Patrick Walton).
License
MIT License. See LICENSE.
Documentation
¶
Overview ¶
Package galloc provides an O(1) offset allocator for GPU memory sub-allocation.
This is a Pure Go port of Sebastian Aaltonen's OffsetAllocator (https://github.com/sebbbi/OffsetAllocator, MIT, 1,051 stars). It manages a single contiguous range of offsets (e.g. a GPU heap or buffer) and hands out sub-regions in O(1) time with O(1) free and automatic neighbor coalescing.
Algorithm ¶
The allocator uses a two-level bitfield bin system inspired by TLSF (Two-Level Segregated Fit) memory allocators. Bin sizes follow a SmallFloat encoding with a 3-bit mantissa and 5-bit exponent, yielding 256 size classes that cover the full 32-bit range with at most 12.5% overhead per allocation.
Allocation searches the two-level bitfield for the smallest bin that fits the request. Free regions within each bin are stored in a doubly-linked free list. When a region is freed, the allocator checks its spatial neighbors (tracked via a doubly-linked neighbor list) and coalesces adjacent free regions.
All operations (Allocate, Free) are O(1) with respect to the number of existing allocations. The hot path performs zero heap allocations — all node storage is pre-allocated in New.
Thread Safety ¶
Allocator is NOT safe for concurrent use. Use SyncAllocator for a thread-safe wrapper that adds a sync.Mutex.
Usage ¶
a := galloc.New(1024*1024, 1024) // 1 MB range, up to 1024 allocations
alloc := a.Allocate(256)
if alloc.Failed() {
// no space
}
// use alloc.Offset as the sub-allocation offset
a.Free(alloc)
Index ¶
Constants ¶
const NoSpace = 0xFFFFFFFF
NoSpace is the sentinel value indicating a failed allocation.
Variables ¶
This section is empty.
Functions ¶
func MinAllocatorSize ¶
MinAllocatorSize returns the minimum allocator size needed to hold an object of the given size. Due to SmallFloat bin rounding, the allocator size may need to be slightly larger than the requested object size.
Types ¶
type Allocation ¶
Allocation represents a sub-region returned by Allocator.Allocate.
Offset is the starting position within the managed range. Metadata is an opaque internal handle required by Allocator.Free and Allocator.AllocationSize. Do not interpret or modify it.
func (Allocation) Failed ¶
func (a Allocation) Failed() bool
Failed reports whether the allocation failed (no contiguous space available).
type Allocator ¶
type Allocator struct {
// contains filtered or unexported fields
}
Allocator manages a contiguous range of [0, size) and sub-allocates regions from it in O(1) time. All internal storage is pre-allocated; Allocate and Free perform zero heap allocations.
Allocator is NOT safe for concurrent use from multiple goroutines. Use SyncAllocator for a thread-safe wrapper.
func New ¶
New creates an Allocator that manages a contiguous range of size units with room for at most maxAllocs simultaneous allocations.
All internal storage is allocated up front. Subsequent Allocate and Free calls perform zero heap allocations.
func (*Allocator) Allocate ¶
func (a *Allocator) Allocate(size uint32) Allocation
Allocate reserves a contiguous region of the given size and returns an Allocation describing it. If there is not enough contiguous space, or the maximum number of allocations has been reached, the returned Allocation will have Offset == NoSpace (check with Allocation.Failed).
A size of 0 is treated as a valid allocation of zero bytes at offset 0 (matching the C++ original behavior).
func (*Allocator) AllocationSize ¶
func (a *Allocator) AllocationSize(alloc Allocation) uint32
AllocationSize returns the size stored for an allocation. This is the size that was passed to Allocate, not the bin-rounded size.
func (*Allocator) Free ¶
func (a *Allocator) Free(alloc Allocation)
Free releases a previously-made allocation, returning its space to the pool. Adjacent free regions are automatically coalesced.
Passing a failed allocation (Offset == NoSpace) is a no-op. Freeing the same allocation twice will panic.
func (*Allocator) Reset ¶
func (a *Allocator) Reset()
Reset clears all allocations and returns the allocator to its initial state.
func (*Allocator) StorageReport ¶
func (a *Allocator) StorageReport() StorageReport
StorageReport returns a summary of the allocator's free space, including the total free space and the largest single contiguous free region.
type StorageReport ¶
StorageReport summarizes the free space in an Allocator.
type SyncAllocator ¶
type SyncAllocator struct {
// contains filtered or unexported fields
}
SyncAllocator is a thread-safe wrapper around Allocator. All methods are protected by a sync.Mutex.
func NewSync ¶
func NewSync(size, maxAllocs uint32) *SyncAllocator
NewSync creates a thread-safe allocator that manages a contiguous range of size units with room for at most maxAllocs simultaneous allocations.
func (*SyncAllocator) Allocate ¶
func (s *SyncAllocator) Allocate(size uint32) Allocation
Allocate reserves a contiguous region of the given size. See Allocator.Allocate for details.
func (*SyncAllocator) AllocationSize ¶
func (s *SyncAllocator) AllocationSize(alloc Allocation) uint32
AllocationSize returns the size stored for an allocation. See Allocator.AllocationSize for details.
func (*SyncAllocator) Free ¶
func (s *SyncAllocator) Free(alloc Allocation)
Free releases a previously-made allocation. See Allocator.Free for details.
func (*SyncAllocator) Reset ¶
func (s *SyncAllocator) Reset()
Reset clears all allocations and returns the allocator to its initial state. See Allocator.Reset for details.
func (*SyncAllocator) StorageReport ¶
func (s *SyncAllocator) StorageReport() StorageReport
StorageReport returns a summary of the allocator's free space. See Allocator.StorageReport for details.
Source Files