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">
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" />
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>,
34 <div id=
"NCCG_res_div">
36 <div id=
"NCCG_text_find_timing_test_hash">
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>
42 <tt>std::tr1::unordered_map
</tt> with
<tt>cache_hash_code
</tt> =
<tt><b>false
</b></tt></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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
1</i></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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
2</i></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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
1</i></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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
2</i></li>
76 </div><div style=
"width: 100%; height: 20px"></div></div>
81 <div id=
"NCCM_res_div">
83 <div id=
"NCCM_text_find_timing_test_hash">
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>
89 <tt>stdext::hash_map
</tt></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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
1</i></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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
1</i></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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
2</i></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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
2</i></li>
123 </div><div style=
"width: 100%; height: 20px"></div></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>
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>
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
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
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>