After looking at various priority queue implementation possibilities and creating 3 separate implementations, it became necessary to test the data structures for correctness. Jesper Louis Andersen added PropEr integration, which provided randomized test cases to determine correctness, based on a priority queue model. Then, it became clear that the efficiency testing needed to focus on separate cases for different priority usage patterns. The main cases are usage of: a single priority, 2 priorities, 41 priorities, and 64 priorities, where all the priorities are evenly distributed with random, concurrent usage. The results indicate 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. 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: 444087.9 µs ( 1.8), set: 378655.3 µs ( 2.3)
pqueue2 get: 346286.3 µs ( 1.4), set: 407807.4 µs ( 2.4)
pqueue3 get: 877157.6 µs ( 3.6), set: 810117.1 µs ( 4.8)
priority_queue get: 245788.8 µs ( 1.0), set: 168242.6 µs ( 1.0)
TEST pqueue_priorities2
N == 1000000 (10 runs)
2x pqueue get: 437337.3 µs ( 1.2), set: 430425.9 µs ( 1.0)
2x pqueue2 get: 363276.3 µs ( 1.0), set: 514642.0 µs ( 1.2)
2x pqueue3 get: 871478.7 µs ( 2.4), set: 759261.5 µs ( 1.8)
2x priority_queue get: 419643.7 µs ( 1.2), set: 501706.6 µs ( 1.2)
TEST pqueue_priorities41
N == 1000000 (10 runs)
41 pqueue get: 538690.6 µs ( 1.6), set: 509626.7 µs ( 1.0)
41 pqueue2 get: 336863.6 µs ( 1.0), set: 2518901.4 µs ( 4.9)
41 pqueue3 get: 906567.4 µs ( 2.7), set: 816174.1 µs ( 1.6)
41 priority_queue get: 400770.3 µs ( 1.2), set: 1676239.8 µs ( 3.3)
TEST pqueue_priorities64
N == 1000000 (10 runs)
64 pqueue2 get: 337312.1 µs ( 1.0), set: 3721587.8 µs ( 4.3)
64 pqueue3 get: 923038.7 µs ( 2.7), set: 863387.5 µs ( 1.0)
64 priority_queue get: 399396.4 µs ( 1.2), set: 2178070.5 µs ( 2.5)
