RE: incremental garbage collector?

[David Bhowmik <david.bhowmik@...>]

Hello,

we have been using lua for our game engine too. The thing about the lua user
data types is that that for every user data type you create it will create a
marker structure and place it in a link list for use later with garbage
collection etc. Each marker structure is malloced and freed and kept in a
pool, but when the number of markers in use shrinks by a binary order of
magnitude the free pool is shrunk. If you are creating loads of user data
types and and destroying them a lot then this shrinking and growing will
occur a lot. The same thing occurs for lua strings. The minimum pool size is
hard wired to be 10 (dont know why, or why so small). Any way below is an
example patch to increase the pool size and so stop all the malloc and
freeing.

We have got lua malloced stuff under memory management too. This is
particularly good for the TString structures that are used as the markers in
the above mentioned list and are malloced and freed a lot. Mail me if you
wish to know more.

hope that is of some help


Dave


#define STRING_MIN_POOLSIZE whatever you want
#define USERDATATYPE_MIN_POOLSIZE whatever you want

void collectstrings (lua_State *L, int all) {
  int i;
  for (i=0; i<L->strt.size; i++) {  /* for each list */
    TString **p = &L->strt.hash[i];
    TString *next;
    while ((next = *p) != NULL) {
      if (next->marked && !all) {  /* preserve? */
        if (next->marked < FIXMARK)  /* does not change FIXMARKs */
          next->marked = 0;
        p = &next->nexthash;
      } 
      else {  /* collect */
        *p = next->nexthash;
        L->strt.nuse--;
        L->nblocks -= sizestring(next->len);
        luaM_free(L, next);
      }
    }
  }
  checktab(L, &L->strt, STRING_MIN_POOLSIZE);
}



void collectudata (lua_State *L, int all) {
  int i;
  for (i=0; i<L->udt.size; i++) {  /* for each list */
    TString **p = &L->udt.hash[i];
    TString *next;
    while ((next = *p) != NULL) {
      LUA_ASSERT(next->marked <= 1, "udata cannot be fixed");
      if (next->marked && !all) {  /* preserve? */
        next->marked = 0;
        p = &next->nexthash;
      } 
      else {  /* collect */
        int tag = next->u.d.tag;
        *p = next->nexthash;
        next->nexthash = L->TMtable[tag].collected;  /* chain udata */
        L->TMtable[tag].collected = next;
        L->nblocks -= sizestring(next->len);
        L->udt.nuse--;
      }
    }
  }
  checktab(L, &L->udt, USERDATATYPE_MIN_POOLSIZE);
}



static void checktab (lua_State *L, stringtable *tb, int minPoolSize) {
  if (tb->nuse < (lint32)(tb->size/4) && tb->size > minPoolSize)
    luaS_resize(L, tb, tb->size/2);  /* table is too big */
}


-----Original Message-----
From: paul@theV.net [mailto:paul@theV.net]
Sent: 05 March 2002 10:32
To: Multiple recipients of list
Subject: incremental garbage collector?


Hi the list,

Sorry to raise this overly discussed topic again, but I'd
believe there has to be some real solution to embed lua in a
real-time environment, I mean, eventually.

We are using Lua extensively in building our game, including
the main loop, the entire GUI, and almost everything is written
in Lua. As the code explodes, we are finding that sometimes
lua's GC takes 2 seconds! So we change to force the GC every 4
seconds, which results in a GC time around 60ms to 130ms, which
is tolerable, but I wouldn't say satisfactory.

So my question is, is there anybody currently working on a
incremental GC patch or something? Just in case somebody is
already working on it, I don't want to reinvent the wheel :)

Otherwise, I'd like to make a proposal to accelerate the
progress. The good news is, a guy in our team has internally
coded a GC library that does incremental mark-and-sweep, and we
don't mind opening our code; the bad news is, the library is
freshly made from scratch with no much similarity to Lua's
internal, so expect a lot of work to be done.

The solution I have in mind is either

    1) to wrap of Lua's bytecode core around our GC lib
       and maintain bytecode compatibility;
or
    2) using our GC lib as a reference implementation to
       adapt Lua's current GC code to a incremental one;

Unfortunately, solution 1) is going to cause a fork in Lua,
which is something probably nobody wants to see.

Our team is currently pretty tied up, and we aren't in the
position to volunteer as a lead of this project. I am seeking
any opinions or suggestions on this issue, and of course, Lua's
author is best to comment on this.

Regards,
.paul.