For granularity, the test is split into the several sources, each checking only some containers.
For more details, consult the files in
testsuite/ext/pb_ds/regression
.
This test inserts a number of values with keys from an
arbitrary text ([biblio.wickland96thirty]) into a container,
then performs a series of finds using
find
. It measures the average
time for find
as a function of
the number of values inserted.
It uses the test file:
performance/ext/pb_ds/text_find_timing_test.cc
And uses the data file:
filethirty_years_among_the_dead_preproc.txt
The test checks the effect of different rangehashing functions, trigger policies, and cachehashing policies.
Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
cc_hash_mod_prime_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mask_exp_1div2_sth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
cc_hash_mask_exp_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mask_exp_1div2_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

In this setting, the rangehashing scheme affects performance more than other policies. As the results show, containers using modbased rangehashing (including the native hashbased container, which is currently hardwired to this scheme) have lower performance than those using maskbased rangehashing. A modulobased rangehashing scheme's main benefit is that it takes into account all hashvalue bits. Standard string hashfunctions are designed to create hash values that are nearlyuniform as is ([biblio.knuth98sorting]).
Trigger policies, i.e. the loadchecks constants, affect performance to a lesser extent.
Perhaps surprisingly, storing the hash value alongside each
entry affects performance only marginally, at least in this
library's implementation. (Unfortunately, it was not possible to run
the tests with std::tr1::unordered_map
's
cache_hash_code = true
, as it appeared to
malfuntion.)
Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
cc_hash_mod_prime_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mod_prime_1div2_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
cc_hash_mask_exp_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mask_exp_1div2_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
gp_hash_mod_quadp_prime_1div2_nsth_map  
gp_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Probe_Fn

quadratic_probe_fn
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
gp_hash_mask_linp_exp_1div2_nsth_map  
gp_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Probe_Fn

linear_probe_fn
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
cc_hash_mod_prime_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mod_prime_1div2_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
cc_hash_mask_exp_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mask_exp_1div2_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
gp_hash_mod_quadp_prime_1div2_nsth_map  
gp_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Probe_Fn

quadratic_probe_fn
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
gp_hash_mask_linp_exp_1div2_nsth_map  
gp_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Probe_Fn

linear_probe_fn
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

It uses the test file:
performance/ext/pb_ds/random_int_subscript_insert_timing.cc
The test checks the effect of different underlying hashtables.
Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
cc_hash_mod_prime_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mod_prime_1div2_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
cc_hash_mask_exp_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mask_exp_1div2_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
gp_hash_mod_quadp_prime_1div2_nsth_map  
gp_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Probe_Fn

quadratic_probe_fn
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
gp_hash_mask_linp_exp_1div2_nsth_map  
gp_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Probe_Fn

linear_probe_fn
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

It uses the test file:
performance/ext/pb_ds/hash_zlob_random_int_find_timing.cc
The test checks the effect of different rangehashing functions and trigger policies.
Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
cc_hash_mod_prime_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mask_exp_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
gp_hash_mod_quadp_prime_1div2_nsth_map  
gp_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Probe_Fn

quadratic_probe_fn
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

It uses the test file:
performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc
The test checks how containers adjust internally as their logical size decreases.
Name/Instantiating Type  Parameter  Details  Parameter  Details 

n_hash_map_ncah  
std::tr1::unordered_map

cache_hash_code

false
 
cc_hash_mod_prime_1div1_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mod_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_prime_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/1
 
cc_hash_mask_exp_1div2_nsth_map  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
gp_hash_mask_linp_exp_1div2_nsth_set  
gp_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Probe_Fn

linear_probe_fn
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

The test checks the effect of different underlying data structures.
It uses the test file:
performance/ext/pb_ds/tree_text_insert_timing.cc
Name/Instantiating Type  Parameter  Details 

n_map  
std::map
 
splay_tree_map  
tree

Tag

splay_tree_tag

Node_update

null_node_update
 
rb_tree_map  
tree

Tag

rb_tree_tag

Node_update

null_node_update

The graphic below shows the results for the native tree type and a vectorbased tree type.
Name/Instantiating Type  Parameter  Details 

n_map  
std::map
 
ov_tree_map  
tree

Tag

ov_tree_tag

Node_update

null_node_update

The graphic below shows the results for the native tree type and a PATRICIA trie type.
Name/Instantiating Type  Parameter  Details 

n_map  
std::map
 
pat_trie_map  
tree

Tag

pat_trie_tag

Node_update

null_node_update

