[gclist] Baker's treadmill improvments.

Charles Fiterman cef@geodesic.com
Fri, 31 Jan 1997 14:22:22 -0600

>1) Coalescing.  I haven't seen versions of the treadmill algorithm that can
>reuse blocks for different request sizes.  On the other hand, it's not obvious
>this can't be done.  Based on what I remember from some of Ben Zorn's
>measurements, not coalescing does cost you space.  (Our collector only
>coalesces when an entire page is empty.  But even that seems to be a frequent

Our treadmill collector sits on top of the C++ allocator so Coalescing is
not our issue. SmartHeap does a good job of it and if its the allocator we
sit on top of we don't stop it. The same for allocation ordering issues.

>3) (I think this one is actually quite significant in practice, and usually
>underestimated.)  I don't know how to allocate pointerfree objects with a
>treadmill collector so that they are not touched during a garbage collection.

We do! No problem! The first time an class is instantiated we build a map and
there is a static template object that gets pointed at it. If there were no
pointers or references in the map future objects of this type get allocated
as leaf objects. We get a lot of very good information into the map including
stuff about user mark methods. We still touch the handles of leaf objects but
these are allocated in large pages. If there is a user mark method it's address
lands in the map so if it can work without touching the object it does.

> Our collector goes out of its way to assure this, even to the point of making
>everything else somewhat more expensive.  The experience with Cedar was that
>this effort wins big.  In Cedar, typically 2/3 or 3/4 of the heap was
>pointerfree.  I've heard estimates that in some other systems it's 98%.  Any
>tracing garbage collector must at least read pointer containing objects.  But
>touching other heap areas is a waste.

We tell users of the conservative collector who want to optimize that they
need to identify leaf objects. Everything else tends to be trivia.

Charles Fiterman		Geodesic Systems
414 North Orleans Suite 410	Phone 312 832 1221 x223
Chicago IL 60610-4418		FAX   312 832 1230

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