lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Maintaining a count has some drawbacks.
1) Each rawset would get worse performance.
2) A count would be hard to implement for weak tables, unless the garbage collection itself started modifying the count for all tables when collecting objects.

(Personally I think Lua should separate tables from arrays, i.e. add a pure array type as a complement to the current tables.)

Btw, if your tab:count() function uses next(t) to determine if the table is non-empty, that's still a complete table traversal if it's in fact empty, since it has to look at all array and hash positions.
(But if you're just checking t[1], that would obviously be fast enough).

On Wed, Jun 24, 2009 at 4:19 PM, John Hind <john.hind@zen.co.uk> wrote:
In my opinion (for what little it is worth) it would be useful if the Lua core kept a count of the total number of elements in a table. Then it could compare the "array count" with the "true count".

Although Lua maintains the "user illusion" that all possible keys exist, but some reference null values, in reality it must be possible for the table handling code to determine if it is changing a null value to non-null or a non-null value to null. So it should be able to maintain the total number of non-null elements by incrementing or decrementing a counter during lua_settable operations.

I guess we are now going to be regaled with schemes for doing this using metamethods, but these must be pretty inefficient compared to doing it in the core. Such an innovation would not need to be an obvious or breaking change: just have a new library function which recovers the "true count" and then metamethods can be used to replace the # operator with this, or raise an error if the two counts do not match. Of course small tables would need to be a little larger to accommodate the counter and a policy would be needed on overflow.

Incidentally in my own take on the "standard object-oriented table library" I introduced a "count" method - this takes an optional limit number so tab:count(1) determines if the table has at least 1 element etc. This avoids a complete table traversal when unnecessary (for example if just determining if the table is empty).

> -----Original Message-----
> From: lua-bounces@bazar2.conectiva.com.br [mailto:lua-
> bounces@bazar2.conectiva.com.br] On Behalf Of Cosmin Apreutesei
> Sent: 24 June 2009 14:17
> To: Lua list
> Subject: Re: Lua next version
>
> On Wed, Jun 24, 2009 at 14:36, Luiz Henrique de
> Figueiredo<lhf@tecgraf.puc-rio.br> wrote:
> >> Given the persistent confusion about arrays vs. tables, and the
> scope
> >> for really nasty hard-to-find bugs if people get it wrong, it might
> be
> >> worth considering a 'strict mode' option (by default off, of course)
> >> that cause #, table.remove/insert etc to *fail* if you give them a
> table
> >> that's not an array. By fail, I mean throw an error to cause you
> >> application to stop.
> >
> > How do you propose to do that? I mean, how can the Lua core detect
> that a
> > table is not an array without traversing it completely?
> >
>
> That's easy, just flag the table on each modification and then just
> read the flag, that shouldn't produce much overhead, and would even
> help making some optimizations (like allocating the map part
> differently from the array part, etc.).
>
> This would settle the matter straight about what a table is and how it
> behaves at any point at runtime, but more importantly, in the manual
> (eg. more meaningful definitions for #).
>
> This leads to a chain of changes:
>
> 1) make a subtype() built-in function to read that flag (it would give
> you "array", "sparse array", "map", etc.).. let type() alone for
> compatibility.
> 2) throw an error when applying # to any table that's not subtype
> "array" -- very much needed for reliability of programs in general,
> IMHO.
> 3) allow appending with a[] = x instead of a[#a + 1] = x, to allow
> change 2).
>
> You might argue that these features are not core enough to worth
> bloating the language with, especially since you can do them in plain
> lua or C, but I can argue that the problems with that approach are
> even bigger: 1) didactic (new users), 2) standardization, 3)
> efficiency. A standard library of common abstractions would solve all
> problems of course, but I is it possible to build it efficiently
> (either in C or lua) on top of current infrastructure?