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)