An Erlang Priority Queue (continued)
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)