2.10 – Garbage Collection

Lua performs automatic memory management. This means that you have to worry neither about allocating memory for new objects nor about freeing it when the objects are no longer needed. Lua manages memory automatically by running a garbage collector from time to time to collect all dead objects (that is, objects that are no longer accessible from Lua). All memory used by Lua is subject to automatic management: tables, userdata, functions, threads, strings, etc.

---

补充：

Since its first version until version 5.0, Lua always used a simple mark-andsweep garbage collector. This collector is sometimes called a “stop-the-world” collector. This means that, from time to time, Lua stops interpreting the main program to perform a whole garbage-collection cycle. Each cycle comprises four phases: mark, cleaning, sweep, and finalization.

Lua starts the mark phase marking as alive its root set, the objects that Lua has direct access to: the registry and the main thread. Any object stored in a live object is reachable by the program, and therefore is marked as alive too. The mark phase ends when all reachable objects are marked as alive.

Before starting the sweep phase, Lua performs the cleaning phase, which is related to finalizers and weak tables.

First, it traverses all userdata looking for non-marked userdata with a __gc metamethod; those userdata are marked as alive and put in a separate list, to be used in the finalization phase.

Second, Lua traverses its weak tables and removes from them all entries wherein either the key or the value is not marked.

The sweep phase traverses all Lua objects. (To allow this traversal, Lua keeps all objects it creates in a linked list.) If an object is not marked as alive, Lua collects it. Otherwise, Lua clears its mark, in preparation for the next cycle.

The last phase, finalization, calls the finalizers of the userdata that were separated in the cleaning phase. This is done after the other phases to simplify error handling. A wrong finalizer may throw an error, but the garbage collector cannot stop during other phases of a collection, at the risk of leaving Lua in an inconsistent state. If it stops during this last phase, however, there is no problem: the next cycle will call the finalizers of the userdata that were left in the list.

With version 5.1 Lua got an incremental collector. This new incremental collector performs the same steps as the old one, but it does not need to stop the world while it runs. Instead, it runs interleaved with the interpreter. Every time the interpreter allocates some fixed amount of memory, the collector runs a small step. This means that, while the collector works, the interpreter may change an object’s reachability. To ensure the correctness of the collector, some operations in the interpreter have barriers that detect dangerous changes and correct the marks of the objects involved.

To avoid too much complexity, the incremental collector performs some operations atomically; that is, it cannot stop while performing those operations. In other words, Lua still “stops the world” during an atomic operation. If an atomic operation takes too long to complete, it may interfere with the timing of your program. The main atomic operations are table traversal and the cleaning phase.

The atomicity of table traversal means that the collector never stops while traversing a table. This can be a problem only if your program has a really huge table. If you have this kind of problem, you should break the table in smaller parts. (That may be a good idea even if you do not have problems with the garbage collector.) A typical reorganization is to break the table hierarchically, grouping related entries into subtables. Notice that what matters is the number of entries in the table, not the size of each entry.

The atomicity of the cleaning phase implies that the collector collects all userdata to be finalized and clears all weak tables in one step. This can be a problem if your program has huge quantities of userdata or huge numbers of entries in weak tables (either in a few large weak tables or in countless weak tables).

---

Lua implements an incremental mark-and-sweep collector. It uses two numbers to control its garbage-collection cycles: the garbage-collector pause and the garbage-collector step multiplier. Both use percentage points as units (so that a value of 100 means an internal value of 1).

The garbage-collector pause controls how long the collector waits before starting a new cycle. Larger values make the collector less aggressive. Values smaller than 100 mean the collector will not wait to start a new cycle. A value of 200 means that the collector waits for the total memory in use to double before starting a new cycle.

---

补充：

