Priority Queue Text push Timing Test

Description

This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container using push . It measures the average time for push as a function of the number of values pushed.

(The test was executed with priority_queue_text_push_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 NBRG, NBRM, and NBRL shows the results for the binary-heap based native priority queues and pb_ds's pairing-heap 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. n_pq_vector- std::priority_queue adapting std::vector
  2. n_pq_deque- std::priority_queue adapting std::deque
  3. binary_heap- priority_queue with Tag = binary_heap_tag
  4. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  5. thin_heap- priority_queue with Tag = thin_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 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. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  3. binary_heap- priority_queue with Tag = binary_heap_tag
  4. binomial_heap- priority_queue with Tag = binomial_heap_tag
  5. n_pq_vector- std::priority_queue adapting std::vector
  6. pairing_heap- priority_queue with Tag = pairing_heap_tag
  7. thin_heap- priority_queue with Tag = thin_heap_tag
no image
NPL: Native and pb ds priority queue push timing test - local
no image
NBRG: Native and pb ds pairing priority queue push timing test - g++

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

  1. n_pq_vector- std::priority_queue adapting std::vector
  2. n_pq_deque- std::priority_queue adapting std::deque
  3. thin_heap- priority_queue with Tag = thin_heap_tag
  4. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NBRM: Native and pb ds pairing 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. pairing_heap- priority_queue with Tag = pairing_heap_tag
  4. thin_heap- priority_queue with Tag = thin_heap_tag
no image
NBRL: Native and pb ds pairing priority queue push timing test - local

Observations

Pairing heaps (priority_queue with Tag = pairing_heap_tag) are the most suited for sequences of push and pop operations of non-primitive types (e.g. std::strings). (see also Priority Queue Text push and pop Timing Test.) They are less constrained than binomial heaps, e.g., and since they are node-based, they outperform binary heaps. (See Priority Queue Random Integer push Timing Test for the case of primitive types.)

The STL's priority queues do not seem to perform well in this case: the std::vector implementation needs to perform a logarithmic sequence of string operations for each operation, and the deque implementation is possibly hampered by its need to manipulate a relatively-complex type (deques support a O(1) push_front, even though it is not used by std::priority_queue.)

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