Extend table allocation options (e.g. table fill & resize) about luau HOT 4 CLOSED

WASM is a bit different because there you can't grow the table by simply writing to it.

These aren't difficult to implement, but I'd like to hear the motivation from the ergonomics or performance perspective. For example, when we were adding table.create, the discussion was essentially:

• it helps performance because any time there's a loop that table.insert's values into a fresh table and you can estimate the capacity, it significantly cuts down on reallocation cost; this is very common!
• it helps ergonomics because there's common cases in algorithms when you initialize a table with zeroes; this is not as common as 1
• while ergonomics can be solved with a wrapper function in user code, performance can not be.

table.move is an interesting example because we added this as a Lua 5.3 port to align with the upstream library, so there wasn't a specific motivation in performance. Subsequently we haven't seen this being used as often as I'd expect, and we even had some period of time while an optimal loop that copied values was actually faster than table.move :)

So for either of these to be added I think it's important to know what type of code would leverage these and how, because it'll make the case for including or not including these easier. table.resize in particular is complicated because it's effectively a no-op semantically if the length is larger than internal array size and if the length is smaller it's more difficult to implement (does table.resize(0) wipe out all numeric keys larger than 0?), which means we should make sure that it solves a need that commonly occurs in practice.

from luau.

WASM is a bit different because there you can't grow the table by simply writing to it.

These aren't difficult to implement, but I'd like to hear the motivation from the ergonomics or performance perspective. For example, when we were adding table.create, the discussion was essentially:

• it helps performance because any time there's a loop that table.insert's values into a fresh table and you can estimate the capacity, it significantly cuts down on reallocation cost; this is very common!
• it helps ergonomics because there's common cases in algorithms when you initialize a table with zeroes; this is not as common as 1
• while ergonomics can be solved with a wrapper function in user code, performance can not be.

table.move is an interesting example because we added this as a Lua 5.3 port to align with the upstream library, so there wasn't a specific motivation in performance. Subsequently we haven't seen this being used as often as I'd expect, and we even had some period of time while an optimal loop that copied values was actually faster than table.move :)

So for either of these to be added I think it's important to know what type of code would leverage these and how, because it'll make the case for including or not including these easier. table.resize in particular is complicated because it's effectively a no-op semantically if the length is larger than internal array size and if the length is smaller it's more difficult to implement (does table.resize(0) wipe out all numeric keys larger than 0?), which means we should make sure that it solves a need that commonly occurs in practice.

This is all makes sense to me. I'll try and do a mock of your bullets for both functions as well as giving some specific generalized use cases...
Overall, these functions would benefit data oriented design the most for sure.

For table fill:
Key property of its use cases: Deterministic bulk table changes
Key scenarios it benefits: Large quantities of small, repetitive & high frequency writes. Small quantities of large, repetitive & low frequency writes. (Comparable to table.concat vs string.repeat)
Common cases: Primarily data & image processing, assembly/bytecode emulation.

• It helps ergonomics because there are common cases in algorithms when you may need to clear, reset, or update data in quantity. Flood algorithms, compression algorithms, flow grids, and memory emulation would benefit from this.
• It also helps ergonomics & readability by condensing repetitive writes into an easy to understand form.
• It slightly benefits performance for repetitive, small writes by reducing the number of variable allocations & operations (which are likely to be done in bulk where it best applies). This is commonly applicable in data processing (especially in compression, as repetition is effectively the whole purpose) where its expected there will be a large quantity of small writes.
• Low overhead

For table resize:
Key property of its use cases: Non deterministic bulk table changes
Key scenarios it benefits: Low frequency writes. Small quantities of large, unique writes. Predictable frequencies, quantities & phases of writes.
Common cases: Highly dynamic environments. (Networking, dynamic/interactive games, etc)

• It helps performance when adding lots of new data to existing tables. This follows table.create loosely, benefiting large quantities over small ones, but applies more to dynamic environments where size is likely to change very frequently, whereas table.create applies to static ones where size is expected to be mostly static. This is common in any sort of code involving dynamic bodies where many items will be inserted and removed at once.
• This applies to scenarios where there are very predictable events where things are likely to be deleted or created all at once.
• For example, node based pathfinding algorithms such as A* needs to manage a large node array, and different areas of a game map might be activated or deactivated based on the states of different doors in the world.
• High overhead if used incorrectly

from luau.

Coming back to this, it would be interesting to see examples of code where either resize or fill would be useful. Ideally we'd look at some algorithm implementation that we can then benchmark with or without first-class functions like this to determine how important these would be. Overall I'm hesitant to expose resize as it raises too many questions about the behavior in edge cases, but fill would be a more straightforward addition because it can be formulated in terms of simple table assignment - the key question being, what's an example of an algorithm where it improves performance.

from luau.

I'm going to close this for now, feel free to suggest examples of code where filling a table with the same value is important wrt performance and then we can reevaluate.

from luau.