Functional languages don't have mutable data (in the traditional sense) so certain data structures become more difficult to implement. A priority queue is normally implemented with a heap, however, after looking at heap implementations within Chris Okasaki's book ("Purely Functional Data Structures"
), it didn't seem correct to use an Erlang heap data structure to implement a priority queue.
The previous Erlang priority queue data structure is used within both Riak
). However, the "in" (i.e., "append") operation seemed quite slow because of its usage of a list of tuples to store the separate queues for each priority.
So, I created a priority queue implementation called "pqueue"
that relies on tuple storage for individual priorities. However, because I am using tuple storage, I needed to use a static range of priorities. I chose the common UNIX operating system priority range for nice (-20 (high) to 20 (low)). I was able to obtain fast "in" operations at the slight expense of the "out" operations, as shown below. The benchmark was ran (with R14B02, without HiPE) on an AMD Phenom 9950 Quad-Core (64 bit) running Linux 2.6.32-23-generic (Ubuntu).
N == 1000000 (10 runs)
pqueue get: 475747.2 µs ( 1.3), set: 504762.3 µs ( 1.0)
priority_queue get: 372439.6 µs ( 1.0), set: 1466042.1 µs ( 2.9)