New Garbage Collector http://wiki.luajit.org/New-Garbage-Collector

GC Algorithms

This is a short overview of the different GC algorithms used in Lua 5.x and LuaJIT 1.x/2.0 as well as the proposed new GC in LuaJIT 3.0.

All of these implementations use a tracing garbage collector (#) with two basic phases:

The mark phase starts at the GC roots (e.g. the main thread) and iteratively marks all reachable (live) objects. Any objects that remain are considered unreachable, i.e. dead.
The sweep phase frees all unreachable (dead) objects.

Any practical GC implementation has a couple more phases (e.g. an atomic phase), but this is not relevant to the following discussion. To avoid a recursive algorithm, a mark stack or mark list can be used to keep track of objects that need to be traversed.

Note that most of the following is just describing well-established techniques. Please refer to the literature on garbage collection for details.

_{(#) 'Tracing' in this context means it's tracing through the live object graph, as opposed to a reference counting garbage collector, which manages reference counts for each object. The terminology is not related to the concept of a trace compiler.}