Priority Queue Text Pop Memory Use Test (original) (raw)

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, andNPL show the results for the native priority queues and pb_ds 's priority queues in g++, msvc++, andlocal, respectively.

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 andPriority 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.)