• Subject: Why Lua table pairs iteration doesn't hold the last key's position in Node[] ?
• From: 张伟智 <robotkzhang@...>
• Date: Fri, 9 Oct 2020 02:41:07 +0800

```for k,v in pairs(tbl) do end -->
detail:
1 local tbl = {}
2 local iter_func, tbl, init = pairs(tbl)
3 local k, v = iter_func(tbl, init) --iter_func is next(luaB_next)
4 while k do
5     k, v = iter_func(tbl, k)
6 end

tbl = {A1=1, A2=1, A3=1, B1=1, B2=1}
struct Table Node[]: |... |A1|...|B1| ...|B2|...|A3|...|A2|...|
i        j        k
Suppose hash(Ai)、hash(Bi) are equal.

luaB_next is a normal C function, it is stateless and doesn't hold
so pairs(tbl) needs to find out all key's position in Node[].
Take next(tbl, "B2") as an example:
1. find the mainpostion of B2: i
2. Node[i] is B1, B1 != B2, try Node[i]->next: j;
3. Node[j] == B2, look for the first not null value from j+1,
which is A3,so next(tbl, "B2") returns "A3".
The overhead of next(tbl, "B2") equals to tbl["B2"] (retrieve "B2").
table.len() is widely used in our project:
function table.len(t)
local cnt = 0
for k,v in pairs(t) do
cnt = cnt + 1
end
return cnt
end
and the overhead of table.len() equals to retrieving all keys from table.
why pairs doesn't return a C closure with an integer upvalue to hold
the last key's position in Node[] ?
I think this can be improved.

Python2.7 dict(hashmap) also stores all key,value in an array
(Include/dictobject.h PyDictEntry ma_table[]).
dict.iteritems() returns a dict iter object, which use an integer to
represent the last key's position in ma_table[]. (Objects/dictobject.c
struct dictiterobject Py_ssize_t di_pos)

```

• Follow-Ups: