{"id":"vikmanou/infarray","name":"infarray","scope":"vikmanou","platform":"roblox","description":"Bypass Luau's internal table size limitation of 2^26","version":"1.0.0","latest":"1.0.0","versions":["1.0.0"],"license":"MIT","licenseRating":"safe","licenseCaveats":[],"licenseVerified":true,"dependencies":{},"integrity":"590f3c3fc37b917597b0a788c446025381d4b0b99b26914e093660e50770f844","likes":0,"downloads":0,"install":"forest install vikmanou/infarray","url":"https://forest.dev/p/roblox/vikmanou/infarray","files":"https://api.forest.dev/ai/package/roblox/vikmanou/infarray/files","readme":"
\r\n\r\n# InfArray\r\n\r\n\"version\"\r\n\"luau\"\r\n\"license\"\r\n\"tests\"\r\n\r\n
\r\n\r\n> A Luau array that holds more than `2^26` elements by chunking the data across many backing tables. Indices stay valid up to `2^53` — the largest exact integer a Luau `number` can represent.\r\n\r\nInfArray exists because a single Luau table cannot grow past `2^26`\r\n(`67,108,864`) elements. It splits storage into fixed-size chunks and maps a\r\nglobal index onto `(chunkIndex, positionInChunk)` with integer math, so the array behaves like one contiguous sequence while never asking any individual table to exceed the engine's limit.\r\n\r\n```lua\r\nlocal InfArray = require(path.to.InfArray)\r\n\r\nlocal arr = InfArray.new()\r\nfor i = 1, 100_000_000 do -- 10^8 > 2^26: a native table errors here\r\n arr:PushBack(i)\r\nend\r\n\r\nprint(arr:Length(), arr:Count()) --> 100000000 100000000\r\n```\r\n\r\n---\r\n\r\n## What is InfArray?\r\n\r\nLuau's table upper bound seems to be `2^26`, defined in\r\nthe official [Luau source](https://github.com/luau-lang/luau/blob/master/VM/src/ltable.cpp#L36-L38):\r\n\r\n```cpp\r\n// Luau caps the array portion of a table at 2^MAXBITS\r\n#define MAXBITS 26\r\n#define MAXSIZE (1 << MAXBITS)\r\n```\r\n\r\nInfArray bypasses this.\r\n\r\n## How it works\r\n\r\nA global 1-based `index` maps to a chunk and a 1-based position inside it:\r\n\r\n```lua\r\nlocal LIMIT = 2 ^ 26 -- 67,108,864 elements per chunk\r\n\r\nlocal function locate(index)\r\n local i = index - 1\r\n local chunkIndex = i // LIMIT\r\n return chunkIndex + 1, i - chunkIndex * LIMIT + 1\r\nend\r\n```\r\n\r\nThe instance keeps four fields:\r\n\r\n| Field | Meaning |\r\n| ---------- | ------------------------------------------------------------- |\r\n| `_chunks` | Array of backing tables; each holds up to `LIMIT` elements. |\r\n| `_lens` | Per-chunk logical length (holes included). |\r\n| `_length` | Logical span of the whole array — the highest assigned index. |\r\n| `_count` | Number of present (non-`nil`) elements. |\r\n\r\nBecause removals leave `nil` holes, the code **never** relies on `#chunk` (which is undefined once a table has holes). Every length is tracked explicitly.\r\n\r\n### Two lengths\r\n\r\nAn InfArray tracks two distinct sizes:\r\n\r\n* **`Length()`** — the *logical span*: the highest assigned index, holes\r\n included.\r\n* **`Count()`** — the number of *present* (non-`nil`) elements.\r\n\r\nAfter `arr:RemoveIndex(i)` in the middle of the array, `Count()` drops by one but `Length()` is unchanged. The slot becomes a `nil` hole rather than shifting everything after it down (`O(1)` removal instead of `O(n)`).\r\n\r\n---\r\n\r\n## The core design tension: performance vs. ease of use\r\n\r\nThe hardest part of building InfArray was balancing **raw performance** against a **safe, ergonomic API**. Every safety convenience (nil-checking, count maintenance, hole-skipping) costs cycles on a hot path that runs billions of times in a workload.\r\n\r\nInfArray resolves this with a **two-tier API**:\r\n\r\n* **Safe tier** — `Get`, `Set`, `PushBack`, `RemoveIndex`, `Iterate`,\r\n `Transform`. \r\n* **Raw tier** — `GetChunk`, `SetChunk`, `IterateChunks`, `GetChunkAndPosition`, and the exported `InfArray.locate`.\r\n They are the fastest path for bulk work, but **you** are responsible for\r\n nil-checking and respecting per-chunk lengths.\r\n\r\n```lua\r\n-- Safe: pays a callback + hole-skip per element\r\narr:Iterate(function(index, value) ... end)\r\n\r\n-- Raw: fastest bulk throughput; you nil-check chunk[j] yourself\r\narr:IterateChunks(function(chunk, base, len)\r\n for j = 1, len do\r\n local v = chunk[j]\r\n if v ~= nil then\r\n -- global index is base + j\r\n end\r\n end\r\nend)\r\n```\r\n\r\nPick the tier per call site: reach for the raw tier only in the inner loops\r\nwhere the per-element overhead actually shows up in a profile.\r\n\r\n---\r\n\r\n## API\r\n\r\n`InfArray.new([size: number], [value: any])` creates a new instance. Think of it as `table.create`. See [Limitations](#limitations) for sizes beyond `2^24`.\r\n\r\n| Method | Description | Argument(s) | Returns | Time |\r\n| ---------------------- | --------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------- | ----------------------------- | ----------- |\r\n| `Get` | Value at a global index (`nil` if absent or out of range). | `index: number` | `any?` | `O(1)` |\r\n| `Set` | Overwrite an index inside an existing chunk. Does **not** allocate past the end — use `PushBack` to grow. Returns whether the write happened. | `index: number, value: any?` | `boolean` (`true` if written, `false` if no-op) | `O(1)` |\r\n| `PushBack` | Append a value to the end. | `value: any` | `index: number` (where it landed) | `O(1)` |\r\n| `RemoveIndex` | Clear an index, leaving a `nil` hole (does not shift; `Length` unchanged). | `index: number` | `nil` | `O(1)` |\r\n| `Count` | Number of present (non-`nil`) elements. | — | `number` | `O(1)` |\r\n| `Length` | Logical span: highest assigned index, holes included. | — | `number` | `O(1)` |\r\n| `Find` | First global index whose value equals `needle`. | `needle: any` | `number?` | `O(n)` |\r\n| `Iterate` | Visit present elements in order; return `true` from the callback to stop. | `callback: (index: number, value: any) -> boolean?` | `nil` | `O(n)` |\r\n| `IterateChunks` | Hand raw chunks to the caller for bulk work; caller nil-checks. Return `true` to stop. | `callback: (chunk: { any }, base: number, len: number) -> boolean?` | `nil` | `O(chunks)` |\r\n| `Transform` | Apply `updateFunc` over `[start, stop]` by `step`; maintains `Count`. | `start, stop, step: number, updateFunc: (index: number, value: any) -> any` | `nil` | `O(range)` |\r\n| `GetChunk` | The backing chunk table at a chunk index. | `chunkIndex: number` | `{ any }?` | `O(1)` |\r\n| `SetChunk` | Replace a whole chunk; pass `len` for sparse data (defaults to `#value`). | `chunkIndex: number, value: { any }, len: number?` | `nil` | `O(chunk)` |\r\n| `GetChunkAndPosition` | The chunk and 1-based local position for a global index. | `index: number` | `{ any }?, number` | `O(1)` |\r\n\r\nThe array also supports `#arr` (via `__len`, equals `Length()`) and\r\n`for index, value in arr` (via `__iter`, skips holes, but prefer\r\n`IterateChunks` for bulk throughput).\r\n\r\nAlso exported:\r\n\r\n* `InfArray.LIMIT` — elements per chunk (`2^26`).\r\n* `InfArray.locate(index)` — maps a global index to `chunkIndex, posInChunk`.\r\n\r\n###### *n is the number of elements.*\r\n\r\n### Legacy names\r\n\r\nThese older names remain as aliases for forward compatibility, but new code\r\nshould prefer the primary names above:\r\n\r\n`get` / `GetValueAtIndex` → `Get` · `set` / `Replace` → `Set` ·\r\n`InsertBack` → `PushBack` · `GetTotalLen` → `Count` · `GetLength` → `Length` ·\r\n`TransformRange` → `Transform`\r\n\r\n---\r\n\r\n## Installation\r\n\r\nInfArray is a single file: [`InfArray.luau`](InfArray.luau). Drop it into your\r\nproject and require it.\r\n\r\n---\r\n\r\n## Usage example\r\n\r\n```lua\r\nlocal InfArray = require(game.ReplicatedStorage.InfArray)\r\n\r\nlocal t = InfArray.new(10)\r\n\r\nlocal limit = 30\r\n\r\nprint(t:Count())\r\nprint(t:Get(5))\r\n\r\nlocal i = 0\r\nwhile i < limit do\r\n i += 1\r\n t:PushBack(i)\r\nend\r\n\r\nt:Iterate(function(index: number, value: any)\r\n print(index, value)\r\nend)\r\n\r\n-- Double every element in [1, t:Length()]\r\nt:Transform(1, t:Length(), 1, function(index, value)\r\n return value * 2\r\nend)\r\n\r\nprint(t:Find(8))\r\nprint(t:Count())\r\nprint(t:Get(5))\r\nt:Set(5, 'replace thing')\r\nprint(t:Get(5))\r\n```\r\n\r\nMore complete, real-world programs live in [`examples/`](examples/):\r\n\r\n* [`examples/DivisorsCountSieve.luau`](examples/DivisorsCountSieve.luau) — a sieve that records the number of divisors of every integer up to `n`, using `Transform` to accumulate prime-power contributions across an InfArray-backed table.\r\n* [`examples/TotientsToN.luau`](examples/TotientsToN.luau) — computes Euler's totient `φ(i)` for every `i` up to `n` with a nested `Transform` sieve.\r\n\r\n---\r\n\r\n## Benchmarks\r\n\r\nInfArray trades a little per-element speed for the ability to hold more than a\r\nsingle Luau table can. Every benchmark below stays *under* `2^26` so a regular table is a fair baseline. These measure the chunking overhead, **not** the cases where a native table can't compete.\r\n\r\nRun them yourself with [Lute](https://github.com/luau-lang/lute) on your PATH:\r\n\r\n```sh\r\nlute run benchmark/run.luau # print results\r\n```\r\n\r\nLatest numbers (`n = 4,194,304` (`2^22`); AMD Ryzen 9 9950X, Windows; machine-specific —\r\ntreat as relative ratios):\r\n\r\n| Workload | InfArray | Luau table | InfArray vs table |\r\n| --------------------------------- | ---------- | ---------- | ----------------- |\r\n| `PushBack` — append N | 48.4 ns | 8.0 ns | 6.07× slower |\r\n| `Set` — overwrite N in-range | 32.4 ns | 3.3 ns | 9.73× slower |\r\n| `Get` — sequential read | 26.8 ns | 3.3 ns | 8.08× slower |\r\n| `Get` — random-access read | 108.6 ns | 36.7 ns | 2.96× slower |\r\n| `Iterate` — visit every element | 13.7 ns | 2.6 ns | 5.38× slower |\r\n| `for .. in arr` (`__iter`) | 28.7 ns | 2.5 ns | 11.37× slower |\r\n| `Find` — linear search (needle at end) | 3.9 ns | 1.9 ns | 2.10× slower |\r\n\r\nSee [benchmark/README.md](benchmark/README.md) for full output, methodology and how to add your own cases.\r\n\r\n---\r\n\r\n## Testing\r\n\r\nTests live in [`tests/`](tests/) and use Lute's built-in test runner:\r\n\r\n```sh\r\nlute test\r\n```\r\n\r\n---\r\n\r\n## Limitations\r\n\r\n* **Built for arrays, not dictionaries.** InfArray is a sequence keyed by\r\n contiguous integer indices. There is no hashed-key storage.\r\n* **Slower per element than a native table.** Every access pays an extra chunk lookup. Use InfArray when you need capacity past `2^26`, not for small arrays that already fit.\r\n* **`Set` does not allocate new chunks.** It writes only inside a chunk that already exists, returning `true` when the write lands and `false` (a no-op) when the target index maps to an unallocated chunk. Within an existing chunk it *can* fill a hole past the current `Length()` and extend it; it just won't create the next chunk — use `PushBack`, `new(size)` or `SetChunk` for that.\r\n* **Removals leave holes.** `RemoveIndex` does not shift elements. The slot becomes `nil`. This keeps removal `O(1)`.\r\n* **Large pre-allocation is slow.** Initializing beyond `2^24` elements via\r\n `new(size, value)` may be significantly slower. This is due to Luau's `table.create` function taking longer for initializing larger counts (with `table.create(2^26)` taking ~0.5s).\r\n\r\n---\r\n\r\n## Further reading\r\n\r\nI wrote up the design decisions, the `2^26` limit, and the performance\r\ntrade-offs behind InfArray in a blog post:\r\n\r\n* **[The story behind InfArray](https://viken.games/blog/infarray)** — why a\r\n single Luau table caps out, how the chunking scheme works, and the\r\n performance-vs-ergonomics tension that brought the two-tier API.\r\n\r\n---\r\n\r\n— [@Vikmanou](https://github.com/Vikmanou)\r\n","readmeTruncated":false}