Re: implementing a DAG using lua tables

[Dimitris Papavasileiou <jimmyp@...>]

> The way I usually do DAGs is to represent each node as a table whose keys
> are child nodes and whose values are all true (or any other constant).
> This can be rapidly traversed with a next (or lua_next) loop.

I don't get this. Why should the child nodes be kept in the table keys?
lua_next will return  the value as well so wouldn't it be just as fast(and
more logical) to keep the children in a vector table (i.e. with numeric-only keys)?
Besides a simple benchmark I coded a few hours ago suggested that traversing
a vector table with lua_rawgeti is faster than lua_next. Also each node must have a
value (a string currently but it could be anything). Where do you suggest I
keep that to minimize table lookups etc?

> If your DAGs really are trees, you can do reasonably fast node deletion by
> making the tables weak-keyed and maintaining a separate strong-keyed table
> of all the nodes; you can then "delete" a node by removing it from the
> strong-keyed table. However, this will not actually make it go away until
> you garbage collect, so it depends on how precise your deletion has to be.
> If you were going to delete a lot of nodes at once, for example, you could
> delete them all as described above, and then call collectgarbage() to get
> them to go away. (Calling collectgarbage at the end of every frame is not
> an unreasonable approach to managing garbage collection.)

This is very interesting!

Btw, since we're talking about performance, what is the fastest way to traverse a
table (in arbitrary order) from C? And how does this compare to traversing a C linked
list? I thought the times for these tasks would be close but a benchmark suggested
otherwise.