Re: lua table internals: firstfree and numuse?

[Roberto Ierusalimschy <roberto@...>]

> 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.

The key idea is that, although it looks like a linear scan (well, it is
a linear scan ;-), the average time for finding a free element is O(1).
To fill a table with "n" elements, firstfree is moved at most n times
(going all the way from top to bottom), so the average move for each
insertion is 1!! (This argument is from Knuth, in his classic book about
sorting and searching.)

>   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?)

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.

-- Roberto