# Introduction

Recently, I’ve been exploring competitive programming with mathematics and realized that things get tough to compute with 64 bits (even 32). Because I had a specific library made in Lua, I decided to solve a specific problem through Luau to make things more simple. I soon realized that I’ve reached the maximum table element limit Luau supports. This value is `0b100000000000000000000000000` or more standardly known as 67108864 (or 2^26) elements.

The module allows you to keep track of values larger than the Roblox limit. This of course comes with some disadvantages (listed at the end).

This was also not made to be used in an actual game but rather for computing large stuff. If it is ever implemented in a game, I’d be curious to know how efficient it is and how time/memory is managed.

# API

### InfTable.new(tableType: ‘index’ | ‘dict’)

*Note: The default value for `tableType` is a dictionnary

### Methods

Method Name Description Argument(s) Return Value(s) Time Complexity
`GetChunk` Returns the chunk at the specified index. `chunkIndex: number` `{ any }?` `O(1)`
`SetChunk` Sets the chunk at the specified index `chunkIndex: number, value: { any }` `nil` `O(1)`
`GetTotalElementLen` Returns the amount of elements in the InfTable `nil` `number` `O(n)` or `O(m)`
`Iterate` Iterate through the InfTable `predicate: ((number, any, { any }) -> any?)` `predicateReturn: any?` `O(m)`
`Find` Goes through the table and finds this value `value: any` `indexInChunk: number?, indexInTable: number, chunkIndex: number?` `O(m)`
`GetValueAtIndex` Gets the value at specified index `index: any` `valueInChunk: any?, chunkIndex: number?, yourIndex: number?` `O(n)`
`Add` Add element to table `indexOrValue: any, value: any?` `nil` `O(n)`
`RemoveIndex` Remove index from table `index: any` `nil` `O(1)`
`Replace` Replace index in table `index: any, newValue: any` `nil` `O(1)`

# Usage

Usage for index based tables
``````local InfTable = require(game:GetService'ReplicatedStorage'.InfTable)

local t = InfTable.new('index')

local limit = 30

local i = 0
while i < limit do
i += 1
end

t:Iterate(function(index: number, value: any, chunk: { any }): boolean
if value == 4 then
return true
end
end)

print(t:Find(8))
print(t:GetTotalElementLen())
print(t:GetValueAtIndex(5))
t:Replace(5, 'replace thing')
print(t:GetValueAtIndex(5))
``````
Usage for index & value based tables (dictionnary/map)
``````local InfTable = require(game:GetService'ReplicatedStorage'.InfTable)

local t = InfTable.new('dict')

local limit = 500

local i = 0
while i < limit do
i += 1
end

print(t:GetTotalElementLen())
if t:GetValueAtIndex('a') then
print('a was found')
t:Replace('a', 'replace thing')
end
print(t:GetValueAtIndex('a'))
``````
``````local HttpService = game:GetService('HttpService')
local InfTable = require(game:GetService'ReplicatedStorage'.InfTable)

local t = InfTable.new('dict')

local limit = 500

local i = 0
while i < limit do
i += 1
end

local predicateAnswer = t:Iterate(function(index: number, value: any, chunk: { any }): boolean
if value*10 > 9.8 then
return index
end
end)

print(t:GetTotalElementLen())
``````

# Limitations

• You can not have mixed tables.
• Keys for dictionaries may duplicate (to fix maybe)
• Compatibility problem with functions that table in tables as argument (to fix soon)
• Less performant than the actual implementation of tables

Fun fact: Reaching 2^26 elements in a table takes under 1 second if you insert them strategically (and this is without using `table.create`). The same approach would take almost 15 seconds with InfTable.

# Source

Expand for source code
``````--[[

InfTable.lua
uhi_o

A module used to store table larger than Roblox Luau's (or C's) table limit

Example:

local tableName = InfTable.new('index')

-- populate the table
local i, limit = 0, 30
while i < limit do
i += 1
end

t:Iterate(function(index: number, value: any, chunk: { any }): boolean
if value == 4 then
print('a', index)
return true
end
end)

print(t:GetValueAtIndex(5))
t:RemoveIndex(5)
print(t:GetValueAtIndex(5))

--

]]

