You are viewing okeuday

Michael Truog - An Erlang Priority Queue
okeuday
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)
profile
User: okeuday
Name: Michael Truog
Website: My Website
calendar
Back December 2012
1
2345678
9101112131415
16171819202122
23242526272829
3031
links
License
tags