November 8th, 2011

An Erlang Priority Queue

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 and RabbitMQ (see priority_queue.erl). 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).

TEST run_priority_queue
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)