lua table internals: firstfree and numuse?

[Russ Webb <Russell.Webb@...>]

For those interested in how lua works internally:

I don't quite get the purpose of the firstfree field in tables.  I see how
it is used, but why is it better than just scanning linearly for a free node
from the main position of a key since it seems to scan linearly for the next
free node after firstfree is used in luaH_set?

I suspect this is how it works:
    When the freenode hits the bottom of the array and
    there are free nodes above it the table is rehashed
    to the same size which only resets the firstfree to
    the top of the array (why not just do that and skip
    the memory thrash, rehashing, and rechaining?)

Seems convoluted, but maybe I just don't get it.  How about setting
firstfree to any node higher in index when that node is set to nil?  Or just
get rid of firstfree and use a linear scan from the main position that is in
use making all tables smaller by 4 bytes?  BTW, I looked at using a linked
list of free nodes off the next field, but one quickly hits a dead end when
you try to grab a free main key position and figure out how to remove that
node from the free list.

Also, why is it OK for numuse to actually do a linear scan over all the
elements?  Shouldn't linear scans be avoided even if they are of low time
constant?  How about keeping numUsed in the table structure, so no scan is
needed?  It could replace firstfree.

Obviously, Lua tables are great and becoming more and more the heart of Lua.
Which is why I'd like to understand them better.

I'm looking at Lua 4.0, BTW.

Russ