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@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users