[gclist] Name that hypothesis

[Mark Tillotson]

On Dec 3, 12:40pm, Nick Barnes wrote:
> > 	"Most references in a system point backwards in time, i.e. from
> > 	 younger objects to older objects."
> >
> > In the GC community we all know this, and many of us use it
> > frequently, but we don't seem to have agreed on a name for it.
> >

boehm@hoh.mti.sgi.com (Hans Boehm) replied:

> It seems to me that this is actually
> 
> 1) Much stronger than required by a generational collector, and
> 2) False for a significant fraction of nonfunctional programs.
> 
> Counterexamples:
> 
> a) Programs that build lists or trees "front-to-back" or "top-down".
> 
> b) Programs that use mostly doubly linked structures.
> 

One could address this by bringing in a notion of the span of a reference
(the difference in allocation time(*) between the destination and
the object containing the pointer)

Then on the assumption that contents of lists/trees are allocated before
the lists/trees:

   Front-to-back-built lists/trees have a lot of very short positive
   spans (pointing forwards in time), but the cars of the list will all
   be (much!) larger negative spans, so that the total of the span is
   still negative (from young to old).

   So the hypothesis becomes

     "The sum of spans of references in a system tends to be negative"

Note that pointer-cycles contribute zero, whatever the proportion of its
pointers point backwards or forwards in time.  Doubly linked lists
also contribute zero for the links, since they are made of 2-cycles.

Maybe a better formulation is
     "The sum of negative spans is significantly greater in magnitude
      than the sum of the positive spans"


(*) this "time" could mean a clock that is advanced on each
    allocation, or you could have a notion of time that magically
    forgets that dead objects were ever allocated ("linear time" or
    "compacting time"??)   This metric might take account of the size
    of objects or not...

__Mark
[ markt@harlequin.co.uk | http://www.harlequin.co.uk/ | +44(0)1954 785433 ]