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

[Philipp Janda <siffiejoe@...>]

Am 29.03.2018 um 05:46 schröbte Petri Häkkinen:
> 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?

What would the length of this array be:

    local t = []
    t[ -1 ] = true  -- ignore if not allowed in your patch
    t[ 13 ] = 1
    t[ 127 ] = 2

If I read your proposal correctly, the length should now be 127 with a 
lot of nil elements.

> 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?

Do we remove the entry from the table literal above or from the 
resulting table? If the former, the length should be 13, otherwise the 
length should be 126.

> 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.

Constructing a table from a table literal is linear time anyway. No harm 
updating the length field with the currently largest integer key as you 
add the elements to the table.

I suspect you want to know the length before constructing the table so 
that you can allocate the array part? I'd just use the hash part in this 
case. The table is most likely sparse if you use this form of table literal.

> 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).

How is that different from your current patch?

> 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?

Not right now. I'll post it when I find it.

> 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

Philipp