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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

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

张伟智-2
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)
Reply | Threaded
Open this post in threaded view
|

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

Robert Burke
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
Reply | Threaded
Open this post in threaded view
|

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

Roberto Ierusalimschy
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
Reply | Threaded
Open this post in threaded view
|

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

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

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

Philippe Verdy-2


Le jeu. 8 oct. 2020 à 22:57, William Ahern <[hidden email]> a écrit :
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.

Closures are usually very small and have a static size, this means you can allocate/free/reallocate them very fast with a pool-based allocator, and there's not much overhead. I thing that any decent implementation of Lua engines should have a pool for small objects of static sizes
And I think it can also use some statistic metrics to know the most frequent sizes in order to tune the number of the pools and the number of free slots to keep for each pool.
For small sizes, the slots in each pool can be preallocated in pages with minimum size, and the garbage collector can more easily group together the pages that are insufficient used if it needs to free up some pages (according to its collected usage statistics for each pool).
Basically the default implementation Lua just trusts the standard C library for malloc/calloc/realloc/free, but you can link your C program with a more convenient memory allocator without really needing to modify the Lua sources. And there are many excellent replacement libraries (including some with additional security features, like randomization of addresses, or debugging, or that can also monitor external metrics from the OS) that will implement the allocation strategy that fits your needs in your app, or the restriction requirements for your device, or that will trade between reduction of memory footprint, data locality, speed/real time constraints, or extreme security with constant allocation time for known sizes (managing constraints is where pools become effective, and pools are a native feature of C++ with its "placement" feature).

Reply | Threaded
Open this post in threaded view
|

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

William Ahern
On Fri, Oct 09, 2020 at 07:55:58PM +0200, Philippe Verdy wrote:

> Le jeu. 8 oct. 2020 à 22:57, William Ahern <[hidden email]> a
> écrit :
>
> > 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.
>
>
> Closures are usually very small and have a static size, this means you can
> allocate/free/reallocate them very fast with a pool-based allocator, and
> there's not much overhead. I thing that any decent implementation of Lua
> engines should have a pool for small objects of static sizes

Most system allocators already use fast pools for small object sizes, so I
don't bother.

The problem with dynamic allocation in the general case is 1) it doesn't
play nice with CPU pipelines and caches and 2) all the dynamic memory
creates more garbage for the GC to chew threw, which likewise increases the
amount of the worst kind of work for the CPU.

In general you can't really optimize general purpose allocations very well.
I do often use special purpose allocators in my C libraries, but
specifically for FIFO buffers and so-called object stacks. They work
exceptionally well, both in terms of convenience and performance, because
they're specialized to the lifetime and relational semantics of the objects
being allocated. And because they're specialized to specific use cases the
various functions are short and simple and can be optimized well, whether
compiled inline (i.e. as header files) or inlined through the link-time
optimizer.

If you're smart about how you use Lua in critical paths, you don't need to
incur the cost of sub-optimal memory and object semantics. You can use Lua
to stitch together bits of C code (leaves in the codeflow graph) without the
Lua VM or its library calls blowing your pipelines, prediction buffers, etc
through unnecessary memory churn and code paths.

That said, I don't normally worry about this. My point is just that C++ and
Rust aren't the only ones providing so-called "zero-cost" abstractions. In
its own way Lua does as well. If all I want out of Lua in a particular
scenario is a tight bytecode loop operating on scalar values (like Forth or
K), then I can have that. Introducing dynamic allocations in simple
iterators breaks that model.