Re: GC by tracking

[Mark Hamburg <mhamburg@...>]

on 1/7/05 6:35 PM, skaller at skaller@users.sourceforge.net wrote:

> [ a long analysis of how to treat this as a scheduling problem with feedback
that I urge people to go read ]

I like that analysis and I like the notion of scheduling the major
collections independently of the minor collections. The trick then is to
make it fit within the Lua framework.

I think I now have a pretty good understanding of why the Lua framework
generates the results that it does or more specifically what it is about the
generational collector that leads to the huge memory usage. Essentially, we
wait longer than we would otherwise wait to do a major collection and this
causes garbage to accumulate. Furthermore, since the major and minor
collectors are locked together, this causes additional scheduling issues.

Here is my summary of how I think the GC process works in Lua. Please
correct me if I'm wrong.

1. We sit in the paused state until the threshold is crossed.

2. Once crossed, we either do an atomic minor marking pass or we start an
incremental major marking pass. The decision of which to do was previously
determined and will be determined again below. The incremental pass ends
with an atomic step.

3. At the end of the atomic step, decide whether the next collection will be
minor or major.

4. Incrementally sweep all of the storage collecting garbage, building
finalization lists, etc.. This step also preps the mark state for the next
collection which is why we need to know whether the next collection will be
major or minor.

5. Incrementally finalize userdata objects.

6. Go into the pause state and go back to step 1.

The messy part for scheduling (besides the question of when) seems to be in
step 3. Scheduling would be much simpler if we could say "do a minor
collection" or "do a major collection". The need to adjust mark bits in step
4 also makes it harder to have the minor collections only sweep the nursery
objects. This could be addressed by starting a major collection with a sweep
to set the colors appropriately, but that makes a major collection more
expensive since it forces an extra pass through all of the data. It might
also be addressable with an appropriate number of colors for nodes, but I'm
going to hold off on that analysis.

So, what if we adopted your framework and did something like the following:

* Minor collections are scheduled based on a programmatically controllable
period. If they could be made to sweep just the nursery, then there wouldn't
be much pressure to make the period dependent on the memory usage.

* In step 3 above, use the minor collection period to figure out when the
next minor collection would be. If the collection was a major collection,
use the major collection period to schedule the next major collection.
Compare the next scheduled minor collection with the next scheduled major
collection and decide whether the next collection will be major or minor.

* At the end of the sweep for a major collection -- i.e., we need to know
whether the previous mark phase was major as opposed to whether the next one
will be major -- compare the amount of garbage collected to the desired
amount of garbage. Use this to adjust the period for major collections. If
we want to, we can adjust the timing to the next major collection rather
than waiting a cycle, but we need to be prepared to re-sweep if this changes
the next cycle from minor to major. We also calculate the desired amount of
garbage for the next major cycle based on the current total memory.

* Explicitly stepping the GC needs to see whether it pushes us up to the
next major collection and if so it needs to do a major collection rather
than potentially doing a minor collection.'

Your framework relies on the feedback loop to discover the effects of minor
collections on the need for major collections. Is it reasonable to allow
minor collections to also directly slow major collections by generating
"negative time" through recovered storage? This would allow the machinery
that uses totalbytes and GCthreshold to manage the schedule to remain more
or less in tact. The calculation and maintenance of GCthreshold would
change.

Lua has been reasonably successful with an even simpler scheduling mechanism
for major collections: Multiply totalbytes by a factor and use that as the
threshold for the next major collection. That might actually be sufficient
though it provides less opportunity for tuning.

Now, I just need to find the time to (a) move to 5.1w4 and (b) play with
implementing such schemes.

Mark