It uses the test file:
performance/ext/pb_ds/text_find_timing.cc
The test checks the effect of different underlying data structures.
Name/Instantiating Type  Parameter  Details 

n_map  
std::map
 
splay_tree_map  
tree

Tag

splay_tree_tag

Node_Update

null_node_update
 
rb_tree_map  
tree

Tag

rb_tree_tag

Node_Update

null_node_update
 
ov_tree_map  
tree

Tag

ov_tree_tag

Node_Update

null_node_update
 
pat_trie_map  
tree

Tag

pat_trie_tag

Node_Update

null_node_update

Name/Instantiating Type  Parameter  Details 

n_map  
std::map
 
splay_tree_map  
tree

Tag

splay_tree_tag

Node_Update

null_node_update
 
rb_tree_map  
tree

Tag

rb_tree_tag

Node_Update

null_node_update
 
ov_tree_map  
tree

Tag

ov_tree_tag

Node_Update

null_node_update
 
pat_trie_map  
tree

Tag

pat_trie_tag

Node_Update

null_node_update

Name/Instantiating Type  Parameter  Details 

n_set  
std::set
 
splay_tree_set  
tree

Tag

splay_tree_tag

Node_Update

null_node_update
 
rb_tree_set  
tree

Tag

rb_tree_tag

Node_Update

null_node_update
 
ov_tree_set  
tree

Tag

ov_tree_tag

Node_Update

null_node_update
 
pat_trie_map  
tree

Tag

pat_trie_tag

Node_Update

null_node_update

Name/Instantiating Type  Parameter  Details 

n_set  
std::set
 
splay_tree_ost_set  
tree

Tag

splay_tree_tag

Node_Update

tree_order_statistics_node_update
 
rb_tree_ost_set  
tree

Tag

rb_tree_tag

Node_Update

tree_order_statistics_node_update

It uses the test file:
performance/ext/pb_ds/multimap_text_find_timing_small.cc
The test checks the findtime scalability of different "multimap" designs.
Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_mmap  
std::multimap
 
rb_tree_mmap_lu_mtf_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_hash_mmap  
std::tr1::unordered_multimap
 
rb_tree_mmap_lu_mtf_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

It uses the test file:
performance/ext/pb_ds/multimap_text_find_timing_large.cc
The test checks the findtime scalability of different "multimap" designs.
Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_mmap  
std::multimap
 
rb_tree_mmap_lu_mtf_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_hash_mmap  
std::tr1::unordered_multimap
 
rb_tree_mmap_lu_mtf_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

It uses the test file:
performance/ext/pb_ds/multimap_text_insert_timing_small.cc
The test checks the inserttime scalability of different "multimap" designs.
Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_mmap  
std::multimap
 
rb_tree_mmap_lu_mtf_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_hash_mmap  
std::tr1::unordered_multimap
 
rb_tree_mmap_lu_mtf_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

It uses the test file:
performance/ext/pb_ds/multimap_text_insert_timing_large.cc
The test checks the inserttime scalability of different "multimap" designs.
Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_mmap  
std::multimap
 
rb_tree_mmap_lu_mtf_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_hash_mmap  
std::tr1::unordered_multimap
 
rb_tree_mmap_lu_mtf_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

The test measures the memory use as a function of the number of values inserted.
It uses the test file:
performance/ext/pb_ds/multimap_text_insert_mem_usage_small.cc
The test checks the memory scalability of different "multimap" designs.
Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_mmap  
std::multimap
 
rb_tree_mmap_lu_mtf_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_hash_mmap  
std::tr1::unordered_multimap
 
rb_tree_mmap_lu_mtf_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

The test measures the memory use as a function of the number of values inserted.
It uses the test file:
performance/ext/pb_ds/multimap_text_insert_mem_usage_large.cc
The test checks the memory scalability of different "multimap" designs.
Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_mmap  
std::multimap
 
rb_tree_mmap_lu_mtf_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
tree

Tag

rb_tree_tag
 
Node_Update

null_node_update
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

Name/Instantiating Type  Parameter  Details  Parameter  Details  Parameter  Details 

n_hash_mmap  
std::tr1::unordered_multimap
 
rb_tree_mmap_lu_mtf_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

list_update

Update_Policy

lu_move_to_front_policy
 
rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set  
cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2
 
Mapped

cc_hash_table

Comb_Hash_Fn

direct_mask_range_hashing
 
Resize_Policy

hash_standard_resize_policy

Size_Policy

hash_exponential_size_policy
 
Trigger_Policy

