Hash-Based Random-Integer operator[] FindTiming Test

Description

This test inserts a number of values with uniform i.i.d. integer keys into a container, then performs a series of finds using operator[]. It measures the average time for operator[] as a function of the number of values inserted.

(The test was executed with hash_random_int_subscript_find_timing_test 200 200 2100)

Purpose

The test checks the effect of different underlying hash-tables (see Design::Hash-Based Containers ), range-hashing functions, and trigger policies (see Design::Hash-Based Containers::Hash Policies and Design::Hash-Based Containers::Resize Policies ).

Results

Figures NCCG, NCCM, and NCCL show the results for the native and collision-chaining types in g++, MSVC++, and local, respectively; Figures NGPG, NGPM, and NGPL show the results for the native and probing types in g++, MSVC++, and local, respectively.

no image
NCCG: Native and collision-chaining hash random int find timing test using operator[] - g++

In the above figure, the names in the legends have the following meaning:

  1. n_hash_map_ncah- std::tr1::unordered_map with cache_hash_code = false
  2. cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- 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
  3. cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 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/2
  4. cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 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/1
  5. cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 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
no image
NCCM: Native and collision-chaining hash random int find timing test using operator[] - msvc++

In the above figure, the names in the legends have the following meaning:

  1. cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- 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
  2. cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 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/2
  3. n_hash_map_ncah- stdext::hash_map
  4. cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 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/1
  5. cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 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
no image
NCCL: Native and collision-chaining hash random int find timing test using operator[] - local
no image
NGPG: Native and probing hash random int find timing test using operator[] - g++

In the above figure, the names in the legends have the following meaning:

  1. n_hash_map_ncah- std::tr1::unordered_map with cache_hash_code = false
  2. gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- gp_hash_table with Comb_Hash_Fn = direct_mod_range_hashing , 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/2, and Probe_Fn = quadratic_probe_fn
  3. gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 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
no image
NGPM: Native and probing hash random int find timing test using operator[] - msvc++

In the above figure, the names in the legends have the following meaning:

  1. gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- gp_hash_table with Comb_Hash_Fn = direct_mod_range_hashing , 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/2, and Probe_Fn = quadratic_probe_fn
  2. n_hash_map_ncah- stdext::hash_map
  3. gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 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
no image
NGPL: Native and probing hash random int find timing test using operator[] - local

Observations

This test shows similar results to Hash-Based Random-Integer find Find Timing Test .