Accessing new heap costs more than old?

[Jan-Willem Maessen]

On Sep 5, 2005, at 3:11 AM, Adrian Hey wrote:

> On Saturday 03 Sep 2005 6:14 pm, Adrian Hey wrote:
>> But I can't think of a plausible explanation for this. The overall 
>> heap
>> burn rate should be about the same in each case, as should the overall
>> amount of live (non-garbage) heap records.
>
> Hmm.. A little more thought leads me to suspect that this is an 
> artifact
> of generational garbage collection, which I guess is much faster if
> the youngest generation is entirely garbage. Is that reasonable?

This agrees with my theory.  Assume that your original tree with n 
elements ends up in the old generation used by the GC.  It will only 
occasionally be traversed and copied.  When you perform d deletions on 
that tree, you'll allocate O(d lg n) new nodes, but since you're 
retaining only the last tree, you will only have O(lg n) new nodes to 
be scanned and copied by the garbage collector.

By contrast, if you make a sequence of i insertions to grow the tree by 
i elements, you'll again allocate O(i lg n) new nodes---but you'll 
retain a good many of them, at least Omega(i).  When i > lg n, the GC 
clearly does more work for insertion than for deletion.  If you'd made 
all the insertions to the original tree, you again retain only O(lg n) 
new nodes, and the relative speeds of insertion vs deletion come into 
play.

-Jan-Willem Maessen

>
> Regards
> --
> Adrian Hey
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users