hash_load_check_resize_trigger with
α_{min} = 1/8 and α_{max} = 1/2

It uses the test file:
performance/ext/pb_ds/priority_queue_text_push_timing.cc
The test checks the effect of different underlying data structures.
Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

binomial_heap  
priority_queue

Tag

binomial_heap_tag

rc_binomial_heap  
priority_queue

Tag

rc_binomial_heap_tag

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

It uses the test file:
performance/ext/pb_ds/priority_queue_text_push_pop_timing.cc
The test checks the effect of different underlying data structures.
Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

binomial_heap  
priority_queue

Tag

binomial_heap_tag

rc_binomial_heap  
priority_queue

Tag

rc_binomial_heap_tag

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue adapting std::vector

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

pairing_heap  
priority_queue

Tag

pairing_heap_tag

It uses the test file:
performance/ext/pb_ds/priority_queue_random_int_push_timing.cc
The test checks the effect of different underlying data structures.
Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

binomial_heap  
priority_queue

Tag

binomial_heap_tag

rc_binomial_heap  
priority_queue

Tag

rc_binomial_heap_tag

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue adapting std::vector

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

It uses the test file:
performance/ext/pb_ds/priority_queue_random_int_push_pop_timing.cc
The test checks the effect of different underlying data structures.
Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

binomial_heap  
priority_queue

Tag

binomial_heap_tag

rc_binomial_heap  
priority_queue

Tag

rc_binomial_heap_tag

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

It uses the test file:
performance/ext/pb_ds/priority_queue_text_pop_mem_usage.cc
The test checks the effect of different underlying data structures.
Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

binomial_heap  
priority_queue

Tag

binomial_heap_tag

rc_binomial_heap  
priority_queue

Tag

rc_binomial_heap_tag

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

It uses the test file:
performance/ext/pb_ds/priority_queue_text_join_timing.cc
The test checks the effect of different underlying data structures.
Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

binomial_heap  
priority_queue

Tag

binomial_heap_tag

rc_binomial_heap  
priority_queue

Tag

rc_binomial_heap_tag

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

binomial_heap  
priority_queue

Tag

binomial_heap_tag

rc_binomial_heap  
priority_queue

Tag

rc_binomial_heap_tag

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

Name/Instantiating Type  Parameter  Details 

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

It uses the test file:
performance/ext/pb_ds/priority_queue_text_modify_down_timing.cc
The main purpose of this test is to contrast Priority Queue
Text modify
Up Timing Test.
Name/Instantiating Type  Parameter  Details 

n_pq_vector  
std::priority_queue

Sequence

std::vector

n_pq_deque  
std::priority_queue

Sequence

std::deque

binary_heap  
priority_queue

Tag

binary_heap_tag

binomial_heap  
priority_queue

Tag

binomial_heap_tag

rc_binomial_heap  
priority_queue

Tag

rc_binomial_heap_tag

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

Name/Instantiating Type  Parameter  Details 

thin_heap  
priority_queue

Tag

thin_heap_tag

pairing_heap  
priority_queue

Tag

pairing_heap_tag

push  pop  modify  erase  join  

std::priority_queue
 Θ(n) worst Θ(log(n)) amortized  Θ(log(n)) Worst  Θ(n log(n)) Worst _{[std note 1]}  Θ(n log(n)) _{[std note 2]}  Θ(n log(n)) _{[std note 1]} 
priority_queue
<Tag =
pairing_heap_tag >
 O(1)  Θ(n) worst Θ(log(n)) amortized  Θ(n) worst Θ(log(n)) amortized  Θ(n) worst Θ(log(n)) amortized  O(1) 
priority_queue
<Tag =
binary_heap_tag >
 Θ(n) worst Θ(log(n)) amortized  Θ(n) worst Θ(log(n)) amortized  Θ(n)  Θ(n)  Θ(n) 
priority_queue
<Tag =
binomial_heap_tag >
 Θ(log(n)) worst O(1) amortized  Θ(log(n))  Θ(log(n))  Θ(log(n))  Θ(log(n)) 
priority_queue
<Tag =
rc_binomial_heap_tag >
 O(1)  Θ(log(n))  Θ(log(n))  Θ(log(n))  Θ(log(n)) 
priority_queue <Tag =
thin_heap_tag >
 O(1)  Θ(n) worst Θ(log(n)) amortized  Θ(log(n)) worst O(1) amortized, or Θ(log(n)) amortized _{[thin_heap_note]}  Θ(n) worst Θ(log(n)) amortized  Θ(n) 