What if arrays could hold infinite values?

Why I made a module that can store an infinite amount of values in a "table"

Back in 2023, my professor introduced me to Project Euler. It's a site with a long list of mathematical/computational problems that get progressively nastier. It wasn't part of the curriculum, it was a supplementary thing he handed me because I was ahead of my peers.

At the time my programming knowledge was limited to Luau, Python and JavaScript. I got maybe a dozen problems in before realizing that brute force stops working almost immediately and that I'd actually have to study. That's when I started properly learning data structures and algorithms, and picked up C++ (plus a few other languages) specifically to solve these.

After around 30 problems, I asked myself the obvious question: why don't I just do this in Luau? It's the language I write every day. So I opened problem 187, allocated the sieve I needed, and hit an error I had genuinely never seen before: table overflow.

There's a ceiling on Luau tables

I did not know tables had a size limit. I always assumed you ran out of RAM and that was that.

So I went digging through the Luau source, and it's right there in ltable.cpp:

// max size of both array and hash part is 2^MAXBITS
#define MAXBITS 26
#define MAXSIZE (1 << MAXBITS)

2^26 is 67,108,864 elements. That's the hard cap on the array portion of a single table. It isn't a memory thing, it's structural. The VM packs size information into a fixed number of bits, so 26 is simply where it stops.

And problem 187 asks for composites below 10^8 with exactly two prime factors. 10^8 is 100,000,000. The sieve you need is about 1.5× larger than the biggest table Luau will give you. There's no clever rewrite around it either, the algorithm is a sieve.

This wasn't fun. I gave up on doing Project Euler in Luau.

Stealing an idea from DataStores

A while later I remembered an open source module I'd come across in boatbomber's gists: InfStore. DataStores have a hard cap on value size per key, and InfStore gets around it by chunking one logical value across multiple keys. You read and write as if it were one blob and the splitting happens underneath.

I thought that was genius, and the shape of the problem is identical. A hard per-container cap, and a caller who just wants one continuous thing. So I applied the same concept to tables.

My first prototype was called InfTable and supported both arrays and dictionaries. It worked. It was also awful. Every operation went through a pile of branching to figure out which mode it was in and dictionary keys don't chunk cleanly because there's no natural order to slice along. I shelved it for about a year.

When I came back to Project Euler, I rewrote my module from scratch and cut dictionaries entirely. Arrays only. That one decision is responsible for basically all of the performance, because once every key is a contiguous integer, locating a value is pure arithmetic instead of a lookup. That rewrite became InfArray.

Version 1: just chunk it

The first version was as simple as it gets. Instead of one giant array, InfArray keeps a list of chunks, where each chunk is a normal Luau table holding up to 2^26 elements. When one fills up, the next one is created.

Since the chunk list is itself a table capped at 2^26 entries, the theoretical ceiling is 2^52 elements. In practice the real limit is 2^53, which is the largest integer a Luau number can represent exactly. Past that, index math silently stops being correct, so that's where I draw the line.

The entire trick is turning a global index into "which chunk, and where in it":

local LIMIT = 2 ^ 26 -- elements per chunk

local function locateWithIndex(index: number): (number, number)
	local i = index - 1
	local chunkIndex = i // LIMIT
	return chunkIndex + 1, i - chunkIndex * LIMIT + 1
end

function InfArray.Get(self: InfArray, index: number): any?
	local chunkIndex, pos = locateWithIndex(index)
	local chunk = self._chunks[chunkIndex]
	return chunk and chunk[pos]
end

That's the whole data structure. Everything after this point is me finding out where it breaks and fixing it.

Never trust #

The first thing that bit me was removal.

RemoveIndex doesn't shift anything. It writes nil into the slot and leaves a hole. Shifting would be O(n) and would mean touching every chunk after the removal.

But the moment a table has holes, the length operator # becomes undefined. Not wrong in a predictable way, undefined. Luau does a binary search over the array part and can hand you any boundary it finds. So InfArray never calls # on a chunk. It tracks lengths by hand within a private property.

Which is why there are two different length concepts:

Push 10 values, remove index 3 and you get Length() == 10 but Count() == 9.

Two tiers of API

Once it worked, I started actually using it, and the safe methods were too slow for sieves. They nil-check and skip holes for you but it costs a branch per element, and when you're iterating 100 million values that branch is the entire cost of the loop.

So I added a raw tier that hands you the backing tables directly and makes the nil-checking your problem:

arr:IterateChunks(function(chunk, base, len)
	for j = 1, len do
		local v = chunk[j]
		if v ~= nil then
			-- base + j is the global index
		end
	end
end)

You get a plain Luau table and a plain numeric loop, which is exactly what the VM optimizes best. GetChunk, SetChunk and GetChunkAndPosition exist for the same reason. SetChunk in particular is the fast path for bulk population, since you build a normal table however you like and hand the whole thing over in one call.

Preallocation

New chunks are created with table.create(APPEND_PREALLOC) where the prealloc is 2^16, not the full 2^26. Allocating 67 million slots the instant you append your first value would be costy. To my surprise, Roblox freezes and lags for ~2 seconds when running table.create(2^26). I haven't looked much into why it does this though.

Transform

The operation I actually needed for Project Euler. The sieve visits every multiple of p and updates it. Doing that through Set means recomputing the chunk location on every single step.

Transform(start, stop, step, fn) resolves the chunk once per chunk, then runs a tight local loop inside it before advancing:

