Priority Queue Text modify Timing Test - I

Description

This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into into a container then modifies each one "up" (i.e., it makes it larger). 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_up_timing_test thirty_years_among_the_dead_preproc.txt 200 200 2100 t)

Purpose

The test checks the effect of different underlying data structures (see Design::Priority Queues::Implementations) for graph algorithms settings. Note that making an arbitrary value larger (in the sense of the priority queue's comparison functor) corresponds to decrease-key in standard graph algorithms [clrs2001].

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. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  5. pairing_heap- priority_queue with Tag = pairing_heap_tag
  6. binomial_heap- priority_queue with Tag = binomial_heap_tag
  7. thin_heap- priority_queue with Tag = thin_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. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  5. pairing_heap- priority_queue with Tag = pairing_heap_tag
  6. binomial_heap- priority_queue with Tag = binomial_heap_tag
  7. thin_heap- priority_queue with Tag = thin_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. pairing_heap- priority_queue with Tag = pairing_heap_tag
  2. thin_heap- priority_queue with Tag = thin_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. pairing_heap- priority_queue with Tag = pairing_heap_tag
  2. thin_heap- priority_queue with Tag = thin_heap_tag
no image
NRTL: Pairing and thin priority queue modify timing test - local

Observations

As noted above, increasing an arbitrary value (in the sense of the priority queue's comparison functor) is very common in graph-related algorithms. In this case, a thin heap (priority_queue with Tag = thin_heap_tag) outperforms a pairing heap (priority_queue with Tag = pairing_heap_tag). Conversely, Priority Queue Text push Timing Test, Priority Queue Text push and pop Timing Test, Priority Queue Random Integer push Timing Test, and Priority Queue Random Integer push and pop Timing Test show that the situation is reversed for other operations. It is not clear when to prefer one of these two different types.

In this test pb_ds's binary heaps effectively perform modify in linear time. As explained in Priority Queue Design::Traits, given a valid point-type iterator, a binary heap can perform modify logarithmically. The problem is that binary heaps invalidate their find iterators with each modifying operation, and so the only way to obtain a valid point-type iterator is to iterate using a range-type iterator until finding the appropriate value, then use the range-type iterator for the modify operation.

The explanation for the STL's priority queues' performance is similar to that in Priority Queue Text join Timing Test.

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