The pause parameter controls how long the collector waits between finishing a collection and starting a new one. Lua uses an adaptive algorithm to start a collection: given that Lua is using m Kbytes when a collection ends, it waits until it is using m*pause Kbytes to start a new collection. So, a pause of 100% starts a new collection as soon as the previous one ends. A pause of 200% waits for memory usage to double before starting the collector; this is the default value. You can set a lower pause if you want to trade more CPU time for lower memory usage. Typically, you should keep this value between 100% and 300%.

---

The step multiplier controls the relative speed of the collector relative to memory allocation. Larger values make the collector more aggressive but also increase the size of each incremental step. Values smaller than 100 make the collector too slow and can result in the collector never finishing a cycle. The default, 200, means that the collector runs at “twice” the speed of memory allocation.

---

补充：

The stepmul parameter controls how much work the collector does for each kilobyte of memory allocated. The higher this value the less incremental is the collector. A huge value like 100000000% makes the collector work like a nonincremental collector. The default value is 200%. Values lower than 100% make the collector so slow that it may never finish a collection.

---

You can change these numbers by calling lua_gc in C or collectgarbage in Lua. With these functions you can also control the collector directly (e.g., stop and restart it).

---

补充：

Lua offers an API that allows us to exert some control over the garbage collector.
From C we use lua_gc:

int lua_gc (lua_State *L, int what, int data);

From Lua we use the collectgarbage function:

collectgarbage(what [, data])

Both offer the same functionality. The what argument (an enumeration value in C, a string in Lua) specifies what to do. The options are:
LUA_GCSTOP (“stop”): stops the collector until another call to collectgarbage (or to lua_gc) with the option “restart”, “collect”, or “step”.

LUA_GCRESTART (“restart”): restarts the collector.

LUA_GCCOLLECT (“collect”): performs a complete garbage-collection cycle, so that all unreachable objects are collected and finalized. This is the default option for collectgarbage.

LUA_GCSTEP (“step”): performs some garbage-collection work. The amount of work is given by the value of data in a non-specified way (larger values mean more work).

LUA_GCCOUNT (“count”): returns the number of kilobytes of memory currently in use by Lua. The count includes dead objects that were not collected yet.

LUA_GCCOUNTB (not available): returns the fraction of the number of kilobytes of memory currently in use by Lua.

In C, the total number of bytes can be computed by the next expression (assuming that it fits in an int):

lua_gc(L, LUA_GCCOUNT, 0)*1024 + lua_gc(L, LUA_GCCOUNTB, 0)

In Lua, the result of collectgarbage(“count”) is a floating-point number, and the total number of bytes can be computed as follows:

collectgarbage("count") * 1024

So, collectgarbage has no equivalent to this option.

LUA_GCSETPAUSE (“setpause”): sets the collector’s pause parameter. The value is given by data in percentage points: when data is 100 the parameter is set to 1 (100%).

LUA_GCSETSTEPMUL (“setstepmul”): sets the collector’s stepmul parameter. The value is given by data also in percentage points.

The other options of lua_gc give you more explicit control over the collector.

Games are typical clients for this kind of control. For instance, if you do not want any garbage-collection work during some periods, you can stop it with a call collectgarbage(“stop”) and then restart it with collectgarbage(“restart”).

In systems where you have periodic idle phases, you can keep the collector stopped and call collectgarbage(“step”,n) during the idle time. To set how much work to do at each idle period, you can either choose experimentally an appropriate value for n or calls collectgarbage in a loop, with n set to zero (meaning small steps), until the period expires.

---

2.10.1 – Garbage-Collection Metamethods

Using the C API, you can set garbage-collector metamethods for userdata (see §2.8). These metamethods are also called finalizers. Finalizers allow you to coordinate Lua’s garbage collection with external resource management (such as closing files, network or database connections, or freeing your own memory).

Garbage userdata with a field __gc in their metatables are not collected immediately by the garbage collector. Instead, Lua puts them in a list. After the collection, Lua does the equivalent of the following function for each userdata in that list:

     function gc_event (udata)
       local h = metatable(udata).__gc
       if h then
         h(udata)
       end
     end

At the end of each garbage-collection cycle, the finalizers for userdata are called in reverse order of their creation, among those collected in that cycle. That is, the first finalizer to be called is the one associated with the userdata created last in the program. The userdata itself is freed only in the next garbage-collection cycle.

2.10.2 – Weak Tables

A weak table is a table whose elements are weak references. A weak reference is ignored by the garbage collector. In other words, if the only references to an object are weak references, then the garbage collector will collect this object.

A weak table can have weak keys, weak values, or both. A table with weak keys allows the collection of its keys, but prevents the collection of its values. A table with both weak keys and weak values allows the collection of both keys and values. In any case, if either the key or the value is collected, the whole pair is removed from the table.

The weakness of a table is controlled by the __mode field of its metatable. If the __mode field is a string containing the character ‘k’, the keys in the table are weak. If __mode contains ‘v’, the values in the table are weak.

After you use a table as a metatable, you should not change the value of its __mode field. Otherwise, the weak behavior of the tables controlled by this metatable is undefined.

---

补充：

A garbage collector can collect only what it can be sure is garbage; it cannot guess what you consider garbage.

A typical example is a stack, implemented with an array and an index to the top. You know that the valid part of the array goes only up to the top, but Lua does not. If you pop an element by simply decrementing the top, the object left in the array is not garbage for Lua. Similarly, any object stored in a global variable is not garbage for Lua, even if your program will never use it again. In both cases, it is up to you (i.e., your program) to assign nil to these positions so that they do not lock an otherwise free object.

However, simply cleaning your references is not always enough. Some constructions need extra collaboration between the program and the collector.

A typical example happens when you want to keep a collection of all live objects of some kind (e.g., files) in your program. This task seems simple: all you have to do is to insert each new object into the collection. However, once the object is inside the collection, it will never be collected! Even if no one else points to it, the collection does. Lua cannot know that this reference should not prevent the reclamation of the object, unless you tell Lua about this fact.

Weak tables are the mechanism that you use to tell Lua that a reference should not prevent the reclamation of an object. A weak reference is a reference to an object that is not considered by the garbage collector. If all references pointing to an object are weak, the object is collected and somehow these weak references are deleted. Lua implements weak references as weak tables: A weak table is a table whose entries are weak. This means that, if an object is held only inside weak tables, Lua will eventually collect the object.

Tables have keys and values, and both may contain any kind of object. Under normal circumstances, the garbage collector does not collect objects that appear as keys or as values of an accessible table. That is, both keys and values are strong references, as they prevent the reclamation of objects they refer to. In a weak table, keys and values may be weak. This means that there are three kinds of weak tables: tables with weak keys, tables with weak values, and fully weak tables, where both keys and values are weak. Irrespective of the table kind, when a key or a value is collected the whole entry disappears from the table .

例子：弱表

-- 创建一个弱表
local weakTable = setmetatable({}, {__mode = "v"})  -- "v" 表示值是弱引用

-- 创建一个对象
local obj = {name = "some object"}

-- 将对象插入到弱表中
weakTable[1] = obj

-- 此时，obj 还存在于 weakTable 中，并且没有其他引用指向它
print(weakTable[1].name)  -- 输出: some object

-- 删除强引用
obj = nil

-- 因为 obj 没有其他强引用，Lua 会在下一次垃圾回收时回收它
collectgarbage()  -- 强制进行垃圾回收

-- 现在，weakTable[1] 会变成 nil，因为 obj 被回收
print(weakTable[1])  -- 输出: nil

例子：弱表

a = {}
b = {__mode = "k"}
setmetatable(a, b) -- now ’a’ has weak keys
key = {} -- creates first key
a[key] = 1
key = {} -- creates second key
a[key] = 2
collectgarbage() -- forces a garbage collection cycle
for k, v in pairs(a) do print(v) end
--> 2

