Performance of functional queues

[Ross Paterson]

On Wed, Nov 02, 2005 at 06:06:55PM +0200, Einar Karttunen wrote:
> I benchmarked the various functional queue implementations
> including simple batched queues (data Q = Q [a] [a]),
> Data.Queue and Data.Sequence.
> 
> The end result was that the simple batched queues are
> fast and toList of Data.Sequence is very slow. For most
> applications Data.Sequence is faster than Data.Queue, but
> slower than the batched queues, but the differences are
> not huge. Of course it offers other functionality which 
> the other queues don't provide.

Also Data.Queue (Okasaki's real-time queues) and Data.Sequence
(fingertrees) retain their performance bounds under persistent use,
while batched queues don't.  That's an important property for a
general purpose library.

Repeatedly taking the head doesn't show this, as batched queues keep the
first list nonempty unless the whole queue is empty.  It would show if
you repeatedly computed

	head (tail (Q [x] long_list))