On Tue, Jun 15, 2004 at 11:24:23AM +0100, Simon Marlow wrote:
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.
Another way to use it is to prune out the dominated implementations, and then advise people to choose the implementation that accelerates the operations they care about and as few others as possible (because they'll pay for the extras in higher constant factors).
Why would anyone prefer Catenable over JoinList?
Catenable has guaranteed bounds for head, even in a persistent setting, and JoinList doesn't. But Catenable and CatDeque seem to be uniformly inferior to FingerTree. Similarly real-time and bootstrapped queues are dominated by Banker's queues.
Have you compared with the sequence implementation in DData? (it's like JoinList, but has some optimisations that make conversion to/from lists faster).
It's only a couple of percent faster on append, presumably because of Cons/Snoc. That test doesn't exercise the list stuff. But JoinList does rotations on tail/init, which makes it a much better queue/deque than DData.Seq (and those would be much more work with all the extra constructors).