Re: Why Lua table pairs iteration doesn't hold the last key's position in Node[] ?

[William Ahern <william@...>]

On Fri, Oct 09, 2020 at 02:41:07AM +0800, 张伟智 wrote:
> 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.
> Link: A1->A2->A3, B1->B2
> 
> luaB_next is a normal C function, it is stateless and doesn't hold
> information about iteration,
> 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.

A closure requires heap allocation, though. I often make use of closures to
write iterators, but in heavily used functions I try to avoid that.

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

Python allocates from the heap everywhere. Lua is much more judicious about
heap allocations, which is one reason Lua code is generally faster than
Python. ("Fast" Python code in benchmarks is usually a result of leaning on
Python's large set of built-in C modules.)