Hash-Based Erase Memory-Use Test
This test inserts a number of uniform i.i.d. integer keys
into a container, then erases all keys except one. It measures
the final size of the container.
(The test was executed with hash_random_int_erase_mem_usage.cc
2000 2000 2100)
The test checks how containers adjust internally as their
logical size decreases (see Motivation::Associative
Containers::Slightly Different Methods::Methods Related to
Erase).
Figures NHG, NHM and
NHL show the results for the native and
collision-chaining types in g++, msvc++ and
local,
respectively.
NHG: Native, collision-chaing, and probing, hash random int erase test -
g++In the above figure, the names in the legends have the following meaning:
-
n_hash_set_ncah-
std::tr1::unordered_set with cache_hash_code = false
-
gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set-
gp_hash_table
with Comb_Hash_Fn = direct_mask_range_hashing
, Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_exponential_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/2, and Probe_Fn = linear_probe_fn
-
cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-
cc_hash_table
with Comb_Hash_Fn = direct_mod_range_hashing
, and Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_prime_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/1
-
cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-
cc_hash_table
with Comb_Hash_Fn = direct_mask_range_hashing
, and Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_exponential_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/2
NHM: Native, collision-chaing, and probing, hash random int erase test -
msvc++In the above figure, the names in the legends have the following meaning:
-
n_hash_set_ncah-
stdext::hash_set
-
gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set-
gp_hash_table
with Comb_Hash_Fn = direct_mask_range_hashing
, Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_exponential_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/2, and Probe_Fn = linear_probe_fn
-
cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-
cc_hash_table
with Comb_Hash_Fn = direct_mod_range_hashing
, and Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_prime_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/1
-
cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-
cc_hash_table
with Comb_Hash_Fn = direct_mask_range_hashing
, and Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_exponential_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/2
NHM: Native, collision-chaing, and probing, hash random int erase test -
msvc++In the above figure, the names in the legends have the following meaning:
-
n_hash_set_ncah-
stdext::hash_set
-
gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set-
gp_hash_table
with Comb_Hash_Fn = direct_mask_range_hashing
, Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_exponential_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/2, and Probe_Fn = linear_probe_fn
-
cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-
cc_hash_table
with Comb_Hash_Fn = direct_mod_range_hashing
, and Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_prime_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/1
-
cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-
cc_hash_table
with Comb_Hash_Fn = direct_mask_range_hashing
, and Resize_Policy = hash_standard_resize_policy
with Size_Policy = hash_exponential_size_policy
, and Trigger_Policy = hash_load_check_resize_trigger
with αmin = 1/8 and αmax = 1/2
NHL: Native, collision-chaing, and probing, hash random int erase test -
local
STL hash-based containers act very differently than trees in
this respect. When erasing numerous keys from an STL
associative-container, the resulting memory user varies greatly
depending on whether the container is tree-based or hash-based.
As noted in Motivation::Choice of
Methods , this is a fundamental consequence of the STL's
associative containers' interface, it is not due to a specific
implementation.
(See Priority Queue
Text pop Memory Use Test for a similar phenomenon
regarding priority queues.)