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"> 5<head> 6<meta name="generator" content="HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" /> 7<title>Hash Text 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 Text <tt>find</tt> Find Timing Test</h1> 13<h2><a name="description" id="description">Description</a></h2> 14<p>This test inserts a number of values with keys from an 15 arbitrary text ([ <a href="references.html#wickland96thirty">wickland96thirty</a> ]) into 16 a container, then performs a series of finds using 17 <tt>find</tt> . It measures the average time for <tt>find</tt> 18 as a function of the number of values inserted.</p> 19<p>(The test was executed with <a href="http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/performance/ext/pb_ds/text_find_timing.cc"><tt>text_find_timing_test</tt></a> 20 thirty_years_among_the_dead_preproc.txt 200 200 2100)</p> 21<h2><a name="purpose" id="purpose">Purpose</a></h2> 22<p>The test checks the effect of different range-hashing 23 functions, trigger policies, and cache-hashing policies (see 24 <a href="hash_based_containers.html#hash_policies">Design::Associative 25 Containers::Associative Containers::Hash-Based Containers::Hash 26 Policies</a> and <a href="hash_based_containers.html#resize_policies">Design::Associative 27 Containers::Hash-Based 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 respetively.</p> 34<div id="NCCG_res_div"> 35<div id="NCCG_gcc"> 36<div id="NCCG_text_find_timing_test_hash"> 37<div id="NCCG_assoc"> 38<div id="NCCG_Native_and_collision-chaining_hash_text_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="text_find_timing_test_hash_gcc.png" alt="no image" /></a></h6>NCCG: Native and collision-chaining hash text 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> 39<ol> 40<li> 41n_hash_map_ncah- 42<tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li> 43<li> 44cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- 45<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 46with <tt>Comb_Hash_Fn</tt> = <a href="direct_mod_range_hashing.html"><tt>direct_mod_range_hashing</tt></a> 47, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 48 with <tt>Size_Policy</tt> = <a href="hash_prime_size_policy.html"><tt>hash_prime_size_policy</tt></a> 49, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 50 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 51<li> 52cc_hash_mask_exp_nea_lc_1div8_1div2_sth_map- 53<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 54with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 55, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 56 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 57, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 58 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 59<li> 60cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- 61<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 62with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 63, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 64 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 65, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 66 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li> 67<li> 68cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 69<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 70with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 71, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 72 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 73, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 74 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 75</ol> 76</div><div style="width: 100%; height: 20px"></div></div> 77</div> 78</div> 79</div> 80</div> 81<div id="NCCM_res_div"> 82<div id="NCCM_msvc"> 83<div id="NCCM_text_find_timing_test_hash"> 84<div id="NCCM_assoc"> 85<div id="NCCM_Native_and_collision-chaining_hash_text_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="text_find_timing_test_hash_msvc.png" alt="no image" /></a></h6>NCCM: Native and collision-chaining hash text 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> 86<ol> 87<li> 88n_hash_map_ncah- 89<tt>stdext::hash_map</tt></li> 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_mask_exp_nea_lc_1div8_1div1_nsth_map- 100<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 101with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_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_exponential_size_policy.html"><tt>hash_exponential_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/1</i></li> 106<li> 107cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- 108<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 109with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 110, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 111 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 112, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 113 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 114<li> 115cc_hash_mask_exp_nea_lc_1div8_1div2_sth_map- 116<a href="cc_hash_table.html"><tt>cc_hash_table</tt></a> 117with <tt>Comb_Hash_Fn</tt> = <a href="direct_mask_range_hashing.html"><tt>direct_mask_range_hashing</tt></a> 118, and <tt>Resize_Policy</tt> = <a href="hash_standard_resize_policy.html"><tt>hash_standard_resize_policy</tt></a> 119 with <tt>Size_Policy</tt> = <a href="hash_exponential_size_policy.html"><tt>hash_exponential_size_policy</tt></a> 120, and <tt>Trigger_Policy</tt> = <a href="hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger</tt></a> 121 with <i>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/2</i></li> 122</ol> 123</div><div style="width: 100%; height: 20px"></div></div> 124</div> 125</div> 126</div> 127</div> 128<div id="NCCL_res_div"> 129<div id="NCCL_local"> 130<div id="NCCL_text_find_timing_test_hash"> 131<div id="NCCL_assoc"> 132<div id="NCCL_Native_and_collision-chaining_hash_text_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="text_find_timing_test_hash_local.png" alt="no image" /></a></h6>NCCL: Native and collision-chaining hash text 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> 133</div> 134</div> 135</div> 136</div> 137<h2><a name="observations" id="observations">Observations</a></h2> 138<p>In this setting, the range-hashing scheme (See <a href="hash_based_containers.html#hash_policies">Design::Associative 139 Containers::Hash-Based Containers::Hash Policies</a> ) affects 140 performance more than other policies. As Figure <a href="#NCCG">NCCG</a> shows, containers using mod-based 141 range-hashing (including the native hash-based container, which 142 is currently hard-wired to this scheme) have lower performance 143 than those using mask-based range-hashing. A modulo-based 144 range-hashing scheme's main benefit is that it takes into 145 account all hash-value bits. Standard string hash-functions are 146 designed to create hash values that are nearly-uniform as is [ 147 <a href="references.html#knuth98sorting">knuth98sorting</a> 148 ].</p> 149<p>Trigger policies (see <a href="hash_based_containers.html#resize_policies">Design::Associative 150 Containers::Hash-Based Containers::Resize Policies</a> ), 151 <i>i.e.</i> the load-checks constants, affect performance to a 152 lesser extent.</p> 153<p>Perhaps surprisingly, storing the hash value alongside each 154 entry affects performance only marginally, at least in 155 <tt>pb_ds</tt> 's implementation. (Unfortunately, it was not 156 possible to run the tests with <tt>std::tr1::unordered_map</tt> 157 's <tt>cache_hash_code = <b>true</b></tt> , as it appeared to 158 malfuntion.)</p> 159<p><a href="assoc_performance_tests.html#hash_based_policies">Observations::Hash-Based 160 Containers' Policies</a> summarizes some observations on 161 hash-based containers' policies.</p> 162</div> 163</body> 164</html> 165