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

  • trie retest

    The older trie (speed) testing didn't experiment with Erlang compilation options and used Erlang R14B01 (newest, at the time). To examine how…

  • v4 UUIDs

    After updating the Erlang uuid implementation to fix various bugs, I added uuid:get_v4_urandom/0 function to utilize the 2006 Wichmann-Hill…

  • A Better Erlang Priority Queue

    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…

  • Post a new comment

    Error

    switch
    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.
    Help
  • 0 comments