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 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>find</tt> Find Timing 13 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>find</tt>. It measures the average time 18 for<tt>find</tt> as a function of the number of values 19 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_find_timing.cc"><tt>random_int_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::Associative 25 Containers::Associative Containers::Hash-Based Containers</a>), 26 range-hashing functions, and trigger policies (see <a href="hash_based_containers.html#hash_policies">Design::Associative 27 Containers::Hash-Based Containers::Hash Policies</a> and 28 <a href="hash_based_containers.html#resize_policies">Design::Associative 29 Containers::Hash-Based Containers::Resize Policies</a>).</p> 30<h2><a name="results" id="results">Results</a></h2> 31<p>Figures <a href="#NCCG">NCCG</a>, <a href="#NCCM">NCCM</a>, 32 and <a href="#NCCL">NCCL</a> show the results for the native 33 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 34 <a href="assoc_performance_tests.html#local"><u>local</u></a>, 35 respectively; Figures <a href="#NGPG">NGPG</a>, <a href="#NGPM">NGPM</a>, and <a href="#NGPL">NGPL</a> show the results 36 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 37 <a href="assoc_performance_tests.html#local"><u>local</u></a> 38 respectively.</p> 39<div id="NCCG_res_div"> 40<div id="NCCG_gcc"> 41<div id="NCCG_cc_hash_random_int_find_timing_test"> 42<div id="NCCG_assoc"> 43<div id="NCCG_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt_find_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_find_timing_test_gcc.png" alt="no image" /></a></h6>NCCG: Native and collision-chaining hash random int find timing test using <tt>find</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> 44<ol> 45<li> 46n_hash_map_ncah- 47<tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li> 48<li> 49cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- 50<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 51with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 52, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 53 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 54, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 55 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 56<li> 57cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 58<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 59with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 60, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 61 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 62, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 63 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 64<li> 65cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 66<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 67with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 68, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 69 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 70, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 71 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 72<li> 73cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 74<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 75with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 76, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 77 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 78, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 79 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 80</ol> 81</div><div style="width: 100%; height: 20px"></div></div> 82</div> 83</div> 84</div> 85</div> 86<div id="NCCM_res_div"> 87<div id="NCCM_msvc"> 88<div id="NCCM_cc_hash_random_int_find_timing_test"> 89<div id="NCCM_assoc"> 90<div id="NCCM_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt_find_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_find_timing_test_msvc.png" alt="no image" /></a></h6>NCCM: Native and collision-chaining hash random int find timing test using <tt>find</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> 91<ol> 92<li> 93cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- 94<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 95with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 96, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 97 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 98, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 99 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 100<li> 101cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- 102<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 103with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 104, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 105 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 106, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 107 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 108<li> 109n_hash_map_ncah- 110<tt>stdext::hash_map</tt></li> 111<li> 112cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 113<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 114with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 115, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 116 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 117, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 118 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 119<li> 120cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 121<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 122with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 123, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 124 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 125, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 126 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 127</ol> 128</div><div style="width: 100%; height: 20px"></div></div> 129</div> 130</div> 131</div> 132</div> 133<div id="NCCL_res_div"> 134<div id="NCCL_local"> 135<div id="NCCL_cc_hash_random_int_find_timing_test"> 136<div id="NCCL_assoc"> 137<div id="NCCL_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt_find_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_find_timing_test_local.png" alt="no image" /></a></h6>NCCL: Native and collision-chaining hash random int find timing test using <tt>find</tt> - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 138</div> 139</div> 140</div> 141</div> 142<div id="NGPG_res_div"> 143<div id="NGPG_gcc"> 144<div id="NGPG_gp_hash_random_int_find_timing_test"> 145<div id="NGPG_assoc"> 146<div id="NGPG_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt_find_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_find_timing_test_gcc.png" alt="no image" /></a></h6>NGPG: Native and collision-chaining hash random int find timing test using <tt>find</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> 147<ol> 148<li> 149gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- 150<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 151 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 152, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 153 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 154, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 155 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> 156</li> 157<li> 158n_hash_map_ncah- 159<tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li> 160<li> 161gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 162<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 163 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 164, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 165 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 166, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 167 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> 168</li> 169</ol> 170</div><div style="width: 100%; height: 20px"></div></div> 171</div> 172</div> 173</div> 174</div> 175<div id="NGPM_res_div"> 176<div id="NGPM_msvc"> 177<div id="NGPM_gp_hash_random_int_find_timing_test"> 178<div id="NGPM_assoc"> 179<div id="NGPM_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt_find_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_find_timing_test_msvc.png" alt="no image" /></a></h6>NGPM: Native and collision-chaining hash random int find timing test using <tt>find</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> 180<ol> 181<li> 182gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- 183<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 184 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 185, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 186 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 187, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 188 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> 189</li> 190<li> 191n_hash_map_ncah- 192<tt>stdext::hash_map</tt></li> 193<li> 194gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- 195<a href="gp_hash_table.html"><tt>gp_hash_table</tt></a> 196 with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 197, <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 198 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 199, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 200 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> 201</li> 202</ol> 203</div><div style="width: 100%; height: 20px"></div></div> 204</div> 205</div> 206</div> 207</div> 208<div id="NGPL_res_div"> 209<div id="NGPL_local"> 210<div id="NGPL_gp_hash_random_int_find_timing_test"> 211<div id="NGPL_assoc"> 212<div id="NGPL_Native_and_collision-chaining_hash_random_int_find_timing_test_using__tt_find_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_find_timing_test_local.png" alt="no image" /></a></h6>NGPL: Native and collision-chaining hash random int find timing test using <tt>find</tt> - <a href = "assoc_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div> 213</div> 214</div> 215</div> 216</div> 217<h2><a name="observations" id="observations">Observations</a></h2> 218<p>In this setting, the choice of underlying hash-table (see 219 <a href="hash_based_containers.html">Design::Associative 220 Containers::Hash-Based Containers</a> ) affects performance 221 most, then the range-hashing scheme (See <a href="hash_based_containers.html#hash_policies">Design::Associative 222 Containers::Hash-Based Containers::Hash Policies</a> ), and, 223 only finally, other policies.</p> 224<p>When comparing Figures <a href="#NCCG">NCCG</a> and <a href="#NCCM">NCCM</a> to <a href="#NGPG">NGPG</a> and <a href="#NGPM">NGPM</a> , respectively, it is apparent that the 225 probing containers are less efficient than the 226 collision-chaining containers (both 227 <tt>std::tr1::unordered_map</tt> and <tt>stdext::hash_map</tt> 228 use collision-chaining) in this case.</p> 229<p>( <a href="hash_random_int_subscript_insert_timing_test.html">Hash-Based 230 Random-Integer Subscript Insert Timing Test</a> shows a 231 different case, where the situation is reversed; <a href="assoc_performance_tests.html#hash_based_types">Observations::Hash-Based 232 Container Types</a> discusses some further considerations.)</p> 233<p>Within each type of hash-table, the range-hashing scheme 234 affects performance more than other policies; <a href="hash_text_find_find_timing_test.html#observations">Hash-Based 235 Text <tt>find</tt> Find Timing Test::Observations</a> discusses 236 this. In Figures <a href="#NCCG">NCCG</a> , <a href="#NCCM">NCCM</a> , <a href="#NGPG">NGPG</a> , and <a href="#NGPM">NGPM</a> , it should be noted that 237 <tt>std::tr1::unordered_map</tt> and <tt>stdext::hash_map</tt> 238 are hard-wired currently to mod-based and mask-based schemes, 239 respectively.</p> 240<p><a href="assoc_performance_tests.html#hash_based_types">Observations::Hash-Based 241 Container Types</a> summarizes some observations on hash-based 242 containers; <a href="assoc_performance_tests.html#hash_based_policies">Observations::Hash-Based 243 Containers' Policies</a> summarizes some observations on 244 hash-based containers' policies.</p> 245</div> 246</body> 247</html> 248
