Are new sequences really O(1)?

[Adrian Hey]

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