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

[Dirk Laurie <dirk.laurie@...>]

2018-03-29 14:43 GMT+02:00 pocomane <pocomane_7a@pocomane.com>:
> On Wed, Mar 28, 2018 at 6:04 PM, Petri Häkkinen <petrih3@gmail.com> wrote:
>> I don't see your point about fairness. If we would be comparing pure Lua version of arrays (or tables with 'n' field), the speed difference vs. native array implemention would be much higher than my benchmarks show and in favor of arrays. Every array insertion/removal would need to update 'n' which would be much, much slower than with arrays or even regular unordered tables.
>
> 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.

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.