[gclist] Re: Name that hypothesis

[Marc Shapiro]

 || From: Nick Barnes <nickb@harlequin.co.uk>
 || Date: Tue, 03 Dec 1996 12:40:38 +0000
 || Subject: [gclist] Name that hypothesis
 || 
 || What is the name of the following hypothesis?
 || 
 || 	"Most references in a system point backwards in time, i.e. from
 || 	 younger objects to older objects."

We tested that hypothesis.  It is incorrect.

Specifically, here is how some well-known C programs behave:

 - cfrac: most are forward (in time) but a large proportion are backward
 - gs: almost all are backward
 - espresso: almost all are forward
 - ical: equally balanced, forward and backward
 - gawk: a high peak of backward pointers, but a long tail of forward ones
 - GNU make: equally balanced in both directions
 - perl: mostly backwards

The above is for live objects.  Interestingly the behaviour differs for
garbage:

 - cfrac: results not significant
 - gs: backwards
 - espresso: equal balance
 - ical: most backwards
 - gawk: high peak backwards, long tail forwards
 - GNU make: backwards
 - perl: predominantly backwards

The exact figures can be found in the master's thesis of one of my students:
        Mesure et caractérisation d'applications réparties
        Cédric Adjih
        http://www-sor.inria.fr/SOR/docs/MCAR_dea96.html
See Figure 4.12 and 4.10.

-- 
						Marc Shapiro

M. Shapiro, INRIA Rocquencourt, BP 105, 78153 Le Chesnay Cedex, France.
Tel.: +33 1 39 63 53 25.  Fax: +33 1 39 63 53 30.
e-mail: marc.shapiro@inria.fr.  http://www-sor.inria.fr/~shapiro/