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

[Duane Leslie <parakleta@...>]

>> On 29 Mar 2018, at 14:46, Petri Häkkinen <petrih3@gmail.com> wrote:
>> 
>> 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?

It's not an "array-like" table, and is not legal in your new proposal either.  Constructing a new "array-like" table and inserting an element at 127 would set the length to 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?

This depends on how you do it, if you assign nil the length is unchanged, if you use the remove function the length is shortened.

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

It is impossible to do it in constant time, but in the case where this is what someone wants you don't offer any solution to this problem either.

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

They do have different semantics, but I believe you can implement everything you've proposed directly in Lua with equivalent performance (some small constant overhead for the VM) except maybe for the resize function.

Consider:

```lua
local mtype = math.type
local tpack, tinsert, tremove = table.pack, table.insert, table.remove

local ARR_MT = {}
function ARR_MT:__newindex(k,v)
    if mtype(k) ~= "integer" or k < 1 then
        error("invalid array index")
    end
    if k > self[ARR_MT] then
        self[ARR_MT] = k
    end
    rawset(self,k,v)
end
local function __next(arr, k)
    k = (k or 0) + 1
    if k > arr[ARR_MT] then
        return nil
    end
    return k, arr[k]
end
function ARR_MT:__pairs()
    return __next, self, 0
end
function ARR_MT:__len()
    return self[ARR_MT]
end

function table.pack(...)
    local arr = tpack(...)
    local len = arr.n
    arr.n = nil
    arr[ARR_MT] = len
    return setmetatable(arr,ARR_MT)
end
function table.insert(t,...)
    tinsert(t,...)
    t[ARR_MT] = t[ARR_MT]+1
end
function table.remove(t,...)
    local len = t[ARR_MT]
    local ret = tremove(t,...)
    if len ~= 0 and (... or 0) <= len then
        t[ARR_MT] = len-1
    end
    return ret
end
function table.resize(t,s)
    -- No implementation available
end
```

Note that I've overridden `table.pack` as the constructor for my "array-like" tables.

Regards,

Duane.