Generational Garbage Collector

[Inny]

This thread is on the Lua mailing list today:

Is anyone using the generational mode for the garbage collection in
Lua 5.2.1?

We received very little feedback about the generational mode since it
was introduced in Lua 5.2. In our own experiments the generational mode
did not show relevant advantages (although it is still hard for us to
find real Lua programs where to test that kind of stuff). As it is a big
source of complexity for the collector, we are considering whether it is
worth keeping it in Lua.

-- Roberto

With upgrading to 5.2 on the (distant) horizon, is this going to have any impact on love?

[dreadkillz]

What is the advantage of the generational collector vs the default collector? I like Lua's ability to auto manage memory as it is.

[Inny]

I don't know the exact details on how the Lua collector is implemented, but let me give you a little primer on garbage collection. I'm going to use the term object here, because Lua has several types of objects (tables, functions, strings, love's userdata, etc).

Mark and Sweep
Also known as "Stop The World", the idea behind this style of garbage collection is that the interpreter is completely halted while garbage collection occurs. It works by working through the entire state of the interpreter in two phases to find out which objects are still inside variables. The "Mark" phase is when every object in the interpreter is marked as "Visible". Then, during the "Sweep" phase, everything not contained in a variable is marked as "Garbage." Then, every piece of garbage is returned back to the operating system for use elsewhere.

This method is perfect, except for one hangup: it's slow. In terms of real-time performance, a full cycle of garbage collection would halt your game for anywhere between several frames and several seconds.

Tri-Color Marking
Also known as "Incremental Mark and Sweep." The idea with this one is that instead of "Visible" and "Garbage" states, we have three colors White, Black, and Grey. White objects might be garbage. Black object aren't garbage. Grey objects are visible. When you make an object, it starts its life in the White group. When you assign an object to a variable, it moves into the Grey group. When you nil a variable, then the object that was there moves back into the White group. Then, periodically, you perform a Mark and Sweep garbage collection cycle. The way this is done is by picking an object from the Grey group, and marking every object it contains as Black. Every once in a while, the Grey set will be empty, and the White group will be full of garbage, which you can return to the operating system.

Lua 5.1 uses this form of garbage collection. It has good performance characteristics because you don't have to stop the world to work with it, you just have to keep track of the size of the White group and keep checking objects in the Grey group. When the white group gets too large, then Lua finishes checking the Grey group. You can watch this happen if you keep printing the output of collectgarbage("count") on the screen.

Generational Garbage
Also known as Ephemeral. The way it works is by observing the knowledge that some items when made will stick around for a long time (like the player, sprites, text on screen, levels, etc.) and other objects will be made garbage quickly (like the objects that pairs and ipairs create). Objects are born in the Infant pool, and on each garbage collection cycle that they survive, are promoted into the next pool of life. The garbage collector is much more aggressive with the objects that are both in the Infant Pool and the Grey pool, while mostly ignoring objects in the older pools.

This one is new in Lua 5.2 and not in Love2d yet. The value of this collection method is that apps and games use less memory overall, while gaining the performance benefit of not having to keep having check and recheck objects that are staying around for the life of the program.


So, the reason that the Lua maintainers are looking to remove it is because nobody actually has benchmark or performance numbers about the new collector. Lua is a very simple language, both in the syntax of its grammar, and in the implementation of its interpreter. Apparently the Generational collector is really complex and might not be necessary, and the incremental collector might perform just as well as the generational collector given all of the places that Lua runs.

The reason I brought this up in the first place is to see if anyone had any opinions on it, or if anyone might see how it would affect us. Roberto Ierusalimschy would probably be more than receptive to any hard data or use-cases.

I personally can't decide if Generational GC in Lua is a good thing or a bad thing. I mean, if they can get the performance claims, then yeah, keep it. If they can't, then lose it. Right?

[dreadkillz]

Oh that's over my head. You know a lot about this. Perhaps you could do your own testing and share with the mailing list?

[Xgoff]

generational would be awesome for vectors etc (to an extent). i dunno if 5.2's gc's generational mode is also incremental, or stop-the-world... if it's the latter then i would imagine the pausing would eat up any advantages you'd get from the generational mode.

Mike Pall has already mentioned that lua's gc just doesn't handle large numbers of objects very efficiently anyway... which is what a generational gc should help with, but so far apparently doesn't. maybe the implementation is just not good/clever enough? lua's kinda lagging behind in gc performance nowadays, apparently, enough that luajit's getting a new gc in the next version (the current gc is more or less the same one the standard interpreter uses)

[kikito]

I'm inclined to think that the guys who are really worried about performance, the ones who would be able to provide useful feedback regarding gc, are just using Luajit.

[Inny]

I'm inclined to think that the guys who are really worried about performance, the ones who would be able to provide useful feedback regarding gc, are just using Luajit.

That's a really good observation. I know there was some luajit talk in the thread about upgrading to lua5.2, and it's important to note that LuaJit uses a variant of Tri-Color Marking (called Quad-Color Optimized Incremental Mark & Sweep), and skip out on Generational GC.

[tv_user]

Wow, nice explanation about garbage collecting Inny!
Now that I understand something about it (thanks xD) I agree with you: Lua being such a simple language, if the generational garbage collector ends up being too much for it (like "killing a fly with a shotgun"), we should ditch it.