[erlang-questions] queue:split/2 unsafe!

[Richard A. O'Keefe]

On 10/04/2013, at 1:29 PM, Fred Hebert wrote:
> What's your main problem with it?

I have two problems, and I think both of them boil down
to the same thing.  Once there was a queue.erl which _just_
implemented queues.  The interface was not what I'd have
made it, but it was smallish, and the underlying
representation was adequate to the job.

Now there is a queue.erl which provides deques, and has
a mashup of at least three different interfaces.  It
is possible to implement deques tolerably efficiently
in a functional language.  However, this module still
uses a data structure which is basically only adequate,
and tweaks it lightly to be less inadequate for deques.
But still not adequate.

The claims of O(1) amortised time are, sadly, *bogus*.
Try it for yourself.  Make a benchmarks that creates a
queue of 4N elements, and then times a loop that
repeats drop(drop(drop_r(drop_r(Q)))) until the queue
is empty.  If the operations are O(1) amortised time,
the cost should scale linearly with N.

By actual measurement, the cost is O(N**2), which means
that the operations are O(N) amortised time, not O(1).

The code is much more complicated than code for simple
queues.  There are extra overheads making it slower than
code for simple queues when used as simple queues.  For
a trivial example, converting a list to a simple queue
is an O(1) operation, but queue.erl takes O(|list|) time.

We're paying constant factor overheads in order to gain
asymptotic performance that we don't actually _get_, for
operations that, if we just want queues, we don't use.

I suggest that having *separate* 'queues' and 'deques'
modules would be a good idea.