Notice that only objects can be collected from a weak table. Values, such as numbers and booleans, are not collectible. For instance, if we insert a numeric key in table a (from our previous example), it will never be removed by the collector. Of course, if the value corresponding to a numeric key is collected, then the whole entry is removed from the weak table.

From the programmer’s point of view, string s are values, not objects. Therefore, like a number or a boolean, a string is not removed from weak tables (unless its associated value is collected).

A common programming technique is to trade space for time. You can speed up some functions by memoizing their results so that, later, when you call the function with the same argument, it can reuse the result.

例子：

-- the server can memoize the results from loadstring using an auxiliary table.
local results = {}
-- The savings with this scheme can be huge. However, it may also cause unsuspected waste.
-- A weak table providesa simple solution to this problem. If the results table has weak values, each
-- garbage-collection cycle will remove all translations not in use at that moment
-- (which means virtually all of them)
setmetatable(results, {__mode = "v"}) -- make values weak

function mem_loadstring (s)
    local res = results[s]
    if res == nil then -- result not available?
        res = assert(loadstring(s)) -- compute new result
        results[s] = res -- save for later reuse
    end
    return res
end

The memoize technique is useful also to ensure the uniqueness of some kind of object. For instance, assume a system that represents colors as tables, with fields red, green, and blue in some range. A naive color factory generates a new color for each new request:

function createRGB (r, g, b)
    return {red = r, green = g, blue = b}
end

Using the memoize technique, we can reuse the same table for the same color. To create a unique key for each color, we simply concatenate the color indices with a separator in between:

local results = {}
setmetatable(results, {__mode = "v"}) -- make values weak
function createRGB (r, g, b)
    local key = r .. "-" .. g .. "-" .. b
    local color = results[key]
    if color == nil then
        color = {red = r, green = g, blue = b}
        results[key] = color
    end
    return color
end

An interesting consequence of this implementation is that the user can compare colors using the primitive equality operator, because two coexistent equal colors are always represented by the same table.

Another important use of weak tables is to associate attributes with objects. There are endless situations where we need to attach some attribute to an object: names to functions, default values to tables, sizes to arrays, and so on.

In all these cases, we need an alternative way to associate attributes to objects. Of course, an external table provides an ideal way to associate attributes to objects (it is not by chance that
tables are sometimes called associative arrays). We use the objects as keys, and their attributes as values. An external table can keep attributes of any type of object, as Lua allows us to use any type of object as a key. Moreover, attributes kept in an external table do not interfere with other objects, and can be as private as the table itself.

However, this seemingly perfect solution has a huge drawback: once we use an object as a key in a table, we lock the object into existence. Lua cannot collect an object that is being used as a key. If we use a regular table to associate functions to its names, none of these functions will ever be collected. As you might expect, we can avoid this drawback by using a weak table. This time,
however, we need weak keys. The use of weak keys does not prevent any key from being collected, once there are no other references to it. On the other hand, the table cannot have weak values; otherwise, attributes of live objects could be collected.

How to implement tables with non-nil default values.

In the first solution, we use a weak table to associate to each table its default value:

local defaults = {}
setmetatable(defaults, {__mode = "k"})
local mt = {__index = function (t) return defaults[t] end}
function setDefault (t, d)
    defaults[t] = d
    setmetatable(t, mt)
end

In the second solution, we use distinct metatables for distinct default values, but we reuse the same metatable whenever we repeat a default value. This is a typical use of memoizing:

local metas = {}
setmetatable(metas, {__mode = "v"})
function setDefault (t, d)
    local mt = metas[d]
    if mt == nil then
        mt = {__index = function () return d end}
        metas[d] = mt -- memoize
    end
    setmetatable(t, mt)
end

We use weak values, in this case, to allow the collection of metatables that are not being used anymore.

If your application has thousands of tables with a few distinct default values, the second implementation is clearly superior. On the other hand, if few tables share common defaults, then you should favor the first implementation.

---