Re: table insertion [was: Lua 5.1 (work2) now available]

[Roberto Ierusalimschy <roberto@...>]

table.insert is too slow and we all agree that is would be good a
standard way to do that operation (insertion at the "end" of an array).

I have a proposal for a new operator (after all these years): "*t" would
return the "size" of table t. With that operator, the insertion of a new
element in an array would be written as <<t[*t+1] = v>>. To remove the
last element, we would write <<t[*t] = nil>>.

That operator would deprecate table.getn and table.setn. getn(t) would
become *t; setn(t) would vanish. (Those operations have become quite
complex; they are slow and difficult to understand.)

The definition of *t is also a little tricky, but simpler than the
current getn. To allow an efficient implementation, *t cannot return
the largest integer index in the table. (That would demand a linear
search.) Instead, it returns an index i such that t[i] is not nil and
t[i+1] is nil. For arrays without holes, this is the largest index.
For arrays with holes, this is a "possible" end. (This value is what
getn returns in Lua 5.1w when there is no setn.)  With that definition,
we can implement *t with a binary search right into the array part
of the table. This is quite efficient. Even for very large tables
(10Mega elements) an insertion <<t[*t+1] = v>> is *much* faster than
table.insert.

-- Roberto