ltable.c: observations and questions

[Reuben Thomas <rrt@...>]

I have continued to study the code, and now think I have some
observations, which may be of interest. One or two properties of the
current table implementation certainly foxed me.

1. Although the hash part and array part can be shrunk, this will happen
rarely, because the table is only resized when one or the other part
becomes too small. This seems to run counter to the invariant that states
in the comments that the array part is always at least half full. In one
sense it is, it's just that the entries can all be nil. In fact, entries
are never deleted from the table (except when it's rehashed).

2. nil entries don't disappear until and unless the table is resized.

3. Since resizing only happens when the table grows, you can get the
following weird situation: set

t = {a=1,b=2,c=3}

Since the keys are strings, they will of course occupy the hash part of
the table. Now set

t.a = nil; t.b = nil; t.c = nil

This removes the entries, but doesn't shrink the table (which will have
size 4, i.e. 2^2). At least, this assumes that the table was originally
created with both hash part and array part of size 0, but since
OP_NEWTABLE is only ever emitted with these values set to 0, I think
that's a safe assumption.

Now do

t[1]="foo"; t[2]="bar", t[3]="baz"

You might think that this would use the efficient array part of the table,
but it doesn't. The array part is currently of size 0, so indices 1-3
aren't in the acceptable range for the array. But there is room for them
in the hash table part. So in they go.


I doubt that any of this is a problem in real-world applications: one is
unlikely to fill a table with non-integer keys, then empty it, then fill
it with integer keys. Also note that doing the reverse is no problem:
having made a large array part to the table, then emptied it, the first
time you try to add a non-integer key the array will be collapsed, and the
hash table part enlarged.

I presume that the reason that "deleted" elements are set to nil rather
than being removed and then, potentially, shrinking the hash table, is
because in practice tables tend only to increase in size, and also that it
makes next() work even when existing elements of a table are set to nil,
hence the rule that you musn't set non-existent elements of a table in a
next() loop, but you can delete existing elements.


I'd be interested to hear any further rationale for, and most especially
errors in the above.

-- 
http://www.mupsych.org/~rrt/ | God is the name of our ignorance (Grayling)