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

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

On 29 Mar 2018, at 5.28, 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.

It’s not possible.

Consider the following table: 
{
  [-1] = true,
  [13] = 1,
  [127] = 2
}

What is the length of the table? Is it 3? Is it 127?

Now remove the entry at index 127. What is the length of the table now? Is it 2? 13? Is it 126? 126 does not make any sense, does it?

I guessed you wanted the table length to be 13. Now tell me how do you find that in constant time? Hint: it’s impossible.

On the other hand, when you remove an element from an array, the array size always simply decrements by one. In the example above, the size of the array would shrink from 127 to 126 (indices in ranges [1,12]  and [14,126] would contain nil).

The thing is, tables and arrays have different semantics and the only real solution to the problem is to change the rules of the problem. The change of rules (semantics) is also what makes the arrays so fast and why they fix the hole issue.

> p.s. I believe this proposal isn't new and was rejected because of the extra space and performance cost for non-array tables, but maybe your benchmarks change that.

Do you have a link?

Again, I’ve not found any (measurable) performance cost with regular tables caused by the patch. But you don’t need to just take my word on it, please do run some tests yourself, the code is there in github. I may even be wrong. I’ve only run the benchmarks on my laptop.

Petri