Re: Lua's GC in interactive applications (games)... feedback appreciated!

["Jonathan Branam" <sspeare@...>]

Comments below:
From: "John Belmonte" <jvb@prairienet.org>
> Jonathan Branam wrote:
> > I am trying to get some feedback on a number of work-arounds that I am
> > considering.
> >
> > 1) I could run the GC manually, and have it take a set amount of time.
> > This way I could run it every couple seconds or so, but not let it take
> > too long.
> > I can use the built-in feedback to find out if I need to run it more
> > often.
>
> With Lua's garbage collector, you can't control how much time a gc cycle
> takes, other than indirectly by controlling the number of objects in the
> system.  In other words, the length of a gc cycle would not be affected by
> how often you forced a cycle.  (This is assuming your ratio of
> live-to-garbage objects is high.)

Sorry, yes I realize that. I should have said "if you could."

> > 2) Avoid operations which cause orphans.
> > 3) Extend Lua so that my new types are "built-in" such as the Number
type.
>
> a gc cycle length is not only related to
> how many garbage objects you've produced since the last cycle, but the
total
> number of all objects (whether they are being used or not).

This is very true, I was a little misguided on those. However, making new
types
built-in does reduce the number of total objects. This is a big win for me,
because
I will have 8+ vectors and such for every object in my game.

>
> > 4) Extend Lua's GC to be use more "active" ref counting.
>
> I think Lua's mark-and-sweep collection is fine, it just needs to be made
> incremental.  I say "just", but it's probably not a few-day (or few-week)
> project.  Switching to reference counting is more of a sideways step than
an
> improvement, and will take just as much work.

I am definitely beginning to agree here. The refcount was just my first
stab,
it really does not seem like a viable solution in general. I've been looking
at
what is needed to make it incremental, and it seems like a rather large task
as well. It seems like the current stack will change a lot as lua code is
running,
and this is one of the "roots" of the GC. Of course, the global table may
not
change too much. It also requires a write barrier. I am thinking setglobal()
and
settable() will fulfill this requirement somewhat.

> Regards,
> -John
>
> p.s.  also see my posting "dream garbage collector"

I went back and read all the posts I could find, many have similar requests.
In the end, it seems an incremental solution is likely the best. I'm not
sure how
much will change between each incremental call, but it does seem to me that
these algorithms must be called fairly often to get anywhere and they have a
big payoff moment when they are done with everything.

[I am talking about tricolor mark-sweep implementations here, Lua's is not
this way. In these white means currently considered garbage, grey means
the object is not garbage, but all of its links have not yet been traversed,
and
black means it is not garbage and all of its links have been traversed]

I was thinking about the total number of objects problem. It seems like
there
are a few things which could help this. One would be if you could only
reprocess objects which have changed since the last full run of the GC.
After a collection, these tricolor algorithms mark everything as white
again and then start over, but this does not really seem necessary to me.
It seems like, if the write-barrier works properly, that you would never
need to mark everything white and start over.

Another idea that occurs to me is to have some sort of a "static" or "const"
table which never needs to be reprocessed. I will have lots of data such as
this which is purely used for configuration. This could be achieved
automatically by my previous suggestion. It seems that this would do a
great deal to aid the total number of objects problem.

If this were simple, I suppose the answer would already exist!
-Jonathan