Why does Lua's length (#) operator return unexpected values?

Question

Lua has the # operator to compute the "length" of a table being used as an array. I checked this operator and I am surprised.

This is code, that I let run under Lua 5.2.3:

t = {};
t[0] = 1;
t[1] = 2;
print(#t); -- 1 aha lua counts from one
t[2] = 3;
print(#t); -- 2 tree values, but only two are count
t[4] = 3;
print(#t); -- 4  but 3 is mssing?
t[400] = 400;
t[401] = 401;
print(#t); -- still 4, now I am confused?


t2 = {10, 20, nil, 40}
print(#t2); -- 4 but documentations says this is not a sequence?

Can someone explain the rules?

Answer 1

Quoting the Lua 5.2 Reference manual:

the length of a table t is only defined if the table is a sequence, that is, the set of its positive numeric keys is equal to {1..n} for some integer n

The result of # operator on non-sequences is undefined. But what happens in C implementation of Lua when we call # on a non-sequence?

Background: Tables in Lua are internally divided into array part and hash part. That's an optimization. Lua tries to avoid allocating memory often, so it pre allocates for the next power of two. That's another optimization.

1. When the last item in the array part is nil, the result of # is the length of the shortest valid sequence found by binsearching the array part for the first nil-followed key.
2. When the last item in the array part is not nil AND the hash part is empty, the result of # is the physical length of the array part.
3. When the last item in the array part is not nil AND the hash part is NOT empty, the result of # is the length of the shortest valid sequence found by binsearching the hash part for for the first nil-followed key (that is such positive integer i that t[i] ~= nil and t[i+1] == nil), assuming that the array part is full of non-nils(!).

So the result of # is almost always the (desired) length of the shortest valid sequence, unless the last element in the array part representing a non-sequence is non-nil. Then, the result is bigger than desired.

Why is that? It seems like yet another optimization (for power-of-two sized arrays). The complexity of # on such tables is O(1), while other variants are O(log(n)).