local LIMIT = bit32.lshift(1, 26) -- Luau source code (ltable.cpp): #define MAXBITS 26 #define MAXSIZE (1 << MAXBITS)

export type InfTableObject = {
_type: string?,
_chunks: { { any } },

GetChunk: (number) -> { any }?,
SetChunk: (number, { any? }) -> (),
GetTotalElementLen: () -> (),
Iterate: ((number, any, { any }) -> any) -> (any?),
Find: (any) -> (number?, number, number?),
GetValueAtIndex: (number) -> (any?, number?, number?),
Replace: (number, any) -> ()
}

local module = {} :: { new: (string?) -> InfTableObject }

local function countInDict(dict: { [any]: any }): number
local res = 0
for _ in pairs(dict) do
res += 1
end
return res
end

function module.new(tableType: 'index' | 'dict')
local InfTable = {
_type = tableType or 'dict', -- assuming it is a dictionnary as default
_chunks = {}
}

function InfTable:GetChunk(index: number)
return self._chunks[index]
end

function InfTable:SetChunk(chunk, value)
self._chunks[chunk] = value
end

function InfTable:GetTotalElementLen()
local i, res = 1, 0

while self._chunks[i] ~= nil do
res += self._type == 'index' and #self._chunks[i] or countInDict(self._chunks[i])
i += 1
end

return res
end

function InfTable:Iterate(predicate)
local finish = false

local i = 1
while self._chunks[i] and not finish do
local chunk = self._chunks[i]

if self._type == 'index' then
for j = 1, #chunk do
local predicateAnswer = predicate(j, chunk[j], chunk)
end
end
else
for k, v in pairs(chunk) do
local predicateAnswer = predicate(k, v, chunk)
end
end
end

i += 1
end
end

function InfTable:Find(value)
local i, items = 1, 0
while self._chunks[i] do
local chunk = self._chunks[i]
local chunkLen

if self._type == 'index' then
chunkLen = #chunk
for j = 1, chunkLen do
if chunk[j] == value then return j, items+j, i end
end
else
chunkLen = countInDict(chunk)
for k, v in pairs(chunk) do
if v == value then return k, items+k, i end
end
end

i += 1
items += chunkLen
end
end

function InfTable:GetValueAtIndex(index)
local i, items = 1, 0
while self._chunks[i] do
local chunk = self._chunks[i]
local chunkLen

if self._type == 'index' then
chunkLen = #chunk
if items+chunkLen >= index then
return chunk[index-items], i, index-items
end
else
chunkLen = countInDict(chunk)
if chunk[index] then return chunk[index], i, index end
end

items += chunkLen
i += 1
end
end

if indexOrValue == nil then
return warn('InfTable -> Can not insert nil for index nor value')
end

local cost = 1

local i = 0
while true do
i += 1

local chunk = self._chunks[i]
if not chunk then
if self._type == 'index' then self._chunks[i] = { indexOrValue }
else self._chunks[i] = { [indexOrValue] = value }
end

break
end

-- No space in this chunk
local chunkLen = self._type == 'index' and #chunk or countInDict(chunk)
if LIMIT - chunkLen <= cost then continue end

if self._type == 'index' then table.insert(chunk, indexOrValue) print('ins')
else chunk[indexOrValue] = value
end

break
end
end

function InfTable:RemoveIndex(index)
if index == nil then
return warn('InfTable -> Unknown index to remove')
end

local value, chunkn, chunkIndex = self:GetValueAtIndex(index)
if not value then return end

local chunk = self._chunks[chunkn]
if not chunk then return end

chunk[self._type == 'index' and chunkIndex or index] = nil

if next(chunk) == nil or countInDict(chunk) == 0 then
self._chunks[chunkn] = nil

