[erlang-questions] Priority queues and Erlang

[Richard O'Keefe]

On 13 Jun 2009, at 4:31 pm, John Haugeland wrote:
> If I remember correctly, it is not possible to implement an efficient
> priority queue without mutability

Much depends on what you mean by "priority queue"
and what you mean by "efficient".

If by "efficient" you mean "same as C or Fortran, including constant
factors equal to within a few percent, then Erlang is not likely to
ever accomplish that with or without mutability.  Mutability per se
is no guarantee of speed.

If you mean good asymptotic bounds, no, the Okasaki and Brodal
paper shows that it can be done with O(1) everything except
delete-min, which is O(lg n).

If you mean something in between, then I think an example is
needed to make your case.  Take a functional language which supports
mutability (such as SML or OCAML, or for that matter Haskell using
the ST monad, or Clean using uniqueness annotations, or perhaps
Mercury), and implement both functional priority queues and some
sort of imperative priority queue.  That will be informative.

> , which is well demonstrated in CLRS.

Where?
>
> The general performance of a tree cannot be matched, let alone
> beaten, by an immutable priority queue.

This is more than a little confusing:  immutable implementations
of priority queues ARE trees.

> There is no purpose to
> implementing a priority queue in Erlang until mutability is available.

Mutability is available NOW, and in two different ways.
(1) You can use ETS/DETS tables, which are mutable.
(2) You can represent mutable variables by processes in a well
known way.
Both of these provide O(1) fetch and store, so, mutability.
For that matter, there is the process dictionary, which uses
a per-process hash table.

Mutability is no guarantee of speed!



> is so large that you're talking several tens of gigabytes before they

> become even remotely competitive.  It's kind of like how if you have a
> C++ container with 20 or so elements, bubble sort pantses almost every
> other sort,

It is news to me that bubble sort is EVER a reasonable choice.
Had you written 'insertion sort', I'd have believed you.
>
> I would love to be proven wrong with benchmarks, though; a priority
> queue would be epic useful to me in Erlang.

Why don't you try proving yourself *right* with benchmarks?

To be useful in Erlang, a priority queue implementation does not
have to be as fast as one in C.  It just has to beat the alternatives
(like gb_trees) currently available in Erlang.