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

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

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!

> The fundamental problem is not that Lua does not have first-class arrays.
> 
> It is that Lua does not have first-class lists.
> 
> table.insert and table.remove are being made to do a job for which
> arrays are not ideal. If we had first-class lists, insert, remove and
> # would all take constant time.


You forgot to mention that lists have horrible random access times and absolute destroy CPU cache performance.

Petri