Michael Truog (okeuday) wrote,
Michael Truog
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)
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments