sequences

[Ross Paterson]

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

Implementations:
[] you know; the rest are from Edison or Chris's book (RandList is skew
binary random access lists), except for the last two:
- an implementation using 2-3 finger trees, giving constant time access
  to the ends and O(log n) append.
- a variant annotated with size information to support index, update and
  split in time O(log(min(i,n-i)).

Conclusions:
- Cute though the real-time queue is, the Banker's version is much better.
- No implementation is clearly superior.  A library would need [],
  JoinList, BankersQueue, BankersDeque, RandList and at least one with
  efficient append.  (I've discounted SimpleQueue because it performs
  badly in a shared context.)  I've argued before that the best way
  to express their commonality is using a Haskell 98 constructor class
  (albeit a fairly big one).
- Catenable lists and catenable deques are still behind finger trees at
  these sizes, though eventually their constant time append will win out.
- Finger trees with sizes look like a reasonable general purpose sequence
  implementation.  They're not too far behind on every operation,
  and they also support split efficiently.  Their main weakness is the
  O(log n) bound on append.  There's a structure by Kaplan and Tarjan
  that improves that to O(log(log n)) while keeping the others, but it
  looks very complicated (and thus may have large constant factors).

The code is at http://www.soi.city.ac.uk/~ross/seq.tar.gz
docs are at http://www.soi.city.ac.uk/~ross/seq/