Optimization for Arrays of Uniform Types

[云风 Cloud Wu]

Lua 5.5 optimized array storage by storing the Tag after the array and
the Value before the array. I wonder if we could further optimize
scenarios where the entire array contains values of the same type by
storing only a single unique Tag in the array.

In scenarios involving large datasets, using Lua tables to store data
(e.g., integers, floats, C pointers) has almost no memory overhead
compared to native arrays in host code (typically written in C/C++).
In embedded environments where Lua is integrated, relying on Lua's
garbage collection (GC) to manage memory is generally more reliable
than manual memory management. This reduces the risk of memory leaks
or segmentation faults caused by improper handling of pointers or
resource allocation. Additionally, processing data in Lua tables is
more cache-friendly, making them highly efficient for memory-intensive
workloads.

--
http://blog.codingnow.com

[Xmilia Hermit]

Cloud Wu:

> Lua 5.5 optimized array storage by storing the Tag after the array and
> the Value before the array. I wonder if we could further optimize
> scenarios where the entire array contains values of the same type by
> storing only a single unique Tag in the array.

I think this would be interesting, but it adds complexity for the
implementation.

Every array access would first need to check what type of array it has
to deal with slowing down the array access. Similar for storing values
in the array. Also most arrays have nil values since the array is
resized in larger steps. It would be possible to use asize for the
separation between values and nils in case of this special array type,
but this would again add complexity in the array assignment path.

Furthermore, there would be the question when to stop. I would assume
that arrays of integers with only the values 0 to 255 are quite often
used too. This could be optimized to use a byte array. What about an
array of boolean values? It could be a bit array. And not long after you
have 20 specialized types of arrays adding complexity and needing to be
maintained.

In short I do not think the implementation complexity and slowdown is
worth the 1 byte save per array entry.

If the memory is a concern there is always the C API which allows to
implement these optimized arrays with the help of userdata types which
can also be garbage collected.

Regards,
Xmilia

[云风 Cloud Wu]

Xmilia Hermit <xmilia...@gmail.com> 于2025年12月18日周四 01:15写道：

>
>
> I think this would be interesting, but it adds complexity for the
> implementation.
>
> Every array access would first need to check what type of array it has
> to deal with slowing down the array access. Similar for storing values
> in the array. Also most arrays have nil values since the array is
> resized in larger steps. It would be possible to use asize for the
> separation between values and nils in case of this special array type,
> but this would again add complexity in the array assignment path.

Yes. But we can reduce its impact on performance by introducing a
subtype of a table like short/long string.
Sequence has always been a special kind of table, but we've never
explicitly differentiated it.

> In short I do not think the implementation complexity and slowdown is
> worth the 1 byte save per array entry.

Adding a subtype would avoid extra branch checks, keeping array access fast.
It's not just about saving a single byte, it's about reducing a memory
access across different cache lines.

> If the memory is a concern there is always the C API which allows to
> implement these optimized arrays with the help of userdata types which
> can also be garbage collected.

Accessing userdata from the C side is fast, but from the Lua side it
requires going through the metatable and additional lua function
calls, making it significantly slower. This forces
performance-critical scenarios to handle it entirely on the C side.

--
http://blog.codingnow.com

[云风 Cloud Wu]

云风 Cloud Wu <clo...@gmail.com> 于2025年12月18日周四 08:52写道：

>
> > In short I do not think the implementation complexity and slowdown is
> > worth the 1 byte save per array entry.
>
> Adding a subtype would avoid extra branch checks, keeping array access fast.
> It's not just about saving a single byte, it's about reducing a memory
> access across different cache lines.

Additionally, this new sub type could also be used to represent a pure
metatable, a sequence that contains only metamethods. This would allow
metamethods to be directly indexed from it, eliminating the need for
string hashing.

--
http://blog.codingnow.com

[Xmilia Hermit]

Cloud Wu:

> Yes. But we can reduce its impact on performance by introducing a
> subtype of a table like short/long string.
> Sequence has always been a special kind of table, but we've never
> explicitly differentiated it.

I was in the impression that this should be invisible to the Lua script.
If it just so happens that all values are of the same type use this
special array else use the generic one. Since type tags which encode
subtypes are immutable (or require a full heap scan to change) the
subtype of the array cannot change at runtime.

> Adding a subtype would avoid extra branch checks, keeping array access fast.

For the load case I guess even with the current method not relying on
subtypes the checks could be moved into the slow path not impacting the
array fast path by setting asize to zero in case of this special array
type and checking for it in the slow path.

Still, even with using the subtype system, more branches are required
since the different array types require different access methods and you
somehow need to run the correct one.

But one actual advantage I found was for the GC which can quickly
determine if it can skip the full array scan when it does not contain
any heap values.

Regards,
Xmilia

[云风 Cloud Wu]

Xmilia Hermit <xmilia...@gmail.com> 于2025年12月18日周四 15:53写道：

>
> Cloud Wu:
> > Yes. But we can reduce its impact on performance by introducing a
> > subtype of a table like short/long string.
> > Sequence has always been a special kind of table, but we've never
> > explicitly differentiated it.
>
> I was in the impression that this should be invisible to the Lua script.
> If it just so happens that all values are of the same type use this
> special array else use the generic one. Since type tags which encode
> subtypes are immutable (or require a full heap scan to change) the
> subtype of the array cannot change at runtime.

You're correct. The solution I can think of is to split into two
subtypes: one for generic tables and one for special tables. During
initialization, we determine its subtype. Once a table transitions
from special to generic, it cannot revert back. This way, the branch
for generic tables can maintain consistency with the current
implementation. For the special table branch, we always perform a
check and update the type tag within TValue based on the result.

> Still, even with using the subtype system, more branches are required
> since the different array types require different access methods and you
> somehow need to run the correct one.

Accessing a table already required a check based on whether it's a
table, userdata, etc.
(https://github.com/lua/lua/blob/master/lvm.h#L89-L100)
I guess replacing if/else with switch/case here would not introduce
significant overhead


--
http://blog.codingnow.com