Re: Design questions for a small s-expression library

[Philipp Janda <siffiejoe@...>]

Am 18.01.2014 15:04 schröbte Antonio Vieiro:
> Hi all,

Hi!

> I would like to build a small s-expression ([1]) library in Lua (5.1),
> so I need to design cons-cells ([2]) first.
>
> I would appreciate some advice in the design of the cons-cells. I am
> thinking of two approaches:
>
> A) Design cons-cells as Lua tables, in plain Lua, with a "car" and a
> "cdr" being other Lua objects (possibly other cons-cells).
> B) Design cons-cells as a C structure (Lua allocated and garbage
> collected with a __gc metamethod), that keeps references to other Lua
> objects using luaL_ref and luaL_unref (possibly with references to other
> cons-cells).

C) Use closures for cons-cells. See [3].
D) Similar to A, but use the keys `1` and `2` (i.e. the array part of 
the table) for head and tail.

`cons`, `car`, `cdr`, `setcar`, and `setcdr` are the only functions that 
need to know the difference, so you can even change the implementation 
later ...

Memory per cons-cell in bytes (as reported by `collectgarbage"count"`):
table-based Lua 5.x:   144
table-based LuaJIT:     80
closure-based Lua 5.1: 136
closure-based Lua 5.2: 128
closure-based LuaJIT:   76
array-based Lua 5.x:    96
array-based LuaJIT:     56

> I am thinking that approach B is going to be more performant and consume
> less memory. These are my assumptions:
>
> 1. B is better because using a Lua table as a cons cell is too heavy
> memory-wise.
> 2. B Is better because I can abuse LUA_REGISTRYINDEX to store references
> to Lua objects, that's better than having as many Lua tables in memory.
> 3. LuaJIT will be as performant in approach B (invoking C functions for
> "car", "cdr", etc.) as in approach A (using Lua native code).
> 4. There's no problem in having circular dependencies using luaL_ref's
> between different cons cells, because the Lua GC will detect that and
> cleanse cons-cells appropriately.
>
> Am I right in these assumptions? I'm a little worried about point 4.

With good reason. You are basically putting reference counting on top of 
garbage collection. Reference counting cannot handle cycles, so the 
cycles never become garbage. Even if you have chains instead of cycles 
you probably need multiple garbage collection runs before the whole 
chain is collected (the `__gc` function has to run before the garbage 
collector can realize that the next cons-cell may be collected as well). 
So I would advise against B even if you can make sure that there will be 
no cycles.

> Thanks in advance,
> Antonio

Philipp


> [1] http://en.wikipedia.org/wiki/S-expressions
> [2] http://en.wikipedia.org/wiki/Cons

  [3]: http://permalink.gmane.org/gmane.comp.lang.lua.general/104428