okeuday

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)

LJ Video