Cons, tuple and __slots__ -- a simple mechanism to implement them in Lua

[Xavier Wang <weasley.wx@...>]

hi list :)

I'm very sad that nobody reply my last post[1], even Roberto didn't.
patch-ev is a very simple and powerful improve for Lua. It fills the
space between simple type such as number and string and the only
complex type table. It's very useful for embedded device that don't
have much memory. this post is a simple introduction for patch-ev and
a document for the four function the patch. I know Lua is the own
language for Roberto, but if you reject this feature, can you give
some reason about it? I mean, this is a very simple change, not more
than 50 loc changed. and it introduces many powerful ability for Lua.
Also I hope all of us in list can comment it. thank you :)

patch-ev is addition to the core of Lua, it adds multi user values
support to Lua's userdata. It means, now userdata can attachment more
than one table values with it. it's more lightweight than table, that
is the most important point. a naked Lua table need 56 bytes to manage
both the array part and hash part of itself. but patch-ev only need 8
bytes for a naked userdata. the 1/7 of table.

multi user values can use to implement tuples[2], its much lightweight
than table, and faster than table, and has a well-defined length of
it. think this Lua code:

local t = tuple(1,2,3)
print(t[1], t[2], t[3]) --> 1   2   3

a tuple above only use 44 bytes (8 bytes for a header, 4 bytes for a
metatable pointer, 4 bytes for a length of userdata, 4 bytes for a
length of user values, and there 24 bytes for three Value structs),
it's even smaller than a empty table! and it only support indexing or
(not and!) hashing, so it's much faster than normal table.

to implement a typed-tuple (or __slots__ in Python) also very easy,
think about this:

local newtypetuple = typetuple("a", "b", "c")
local tt = newtypetuple(1,2,3)
print(tt.a, tt.b, tt.c)

tt has the same of t, but you can use a "proto" to use hashing like
syntax to indexing it. it much faster and smaller than normal hash
table (it's not a real hash table).


I write this patch is for several reason: first, I want implment a
line-to-line scheme language transfer for Lua. But use table to
implement cons of lisp is wasteful, so I think about a more
lightweight way to do it. but I can't contain Lua Values outside of
Lua, So the only way is to change the core of Lua, and this is a
minimized changes to implement such in Lua. think of this:

local c = cons(1, cons(2, cons(3, cons())
local d = list(1,2,3)
assert(c:car() == d:car())

another motivation is my work, a MMORPG game written in Lua, it runs
on Symbian cellphone that only have 20M memory,  it parses online data
to Lua's table, and its very waste memory (use about 2M to store the
result of protocol data), I want to implement a more lightweight
struct to do this, and tuple (typetuple) is a natural selection. it
pushs me to think about how to implement a light weight but generic
container in Lua.

another reason is the garbage collection, Lua don't allow custom
collection and don't allow values outside of it, this is a good
feature, but it makes write C/C++  binding more difficultly, you must
use table to indicate the dependency of values, use multi user values
is more easy than use a global table in registry of Lua.

the advantage of ev:
- don't change any of existing interface of Lua C-API.
- don't change any semantics of Lua.
- much faster and smaller than table.
- fills the space of the huge data structure and the simple data type.

the disadvantage of ev:
- only support fixed length of multi user values (that is, you can not
change the size of values after allocation a new userdata).
- need patch to core of Lua.
- need the approve of Roberto :(

Thank all of you to read this such a long post, and hopes Robert can
reply this post. thank all of you :)


- Xavier Wang

[1] http://lua-users.org/lists/lua-l/2011-09/msg00038.html
[2] http://en.wikipedia.org/wiki/Tuple

Attachment: lua-ev.patch
Description: Binary data