23 Garbage

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

However, simply cleaning our references is not always enough. Some constructions need extra collaboration between the program and the collector. A typical example happens when we want to keep a list of all live objects of some kind (e.g., files) in our program. This task seems simple: all we have to do is to insert each new object into the list. However, once the object is part of the list, it will never be collected! Even if nothing else points to it, the list does. Lua cannot know that this reference should not prevent the reclamation of the object, unless we tell Lua about this fact.

Weak tables are the mechanism that we 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 collector will collect the object and delete these weak references. Lua implements weak references through weak tables: a weak table is a table whose entries are weak. This means that, if an object is held only in weak tables, Lua will eventually collect the object.

Tables have keys and values, and both can 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, both keys and values can be weak. This means that there are three kinds of weak tables: tables with weak keys, tables with weak values, and tables where both keys and values are weak. Irrespective of the kind of table, when a key or a value is collected the whole entry disappears from the table.

The weakness of a table is given by the field __mode of its metatable. The value of this field, when present, should be a string: if this string is "k", the keys in the table are weak; if this string is "v", the values in the table are weak; if this string is "kv", both keys and values are weak. The following example, although artificial, illustrates the basic behavior of weak tables:

      a = {}
      mt = {__mode = "k"}
      setmetatable(a, mt)    -- 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

In this example, the second assignment key = {} overwrites the reference to the first key. The call to collectgarbage forces the garbage collector to do a full collection. As there is no other reference to the first key, Lua collects this key and removes the corresponding entry in the table. The second key, however, is still anchored in the variable key, so Lua does not collect it.

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

Strings present a subtlety here: although strings are collectible from an implementation point of view, they are not like other collectible objects. Other objects, such as tables and closures, are created explicitly. For instance, whenever Lua evaluates the expression {}, it creates a new table. However, does Lua create a new string when it evaluates "a".."b"? What if there is already a string "ab" in the system? Does Lua create a new one? Can the compiler create this string before running the program? It does not matter: these are implementation details. From the programmer’s point of view, strings are values, not objects. Therefore, like a number or a Boolean, a string key is not removed from a weak table unless its associated value is collected.

A common programming technique is to trade space for time. We can speed up a function by memorizing its results so that, later, when we call the function with the same argument, the function can reuse that result.^[21]

Imagine a generic server that takes requests in the form of strings with Lua code. Each time it gets a request, it runs load on the string, and then calls the resulting function. However, load is an expensive function, and some commands to the server may be quite frequent. Instead of calling load repeatedly each time it receives a common command like "closeconnection()", the server can memorize the results from load using an auxiliary table. Before calling load, the server checks in the table whether the given string already has a translation. If it cannot find a match, then (and only then) the server calls load and stores the result into the table. We can pack this behavior in a new function:

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

The savings with this scheme can be huge. However, it may also cause unsuspected waste. Although some commands repeat over and over, many other commands happen only once. Gradually, the table results accumulates all commands the server has ever received plus their respective codes; after enough time, this behavior will exhaust the server’s memory.

A weak table provides a 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):

      local results = {}
      setmetatable(results, {__mode = "v"})  -- make values weak
      function mem_loadstring (s)
         as before

Actually, because the indices are always strings, we can make this table fully weak, if we want:

      setmetatable(results, {__mode = "kv"})

The net result is the same.

