[gclist] Whats the right algorithm for this case?

[Charles Fiterman]

A
>The applications I work on are mainly language tools, which either
>have idle time (in which the GC can run) or are batch tools (so can
>run the GC any time). I wasn't discussing my applications, I was
>observing that there are certainly real-time applications which have
>no idle time. For instance, the switching software in a busy telephone
>exchange. For another instance, on-board software in almost any
>vehicular application.

Your language tools are obviously better off with something like
mark and sweep a copying collector. The advantage of mark and sweep
is the ability to call C functions and not worry about object motion.

That switching software is line limited not cpu limited. It is best
off with the kind of treadmill I described as it will always have
more than enough idle time even at its busiest. The vehicular 
application is mission critical it wont have a single storage allocation.
Everything will be stack, register or static.

>Some applications have real-time limits on GC pauses. Some
>applications get a lot of idle time. The two properties are
>orthogonal, as I said. The treadmill, as I understand it, addresses
>the first property (i.e. it can be used as a real-time GC algorithm).
>"Doing your GC in idle time" (an idea which I first came across in
>Wilson & Moher's opportunistic GC paper) addresses the second.

What I'm describing isn't just doing GC in idle time its doing anything
you can in idle time and using GC finalizers as the vehicle for that.
If your application can move work into idle time it will appear far
more interactive.

>Most interactive user applications aren't very real-time in my
>experience, and can manage with an incremental GC, rather than
>real-time GC. I don't care whether the GC pauses in my word-processor
>are 5ms or 50ms; I don't even care if one in a million pauses is a
>whole second. This shows that word-processing is not a real-time
>application.

Those application are better off with mark and sweep or copying 
collectors. For them treadmill is very expensive overkill. We have
a gcAttemptCollection(isIdle x); which takes the address of an
isIdle routine as a parm. At strategic points in the collection it
calls isIdle and if it gets a zero back aborts the collection trashing
its work. We find this is far more efficient than incremental collection
for the kind of application you describe. The worst case delay comes
in scanning a page which is filled with pointers and this is in the
millesecond range on a Sparc II and totally acceptable. It is very
rare for gcAttemptCollection to abort a collection and we've never seen 
it do so twice in a row in our sample programs.


			-  
Charles Fiterman		Geodesic Systems
414 North Orleans Suite 410	Phone 312 832 1221 x223
Chicago IL 60610-4418		FAX   312 832 1230
				http://www.geodesic.com

A computer language without garbage collection
  is like a city without garbage collection.