Re: Update on GC performance (github version)

[Roberto Ierusalimschy <roberto@...>]

> This message is an update about a problem from last year [1] on the
> performance of the following simple script
> 
> -- collectgarbage("generational")
> N = 2.0e7
> C = {}
> for i=1,N do C[i] = i end
> print(string.format("%.1f",collectgarbage("count")))
> for i=1,10*N do
>     local a = {1,2,3,4}
> end
> print(string.format("%.1f",collectgarbage("count")))

First, a small note: the last line in this script is not reliable.  You
are creating a lot of garbage there, with the collector freeing them at
unknown points. A single "random" sample from that usage cannot give you
much information. Either you get the memory usage frequently during the
loop (e.g., every 1000 iterations) and keep the maximum, or you use an
external way to measure the total memory used by the process. (Despite
all this, your results were consistent with what I get using an external
measure :-)


> Someone versed in GC magics could discuss about the changes made from 5.2
> to github version of GC?

I never fully undestood why the generational collector in 5.2 did not
perform as I expected, but I had one suspect. I fixed that, and it
improved a lot, so probably that is the explanation. But I still
do not undestand why that problem would make such a big difference
(see below). Anyway...

The main change was the pace of aging. In Lua 5.2, any object that
survived one GC cycle became old. The main advantage of this method
is its simplicity. At the end of a GC, all objects are old, so the
invariant that old objects should not point to new ones is trivially
satisfied. The main disadvantage is that, at every collection, a few
objects are doomed to survive, no matter how short are their lives.
(Always at least one object is created "just before" the collection,
and therefore it is still alive when the collection comes.) Therefore,
the old generation keeps growing, and a full collection must be
performed regularly, even if no real old objects are being created.

The problem itself is not difficult to understand. However, even with
this problem, those full collections would be much more spaced than in
the incremental collector. So, I still do not understand why the
generational in 5.2 did practically no difference in performance.

In Lua 5.4, an object becomes old when it survives two GC cycles.
So, even if an object is created just before a collection, it still
must last a full GC cycle before becoming old. When the program is
creating only short-lived objects, it can go forever without a full
collection. However, this implementation is much more complex.
As an example, consider that object A was created in cycle 1,
B in cycle 2, and A points to B. Both are young, so everything
is fine. Now, in the next collection, A becomes old, but B does not,
so A(old) points to B(young). The collector must know about that.
Similarly, if A(old) receives a reference to B(young), the collector
puts A in a list to be traversed again. In 5.2, this list can
be cleared at each collection (as all objects become old). In 5.3,
the object A might be kept in this list for another cycle, because B can
survive a collection and still be young. (The real details,
both in 5.2 and 5.3, are more complex than that, but they are
reasonably more complex in 5.3 than in 5.2.)

-- Roberto