l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/doc/html/ext/pb_ds/hash_text_find_find_timing_test.html

   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="../../../../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>
  41 n_hash_map_ncah-
  42 <tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li>
  43 <li>
  44 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map-
  45 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  46 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/1</i></li>
  51 <li>
  52 cc_hash_mask_exp_nea_lc_1div8_1div2_sth_map-
  53 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  54 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
  59 <li>
  60 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map-
  61 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  62 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/1</i></li>
  67 <li>
  68 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map-
  69 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  70 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
  88 n_hash_map_ncah-
  89 <tt>stdext::hash_map</tt></li>
  90 <li>
  91 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map-
  92 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  93 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/1</i></li>
  98 <li>
  99 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map-
 100 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 101 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/1</i></li>
 106 <li>
 107 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map-
 108 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 109 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
 114 <li>
 115 cc_hash_mask_exp_nea_lc_1div8_1div2_sth_map-
 116 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 117 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>