Re: Virgin tables

[Dirk Laurie <dpl@...>]

On Thu, Dec 30, 2010 at 01:23:19PM +0200, Luiz Henrique de Figueiredo wrote:
> > *   It's an O(1) function.  Virginity is lost by t[k]=nil for 
> >     k<#t and by t[k]=non_nil for k>#t+1, both easy to test.
> 
> How is it O(1)? Do you have a sample implementation?
> 
> > *   #t would be O(1) for all virgin tables.  (At present, many 
> >     numeric entries may actually reside in the hash part of the 
> >     table, and then #t takes O(log n) time.)
> 
> Like I said before, full arrays can have part of their data stored
> in the hash part:
> 	http://lua-users.org/lists/lua-l/2010-12/msg00400.html
> 

Since the term "virgin" seems to prevent the suggestion from
being taken seriously, I'll replace it by "pristine".

I am not proposing any change in the language, not even in the
meaning of #t.  I am only proposing the visibility of a flag
that would be useful to the implementation.

I assume that accessing a specific key in the hash part is O(1),
at least on average.

Keep two fields for every table:
(a) boolean - is the table pristine?
(b) number - if it is pristine, what is the largest numeric index?
    Equivalently, what is #t?  Otherwise, it does not matter, 
    I suggest the most recent value returned for #t.

table.pristine(t) would simply return (a).
#t would for a pristine table simply return (b).  For other tables,
    it might check whether (b) still works, and if not, go through
    the present binary search.

Updating (a): once (a) is false, it stays that way.

__newindex:
While (a) is true, a hole is created by:
    1. Storing a nil at an index less than #t.
    2. Storing a non-nil at an index greater than #t+1.
Either of these is tested in O(1) time.
If no hole is created, (b) stays the same except when a nil
is stored at #t or a non-nil at #t+1.

Standard table functions don't destroy the pristine property
and updating (b) is trivial.

When a table constructor is scanned, we need to examine every 
entry anyway.  In the process we count the number of distinct 
positive integer indices and keep track of the highest such 
index at O(1) operations per item.  If these are the same, 
the table is pristine when constructed.  So even a constructor 
like {[4]=4, [1]=1, [3]=3, [2]=2} can be recognized as giving a
pristine table.  Other indices are just ignored for this purpose.

Admittedly a table can lose the pristine property and later
return to having no holes, but this is fortuitous, and such
a table is not pristine. 

Having the pristine flag available to the implementation
will save time for #t in the common cases where either the
table is pristine or the previous #t still works.

The proposed function table.pristine will enable code to check
array integrity.

Dirk