On Tue, May 24, 2005 at 08:29:57PM +0100, Adrian Hey wrote:
Just been trying a few simple benchmarks to compare the new sequences with AVL trees for simple deque operations and I'm getting some strange results.
The stack overflow is interesting, and relates to all representations based on lazy number systems. If you build a structure without accessing it, you get n/3 nested applications at the second level. That's no more space than they will evaluate to, but as soon as you access the second level, they all go on the stack. GCs that happen during this process will be more expensive, as they have to scan the stack. I suspect that GC costs are swamping everything else for large n. I've fixed the stack overflow; I believe this doesn't break the persistent bounds.