You are viewing okeuday

Michael Truog - A Better Erlang Priority Queue
okeuday
A Better Erlang Priority Queue
The other priority queue implementations were meant to avoid the O(N) task of finding a priority within the implementation used by both Riak and RabbitMQ. The previous results showed that "priority_queue" is best for using 1 priority, "pqueue" is best for using 2 to 41 priorities, and "pqueue3" is best for using 64 or more priorities. Both the "pqueue" data structure and the "pqueue3" data structure benefited from O(1) lookup time within an Erlang tuple. However, the "pqueue" data structure has a static limitation of 41 priorities, whereas the "pqueue3" data structure supports an arbitrary number of priorities (at creation time). To merge the best of both data structures, I created the "pqueue4" data structure, which has a static limitation of 257 priorities but is implemented in a way that is similar to "pqueue".

The "pqueue4" data structure supports the priorities -128 (high) to +128 (low) and compares favorably with both "pqueue" and "pqueue3". The "pqueue4" data structure is faster than the "pqueue3" data structure, but is slightly slower than the "pqueue" data structure (due to its size). The "pqueue4" provides the best performance if 257 priorities need to be supported, and the latency will never grow based on the size of the priority queue (like it does with the "priority_queue" and "pqueue2" data structures). The benchmark was ran (with R14B04, without HiPE) on an AMD Phenom 9950 Quad-Core (64 bit) running Linux 2.6.32-23-generic (Ubuntu).

TEST pqueue_priority0
N == 1000000 (10 runs)
              pqueue get:   449060.6 µs (  1.7), set:   363759.6 µs (  2.3)
             pqueue2 get:   354847.0 µs (  1.4), set:   413158.5 µs (  2.6)
             pqueue3 get:   867085.4 µs (  3.4), set:   815489.8 µs (  5.2)
             pqueue4 get:   540231.5 µs (  2.1), set:   466625.8 µs (  3.0)
      priority_queue get:   257257.6 µs (  1.0), set:   156641.0 µs (  1.0)
TEST pqueue_priorities2
N == 1000000 (10 runs)
           2x pqueue get:   457418.0 µs (  1.3), set:   456008.8 µs (  1.0)
          2x pqueue2 get:   357993.1 µs (  1.0), set:   534914.7 µs (  1.2)
          2x pqueue3 get:   879511.6 µs (  2.5), set:   768901.8 µs (  1.7)
          2x pqueue4 get:   590378.9 µs (  1.6), set:   530402.6 µs (  1.2)
   2x priority_queue get:   428915.3 µs (  1.2), set:   519009.0 µs (  1.1)
TEST pqueue_priorities41
N == 1000000 (10 runs)
           41 pqueue get:   482050.6 µs (  1.5), set:   485457.7 µs (  1.0)
          41 pqueue2 get:   329309.2 µs (  1.0), set:  2489879.6 µs (  5.1)
          41 pqueue3 get:   928454.4 µs (  2.8), set:   834174.2 µs (  1.7)
          41 pqueue4 get:   682014.1 µs (  2.1), set:   646907.9 µs (  1.3)
   41 priority_queue get:   398687.1 µs (  1.2), set:  1600208.7 µs (  3.3)
TEST pqueue_priorities64
N == 1000000 (10 runs)
          64 pqueue2 get:   326512.2 µs (  1.0), set:  3582432.8 µs (  5.5)
          64 pqueue3 get:   875909.0 µs (  2.7), set:   827656.1 µs (  1.3)
          64 pqueue4 get:   668160.2 µs (  2.0), set:   647776.4 µs (  1.0)
   64 priority_queue get:   395522.9 µs (  1.2), set:  2238489.8 µs (  3.5)

profile
User: okeuday
Name: Michael Truog
Website: My Website
calendar
Back December 2012
1
2345678
9101112131415
16171819202122
23242526272829
3031
links
License
tags