Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!ucbvax!hplabs!hp-pcd!hplsla!jima
From: jima@hplsla.HP.COM (Jim Adcock)
Newsgroups: comp.lang.c++
Subject: Re: GC (was Re: Eiffel vs. C++ (vs Smalltalk))
Message-ID: <6590175@hplsla.HP.COM>
Date: 28 Jun 89 18:31:41 GMT
References: <14739@duke.cs.duke.edu>
Organization: HP Lake Stevens, WA
Lines: 27

> The following simple program makes random length trees -- and fools Boehm's
> GC.  I seem to remember something about this in his README file.  Maybe one
> had better bone up on his algorithm before getting too deep in this.
> 
> (change either 2 to a 3 (25% chance verses 50% chance) in randomlinks and
>  the GC works fine.  Program is not "publication quality.")

Oops, sorry, as Boehm pointed out to me, the problem is apparently not with
Boehm's GC, but in my "logic" in analysing the expected behavior of my
"simple" program.

I didn't check how much these things were actually growing.  I thought
about a single leaf, and said to myself that with each child having a
50% probability of not existing, there is a 25% probability of any given
leaf not having any children, therefor the tree "must" terminate.

But when I think of it another way, each leaf has an "expected" amount of
2*0.5 = 1.0 children, (2*0.5)*(2*0.5) = 4*0.25 = 1.0 grandchildren, 
(2*0.5)*(2*0.5)*(2*0.5) = 8*0.125 = 1.0 great-grand-children.... so the
size of a tree would be marginally ill-conditioned, and could grow 
"indefinitely."

Changing a 2 to a 3 makes for "expected" 0.75 children, 0.5625 grand-children,
etc, so then one doesn't have indeterminate growth of the trees.

Now, if Boehm's GC *could* handle my program, then he'd *really* have
something! :-)