prms_magnet/collections
Optimized data structures for Luau
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 20For 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