Re: lists with nil play nice for Lua 5.2

[Lavergne Thomas <thomas.lavergne@...>]

On Fri, Aug 03, 2007 at 09:47:12PM +0100, David Given wrote:
> Roberto Ierusalimschy wrote:
> [...]
> > This 'n' would increase the memory needed to store each table.
> [...]
> > That would demand a new test when writing an element to the table (to see
> > whether the key is in the array part).
> [...]
> > Again this demand a test at each writing, to know whether the element
> > being written is nil.
> 
> This is all correct; but since all this happens in C code inside the VM, the
> overhead is trivial. Storing 'n' is just another machine word in the table
> structure (and may replace the existing #length field, if there is one).
> Comparing for nil is trivial. I would be very surprised if any of this turned
> into more than a dozen or so machine instructions. Any extra overhead should
> be completely absorbed in general housekeeping.

This is what I have in mind when writting my previous post. This cost is
extremly low when I compare it to the code (both in lua and c) I need to
ensure a predictable execution of some of the programs I work on.

I'm prfectly ok to loose a little of speed if, in exchange, I can be
sure of the way my code run. I think unpredictable result of some core
operations in a language is very big flaw.

> One possible complication I can see, however, is what happens if the user
> creates a table with sparse indices and then fills in the gaps later. Does the
> VM move stuff from the hash table portion of the table into the array portion
> (your definition!) of the table when this happens, or does the data all end up
> in the hash table?

This is implementation dependant, but, in my point of view, what I call
the array part (integer index from 1 to #t) can be stored in hash or
array. The array trick is just an implementation optimisation : in some
case you will have code working quicker, but in all case you will have
exactly the same result for your computation.

tom

-- 
Thomas Lavergne                       "Le vrai rêveur est celui qui rêve
                                       de l'impossible."  (Elsa Triolet)
thomas.lavergne@reveurs.org                           http://reveurs.org