Re: Lua 5.4-work1 with first class arrays (implementation & benchmarks)

[Petri Häkkinen <petrih3@...>]

On 29 Mar 2018, at 9.29, Philipp Janda <siffiejoe@gmx.net> wrote:

> Couldn't you just add the length-updating code to normal tables? I mean we already pay the extra space for the length field.

I don't think we are understanding each other. Let me try again:

Lua tables are just key-value pairs with some optimizations. In a sparse table, like the one I showed in my example, there is nothing between the key-values, not even nils. This is the fundamental reason for the issue with holes and why # can't be implemented in constant time.

When you remove a key-value pair from the table, you would have to do some sort of scan of key-values to know the new length. You can do this when you insert/remove key-values, or you can do it lazily in the length operator. The latter is usually more efficient and that's what Lua does. When doing insert/remove on a table the table data structure does not know whether you are removing the last element or not, and in which indices the other values are stored in.

Arrays are different. They are dense and have all key-values between 1 and array size (even nils). When you push a new value, the array size always grows by one. When you insert a new key-value the array size will always be extended up to the new index (so array size becomes the index of the added value). When you remove a key-value, you always decrease the size by one. When you overwrite an existing value, the size does not change. Simple and efficient.

To get the speed benefits and to fix the hole issue, you have to break the rules of the game, i.e. the semantics need to change. Coming up with a new working semantic for tables, as proved by all the discussions over the years on this list, is hard (I would say impossible) and can  break existing code in subtle ways. Luckily, arrays have just the right semantics for the job.

Petri