
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