Accessing new heap costs more than old?
jmaessen at alum.mit.edu
Mon Sep 5 12:42:40 EDT 2005
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
>> 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
> 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
> Adrian Hey
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
More information about the Glasgow-haskell-users