sequences

[Simon Marlow]

On 03 June 2004 11:19, Ross Paterson wrote:

> I've done some crude benchmarking of different implementations of
> sequences: (ghc -O, times in microseconds)
> 
>                                   test cases
>                 Stack   Queue   Deque  Append   Index  Update
> -------------------------------------------------------------
> []               5399       -       -       -       -       -
> JoinList         8498   17897   18197   35194       -       -
> SimpleQueue      9198   12298       -       -       -       -
> RealtimeQueue   64290   72389       -       -       -       -
> BootQueue       17997   22896       -       -       -       -
> BankersQueue    12098   21196       -       -       -       -
> BankersDeque    16997   70589   22496       -       -       -
> Catenable       41593  123881       -   77788       -       -
> CatDeque        57791  145477   62790  132879       -       -
> RandList        11598       -       -       -   13498   29895
> FingerTree      24996   33894   32994   45293       -       -
> FingerTreeS     28995   44693   37894   68689   37094   37994
> 
> Test cases:
> Stack: 100000 random stack operations on a sequence of 2000 elements
> Queue: 100000 random queue operations on a sequence of 2000 elements
> Deque: 100000 random deque operations on a sequence of 2000 elements
> Append: building a sequence of fib 25 elements using appends
> Index: 100000 accesses at random indices on a sequence of 2000
> elements Update: 10000 updates at random indices on a sequence of
> 2000 elements 

Nice!  This is exactly the kind of information someone choosing a
sequence implementation needs to know.  It should even go in the
documentation, IMO.

Why would anyone prefer Catenable over JoinList?

Have you compared with the sequence implementation in DData?  (it's like
JoinList, but has some optimisations that make conversion to/from lists
faster).

Cheers,
	Simon