Extend bulk table manipulation (E.g. table.resize & table.fill)

As a Roblox developer, it is currently still too hard to do performant bulk manipulation of tables.

If Roblox is able to address this issue, it would improve my development experience because it would allow for complex table manipulation to be done performantly.

The WebAssembly spec has examples of these operations using similar terminology to Roblox. The only difference here is that WebAssembly doesn’t automatically resize tables for you, but all of a program’s use cases for these operations still exist in lua and on Roblox in many places.
https://webassembly.github.io/spec/core/exec/instructions.html#xref-syntax-instructions-syntax-instr-table-mathsf-table-grow-x

Being able to resize (grow/shrink) tables & fill values into them would complete Roblox’s set of table manipulation functions. Roblox has table.create (functionally equivalent to table.init on wasm spec), and table.move (functionally equivalent to table.copy on wasm spec), however, Roblox does not have a way to fill into or resize the array parts of tables, which, are both operations that are very important in many programs.

Additionally, its important for me to point out why these operations are needed in place of letting Roblox/luau handle it. Tl;dr, for the same and similar reasons that table.create & table.clear are needed and were implemented, a way to resize and fill tables is also needed.

(This explanation is extremely long and not fully relevant to the request)

Firstly, iirc the way that Roblox resizes tables is by allocating to the next power of two when needed, and, this is okay in most cases, but for the same reason that table.create greatly assists with the performance and memory cost of tables when used correctly, the ability to resize tables would too.

Say you have a large set of objects you’re tracking. Maybe you’re doing inverse kinematics, or stepping entities, etc.

You may have 10 objects you’re tracking in the world. But now let’s say you have a list of 1000 objects you created, maybe a player just joined and you’re loading their base that has a lot of objects in it. You could insert them one by one and face the costs of the extra allocations, or you could allocate a new table for 1010 objects, temporarily using extra memory and providing more work for the garbage collector. The ability to resize a table in this case would perfectly solve this issue, just like table.create does.

Additionally, in the case that those 1000 objects are removed, for example, let’s say a player has a base with many objects you are tracking, and they leave, and you want to delete those tracked objects, now you are stuck in the same dilemma that resizing tables would resolve.

