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

[pocomane <pocomane_7a@...>]

On Thu, Mar 29, 2018 at 8:06 PM, Petri Häkkinen <petrih3@gmail.com> wrote:
> On 29 Mar 2018, at 17.14, Dirk Laurie <dirk.laurie@gmail.com> wrote:
>>
>> 2018-03-29 14:43 GMT+02:00 pocomane <pocomane_7a@pocomane.com>:
>>>
>>> For what I know, # is O(log(n)) when the sequence has holes, while .n
>>> should be accessed in a costant time. E.g. the following code:
>>
>> Sure .n takes a constant time (and can easily be put into __len), but
>> maintenance of .n does not.
>
> Exactly!


On Thu, Mar 29, 2018 at 9:12 PM, Petri Häkkinen <petrih3@gmail.com> wrote:
> 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.

It is not clear to me what you mean with "Maintance'. If you want just
to ignore any hole, it did not suffice to store the bigger index in
.n? At most you need also to decrase .n when you assign nil to the
last element.

I did some test, and this is about 20-25 % faster than a #
implementation [1]. I agree that native array will be faster, but not
that much.

The real issue is: when you incapsulate the set/lenght-update in a
function (or __newindex/__len), the time increases a lot, due to the
function call [2]. But have we to introduce a new data type (an
aggregate one!) to address this problem?

E.g. Not so serious proposal:
- t << v operator on table without metamethod pushes v and update t.n [3]
- t >> v operator on table without metamethod pops last and update t.n [4]

---

[1] Praticaly, the benchmark was `a[1+#a]=0` versus `local n=a.n+1 ;
a.n=n ; a[n]=0`; it just starts with empty table and then it added ~
1M item.

[2] The same benchmark takes ~ 5x time wrt # operator.

[3] Sugar for `if not t.n then t.n = 0 end ; t.n=t.n+1 ; t[t.n] = v`

[4] Sugar for `if not t.n then t.n = 0 end ; if t.n>0 then v = t[t.n]
; t[t.n] = nil ; t.n=t.n-1 end`