Priority Queue Random Integer push and pop Timing Test

Description

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

(The test was executed with priority_queue_random_int_push_pop_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 shows the results for the 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 pop timing test - g++

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

  1. thin_heap- priority_queue with Tag = thin_heap_tag
  2. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  3. binomial_heap- priority_queue with Tag = binomial_heap_tag
  4. pairing_heap- priority_queue with Tag = pairing_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
NPM: Native and pb ds priority queue push pop timing test - msvc++

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

  1. thin_heap- priority_queue with Tag = thin_heap_tag
  2. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  3. binomial_heap- priority_queue with Tag = binomial_heap_tag
  4. pairing_heap- priority_queue with Tag = pairing_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 pop timing test - local

Observations

Binary heaps are the most suited for sequences of push and pop operations of primitive types (e.g. ints). This is explained in Priority Queue Random Int push Timing Test . (See Priority Queue Text push Timing Test for the case of primitive types.)

At first glance it seems that the STL's vector-based priority queue is approximately on par with pb_ds's corresponding priority queue. There are two differences however:

  1. The STL's priority queue does not downsize the underlying vector (or deque) as the priority queue becomes smaller (see Priority Queue Text pop Memory Use Test). It is therefore gaining some speed at the expense of space.
  2. From Priority Queue Random Integer push and pop Timing Test, it seems that the STL's priority queue is slower in terms of pus operations. Since the number of pop operations is at most that of push operations, the test here is the "best" for the STL's priority queue.

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