1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 4<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 5<head> 6<meta name="generator" content="HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" /> 7<title>Hash Random Int Subscript Insert Timing Test</title> 8<meta http-equiv="Content-Type" content="text/html; charset=us-ascii" /> 9</head> 10<body> 11<div id="page"> 12<h1>Hash-Based Random-Integer <tt><b>operator</b>[]</tt> Insert 13 Timing Test</h1> 14<h2><a name="description" id="description">Description</a></h2> 15<p>This test inserts a number of values with uniform i.i.d. 16 integer keys into a container, using 17 <tt><b>operator</b>[]</tt>. It measures the average time for 18 <tt><b>operator</b>[]</tt> as a function of the number of 19 values inserted.</p> 20<p>(The test was executed with <a href="http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/performance/ext/pb_ds/random_int_subscript_insert_timing.cc"><tt>hash_random_int_subscript_insert_timing_test</tt></a> 21 200 200 2100)</p> 22<h2><a name="purpose" id="purpose">Purpose</a></h2> 23<p>The test primarily checks the effect of different underlying 24 hash-tables (see <a href="hash_based_containers.html">Design::Associative 25 Containers::Associative Containers::Hash-Based 26 Containers</a>).</p> 27<h2><a name="results" id="results">Results</a></h2> 28<p>Figures <a href="#NCCG">NCCG</a>, <a href="#NCCM">NCCM</a>, 29 and <a href="#NCCL">NCCL</a> show the results for the native 30 and collision-chaining types in <a href="assoc_performance_tests.html#gcc"><u>g++</u></a>, <a href="assoc_performance_tests.html#msvc"><u>MSVC++</u></a>, and 31 <a href="assoc_performance_tests.html#local"><u>local</u></a>, 32 respectively; Figures <a href="#NGPG">NGPG</a>, <a href="#NGPM">NGPM</a>, and <a href="#NGPL">NGPL</a> show the results 33 for the native and probing types in <a href="assoc_performance_tests.html#gcc"><u>g++</u></a>, <a href="assoc_performance_tests.html#msvc"><u>msvc++</u></a>, and 34 <a href="assoc_performance_tests.html#local"><u>local</u></a> 35 respectively; Figures <a href="#CCGPG">CCGPG</a>, <a href="#CCGPM">CCGPM</a>, and <a href="#CCGPL">CCGPL</a> compare the 36 results for the collision-chaining and probing types of 37 <tt>pb_ds</tt> only, in <a href="assoc_performance_tests.html#gcc"><u>g++</u></a>, <a href="assoc_performance_tests.html#msvc"><u>MSVC++</u></a>, and 38 <a href="assoc_performance_tests.html#local"><u>local</u></a> 39 respectively.</p> 40<div id="NCCG_res_div"> 41<div id="NCCG_gcc"> 42<div id="NCCG_cc_hash_random_int_subscript_timing_test_insert"> 43<div id="NCCG_assoc"> 44<div id="NCCG_Native_and_collision-chaining_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NCCG" id="NCCG"><img src="cc_hash_random_int_subscript_timing_test_insert_gcc.png" alt="no image" /></a></h6>NCCG: Native and collision-chaining hash random int insert timing test using <tt><b>operator</b></tt> - <a href="assoc_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p> 45<ol> 46<li> 47cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 48<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 49with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 50, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 51 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 52, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 53 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 54<li> 55n_hash_map_ncah- 56<tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li> 57<li> 58cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 59<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 60with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 61, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 62 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 63, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 64 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 65<li> 66cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- 67<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 68with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 69, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 70 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 71, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 72 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 73<li> 74cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 75<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 76with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 77, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 78 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 79, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 80 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 81</ol> 82</div><div style="width: 100%; height: 20px"></div></div> 83</div> 84</div> 85</div> 86</div> 87<div id="NCCM_res_div"> 88<div id="NCCM_msvc"> 89<div id="NCCM_cc_hash_random_int_subscript_timing_test_insert"> 90<div id="NCCM_assoc"> 91<div id="NCCM_Native_and_collision-chaining_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NCCM" id="NCCM"><img src="cc_hash_random_int_subscript_timing_test_insert_msvc.png" alt="no image" /></a></h6>NCCM: Native and collision-chaining hash random int insert timing test using <tt><b>operator</b></tt> - <a href="assoc_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p> 92<ol> 93<li> 94n_hash_map_ncah- 95<tt>stdext::hash_map</tt></li> 96<li> 97cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 98<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 99with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 100, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 101 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 102, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 103 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 104<li> 105cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- 106<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 107with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 108, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 109 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 110, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 111 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 112<li> 113cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 114<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 115with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 116, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 117 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 118, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 119 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 120<li> 121cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 122<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 123with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 124, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 125 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 126, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 127 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 128</ol> 129</div><div style="width: 100%; height: 20px"></div></div> 130</div> 131</div> 132</div> 133</div> 134<div id="NCCL_res_div"> 135<div id="NCCL_local"> 136<div id="NCCL_cc_hash_random_int_subscript_timing_test_insert"> 137<div id="NCCL_assoc"> 138<div id="NCCL_Native_and_collision-chaining_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NCCL" id= "NCCL"><img src="cc_hash_random_int_subscript_timing_test_insert_local.png" alt="no image" /></a></h6>NCCL: Native and collision-chaining hash random int insert timing test using <tt><b>operator</b></tt> - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 139</div> 140</div> 141</div> 142</div> 143<div id="NGPG_res_div"> 144<div id="NGPG_gcc"> 145<div id="NGPG_gp_hash_random_int_subscript_timing_test_insert"> 146<div id="NGPG_assoc"> 147<div id="NGPG_Native_and_probing_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NGPG" id="NGPG"><img src="gp_hash_random_int_subscript_timing_test_insert_gcc.png" alt="no image" /></a></h6>NGPG: Native and probing hash random int insert timing test using <tt><b>operator</b></tt> - <a href="assoc_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p> 148<ol> 149<li> 150gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- 151<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 152 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 153, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 154 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 155, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 156 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i>, and <tt>Probe_Fn</tt> = <a href="quadratic_probe_fn.html"><tt>quadratic_probe_fn</tt></a> 157</li> 158<li> 159n_hash_map_ncah- 160<tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li> 161<li> 162gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 163<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 164 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 165, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 166 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 167, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 168 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i>, and <tt>Probe_Fn</tt> = <a href="linear_probe_fn.html"><tt>linear_probe_fn</tt></a> 169</li> 170</ol> 171</div><div style="width: 100%; height: 20px"></div></div> 172</div> 173</div> 174</div> 175</div> 176<div id="NGPM_res_div"> 177<div id="NGPM_msvc"> 178<div id="NGPM_gp_hash_random_int_subscript_timing_test_insert"> 179<div id="NGPM_assoc"> 180<div id="NGPM_Native_and_probing_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NGPM" id="NGPM"><img src="gp_hash_random_int_subscript_timing_test_insert_msvc.png" alt="no image" /></a></h6>NGPM: Native and probing hash random int insert timing test using <tt><b>operator</b></tt> - <a href="assoc_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p> 181<ol> 182<li> 183n_hash_map_ncah- 184<tt>stdext::hash_map</tt></li> 185<li> 186gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- 187<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 188 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 189, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 190 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 191, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 192 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i>, and <tt>Probe_Fn</tt> = <a href="quadratic_probe_fn.html"><tt>quadratic_probe_fn</tt></a> 193</li> 194<li> 195gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 196<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 197 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 198, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 199 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 200, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 201 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i>, and <tt>Probe_Fn</tt> = <a href="linear_probe_fn.html"><tt>linear_probe_fn</tt></a> 202</li> 203</ol> 204</div><div style="width: 100%; height: 20px"></div></div> 205</div> 206</div> 207</div> 208</div> 209<div id="NGPL_res_div"> 210<div id="NGPL_local"> 211<div id="NGPL_gp_hash_random_int_subscript_timing_test_insert"> 212<div id="NGPL_assoc"> 213<div id="NGPL_Native_and_probing_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NGPL" id= "NGPL"><img src="gp_hash_random_int_subscript_timing_test_insert_local.png" alt="no image" /></a></h6>NGPL: Native and probing hash random int insert timing test using <tt><b>operator</b></tt> - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 214</div> 215</div> 216</div> 217</div> 218<div id="CCGPG_res_div"> 219<div id="CCGPG_gcc"> 220<div id="CCGPG_ccgp_hash_random_int_subscript_timing_test_insert"> 221<div id="CCGPG_assoc"> 222<div id="CCGPG_Collision-chaining_and_probing_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="CCGPG" id="CCGPG"><img src="ccgp_hash_random_int_subscript_timing_test_insert_gcc.png" alt="no image" /></a></h6>CCGPG: Collision-chaining and probing hash random int insert timing test using <tt><b>operator</b></tt> - <a href="assoc_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p> 223<ol> 224<li> 225gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- 226<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 227 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 228, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 229 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 230, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 231 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i>, and <tt>Probe_Fn</tt> = <a href="quadratic_probe_fn.html"><tt>quadratic_probe_fn</tt></a> 232</li> 233<li> 234cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 235<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 236with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 237, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 238 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 239, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 240 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 241<li> 242cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 243<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 244with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 245, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 246 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 247, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 248 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 249<li> 250gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 251<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 252 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 253, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 254 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 255, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 256 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i>, and <tt>Probe_Fn</tt> = <a href="linear_probe_fn.html"><tt>linear_probe_fn</tt></a> 257</li> 258</ol> 259</div><div style="width: 100%; height: 20px"></div></div> 260</div> 261</div> 262</div> 263</div> 264<div id="CCGPM_res_div"> 265<div id="CCGPM_msvc"> 266<div id="CCGPM_ccgp_hash_random_int_subscript_timing_test_insert"> 267<div id="CCGPM_assoc"> 268<div id="CCGPM_Collision-chaining_and_probing_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="CCGPM" id="CCGPM"><img src="ccgp_hash_random_int_subscript_timing_test_insert_msvc.png" alt="no image" /></a></h6>CCGPM: Collision-chaining and probing hash random int insert timing test using <tt><b>operator</b></tt> - <a href="assoc_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p> 269<ol> 270<li> 271cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 272<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 273with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 274, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 275 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 276, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 277 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 278<li> 279cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 280<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 281with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 282, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 283 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 284, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 285 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 286<li> 287gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- 288<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 289 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 290, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 291 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 292, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 293 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i>, and <tt>Probe_Fn</tt> = <a href="quadratic_probe_fn.html"><tt>quadratic_probe_fn</tt></a> 294</li> 295<li> 296gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 297<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 298 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 299, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 300 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 301, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 302 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i>, and <tt>Probe_Fn</tt> = <a href="linear_probe_fn.html"><tt>linear_probe_fn</tt></a> 303</li> 304</ol> 305</div><div style="width: 100%; height: 20px"></div></div> 306</div> 307</div> 308</div> 309</div> 310<div id="CCGPL_res_div"> 311<div id="CCGPL_local"> 312<div id="CCGPL_ccgp_hash_random_int_subscript_timing_test_insert"> 313<div id="CCGPL_assoc"> 314<div id="CCGPL_Collision-chaining_and_probing_hash_random_int_insert_timing_test_using__tt__b_operator_455b__455tt_"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="CCGPL" id= "CCGPL"><img src="ccgp_hash_random_int_subscript_timing_test_insert_local.png" alt="no image" /></a></h6>CCGPL: Collision-chaining and probing hash random int insert timing test using <tt><b>operator</b></tt> - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 315</div> 316</div> 317</div> 318</div> 319<h2><a name="observations" id="observations">Observations</a></h2> 320<p>In this setting, as in <a href="hash_text_find_find_timing_test.html">Hash-Based Text 321 <tt>find</tt> Find Timing Test</a> and <a href="hash_random_int_find_find_timing_test.html">Hash-Based 322 Random-Integer <tt>find</tt> Find Timing Test</a> , the choice 323 of underlying hash-table underlying hash-table (see <a href="hash_based_containers.html">Design::Associative 324 Containers::Hash-Based Containers</a> ) affects performance 325 most, then the range-hashing scheme (See <a href="hash_based_containers.html#hash_policies">Design::Associative 326 Containers::Hash-Based Containers::Hash Policies</a> ), and, 327 only finally, other policies.</p> 328<p>There are some differences, however:</p> 329<ol> 330<li>In this setting, probing tables function sometimes more 331 efficiently than collision-chaining tables (see Figures 332 <a href="#CCGPG">CCGPG</a> and <a href="#CCGPM">CCGPM</a> ). 333 This is explained shortly.</li> 334<li>The performance graphs have a "saw-tooth" shape. The 335 average insert time rises and falls. As values are inserted 336 into the container, the load factor grows larger. Eventually, 337 a resize occurs. The reallocations and rehashing are 338 relatively expensive. After this, the load factor is smaller 339 than before.</li> 340</ol> 341<p>Collision-chaining containers use indirection for greater 342 flexibility; probing containers store values contiguously, in 343 an array (see Figure <a href="motivation.html#different_underlying_data_structures">Motivation::Different 344 underlying data structures</a> A and B, respectively). It 345 follows that for simple data types, probing containers access 346 their allocator less frequently than collision-chaining 347 containers, (although they still have less efficient probing 348 sequences). This explains why some probing containers fare 349 better than collision-chaining containers in this case.</p> 350<p>Within each type of hash-table, the range-hashing scheme 351 affects performance more than other policies. This is similar 352 to the situation in <a href="hash_text_find_find_timing_test.html">Hash-Based Text 353 <tt>find</tt> Find Timing Test</a> and <a href="hash_random_int_find_find_timing_test.html">Hash-Based 354 Random-Integer <tt>find</tt> Find Timing Test</a>. 355 Unsurprisingly, however, containers with <u>lower</u> 356<i>alpha<sub>max</sub></i> perform <u>worse</u> in this case, 357 since more re-hashes are performed.</p> 358<p><a href="assoc_performance_tests.html#hash_based_types">Observations::Hash-Based 359 Container Types</a> summarizes some observations on hash-based 360 containers; <a href="assoc_performance_tests.html#hash_based_policies">Observations::Hash-Based 361 Containers' Policies</a> summarizes some observations on 362 hash-based containers' policies.</p> 363</div> 364</body> 365</html> 366