The memorization 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 memorization, 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 = string.format("%d-%d-%d", 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. Any given color can be represented by different tables at different times, because from time to time the garbage collector clears the results table. However, as long as a given color is in use, it is not removed from results. So, whenever a color survives long enough to be compared with a new one, its representation also has survived long enough to be reused by the new color.

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.

When the object is a table, we can store the attribute in the table itself, with an appropriate unique key. (As we saw before, a simple and error-proof way to create a unique key is to create a new table and use it as the key.) However, if the object is not a table, it cannot keep its own attributes. Even for tables, sometimes we may not want to store the attribute in the original object. For instance, we may want to keep the attribute private, or we do not want the attribute to disturb a table traversal. In all these cases, we need an alternative way to map attributes to objects.

Of course, an external table provides an ideal way to map attributes to objects. It is what we called a dual representation in the section called “Dual Representation”. 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. For instance, if we use a regular table to map 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.

In the section called “Tables with default values”, we discussed how to implement tables with non-nil default values. We saw one particular technique and commented that two other techniques needed weak tables, so we postponed them. Now it is time to revisit the subject. As we will see, these two techniques for default values are actually particular applications of the two general techniques that we have just discussed: dual representation and memorization.

In the first solution, we use a weak table to map each table to 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

This is a typical use of a dual representation, where we use defaults[t] to represent t.default. If the table defaults did not have weak keys, it would anchor all tables with default values into permanent existence.

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 memorization:

      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     -- memorize
        end
        setmetatable(t, mt)
      end

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

Given these two implementations for default values, which is best? As usual, it depends. Both have similar complexity and similar performance. The first implementation needs a few memory words for each table with a default value (an entry in defaults). The second implementation needs a few dozen memory words for each distinct default value (a new table, a new closure, plus an entry in the table metas). So, 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.

A tricky situation occurs when, in a table with weak keys, a value refers to its own key.

This scenario is more common than it may seem. As a typical example, consider a constant-function factory. Such a factory takes an object and returns a function that, whenever called, returns that object:

      function factory (o)
        return (function () return o end)
      end

This factory is a good candidate for memorization, to avoid the creation of a new closure when there is one already available. Figure 23.1, “Constant-function factory with memorization” shows this improvement.

      do
        local mem = {}     -- memorization table
        setmetatable(mem, {__mode = "k"})
        function factory (o)
          local res = mem[o]
          if not res then
            res = (function () return o end)
            mem[o] = res
          end
          return res
        end
      end

There is a catch, however. Note that the value (the constant function) associated with an object in mem refers back to its own key (the object itself). Although the keys in that table are weak, the values are not. From a standard interpretation of weak tables, nothing would ever be removed from that memorizing table. Because values are not weak, there is always a strong reference to each function. Each function refers to its corresponding object, so there is always a strong reference to each key. Therefore, these objects would not be collected, despite the weak keys.

This strict interpretation, however, is not very useful. Most people expect that a value in a table is only accessible through its respective key. We can think of the above scenario as a kind of cycle, where the closure refers to the object that refers back (through the memorizing table) to the closure.

Lua solves the above problem with the concept of ephemeron tables.^[22] In Lua, a table with weak keys and strong values is an ephemeron table. In an ephemeron table, the accessibility of a key controls the accessibility of its corresponding value. More specifically, consider an entry (k,v) in an ephemeron table. The reference to v is only strong if there is some other external reference to k. Otherwise, the collector will eventually collect k and remove the entry from the table, even if v refers (directly or indirectly) to k.

Although the goal of the garbage collector is to collect Lua objects, it can also help programs to release external resources. For that purpose, several programming languages offer finalizers. A finalizer is a function associated with an object that is called when that object is about to be collected.

Lua implements finalizers through the metamethod __gc, as the following example illustrates:

      o = {x = "hi"}
      setmetatable(o, {__gc = function (o) print(o.x) end})
      o = nil
      collectgarbage()   --> hi

In this example, we first create a table and give it a metatable that has a __gc metamethod. Then we erase the only link to the table (the global variable o) and force a complete garbage collection. During the collection, Lua detects that the table is no longer accessible, and therefore calls its finalizer —the __gc metamethod.

A subtlety of finalizers in Lua is the concept of marking an object for finalization. We mark an object for finalization by setting a metatable for it with a non-null __gc metamethod. If we do not mark the object, it will not be finalized. Most code we write works naturally, but some strange cases can occur, like here:

      o = {x = "hi"}
      mt = {}
      setmetatable(o, mt)
      mt.__gc = function (o) print(o.x) end
      o = nil
      collectgarbage()   --> (prints nothing)

Here, the metatable we set for o does not have a __gc metamethod, so the object is not marked for finalization. Even if we later add a __gc field to the metatable, Lua does not detect that assignment as something special, so it will not mark the object.

As we said, this is seldom a problem; it is not usual to change metamethods after setting a metatable. If you really need to set the metamethod later, you can provide any value for the __gc field, as a placeholder:

      o = {x = "hi"}
      mt = {__gc = true}
      setmetatable(o, mt)
      mt.__gc = function (o) print(o.x) end
      o = nil
      collectgarbage()   --> hi

Now, because the metatable has a __gc field, o is properly marked for finalization. There is no problem if you do not set a metamethod later; Lua only calls the finalizer if it is a proper function.

When the collector finalizes several objects in the same cycle, it calls their finalizers in the reverse order that the objects were marked for finalization. Consider the next example, which creates a linked list of objects with finalizers:

      mt = {__gc = function (o) print(o[1]) end}
      list = nil
      for i = 1, 3 do
        list = setmetatable({i, link = list}, mt)
      end
      list = nil
      collectgarbage()
        --> 3
        --> 2
        --> 1

The first object to be finalized is object 3, which was the last to be marked.

A common misconception is to think that links among objects being collected can affect the order that they are finalized. For instance, one can think that object 2 in the previous example must be finalized before object 1 because there is a link from 2 to 1. However, links can form cycles. Therefore, they do not impose any order to finalizers.

Another tricky point about finalizers is resurrection. When a finalizer is called, it gets the object being finalized as a parameter. So, the object becomes alive again, at least during the finalization. I call this a transient resurrection. While the finalizer runs, nothing stops it from storing the object in a global variable, for instance, so that it remains accessible after the finalizer returns. I call this a permanent resurrection.

Resurrection must be transitive. Consider the following piece of code:

      A = {x = "this is A"}
      B = {f = A}
      setmetatable(B, {__gc = function (o) print(o.f.x) end})
      A, B = nil
      collectgarbage()   --> this is A

The finalizer for B accesses A, so A cannot be collected before the finalization of B. Lua must resurrect both B and A before running that finalizer.

Because of resurrection, Lua collects objects with finalizers in two phases. The first time the collector detects that an object with a finalizer is not reachable, the collector resurrects the object and queues it to be finalized. Once its finalizer runs, Lua marks the object as finalized. The next time the collector detects that the object is not reachable, it deletes the object. If we want to ensure that all garbage in our program has been actually released, we must call collectgarbage twice; the second call will delete the objects that were finalized during the first call.

The finalizer for each object runs exactly once, due to the mark that Lua puts on finalized objects. If an object is not collected until the end of a program, Lua will call its finalizer when the entire Lua state is closed. This last feature allows a form of atexit functions in Lua, that is, functions that will run immediately before the program terminates. All we have to do is to create a table with a finalizer and anchor it somewhere, for instance in a global variable:

      local t = {__gc = function ()
        -- your 'atexit' code comes here
        print("finishing Lua program")
      end}
      setmetatable(t, t)
      _G["*AA*"] = t

Another interesting technique allows a program to call a given function every time Lua completes a collection cycle. As a finalizer runs only once, the trick here is to make each finalization create a new object to run the next finalizer, as in Figure 23.2, “Running a function at every GC cycle”.

      do
        local mt = {__gc = function (o)
          -- whatever you want to do
          print("new cycle")
          -- creates new object for next cycle
          setmetatable({}, getmetatable(o))
        end}
        -- creates first object
        setmetatable({}, mt)
      end
      
      collectgarbage()   --> new cycle
      collectgarbage()   --> new cycle
      collectgarbage()   --> new cycle

The interaction of objects with finalizers and weak tables also has a subtlety. At each cycle, the collector clears the values in weak tables before calling the finalizers, but it clears the keys after it. The rationale for this behavior is that frequently we use tables with weak keys to hold properties of an object (as we discussed in the section called “Object Attributes”), and therefore finalizers may need to access those attributes. However, we use tables with weak values to reuse live objects; in this case, objects being finalized are not useful anymore.

Up to version 5.0, Lua used a simple mark-and-sweep garbage collector (GC). This kind of collector is sometimes called a “stop-the-world” collector. This means that, from time to time, Lua would stop running the main program to perform a whole garbage-collection cycle. Each cycle comprises four phases: mark, cleaning, sweep, and finalization.

The collector starts the mark phase by marking as alive its root set, which comprises the objects that Lua has direct access to. In Lua, this set is only the C registry. (As we will see in the section called “The registry”, both the main thread and the global environment are predefined entries in this registry.)

Any object stored in a live object is reachable by the program, and therefore is marked as alive too. (Of course, entries in weak tables do not follow this rule.) The mark phase ends when all reachable objects are marked as alive.

Before starting the sweep phase, Lua performs the cleaning phase, where it handles finalizers and weak tables. First, it traverses all objects marked for finalization looking for non-marked objects. Those objects are marked as alive (resurrected) and put in a separate list, to be used in the finalization phase. Then, 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.

Finally, in the finalization phase, Lua calls the finalizers of the objects that were separated in the cleaning phase.

The use of a real garbage collector means that Lua has no problems with cycles among object references. We do not need to take any special action when using cyclic data structures; they are collected like any other data.

In version 5.1, Lua got an incremental collector. This 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 amount of memory, the collector runs a small step. (This means that, while the collector is working, 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.)

Lua 5.2 introduced emergency collection. When a memory allocation fails, Lua forces a full collection cycle and tries again the allocation. These emergencies can occur any time Lua allocates memory, including points where Lua is not in a consistent state to run code; so, these collections are unable to run finalizers.

The function collectgarbage allows us to exert some control over the garbage collector. It is actually several functions in one: its optional first argument, a string, specifies what to do. Some options have an integer as a second argument, which we call data.

The options for the first argument are:

The two parameters pause and stepmul control the collector’s character. Any garbage collector trades memory for CPU time. At one extreme, the collector might not run at all. It would spend zero CPU time, at the price of a huge memory consumption. At the other extreme, the collector might run a complete cycle after every single assignment. The program would use the minimum memory necessary, at the price of a huge CPU consumption. The default values for pause and stepmul try to find a balance between those two extremes and are good enough for most applications. In some scenarios, however, it is worth trying to optimize them.

The pause parameter controls how long the collector waits between finishing a collection and starting a new one. A pause of zero makes Lua start a new collection as soon as the previous one ends. A pause of 200% waits for memory usage to double before restarting the collector. We can set a lower pause if we want to trade more CPU time for lower memory usage. Typically, we should keep this value between 0 and 200%.

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

The other options of collectgarbage give us control over when the collector runs. Again, the default control is good enough for most programs, but some specific applications may benefit from a manual control. Games often need this kind of control. For instance, if we do not want any garbage-collection work during some periods, we can stop it with a call collectgarbage("stop") and then restart it with collectgarbage("restart"). In systems where we have periodic idle phases, we 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, we can either choose experimentally an appropriate value for n or call collectgarbage in a loop, with n set to zero (meaning minimal steps), until the idle period expires.