Re: Update on GC performance (github version)

[Russell Haley <russ.haley@...>]

On Tue, Nov 28, 2017 at 4:32 AM, Roberto Ierusalimschy
<roberto@inf.puc-rio.br> wrote:
>> 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.

I just finished reading about Virtual Memory paging in the FreeBSD
kernel [1]. (I'm hoping this is reasonably accurate) All pages live
for at least two page collection cycles before being moved in to one
of 4 types of lists grouped of usability (active, inactive, cached
(?), free. There is also wired, but only for kernel pages). These bins
are kept at certain percentage thresholds to get optimum performance
out of the system. This causes some things to get unnecessarily moved,
but performs better than not monitoring the overall normalized levels.
Also interesting is the preference for pages from cached instead of
free  due to lower overhead of rebuilding the struct.

I'd like to look at the GC code at some point. Anything you (or any of
the authors) can offer about the design and implementation of Lua on
the mailing list is wonderful.

Thanks,
Russ

[1] https://bookdl.com/978-0321968975/


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