As for table filling, table.clear functions similarly to a fill. For example, table.fill(tab, 1, #tab, nil) would function almost identically (if it were a thing). But, there’s no way to specify the value or range to be filled in that case, and while nil may be lua’s version of nothing, that might not be the version of nothing you need. Or, perhaps you just know you need to fill a large range with the same value, for example, a compression algorithm might take advantage of table filling in Roblox.

A fill operation in lua, which knows how many values its updating can also limit any allocations that would need to be applied to do that fill. For example, table.fill({}, 1, 1000, 0) could function very similarly to table.create(1000, 0).

21 Likes

Bumping this, table resizing would be useful especially when dealing with large amounts of data.

Currently the only workaround is to create a new table with the desired new size and then copying over all the data from the old table into the new one. This for obvious reasons is not the most optimal, ideal or ergonomic solution.

My use case for table resizing would be for my Octree terrain system. Every time the Octree structure changes new chunks need to be added to an instantiation queue. Solely relying on Luau’s automatic array reallocation causes lag spikes probably due to the amount of reallocation that is occurring. Whereas if a table.resize method existed then the table would only need to be reallocated once.

2 Likes

First of all, tables are dynamic arrays, there isn’t a design regarding their allocated size. They are just dynamic arrays. The kind of data that is stored in a dynamically allocated array has nothing to do with the allocated length.

Lua/luau does not represent arrays as “contiguous uniform data” in the way that a piece of low level code does because it’s an abstraction, an array of 64 unsigned integers in lua is not equivalent to an int[64], it’s an array of 64 lua values which have a fixed size. This is generally how dynamic arrays work in lots of places.

Every existing game engine that I know of provides you with the ablity to manipulate the allocated size of dynamic vectors at a high level, lua/luau is not the rule, it’s an exception to the rule. The allocated size of a table is not “low level” it’s just hidden.

The allocated size of an array has a very significant impact on performance and is relevant to quite a few different problems, there are lots of YouTube videos explaining why pre-allocation for dynamically sized arrays is important and how to effectively utilize it, and it’s not something that is typically hidden in the way that it is in lua. The concept of dynamic arrays isn’t unique to lua, it’s not even unique to game engines, the idea of the allocated size and the filled size of a dynamic array is something that exists in the highest level implementations of arrays/vectors in C#, C++, C, JavaScript, etc.

Pretty much all of your points are just that Roblox doesn’t already support this very well therefore Roblox shouldn’t ever support it because it doesn’t provide the tooling for you to utilize it. But you’ve not really given any alternative reasoning for why Roblox should not be supporting this. Besides, it should be Roblox’s job to decide if these things can or should be supported.

4 Likes

No duh. If you cannot possibly anticipate the size of an array on the heap, then pre-allocation is worthless. You pre-allocate when you can anticipate the size, because that is better than reallocating every time an item is added.

table.resize would be beneficial when one needs to insert potentially thousands of items into an array, like dynamic particle simulations. We can currently do this once with table.create, but not multiple times without doing some slow table.move shenanigans.

2 Likes

I am not projecting positions onto you, I just do not believe that the statement that you made was even relevant in the first place which was my point. I didn’t ‘parrot’ anything. Tables don’t need to be ‘designed for scripters to be concerned with their allocated size’ because they are just dynamically allocated arrays. Lacking proper support for working with the allocated length of tables is not itself justification for lacking proper support for working with the allocated length of tables.

Like I said, there are many many examples of this in the wild with very similar datastructures with very close matches to the features I requested. Unity/C#, WASM, Godot, JavaScript, etc all provide ways to manipulate the size of dynamically allocated arrays, even in cases where, like you said, you can’t read the allocated size. That’s not necessary, you don’t need to ‘debug’ anything. You already don’t have control over the allocation so any side effects that the engine may produce as a result of a resize are already within the same set of side effects that the engine could produce in the first place, there aren’t cases to debug.

Indicating an intent to fill or reduce an array to a specific size is also not equivalent to making ‘premature assumptions’ or relying on ‘superstition,’ it’s an indicator of intent. When you know the exact size you require ahead of time, you should be able to indicate to the engine what that size is and have the engine respond accordingly. Whatever strategy that entails it doesn’t matter, the point is that you know how much space needs to be allocated, and it should be possible to indicate that to the engine and expect a reasonable response.

I think that for one you are being too dogmatic. I also think that you don’t recognize that allocation costs can and do apply in real world situations in a measurable and significant way. To imply that there is no world where you can practically benefit from this just because you can’t peer past the layer of abstraction that’s there to ‘debug’ is completely wrong.

Frankly, I think that you are lacking information. I do not care if you don’t personally like the concept of pre-allocation based on the principle that that’s not how it was ‘intended’ to be, because that does not invalidate any of the practical justification I provided.

I support this feature.
However I am curious.

What makes resizing a table worth implementing?
I reckon you can also create a new table with a specified size and move elements from the old table over to the new, right?

It would save some time not having to code it yourself, but I still wonder what makes this useful and better than creating a new table and moving the old elements into it.

This is what you have to do currently, but it requires creating 2 tables just to fill another. Here’s an example:

local function CreateParticles(Length: number): {ImageHandleAdornment}
	local Particles = table.create(Length)
	
	for Iteration = 1, Length do
		table.insert(Particles, Instance.new("ImageHandleAdornment"))
	end
	
	return Particles
end

local function AddParticles(Particles: {ImageHandleAdornment}, Growth: number): {ImageHandleAdornment}
	return table.move(
		CreateParticles(Growth),
		1,
		Growth,
		#Particles + 1,
		Particles
	)
end

With table.resize, we can skip creating another table, resize the original and fill it in normally:

local function AddParticles(Particles: {ImageHandleAdornment}, Growth: number): {ImageHandleAdornment}
	table.resize(Particles, #Particles + Growth)
	
	for Iteration = 1, Growth do
		table.insert(Particles, Instance.new("ImageHandleAdornment"))
	end
	
	return Particles
end

There might be some other ambiguous semantics regarding resizing a table smaller, but another use for table.resize could be to shrink pre-allocated tables.

local function GetDescendantsWithName(Parent: Instance, Name: string): {Instance}
	local Descendants = Parent:GetDescendants()
	local Result = table.create(#Descendants)
	
	for Index, Descendant in Descendants do
		if Descendant.Name == Name then
			table.insert(Result, Descendant)
		end
	end
	
	-- Even though the length may be smaller, it still takes up space (try gcinfo)
	-- ideally, table.resize would return the table
	return table.resize(Result, #Result)
end
1 Like

This is the GitHub issue and contains the response @zeuxcg gave regarding this proposition which basically boils down to “we could, but should we and if so, what reasons would compel us to do this?”

I concur with zeuxcg’s response and fail to see the use case for manual memory allocation – Lua is designed by nature to handle dynamic memory allocations w.r.t. tables and is already a performant language in this regard (as far as languages go, at least). I do not think parity itself is a valid reason to add functions with niche uses (at least in Luau).

In my opinion, table.fill() can be written as a helper function and doesn’t need to be added into Lua’us native table methods.

1 Like

Going to nitpick and say that you shouldn’t be using table.insert with table.create, as its adding unnessary work when the advantage of table.create is that you dont need to allocate for new indexes because you know its size

local function create_particles(len: number): { ImageHandleAdornment }
	local particles = table.create(len)
	
	for index = 1, len do
                particles[index] =  Instance.new("ImageHandleAdornment")
	end
	return particles 
end