[Haskell-cafe] Performance of functional priority queues

[wren ng thornton]

Richard O'Keefe wrote:
> There's a current thread in the Erlang mailing list about
> priority queues.  I'm aware of, for example, the Brodal/Okasaki
> paper and the David King paper. I'm also aware of James Cook's
> priority queue package in Hackage, have my own copy of Okasaki's
> book, and have just spent an hour searching the web.
> 
> One of the correspondents in that thread claims that it is
> provably impossible to have an efficient priority queue implementation
> without mutability.  I think he's cuckoo.  But I'd like to have some
> numbers to back me up.

Sounds cuckoo to me until I see a proof otherwise. I've seen a few proof 
sketches indicating that immutable approaches can always be no worse 
than a O(log n) multiple of imperative ones (by simulating main memory 
with your O(log n) map of choice). Between this and the provable 
asymptotic optimality of skewed binomial heap prioqueues, the argument 
sounds untenable.

Though it really comes down to what they mean by "efficient". Asymptotic 
complexity is the name of the game for most folks in algorithms and 
datastructures, but that seems not to be what they're after. Shrinking 
the constant factors is frequently a game that can go on forever, or 
rather can seldom be proved not to, so the claim seems unlikely to be 
meaningful in this arena either (you'd have to prove you've found the 
smallest possible constant factor for any immutable approach, and then 
find a smaller one for some mutable approach). Also proofs about 
constant factors beyond basic thresholds aren't useful in practice due 
to hardware barriers like cache size and disk access times.

There's also the difference between compilers that are designed to 
optimize immutable patterns, vs ones which aren't. For example, in 
certain circumstances and with suitable annotations Clean will take the 
immutable approach and convert it into a mutable variant for you, thus 
saving on allocation/collection/cache-miss overheads while maintaining 
the spirit of immutability. Is compiled code like this considered 
"mutable" or "immutable"? It all depends on the spirit of the question.


> Can anyone point me to some actual benchmark results comparing
> priority queue performance *with* mutation and priority queue
> performance *without* mutation, in the same functional or
> mostly-functional language?

I'm always curious to see datastructure benchmarks though :)

-- 
Live well,
~wren