Priority Queue Text pop Memory Use Test

Description

This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container, then pops them until only one is left in the container. It measures the memory use as a function of the number of values pushed to the container.

(The test was executed with priority_queue_text_pop_mem_usage_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.

no image
NPG: Native and pb ds priority queue pop memory-use 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. thin_heap- priority_queue with Tag = thin_heap_tag
  5. binomial_heap- priority_queue with Tag = binomial_heap_tag
  6. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  7. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NPM: Native and pb ds priority queue pop memory-use test - msvc++

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. thin_heap- priority_queue with Tag = thin_heap_tag
  5. binomial_heap- priority_queue with Tag = binomial_heap_tag
  6. rc_binomial_heap- priority_queue with Tag = rc_binomial_heap_tag
  7. pairing_heap- priority_queue with Tag = pairing_heap_tag
no image
NPL: Native and pb ds priority queue pop memory-use test - local

Observations

The priority queue implementations (excluding the STL's) use memory proportionally to the number of values they hold: node-based implementations (e.g., a pairing heap) do so naturally; pb_ds's binary heap de-allocates memory when a certain lower threshold is exceeded.

Note from Priority Queue Text push and pop Timing Test and Priority Queue Random Integer push and pop Timing Test that this does not impede performance compared to the STL's priority queues.

(See Hash-Based Erase Memory Use Test for a similar phenomenon regarding priority queues.)