Re: Update on GC performance (github version)

[Dave Hayden <dave@...>]

I wound up adding generations to the 5.3 collector to fix a problem I was
having where I couldn’t give the collector enough time to keep up with the
garbage piling up. (This is on an embedded platform with real time
requirements.) What I found was the collector was spending most of its time
stepping through the allgc list. In my scheme you manually push a new
generation, which moves the allgc list aside--this way, long-lived objects can
be shelved after they’re created and don’t slow down the collector at all. I
took a quick look over the 5.4 changes and it doesn’t look like the new
generational collector will save me from having to walk all of allgc, but I
might be missing something.

I wanted to test it more before sharing with the list (I know it doesn’t work
right with weak tables, for instance, and there’s probably plenty of other
bugs) but since generational GC is back in the news I thought I’d pipe up now.
Here’s a brief rundown:

I used two of the unused (in 5.3.4) “marked" bits--one is “red”, the other
“yellow”. When I push a generation, everything in allgc and finobj are marked
red and the lists are moved to a "generation" struct. After this, any time a
red table gets a reference to a current-gen (neither red nor yellow) object,
the mark changes to yellow and I add it to the generation’s list of yellow
objects. I don’t see any significant slowdown from the overhead of these extra
checks when setting table values. The yellow set is all of the references from
the red set to the current set, so in restartcollection() they're marked gray.
In the propagate phase I ignore red objects altogether. When I pop the
generation, I clear the red/yellow bits from that generation’s allgc and finobj
lists, add the current allgc and finobj lists to the ends of them, and move
them back into the lua state. Then, if there was a generation before the popped
one, I restore the yellow mark on the objects in its yellow list.

It’s working well so far, now that I’ve found (I think) all the places a table
value can be set. The push and pop functions are currently atomic, but it seems
like they could be made iterative without _too_ much trouble.

Anyway, I wanted to mention it in case it’s useful at all. Here’s the diff:

	https://www.dropbox.com/s/fse7k4teqb0chi9/redbit.diff?dl=0

Thanks!
-Dave