Re: Daily gclist MIME digest V5 #102

> -----Original Message-----
> From: Robert Virding [mailto:[email protected]]
> Sent: Monday, October 20, 2008 3:13 PM
> To: Boehm, Hans
> Cc: Richard Jones; [email protected]
> Subject: Re: [gclist] Daily gclist MIME digest V5 #102
>
> I didn't mention it but I did actually do an implementation
> of reference counting gc based on what was written in the
> book. It worked very well.
> There is something very satisfying, at the end of a long run
> when you take down the system in a controlled manner, to see
> all the counts go to zero and everything reclaimed as it should be.
>
> Anyway I had considered the problem of memory fragmentation,
> although I didn't do any proper analysis of it. To get around
> it I used a very simple solution, all allocated cells were of
> the same size. Larger objects were just chains of the basic
> cell. The cell was three words so as to be able fit a list
> cell, (type/count - head - tail). It worked surprisingly
> well. I had no cyclic memory references either which made
> things easier.
That certainly works, at the cost of adding complexity elsewhere.  The pape=
r suggests a more general solution:  An allocation request for n bytes deal=
locates at least n bytes from the to-be-freed list.  From my perspective, t=
he interesting observation is that you can have close to constant time allo=
cation, or (somewhat) reasonable worst-case space bounds, but not both.  Th=
e tradeoffs I would suggest give you O(object size) allocation time, just a=
s a tracing GC gives you O(object size) amortized allocation time.

Hans
>
> Robert
>
> Boehm, Hans wrote:
> > It might be worth pointing out that, at least if I
> correctly understand the technique being referred to, it
> potentially (under conditions that are hopefully unlikely in
> practice) squares space consumption.  See
> http://portal.acm.org/citation.cfm?doid=3D964001.964019 for a proof.
> >
> > Hans
> >
> >