[gclist] Whats the right algorithm for this case?

Nick Barnes nickb@harlequin.co.uk
Fri, 31 Jan 1997 16:09:00 +0000

> >> >> First applications that use the treadmill will be giving the collector 
> >> >> atoms of time when they are idle. This more than fills the collectors 
> >> >> needs for time and can be used to finalize and free objects instead of 
> >> >> having that work done when a header is needed.
> >> >
> >> >Many applications are never idle, or need to be able to run for hours
> >> >or days at a time with no idle time. Should these applications not use
> >> >the treadmill?
> >> 
> >> Thats right. The treadmill trades lots of efficiency for extreme incremental
> >> behavior where the largest collector delay is very small. If you don't need
> >> that you are being very silly to use the treadmill.
> >
> >What if you do need that, and yet are never idle (or may run for hours
> >without idle time)? The two are completely orthogonal.
> I don't know? The applications I'm familiar with have tons of idle time and
> low tolerance for collector delays. Shifting work into idle time is always
> good so having finalizers run in idle time allows the program to shift its
> work into idle time opportunisticly. When you have some work to do in idle
> time build an object that does it in its finalizer and don't point to it.
> I really think you need a different algorithm and this forum is the right
> place to ask. I don't know what will work, maybe you can add more info about
> your specific application.

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.

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.

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

Nick B