# Why Lua table pairs iteration doesn't hold the last key's position in Node[] ? Classic List Threaded 6 messages Open this post in threaded view
|

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

 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. 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)
Open this post in threaded view
|

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

 On Fri, Oct 9, 2020 at 3:41 AM 张伟智 <[hidden email]> wrote: > why pairs doesn't return a C closure with an integer upvalue to hold > the last key's position in Node[] ? Is there a useful notion of a "C closure" that could be used for this? It needs to free the associated integer when it is GCed. The issue you point out is one reason that the iterator protocol could be improved by separating the first user-visible value in the generic for loop from the control variable. That is, instead of being equivalent to this code:   do     local _f, _s, _var = explist     while true do       local var_1, ... , var_n = _f(_s, _var)       _var = var_1       if _var == nil then break end       block     end   end A loop declaration like   for var_1, ..., var_n in explist do block end should perhaps be equivalent to this code:   do     local _f, _s, _c = explist     while true do       local _c, var_1, ... , var_n = _f(_s, _var)       if _c == nil then break end       block     end   end
Open this post in threaded view
|

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

 In reply to this post by 张伟智-2 > 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. Certainly it could. Only note that this would demand a change in the C API, too. -- Roberto
Open this post in threaded view
|

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

 In reply to this post by 张伟智-2 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.)