Re: lua table internals: firstfree and numuse?

[Roberto Ierusalimschy <roberto@...>]

> > Not exactly. Some elements may get a "better" position (if a previously
> > colliding key was removed from the table). It is a time where the table
> > is cleaned. And this only happens when there are a minimum number of
> > free nodes (1/4 of the table, I guess), not only 1.
> 
> That's not what I see.
> [...]
>     4. which eventually calls setnodevector with size == oldSize, which
> reallocates and reinserts all the entries

The new "size" will be floor(log2(nuse*5/4))+1 (or something like that),
so if nuse == (oldSize - a-few-slots) the hash will grow (see function
"rehash").


> 2. keep a numUsed field in the table and get rid of the numuse subroutine
> --- downside: every table is 4 bytes larger

Another downside: you need an extra test everytime you assign a value to
the table, to check whether it is nil.


> 1. reset the firstfree pointer with a linear scan rather than a rehash of
> the whole table --- downside: a tiny bit of new code

That may be worth trying, although in some cases you may end up with a
linear scan for *every* insertion, when the table has only a single free
entry. (For instance, you create a table with 32 elements and after that
you keep doing one inclusion - one exclusion.) With the current method,
the table will grow to 64 elements, and so this problem does not exist.

Notice also that you cannot simply use a node with val==nil as a free
node: It may be part of a list, already. (That is, your "findfree" may
break some links in the table.)

-- Roberto