Performance of functional queues

[Sebastian Sylvan]

On 11/2/05, Einar Karttunen <ekarttun at cs.helsinki.fi> wrote:
> Hello
>
> 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.
>
> For pics of the results and the code look at
> http://www.cs.helsinki.fi/u/ekarttun/haskell/sequence-performance/
>

There ought to be a benchmark where you perform an operation and then,
based on some random factor, either proceed with the next operation
using the resulting queue, or using the queue before the operation you
just performed.
That happens a lot in practice and will show the strength of
Data.Queue better (it's designed specifically to spread out the cost
of the list reversal).

Also. I'm interested in looking at benchmarks where the time of each
operation is squared (or something like that), to show how well suited
they are for real-time operations (where it's better for it to
constantly take 1ms than for it to take 1µs on average but every now
and then take 50 ms).

/S

--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862