[gclist] Re: gclist-digest V2 #76

Hans Boehm boehm@hoh.mti.sgi.com
Wed, 10 Dec 1997 17:26:43 -0800


On Dec 10,  8:15pm, John R Levine wrote:
> Subject: Re: [gclist] Re: gclist-digest V2 #76
> > There is a very small chance that a random integer will
> > correspond to a block. Consider a 2^N heap all of whose
> > data are uniformly distributed integers. The chance of any
> > 1 integer corresponding to some block is 2^(N-64). ...
>
> I would be very careful about analyses like this.
>
> I have this really great 64 bit processor chip, with a minor bug in the
> "compare" instruction so it will never say that its two operands are equal.
> But that doesn't matter, since the chances of two uniformly distributed 64
> bit numbers being equal is 2**-64 -- if a program running on the chip
> executed one comparison every 100 nanoseconds, statistically it would take
> over 29,000 years* before a pair of operands were equal.
>
But those two arguments are quite different.  In the second case, you have
no control over the arguments, and they are not uniformly distributed.

In the GC case, I can (usually, subject to some OS and hardware constraints)
randomly select the heap start address.  This it makes some sense to talk
about probabilities.  I might not actually want to do this, if for example,
I think I can make a better than random choice for heap addresses.

(Note that if I have a deterministic process, I can turn a conservative
GC into a precise GC by running two copies of the code with different heap
addresses, and having the GC look at both copies.  Pointer values will differ
by the heap starting addresses.  Everything else should be the same.
Of course, this doesn't address dead variable issues, etc. which are
often more important.)

Hans


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