1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
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" />
12 <h1>Hash-Based Random-Integer <tt><b>operator</b>[]</tt>
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
20 <p>(The test was executed with <a href="../../../../testsuite/performance/ext/pb_ds/random_int_subscript_find_timing.cc"><tt>hash_random_int_subscript_find_timing_test</tt></a>
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>,
37 <div id="NCCG_res_div">
39 <div id="NCCG_cc_hash_random_int_subscript_timing_test_find">
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>
45 <tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></li>
47 cc_hash_mod_prime_nea_lc_1div8_1div1_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>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li>
55 cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map-
56 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
57 with <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>
63 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map-
64 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
65 with <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>
71 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map-
72 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
73 with <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>
79 </div><div style="width: 100%; height: 20px"></div></div>
84 <div id="NCCM_res_div">
86 <div id="NCCM_cc_hash_random_int_subscript_timing_test_find">
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>
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>α<sub>min</sub></i> = <i>1/8</i> and <i>α<sub>max</sub></i> = <i>1/1</i></li>
99 cc_hash_mod_prime_nea_lc_1div8_1div2_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_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>
108 <tt>stdext::hash_map</tt></li>
110 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map-
111 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
112 with <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>
118 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map-
119 <a href="cc_hash_table.html"><tt>cc_hash_table</tt></a>
120 with <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>
126 </div><div style="width: 100%; height: 20px"></div></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>
140 <div id="NGPG_res_div">
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>
148 <tt>std::tr1::unordered_map</tt> with <tt>cache_hash_code</tt> = <tt><b>false</b></tt></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>α<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>
159 gp_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>
168 </div><div style="width: 100%; height: 20px"></div></div>
173 <div id="NGPM_res_div">
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>
180 gp_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>
190 <tt>stdext::hash_map</tt></li>
192 gp_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>
201 </div><div style="width: 100%; height: 20px"></div></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>
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>