Priority Queue Text modify Timing Test - II

Description

This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into into a container then modifies each one "down" (i.e., it makes it smaller). It uses modify for pb_ds's priority queues; for the STL's priority queues, it pops values from a container until it reaches the value that should be modified, then pushes values back in. It measures the average time for modify as a function of the number of values.

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

Purpose

The main purpose of this test is to contrast Priority Queue Text modify Timing Test - I.

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 NRTG, NRTM, and NRTL show the results for the pairing heap and thin heaps in g++, msvc++, and local, respectively,

no image
NPG: Native and pb ds priority queue modify 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
  4. thin_heap- priority_queue with Tag = thin_heap_tag
  5. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  6. binomial_heap- priority_queue with Tag = binomial_heap_tag
  7. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NPM: Native and pb ds priority queue modify 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
  4. thin_heap- priority_queue with Tag = thin_heap_tag
  5. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  6. binomial_heap- priority_queue with Tag = binomial_heap_tag
  7. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NPL: Native and pb ds priority queue modify timing test - local
no image
NRTG: Pairing and thin priority queue modify 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. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NRTM: Pairing and thin priority queue modify 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. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NRTL: Pairing and thin priority queue modify timing test - local

Observations

Most points in these results are similar to Priority Queue Text modify Timing Test - I.

It is interesting to note, however, that as opposed to that test, a thin heap (priority_queue with Tag = thin_heap_tag) is outperformed by a pairing heap (priority_queue with Tag = pairing_heap_tag). In this case, both heaps essentially perform an erase operation followed by a push operation. As the other tests show, a pairing heap is usually far more efficient than a thin heap, so this is not surprising.

Most algorithms that involve priority queues increase values (in the sense of the priority queue's comparison functor), and so Priority Queue Text modify Timing Test - I is more interesting than this test.