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 Find 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> 13 FindTiming 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, then performs a series of finds 17 using <tt><b>operator</b>[]</tt>. It measures the average time 18 for <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_find_timing.cc"><tt>hash_random_int_subscript_find_timing_test</tt></a> 21 200 200 2100)</p> 22<h2><a name="purpose" id="purpose">Purpose</a></h2> 23<p>The test checks the effect of different underlying 24 hash-tables (see <a href="hash_based_containers.html">Design::Hash-Based Containers</a> 25 ), range-hashing functions, and trigger policies (see <a href="hash_based_containers.html#hash_policies">Design::Hash-Based 26 Containers::Hash Policies</a> and <a href="hash_based_containers.html#resize_policies">Design::Hash-Based 27 Containers::Resize Policies</a> ).</p> 28<h2><a name="results" id="results">Results</a></h2> 29<p>Figures <a href="#NCCG">NCCG</a>, <a href="#NCCM">NCCM</a>, 30 and <a href="#NCCL">NCCL</a> show the results for the native 31 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 32 <a href="assoc_performance_tests.html#local"><u>local</u></a>, 33 respectively; Figures <a href="#NGPG">NGPG</a>, <a href="#NGPM">NGPM</a>, and <a href="#NGPL">NGPL</a> show the results 34 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 35 <a href="assoc_performance_tests.html#local"><u>local</u></a>, 36 respectively.</p> 37<div id="NCCG_res_div"> 38<div id="NCCG_gcc"> 39<div id="NCCG_cc_hash_random_int_subscript_timing_test_find"> 40<div id="NCCG_assoc"> 41<div id="NCCG_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt__b_operator_455b__455tt__457"><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_find_gcc.png" alt="no image" /></a></h6>NCCG: Native and collision-chaining hash random int find 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> 42<ol> 43<li> 44n_hash_map_ncah- 45<tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li> 46<li> 47cc_hash_mod_prime_nea_lc_1div8_1div1_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/1</i></li> 54<li> 55cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 56<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 57with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 58, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 59 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 60, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 61 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 62<li> 63cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 64<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 65with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 66, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 67 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 68, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 69 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 70<li> 71cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 72<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 73with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 74, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 75 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 76, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 77 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 78</ol> 79</div><div style="width: 100%; height: 20px"></div></div> 80</div> 81</div> 82</div> 83</div> 84<div id="NCCM_res_div"> 85<div id="NCCM_msvc"> 86<div id="NCCM_cc_hash_random_int_subscript_timing_test_find"> 87<div id="NCCM_assoc"> 88<div id="NCCM_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt__b_operator_455b__455tt__457"><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_find_msvc.png" alt="no image" /></a></h6>NCCM: Native and collision-chaining hash random int find 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> 89<ol> 90<li> 91cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- 92<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 93with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 94, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 95 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 96, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 97 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 98<li> 99cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 100<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 101with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 102, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 103 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 104, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 105 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 106<li> 107n_hash_map_ncah- 108<tt>stdext::hash_map</tt></li> 109<li> 110cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 111<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 112with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 113, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 114 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 115, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 116 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 117<li> 118cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 119<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 120with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 121, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 122 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 123, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 124 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 125</ol> 126</div><div style="width: 100%; height: 20px"></div></div> 127</div> 128</div> 129</div> 130</div> 131<div id="NCCL_res_div"> 132<div id="NCCL_local"> 133<div id="NCCL_cc_hash_random_int_subscript_timing_test_find"> 134<div id="NCCL_assoc"> 135<div id="NCCL_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt__b_operator_455b__455tt__457"><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_find_local.png" alt="no image" /></a></h6>NCCL: Native and collision-chaining hash random int find 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> 136</div> 137</div> 138</div> 139</div> 140<div id="NGPG_res_div"> 141<div id="NGPG_gcc"> 142<div id="NGPG_gp_hash_random_int_subscript_timing_test_find"> 143<div id="NGPG_assoc"> 144<div id="NGPG_Native_and_probing_hash_random_int_find_timing_test_using__tt__b_operator_455b__455tt__457"><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_find_gcc.png" alt="no image" /></a></h6>NGPG: Native and probing hash random int find 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> 145<ol> 146<li> 147n_hash_map_ncah- 148<tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li> 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> 159gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 160<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 161 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 162, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 163 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 164, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 165 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> 166</li> 167</ol> 168</div><div style="width: 100%; height: 20px"></div></div> 169</div> 170</div> 171</div> 172</div> 173<div id="NGPM_res_div"> 174<div id="NGPM_msvc"> 175<div id="NGPM_gp_hash_random_int_subscript_timing_test_find"> 176<div id="NGPM_assoc"> 177<div id="NGPM_Native_and_probing_hash_random_int_find_timing_test_using__tt__b_operator_455b__455tt__457"><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_find_msvc.png" alt="no image" /></a></h6>NGPM: Native and probing hash random int find 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> 178<ol> 179<li> 180gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- 181<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 182 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 183, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 184 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 185, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 186 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> 187</li> 188<li> 189n_hash_map_ncah- 190<tt>stdext::hash_map</tt></li> 191<li> 192gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 193<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 194 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 195, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 196 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 197, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 198 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> 199</li> 200</ol> 201</div><div style="width: 100%; height: 20px"></div></div> 202</div> 203</div> 204</div> 205</div> 206<div id="NGPL_res_div"> 207<div id="NGPL_local"> 208<div id="NGPL_gp_hash_random_int_subscript_timing_test_find"> 209<div id="NGPL_assoc"> 210<div id="NGPL_Native_and_probing_hash_random_int_find_timing_test_using__tt__b_operator_455b__455tt__457"><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_find_local.png" alt="no image" /></a></h6>NGPL: Native and probing hash random int find 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> 211</div> 212</div> 213</div> 214</div> 215<h2><a name="observations" id="observations">Observations</a></h2> 216<p>This test shows similar results to <a href="hash_random_int_find_find_timing_test.html">Hash-Based 217 Random-Integer <tt>find</tt> Find Timing Test</a> .</p> 218</div> 219</body> 220</html> 221
