Log in

No account? Create an account
An Erlang Priority Queue - Michael Truog
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)
Leave a comment