On Thursday 26 May 2005 2:35 pm, Ross Paterson wrote:
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.
This seems to have improved things quite a bit. Hope your right about the persistent bounds (I wouldn't know :-). But it would be good to test this somehow. Anyway, latest test results from 2^8 to 2^22 are.. sz AVL Sequence 2^ 8 0.0448 0.0331 2^ 9 0.1015 0.0676 2^10 0.2789 0.1490 2^11 0.6707 0.3479 2^12 1.473 0.8010 2^13 3.142 1.676 2^14 6.733 3.461 2^15 14.39 7.181 2^16 30.41 15.36 2^17 62.73 30.82 2^18 130.8 62.89 2^19 270.9 126.6 2^20 559.2 254.8 2^21 1155 513.3 2^22 2411 1035 This is quite impressive. For moderate length sequences, it seems to be about twice as fast as AVL (which AFAIK is the fastest balanced tree implementation currently available for Haskell). The execution times are growing slower than AVL for longer sequences too (looks more like O(1) than it did before, but still not quite O(1) for some reason). Regards -- Adrian Hey