Priority Queue Random Integer push Timing Test

Description

This test inserts a number of values with i.i.d integer keys into a container using push . It measures the average time for push as a function of the number of values.

(The test was executed with priority_queue_random_intpush_timing_test thirty_years_among_the_dead_preproc.txt 200 200 2100)

Purpose

The test checks the effect of different underlying data structures (see Design::Priority Queues::Implementations).

Results

Figures NPG, NPM, and NPL show the results for the native priority queues and pb_ds 's priority queues in g++, msvc++, and local, respectively; Figures NBPG, NBPM, and NBPL shows the results for the binary-heap based native priority queues and pb_ds 's priority queues in g++, msvc++, and local, respectively

no image
NPG: Native and pb ds priority queue push timing test - g++

In the above figure, the names in the legends have the following meaning:

  1. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  2. binomial_heap- priority_queue with Tag = binomial_heap_tag
  3. n_pq_deque- std::priority_queue adapting std::deque
  4. pairing_heap- priority_queue with Tag = pairing_heap_tag
  5. thin_heap- priority_queue with Tag = thin_heap_tag
  6. n_pq_vector- std::priority_queue adapting std::vector
  7. binary_heap- priority_queue with Tag = binary_heap_tag
no image
NPM: Native and pb ds priority queue push timing test - msvc++

In the above figure, the names in the legends have the following meaning:

  1. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  2. binomial_heap- priority_queue with Tag = binomial_heap_tag
  3. pairing_heap- priority_queue with Tag = pairing_heap_tag
  4. thin_heap- priority_queue with Tag = thin_heap_tag
  5. n_pq_deque- std::priority_queue adapting std::deque
  6. n_pq_vector- std::priority_queue adapting std::vector
  7. binary_heap- priority_queue with Tag = binary_heap_tag
no image
NPL: Native and pb ds priority queue push timing test - local
no image
NBPG: Native and pb ds binary priority queue push timing test - g++

In the above figure, the names in the legends have the following meaning:

  1. n_pq_deque- std::priority_queue adapting std::deque
  2. n_pq_vector- std::priority_queue adapting std::vector
  3. binary_heap- priority_queue with Tag = binary_heap_tag
no image
NBPM: Native and pb ds binary priority queue push timing test - msvc++

In the above figure, the names in the legends have the following meaning:

  1. n_pq_deque- std::priority_queue adapting std::deque
  2. n_pq_vector- std::priority_queue adapting std::vector
  3. binary_heap- priority_queue with Tag = binary_heap_tag
no image
NBPL: Native and pb ds binary priority queue push timing test - local

Observations

Binary heaps are the most suited for sequences of push and pop operations of primitive types (e.g. ints). They are less constrained than any other type, and since it is very efficient to store such types in arrays, they outperform even pairing heaps. (See Priority Queue Text push Timing Test for the case of non-primitive types.)

Priority-Queue Performance Tests::Observations discusses this further and summarizes.