fast metamethods (was: lua hacking wondering)

["Thiago Bastos" <hellraider@...>]

> > This is the impression I'm under as well, but I was wondering: since
> > these entries in the metatable (the metamethods that is) are used by the
> > VM it wouldn't be too ugly to keep a number of flags with each
> > table/userdata for storing wich (of the "standard") metamethods have
> > been set in it's metatable. Then every time, say, an index operation
> > takes place all you have to do is check if the index flag is set (a very
> > cheap operation) instead of looking up the metatable and indexing it.
> 
> Actually I think this is roughly how it's implemented in reality.

This is done but not for all metamethods. Only a subset (the most common
metamethods) is cached. Moreover, IIRC this scheme only optimizes 'misses',
that is, the flags records when a metamethod does NOT exist.

I have developed an automatic C++ binding generator (similar to toLua,
although its mechanics and implementation are completely different). It's
targeted at time-critical/real-time applications, such as games; designed
for systems where the core functionality is programmed in C++ and the
application logic is scripted in Lua.

Since my bindings make intensive use of metamethods, I had to optimize the
way metamethods interface with the C API.

My solution was only for full userdatas (not tables), which is what my games
needed; it's 100% backward compatible, but requires the use of some internal
Lua functions.

By default, full userdatas keep a reference to their metatables:

struct {
  ...
  struct Table *metatable;
  ...
} Udata;

What I have done is introduce a new field in the structure, which is used
instead of the metatable for invoking metamethods:

struct {
  ...
  struct Table *metatable;
  const TObject *fastTM;
  ...
} Udata;

The field 'fastTM' is an array of Lua objects, which is indexed from
TM_INDEX to TM_CALL (constants defined in ltm.h). Each table entry can be
set to point to a C closure, for example.

Then I changed the way metamethods are invoked, for full userdatas, in
ltm.c. Originally:

case LUA_TUSERDATA:
  return luaH_getstr(uvalue(o)->uv.metatable, ename);

Patched (lookup is made at the fastTM table first, if it is available):

case LUA_TUSERDATA:
  if( uvalue(o)->uv.fastTM ) {
    /* if a fastTM table is available, use it instead of the metatable */
    const TObject *method = &uvalue(o)->uv.fastTM[event];
    return ( method->tt == LUA_TNONE ? &luaO_nilobject : method );
  }
  return luaH_getstr(uvalue(o)->uv.metatable, ename);


My binding generator transparently generates internal Lua structures and
calls that make use of this fastTM mechanism, to generate much faster and
lighter bindings. The user himself knows nothing about it, so to port my
games to new Lua versions I only have to change the binding generator.

I believe that, if polished, this mechanism could be incorporated into the
official Lua API, as a way to optimize metamethods for full-userdatas.

I believe that 90% of the time, programmers create metatables for their
userdatas just to define metamathods (and nothing else). This patch allows
an alternative and much more efficient way of defining these metamethods.

By the way, the addition of the fastTM field in the Udata structure does not
impose additional memory usage, since that structure had some wasted space
available (due to alignment/union issues). So this functionality comes
virtually for free, I guess.

I have attached a diff file for the patch (against Lua 5.0.1).

PS: I plan to release my binding generator under an open-source license as
soon as I have some spare time. Game developers might find it useful.

-- Thiago Bastos

Attachment: fastTM.patch
Description: Binary data