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

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

On 28 Mar 2018, at 9.29, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:

>The simplest example is standard iteration using for / pairs().
>Existing code does not expect nils to appear. What is problematic is
>that you can't tell if some existing code will break - because it is a
>semantics thing - syntactically it all looks fine.

Nope, there is no such problem. The beauty of a separate array subtype is that regular tables are not affected by the existence of the array type. pairs() and ipairs() work just like they did for tables, but for arrays they iterate though the whole array in order. That’s because the semantics are different. A table is a mapping from keys to values with no particular order and no concept of what lies between the keys (i.e. tables with holes) — the key-values just aren’t there. An array has all the indices in range [1,arraysize].


On 28 Mar 2018, at 10.10, Duane Leslie <parakleta@darkreality.org> wrote:

>I have to admit I haven't read your code, only the Readme, but I fail to see the difference
> between your proposed operation and the `.n` field and some very basic metamethods and extending
> the library functions which you require anyway.  When I spoke about *generic* I meant a length value that was always equal to the largest index in the table.

That's how the length operator works for arrays. An array always has indices [1,arraysize]. The length operator returns the length of the array. That’s the most generic and easy to understand as it can get.

The differences with arrays emulated with tables are:

+ much, much higher performance than possible with ’n’ field trick
+ standardized way to query the length (using the # operator)
+ the length is automatically updated when you insert values — this is essentially for free

> How about compared to using `.n` or the local variable idiom (i.e. `t[next], next = value, next+1`).
> `#t` is known to be slow, so where you need performance you cache it or manage it manually.

#t is known to be slow, but it does not have to be that way. With a fast #, you don't need 'n' anymore. Array length is well defined, extremely fast and automatically updated for you.


On 28 Mar 2018, at 10.35, pocomane <pocomane_7a@pocomane.com> wrote:

> Moreover, about your benchmark, I think that comparing # with the
> access to a stucture field is a bit unfair. In lua you will never use
> # on tables with holes (when performance is important). I would
> compare it against a the common .n idiom, or a full
> Pure-Lua-Array-Type solution.

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.


On 28 Mar 2018, at 12.46, Dirk Laurie <dirk.laurie@gmail.com> wrote:

> I don't see the point of first class arrays whose elements are general
> Lua values. You don't get enough extra speed. It optimizes at the
> wrong place.

Arrays, or more generally ordered sequences are everywhere, they are well understood and very common data structure, and it makes sense to have an optimized solution for them. I bet if I analysed my current codebase (a game I'm developing), a major chunk of the tables would be arrays. The whole existence of the hole problem and slowness of the length operator is caused by the over generalization of tables as a data structure. The problem is that the length of a generic table is ill-defined. Length only makes sense for arrays. Trying to come up with a # operator that works and is efficient in the general case for tables is futile, because the problem is too general. Arrays not only provide an efficient implementation for sequences, they also have better semantics for length.

Petri