Tree Text Locality of Reference Timing Test (original) (raw)

Hash-Based Erase Memory-Use Test

Description

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)

Purpose

The test checks how containers adjust internally as their logical size decreases (see Motivation::Associative Containers::Slightly Different Methods::Methods Related to Erase).

Results

Figures NHG, NHM andNHL show the results for the native and collision-chaining types in g++, msvc++ andlocal, respectively.

no image

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:

  1. n_hash_set_ncah-std::tr1::unordered_set with cache_hash_code = false
  2. 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
  3. cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-cc_hash_tablewith 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
  4. cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-cc_hash_tablewith 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
no image

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:

  1. n_hash_set_ncah-stdext::hash_set
  2. 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
  3. cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-cc_hash_tablewith 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
  4. cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-cc_hash_tablewith 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
no image

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:

  1. n_hash_set_ncah-stdext::hash_set
  2. 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
  3. cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-cc_hash_tablewith 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
  4. cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-cc_hash_tablewith 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
no image

NHL: Native, collision-chaing, and probing, hash random int erase test - local

Observations

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