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>