libstdc++-v3/docs/html/ext/pb_ds/hash_random_int_subscript_insert_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" 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="../../../../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>
  47 cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map-
  48 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  49 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
  54 <li>
  55 n_hash_map_ncah-
  56 <tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li>
  57 <li>
  58 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map-
  59 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  60 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
  65 <li>
  66 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map-
  67 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  68 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/1</i></li>
  73 <li>
  74 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map-
  75 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  76 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
  94 n_hash_map_ncah-
  95 <tt>stdext::hash_map</tt></li>
  96 <li>
  97 cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map-
  98 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
  99 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
 104 <li>
 105 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map-
 106 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 107 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/1</i></li>
 112 <li>
 113 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map-
 114 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 115 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
 120 <li>
 121 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map-
 122 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 123 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
 150 gp_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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
 159 n_hash_map_ncah-
 160 <tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li>
 161 <li>
 162 gp_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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
 183 n_hash_map_ncah-
 184 <tt>stdext::hash_map</tt></li>
 185 <li>
 186 gp_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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
 195 gp_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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
 225 gp_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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
 234 cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map-
 235 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 236 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
 241 <li>
 242 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map-
 243 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 244 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
 249 <li>
 250 gp_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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
 271 cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map-
 272 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 273 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
 278 <li>
 279 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map-
 280 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
 281 with <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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<sub>max</sub></i> = <i>1/2</i></li>
 286 <li>
 287 gp_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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>
 296 gp_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>&alpha;<sub>min</sub></i> = <i>1/8</i> and <i>&alpha;<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>