Sandboxed table system -- Add custom methods to table

What is it?

The sandboxed table system is a little something I designed for my game personally since I’ve found myself in excess need of a few extra methods in the table table provided by Roblox. I make extensive use of this in my own game, but given the versatility it offers, I’ve decided to release it to the public. This was inspired by @TheGamer101’s custom enum system, so kudos to him for kind of getting this idea started! (Here’s my own rewrite of it, for those who want it: https://www.roblox.com/library/3966022155/Custom-Enum-System. At the time of writing, I find myself unable to track down the original.)


What does it have to offer?

Right now, the sandboxed table system offers these new methods:

boolean table.contains(table tbl, Variant obj)

Returns true if the table contains obj, and false if it does not. Searches via calling table.indexOf(tbl, obj) and returns if the data is non-nil.
n.b. table.find is NOT identical to this, as table.find only works on arrays, not lookups (tables)

Variant table.indexOf(table tbl, Variant obj)

A hybrid utility method that first attempts to find obj via table.find(tbl, obj). If table.find cannot locate the value, it searches via table.keyOf (see below).

Variant table.keyOf(table tbl, Variant obj)

Returns the index of obj if it is present in the table, or nil if it is not in the table. This searches using pairs, so it supports custom indices. If your table is structured like an array, use table.find() which comes with Roblox’s new luau VM.

table table.skip(table tbl, int n)

Skips n values in tbl and returns a new table starting from n + 1 to the end of the table. This only works on ordinal tables (arrays).

table table.take(table tbl, int n)

Takes n values from the start of tbl and returns a new table containing only those values. This only works on ordinal tables (arrays).

table table.skipAndTake(table tbl, int skip, int take)

An alias with ever-so-slightly better performance that merges a skip and take operation into one call (so rather than doing table.take(table.skip(MyArray, 4), 2), you just do table.skipAndTake(MyArray, 4, 2).

Variant table.random(table tbl)

Selects a random entry out of tbl using Roblox’s Random class (rather than math.random). This only works on ordinal tables (arrays).

table table.join(table tbl0, table tbl1)

Merges the contents of tbl0 and tbl1 in order. This only works on ordinal tables (arrays).


What do you think should be added or changed? Let me know! Let’s get this module up to its maximum potential.

16 Likes

table.find actually went live recently, which should cover most of your use cases:

2 Likes

Right you are! Whoops.

I did just get the idea of adding skip and take, so I might get to adding those quickly so that this has some use cases to it! :stuck_out_tongue:

Edit: Seems find only supports numeric indices and not custom indices, so I’ll be keeping the methods I have.

1 Like

I’ve never done anything concerning tables so far, but I’m sure I’ll find a use for this soon!
I’m always excited whenever someone adds stuff here

Very cool! My only complaint is keyOf could be using hashtables to significantly speed up processing after first use.

Currently you have this:

Table.keyOf = function (tbl, value)
	for index, obj in pairs(tbl) do
		if obj == value then
			return index
		end
	end
	return nil
end

However you could be using something along the lines of this and be seeing a drop from O(n) for each call to O(n) for the first call and O(1) per proceeding call to the same index.

Table.__cache = {} -- Cache for table
Table.__cache.keyOf = setmetatable({}, {__mode="v"}) -- Cache for table.keyOF
Table.keyOf = function (tbl, value)
	Table.__cache.keyOf[tbl] = Table.__cache.keyOf[tbl] or setmetatable(table.create(#tbl), {__mode = "kv"}) -- Retrieve cache for tbl or create it	
	-- Notice use of the __mode metatable. This will prevent the cache from holding any references thus allowing GCing to occur.

	local cache = Table.__cache.keyOf[tbl][value] -- Retrieve cached index
	if cache ~= nil then -- Check if cached
		if tbl[cache] == value then -- Value is correct
			return cache -- Return cached index
		else -- Value is incorrect
			Table.__cache.keyOf[tbl][value] = nil -- Clear entry
		end
	end

	for index, obj in pairs(tbl) do
		Table.__cache.keyOf[tbl][obj] = index -- Store cached index for each value
		if obj == value then
			return index
		end
	end
end

This might be a bit nitpicky I suppose but I’m obsessed with the performance of my scripts considering I do a lot of would-be CPU heavy code in Heartbeat and Stepped and I like to watch more microseconds go into printing debug info than actually running the code. (But in all seriousness hashtables are amazing performance savers because of their ability to near instantaneously pull information from a table and I know there are people who like to have maximum performance)

2 Likes

You’re the best around
nothing’s gonna ever keep you down

Instead of

table = require(script.Parent.Table)

Why not use this instead to silence the warning with the additional benefits of elegant clean code.

(add to also confuse newbies :smiling_imp:)

return function()
	local env = getfenv(0)
	-- table
	env.table = setmetatable(Table,table)

	setfenv(0, env)
end
1 Like

Probably because any use of getfenv kills some of Luau’s optimizations and it doesn’t really improve the code.

2 Likes

This would not benefit performance as much as you think, and can result in a memory leak if you’re not careful. Allocating a cache is quite expensive, and would be slower for many small unique tables. Instead of addressing complexity in keyOf, consider different solutions for performance-critical code.
Remember to always test optimizations with real input data to make sure that it’s actually faster. You can get rough benchmarks by using tick; I could be wrong for your case :man_shrugging:

Exactly this. I would not recommend overriding the table global either, although doing so would only de-optimize table API members as far as I’m aware.

3 Likes

The above method of caching should only invoke a performance cost once for the first usage on a given table. The value can immediately be returned for the previous cost plus extra caching or you could precache the full table once which would invoke a large performance cost once per table. It actually might make more sense to use a threshold for this “aggressive” caching e.g. 1000 length tables will stop caching. (Can be checked in the loop)

First of all, your code will result in a memory leak because Table.__cache.keyOf isn’t weak via __mode = "v" (the cache will stick around forever).

Secondly, if performance is your goal, Table.__cache.keyOf should be accessed using an upvalue; You are doing multiple table lookups just to access this cache during initialization.

And finally, your code re-initializes if no value is found, making it extremely slow in that case. The only case where your code would be faster, is when the table is massive, the table doesn’t need to be garbage collected, you are certain the value exists, and the function is called many times on the same table; This is a very rare set of conditions for a generic library function.

1 Like

Fair enough. I did miss a weak table (which is fixed now). I also changed the code to less aggressively cache which means it should run just as fast as the original under normal conditions. This means only invalid indexes should cause a recache and the whole table is not recached (matching the previous code format).

Your table.skip and table.take could take advantage of the new table.create and backported table.move functions.

Table.skip = function(tbl,n)
	local new = {}
	for i=1,#tbl-n do
		new[i] = tbl[i+n]
	end
	return new
end

Could become

function Table.skip(tbl,n)
    local length = #tbl
    return table.move(tbl,n+1,length,1,table.create(length-n))
end

and

Table.take = function(tbl,n)
	local new = {}
	for i=1,n do
		new[i] = tbl[i]
	end
	return new
end

could become

function Table.take(tbl,n)
    return table.move(tbl,1,n,1,table.create(n))
end

Also, a table.retrieve function

function Table.retrieve(tbl,i,j)
    return table.move(tbl,i,j,1,table.create(j-i+1))
end

Edit:

Perhaps could use some more metatables for the return table.

return setmetatable({},{
    __index = setmetatable(Table,{
        __index = RobloxTable
    }),
    __newindex = function()
        error("Add new table entries by editing the Module itself.",2)
    end
})
4 Likes

Here’s another one for speedy code tricks.

--[[**
	Like table.remove, but faster. I think it's O(1) versus O(n), but I'm not sure.

	@param [t:array] Array The array you are removing from.
	@param [t:integer] Index The index you want to remove.
**--]]
function Utility.FastRemove(Array, Index)
	local Length = #Array
	Array[Index] = Array[Length]
	Array[Length] = nil
end

@Crazyman32 created (?) this function originally, so credit to him.

1 Like

Those table.create functions are mad fast.
image
image

Just thought of another way to do it.

function Table.skip(tbl,n)
    return {table.unpack(tbl,n+1)}
end
function Table.take(tbl,n)
    return {table.unpack(tbl,1,n)}
end
function Table.retrieve(tbl,i,j)
    return {table.unpack(tbl,i,j)}
end

I’ve appended these changes in the latest version, credit given!

I did rename table.retrieve to table.range (I felt the name was more fitting) and gave it more descriptive parameter names.

I also added table.skipAndTake(tbl, skip, take) which is an alias that takes the elements from skip + 1 up until skip + take. This means that table.take(table.skip(MyArray2, 4), 2) and table.skipAndTake(MyArray2, 4, 2) both have the same result, except skipAndTake is more optimized because it calls table.move once whereas the old method calls it twice.

You partially negate the entire purpose of fast remove when putting it in a utility library. It’s still much faster for large tables, but I recommend just writing it inline.

That code will error if the table is longer than 7997

2 Likes

This is amazing! Great work, I can definitely see a use for this in a future project. Thanks for open sourcing your code for everyone to see!

1 Like

I’ve just added the function table.random(table tbl) which selects a random entry out of the specified table so long as it’s an array. Should get rid of those pesky local selection = myTable[math.random(1, #myTable)] lines.

I do write it inline for the most part. It’s still faster even when in the Utility library. O(1) is much better than O(n).

2 Likes