[gclist] Whats the right algorithm for this case?

Nick Barnes nickb@harlequin.co.uk
Mon, 03 Feb 1997 11:57:03 +0000

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

I'm quite happy with the copying and mostly-copying collectors my
language tools use. As I observed, the batch tools can GC any time
(or, rather, at a time which is good for GC, rather than good for the
user). The interactive tools have idle time often, and can GC
incrementally when they don't.

I say again, I wasn't discussing my applications.

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

Whether they have plenty of CPU is irrelevant. What matters is whether
they can take (say) a whole millisecond out to devote to GC. In at
least some such applications, the answer is no.

> The vehicular application is mission critical it wont have a single
> storage allocation. Everything will be stack, register or static.

Not all vehicular applications are mission critical, and not all
mission critical software is allocation-free. Do you suppose that the
AI system which CMU has driving vans around Pittsburgh runs without
any allocation? (I don't know either, but I have a strong suspicion).

My point is simply this: there are real-time applications, without
chunks of idle time, which benefit from GC. They might get souped-up
CPUs to compensate, but unless your GC can keep up when running
entirely in 10-microsecond chunks (say), it loses. What happens if
you're in the middle of a GC timeslice when that crucial interrupt
comes in?

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

I completely agree with this.

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

I completely agree with this as well.

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

For a wide range of applications, but not everything. Unless your
Sparc II is running a real-time OS (such as VxWorks), it is irrelevant
to the sort of application which I am describing.

Nick B