return function(n: number): InfArray.InfArray
	local sieve = InfArray.new(n, 0)

	for p = 2, n do
		if sieve:Get(p) ~= 0 then continue end

		sieve:Transform(p, n, p, function(mult, currentValue)
			return currentValue + primeCount(mult, p)
		end)
	end

	return sieve
end

At this point InfArray did everything I needed. The next two steps were about making it faster.

Version 2: micro optimizations and the _dense flag

I went through the Luau performance docs and benchmarked every change before and after. Two things came out of it.

Inlining. locateWithIndex was called on every Get, Set and PushBack. A function call is cheap, but not free when it runs millions of times. So I wrote the arithmetic out directly in each method and deleted the helper. Same idea with self._chunks and self._lens: read them into locals once instead of indexing self inside a loop.

A "no holes" flag. Luau has table.find, which is a fastcall into C and much faster than looping in Luau. The catch is it stops at the first nil:

local t = {100, 200, 300, nil, 500, 600, 700}

table.find(t, 300) --> 3
table.find(t, 700) --> nil, the hole hides everything after it

So I added _dense, one boolean per chunk that says "this chunk has no holes". If it's true, Find uses table.find and Iterate skips the nil check. If not, it falls back to the old loop.

I also tried a per-chunk counter instead of a boolean, but it needed an extra write on every PushBack and cost a consistent 7% there. The flag doesn't touch the append path at all.

Measured on my laptop (i5-10310U, n = 2^22):

Find got 2.4× faster and actually edged out a regular Luau table.

Version 3: tombstones

The problem with _dense is that it's an edge case. One removal in a 67 million element chunk turns the fast path off for the whole chunk. And it never comes back, even if you fill the hole again. A sieve removes stuff constantly, so in practice most chunks would end up on the slow path.

So instead of asking "how do I track holes", I asked "what if there are no holes?".

This is a known trick in other languages. CPython's dictionaries, Android's SparseArray and Rust's hashbrown all do it: when you delete something, you don't clear the slot, you write a special marker called a tombstone. InfArray now does the same thing with a private EMPTY value:

local EMPTY = table.freeze({})

function InfArray.Get(self: InfArray, index: number): any?
	local i = index - 1
	local chunkIndex = i // LIMIT
	local chunk = self._chunks[chunkIndex + 1]
	if chunk == nil then return nil end

	local value = chunk[i - chunkIndex * LIMIT + 1]
	if value == EMPTY then return nil end
	return value
end

From Luau's point of view, a chunk is now always a full array with no nil in it. So:

• Find is always one table.find call per chunk. No flag, no fallback.
• Slots never drift into the table's hash part, so random access stays fast.
• _dense became _holes, a count of tombstones per chunk. Unlike the boolean, it recovers when a hole is refilled, and Iterate still uses it to skip the check on chunks with zero holes.

# still isn't trustworthy by the way. Chunks are preallocated past their real length, so the manual length tracking stays.

The one cost is the extra compare in Get. At first it was 19% slower, which surprised me. Turns out it was the way I wrote it. return if value == EMPTY then nil else value was the slow part, and switching to a plain if ... then return nil end made it identical to before. PushBack ended up about 4% slower, which is fine for what it buys:

Find no longer cares how many holes there are.

I also looked at structures that keep the array permanently packed, like a slot map or Rust's swap_remove. They all need an extra layer that maps your index to where the value really lives. That breaks the entire point of InfArray, since in a sieve the index is the number.

EMPTY or nil?

This did make the API a little confusing. When do you compare against EMPTY and when against nil? The rule ended up being simple: use EMPTY only when you index a chunk table yourself, everywhere else use nil.

Only GetChunk, GetChunkAndPosition and IterateChunks give you a raw chunk. If you never call them, you never see EMPTY. So the raw loop from earlier becomes:

arr:IterateChunks(function(chunk, base, len)
	for j = 1, len do
		local v = chunk[j]
		if v ~= InfArray.EMPTY then
			-- base + j is the global index
		end
	end
end)

Benchmarks

Measured at n = 4,194,304 (2^22) elements on an AMD Ryzen 9 9950X (Windows). Every workload stays under 2^26 on purpose, so a regular table is a fair baseline. These numbers measure the chunking overhead, not the cases where a native table can't compete at all.

The suite is in the repo, so you can run it yourself with lute run benchmark/run.luau:

Ratios aren't fixed, they shift with the hardware. On a slower CPU the gap narrows, because the native baseline degrades while InfArray's overhead stays constant. So don't treat any of these multipliers as a constant cost.

When you should actually use this

Honestly? Most of the time, don't.

If your data fits in 2^26 elements, a native table wins on every axis and there is no argument to be made. InfArray will always be slower per element, because it does index math and a chunk lookup that a native table simply doesn't have to do. There's no version of this where chunking is free.

It's worth reaching for when:

• You genuinely exceed 2^26 elements. Sieves, offline number-crunching, big precomputed tables. This is the only reason the module exists.
• You're near the limit and don't want to find out in production.
• You want stable O(1) removals without shifting.

And it's the wrong tool when you need a dictionary, when you need ordered/dense data after removals, or when you were reaching for it as an optimization. It is a capacity trade, not a speed one.

Back to problem 187

The sieve runs. It takes a while and C++ would eat it for breakfast, but it runs in Luau which was the entire point. (It took 1859.5 seconds to execute in studio)

Source and docs are on GitHub.