[gclist] Baker's treadmill improvments.

[Hans Boehm]

On Jan 31,  2:22pm, Charles Fiterman wrote:
> Subject: Re: [gclist] Baker's treadmill improvments.
>
> >Issues:
> >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
> >occurrence.)
>
> 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.
>
So you incrementally return the free list to the system malloc?
That's another interesting design point, but I think it's quite different from
Paul's.  Allocation cost is likely to be significantly higher.  Allocation
doesn't really run in constant time, since the system malloc doesn't.  And
there's likely to be more space overhead, since the system malloc typically
uses its own header.

Coalescing behavior is quite good on many systems.  But in my experience,
allocation ordering issues tend not to be handled well.  That's much easier to
do in a collecting allocator.  Does Smartheap really try to allocate in address
order?

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

That's a good point.  You can always handle pointerfree objects by allocating
the link fields in a separate handle object,  at some cost in space.  And you
incur the space cost for other reasons anyway.

Hans




-- 
Hans-Juergen Boehm
boehm@mti.sgi.com