-- Push down subsequent chunks to fill the whole
local n = 1
while self._chunks[chunkn+n] do
local chunk = self._chunks[chunkn+n]

-- Move chunk down
self._chunks[chunkn+n-1] = chunk
self._chunks[chunkn+n] = nil

n += 1
end
elseif self._type == 'index' then
-- fill in empty gaps in table
for i = chunkIndex, #chunk do
chunk[i] = chunk[i+1]
end
end
end

function InfTable:Replace(index, newValue)
if newValue == nil then
return self:RemoveIndex(index)
end

local value, chunkn, chunkIndex = self:GetValueAtIndex(index)
if not value then return end

local chunk = self._chunks[chunkn]
if not chunk then return end

chunk[chunkIndex] = newValue
end

return InfTable :: InfTableObject
end

return module
``````
9 Likes

I’m sure I’ll use this eventually. Great work

2 Likes

but for what, I am just curious why someone would need to go over the limit of tables on lua, its gigantic, so like it really scares me for what type of work things like going over the table limit are.

2 Likes

Obviously I doubt this will ever be used in any serious/long-term project that plans to be public. But perhaps for a solo sandbox or just messing around etc…

You’re right, I’m also really insanely curious why people would need this for an actual project. This might make me sound like I just made a useless resource.

I know that boatbomber has made an Infinite Datastore which uses the same concept as my InfTable. This makes more sense to be used for a real project.

Here are a few reasons why you might want to use this module:

• Store a massive amount of logs for the server and when moderators or devs join they could view the whole history and not have any loss due to limitations. 67.108 million logs does seem like a lot, but it would be convenient if it could all be stored together so that example the developer, moderator, analyst and more can have their data there.

• Some algorithms require you to store almost n^2 amount of data. I can’t remember their names but I do know for that there are. Some table relationship handling would certainly take extra space, and sometimes more than the input length. (Some algorithms that work with bit manipulation might store data in multiples of 4 bits. This is not usually expressed in O(n * 4) terms but could be considered in the context of bit-level manipulation.)

• Recently AI has been coming into Roblox games which probably means that they are training their network using the Roblox server (I’m really unsure about this). Training complex machine learning models with vast amounts of data may require exceeding this limit. Especially in deep learning and reinforcement learning scenarios where a massive amount of data efficiently improves the learning model.

• Requesting JSON from a database and receiving a really large string. This data has to go somewhere and the module helps you split it efficiently. There doesn’t seem to be a limit to how much we can receive through a `HttpService:Get` as long as Roblox servers can handle it. The max string length of C++ is 2^32 (or 4,294,967,295) characters although I’m not sure if this applies to Luau. I haven’t checked, but you’d probably run out of memory before reaching that amount.

• Making a system similar to the PC’s memory. A string would probably be more fun though.

The main reason why somebody would actually want to use this (from what I know and do), is to experiment and research. Essentially what you said @skelworks, yes.

It doesn’t seem like Roblox is the right platform for this, but I have hope.

1 Like

Btw I wasn’t calling your resource useless, I was just curious as to what type of systems would need this sort of work I guess AI training data sounds like the most popular

1 Like

hot module!!!

1 Like

Off-topic but how’d you make the chart

1 Like

Don’t worry, here’s the Markdown for my chart. I remember grabbing it off a github repo which used this style.

``````| Method Name | Description | Argument(s) | Return Value(s) | Time Complexity
| ----------- | ---------- | ------------- | ------------ | --- |
| `GetChunk` | Returns the chunk at the specified index. | `chunkIndex: number` | `{ any }?` | `O(1)`
| `SetChunk` | Sets the chunk at the specified index | `chunkIndex: number, value: { any }` | `nil` | `O(1)`
``````

Example:

``````| Title1 | Title 2 | Title 3
| - | - | - |
| Info1 | Info2 | Info3
| Info1 | Info2 | Info3
``````
Title1 Title 2 Title 3
Info1 Info2 Info3
Info1 Info2 Info3

Here’s a nice reference for more regarding Markdown

1 Like