Collections - Data structures for Luau

Started: 2026-06-30 | Last major update: 2026-07-02 | Last updated: 2026-10-22

Optimized data structures for Luau.

Status

area	state
Lute	tested
dependencies	none
benchmarks	not public until prms_magnet/bench releases
tests

Tested with Lute 1.0.1-nightly.20260729 through Luau Run.

Requires Luau’s buffer library.

Install

Add this to pesde.toml and run pesde install:

[dependencies]
Collections = { name = "prms_magnet/collections", version = "^0.1.0" }

Quick start

Packages is wherever your project puts pesde’s roblox_packages.

local Collections = require(Packages.Collections)

local Enemies = Collections.SlotMap.new()
local Goblin = Enemies:Insert("goblin")
Enemies:Remove(Goblin)
local Orc = Enemies:Insert("orc") -- Takes the goblin's slot, with a new generation
print(Enemies:Get(Goblin), Enemies:Get(Orc)) -- nil orc
print(Collections.UnpackHandle(Orc)) -- 1 1 (slot, generation)

local Queue = Collections.MinHeap.new({})
Queue:Push(5, 50)
Queue:Push(2, 20)
print(Queue:Pop()) -- 2 20

For hot loops, Bitmap:Raw(), GrowableBuffer:Raw(), SparseSet:RawDense() and SlotMap:RawValues() return the storage itself.

Structures

Structure	What it is
SlotMap	Values stored under handles. A handle to a removed value reads nil, even after its slot is reused.
SlotAllocator	The same handles as SlotMap, without the values, for data kept in your own arrays.
SparseSet	A set of integer ids, packed so it iterates without gaps.
StampSet	A set of integers below a fixed size, cleared in O(1).
Bitmap	A fixed number of on/off bits.
GrowableBuffer	A list of numbers of one type, U8 to F64, that grows as you push.
Ring	A first-in, first-out queue of a fixed size.
MinHeap	A priority queue that pops the smallest key first.
BucketQueue	A priority queue for whole-number priorities that stay close together, such as path-finding costs.
Interner	A two-way map between strings and numbers, one number per distinct string.
Registry	Values stored by name, with a setting for what registering a name twice does.

Collections.PackHandle and Collections.UnpackHandle build and split the handles that SlotMap and SlotAllocator return.

How they work covers what each structure keeps in memory and what its operations cost.

Limitations

new checks its config, and a Push or Insert that cannot store its value raises an error and changes nothing. The rules below are not checked, for speed.

SparseSet ids start at 1. An empty set says it holds id 0, and removing id 0 from a set that holds ids corrupts it.

BucketQueue priorities must fit in a window Span wide. The window starts at the lowest priority in the queue, or at the last one popped since the queue was empty if that is lower. A priority past the window makes pops come out in the wrong order, with no error. Use MinHeap if you cannot promise that.

MinHeap and BucketQueue values are u32. A value outside 0 to 4,294,967,295 wraps, with no error. Handles from SlotMap and SlotAllocator can be larger than that, so push an index into your own array of handles instead.

Ring:Drain’s callback must not change the ring. Pushing, popping or clearing the ring inside the callback loses or repeats entries. If the callback raises, Clear a "Table" ring before using it again: it still counts every entry, but the ones already passed read nil.

A SlotMap backend that acts as u32 is used as u32. At new, the map tests a backend with a Stride of 4 on five 32-bit words. If the backend stores them exactly as buffer.writeu32 and buffer.readu32 do, the map calls those two directly from then on. Anything else your backend does, such as rounding, checking or a default, never runs.

Registry keys must not be its method names. A key of Register, Unregister, Get, Has, List, Each, Clear or Seed replaces that method on the registry.

StampSet and Bitmap indexes are whole numbers. A NaN index raises an error, and a fractional index in a StampSet corrupts the integers next to it.

Tests

Each structure has example tests and a fuzz test. The fuzz test runs random operations on the structure and on a plain-table model of it, and fails when the two differ. The fuzz tests use TestKit.

With pesde and Luau Run installed:

pesde install   # fetches TestKit
luau-run test   # runs every test on Lute

License

MIT

AI Policy