Garbage Collection in Squeak

John M McIntosh johnmci at smalltalkconsulting.com
Fri Oct 29 21:14:43 UTC 2004


As some of you know I from time to time do serious GC tuning in  
VisualWorks.
http://www.smalltalkconsulting.com/papers/GCPaper/GCTalk%202001.htm

For years now (yes years) I've been thinking about doing serious tuning  
in Squeak, but yet things just weren't interesting enough. However with  
the release of Croquet, thoughts on TK4, and mumblings from folks I  
turned my eye upon what the Squeak GC was doing.  First thanks to Ted  
Kaehler (among others) for writing this GC 10 odd years back  which  
we've run with little change over the years until we added the ability  
to shrink/grow the memory space a few years back.

First I'll need some help from macintosh users that have interesting  
images and can run a pending 3.8.4 mac VM with instrumentation
and then send me some diagnostic log.  People who are willing to help  
should email me directly, and I'll get you a VM and changeset, and  
we'll
see if we can fill up my gmail account with log data. I'm very  
interested in getting Croquet data, having a test case you can run  
before/after would
be best.

So lets review how does the Squeak GC work:

A simplistic view is that  your image (25MB) is loaded into Old Space,  
and 4MB (set in Smalltalk) is allocated
for Young Space. After allocating 4000 (if they fit) new object (limit  
set in smalltalk) we do an mark/sweep/compacting GC on young space
using the VM roots plus roots identified from Old Space to Young Space  
references.  Normally this means looking only at a few thousand
objects, then occasionally we might do a full GC across all 300K object  
based on various conditions, but that's rare.

I'll note the Old Space to Young Space remember table, remembers the  
Object containing the reference, not
the reference so that if you have 100,000 element collection we  
interate over all 100,000 entries looking for the 1 or
more old to young references, a cause for performance concern.

If after completing the mark/sweep/compaction and over 2000 objects  
(set in Smalltalk) are survivors we "Tenure" them to
old space by moving the old/young pointer boundary, then start  
allocating objects again, mind if the young space
exceeds now 8MB free (set in smalltalk) we given memory back and reset  
things back to the 4MB boundary.

Now object allocation can end early because we are allocating a big  
object, in that case we do an
young GC, followed by a full GC (very expensive) followed by growing  
young space so the big object can
fit.   Also of course if we run out of root table remember space, we  
end the allocation process early and think about Tenuring things.

Or it can end if we drop below a minimum amount of memory (200K set by  
smalltalk) which makes the image grow, which if it
fails signals the low space semaphore (and brings up a low space dialog  
which no-one really see and have bitterly complained about)
Yes I now know why that occurs too...

The Problem:

Last weekend I built a new VM which has instrumentation to describe  
exactly what the GC is doing, also to
trigger a semaphore when an GC finishes, and to allow you to poke at  
more interesting things that control GC activity.

What I found was an issue which we hadn't realized is there, well I'm  
sure people have seen it, but don't know why...
What happens is that as we are tenuring objects we are decreasing the  
young space from 4MB to Zero.

Now as indicated in the table below if conditions are right (a couple  
of cases in the macrobenchmarks) why as you see the
number of objects we can allocate decreases to zero, and we actually  
don't tenure anymore once the survivors fall below 2000.
The rate at which young space GC activity occurs goes from say 8 per  
second towards 1000 per second, mind on fast machines
the young space ms accumulation count doesn't move much because the  
time taken to do this is under 1 millisecond, or 0, skewing
those statistics and hiding the GC time.

AllocationCount 	Survivors
4000	5400
3209	3459
2269	2790
1760	1574
1592	2299
1105	1662
427	2355
392	2374
123	1472
89	1478
79	2
78	2
76	2
76	2

Note how we allocate 76 objects, do a young space GC, then have two  
survivors, finally we reach the 200K minimum GC
threshold and do a full GC followed by growing young space. However  
this process is very painful. Also it's why the low space dialog
doesn't appear in a timely manner because we are attempting to approach  
the 200K limit and trying really hard by doing thousands of
young space GCed to avoid going over that limit. If conditions are  
right, then we get close but not close enough...

What will change in the future.

a) A GC monitoring class (new) will look at mark/sweep/Root table  
counts and decide when to do a tenure operation if iterating
over the root table objects takes too many iterations. A better  
solution would be to remember old objects and which slot has the young  
reference but that is harder to do.

b) A VM change will consider that after a tenure if the young space is  
less than 4MB then growth will happen to make young space greater than  
4MB plus a calculated slack. Then after we've tenured N MB we will do a  
full GC, versus doing a full GC on every grow operation, this will  
trigger a shrink if required.  For example we'll tenure at 75% and be  
bias to grow to 16MB before doing full GC.

c) To solve hitting the hard boundary when we can not allocate more  
space we need to rethink when the low semaphore is signaled and the  
rate of young space GC activity, signaling the semaphore earlier will  
allow a user to take action before things grind to a halt. I'm not  
quite sure how to do that yet.


Some of this might be back-ported to earlier VM, I think so, yet I  
won't know until we gather more data and try a few things.



--
======================================================================== 
===
John M. McIntosh <johnmci at smalltalkconsulting.com> 1-800-477-2659
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
======================================================================== 
===




More information about the Squeak-dev mailing list