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>Tree Text Locality of Reference Timing Test
</title>
8 <meta http-equiv=
"Content-Type" content=
"text/html; charset=us-ascii" />
12 <h1>Hash-Based Erase Memory-Use Test
</h1>
13 <h2><a name=
"description" id=
"description">Description
</a></h2>
14 <p>This test inserts a number of uniform i.i.d. integer keys
15 into a container, then erases all keys except one. It measures
16 the final size of the container.
</p>
17 <p>(The test was executed with
<a href=
"../../../../testsuite/performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc"><tt>hash_random_int_erase_mem_usage.cc
</tt></a>
19 <h2><a name=
"purpose" id=
"purpose">Purpose
</a></h2>
20 <p>The test checks how containers adjust internally as their
21 logical size decreases (see
<a href=
"motivation.html#assoc_ers_methods">Motivation::Associative
22 Containers::Slightly Different Methods::Methods Related to
24 <h2><a name=
"results" id=
"results">Results
</a></h2>
25 <p>Figures
<a href=
"#NHG">NHG
</a>,
<a href=
"#NHM">NHM
</a> and
26 <a href=
"#NHL">NHL
</a> show the results for the native and
27 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
28 <a href=
"assoc_performance_tests.html#local"><u>local
</u></a>,
30 <div id=
"NHG_res_div">
32 <div id=
"NHG_hash_random_int_erase_mem_usage_test">
34 <div id=
"NHG_Native_456_collision-chaing_456_and_probing_456_hash_random_int_erase_test"><div style=
"border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class=
"c1"><a name=
"NHG" id=
"NHG"><img src=
"hash_random_int_erase_mem_usage_test_gcc.png" alt=
"no image" /></a></h6>NHG: Native, collision-chaing, and probing, hash random int erase test -
<a href=
"assoc_performance_tests.html#gcc">g++
</a><p>In the above figure, the names in the legends have the following meaning:
</p>
38 <tt>std::tr1::unordered_set
</tt> with
<tt>cache_hash_code
</tt> =
<tt><b>false
</b></tt></li>
40 gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set-
41 <a href=
"gp_hash_table.html"><tt>gp_hash_table
</tt></a>
42 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mask_range_hashing.html"><tt>direct_mask_range_hashing
</tt></a>
43 ,
<tt>Resize_Policy
</tt> =
<a href=
"hash_standard_resize_policy.html"><tt>hash_standard_resize_policy
</tt></a>
44 with
<tt>Size_Policy
</tt> =
<a href=
"hash_exponential_size_policy.html"><tt>hash_exponential_size_policy
</tt></a>
45 , and
<tt>Trigger_Policy
</tt> =
<a href=
"hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger
</tt></a>
46 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>
49 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-
50 <a href=
"cc_hash_table.html"><tt>cc_hash_table
</tt></a>
51 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mod_range_hashing.html"><tt>direct_mod_range_hashing
</tt></a>
52 , and
<tt>Resize_Policy
</tt> =
<a href=
"hash_standard_resize_policy.html"><tt>hash_standard_resize_policy
</tt></a>
53 with
<tt>Size_Policy
</tt> =
<a href=
"hash_prime_size_policy.html"><tt>hash_prime_size_policy
</tt></a>
54 , and
<tt>Trigger_Policy
</tt> =
<a href=
"hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger
</tt></a>
55 with
<i>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
1</i></li>
57 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-
58 <a href=
"cc_hash_table.html"><tt>cc_hash_table
</tt></a>
59 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mask_range_hashing.html"><tt>direct_mask_range_hashing
</tt></a>
60 , and
<tt>Resize_Policy
</tt> =
<a href=
"hash_standard_resize_policy.html"><tt>hash_standard_resize_policy
</tt></a>
61 with
<tt>Size_Policy
</tt> =
<a href=
"hash_exponential_size_policy.html"><tt>hash_exponential_size_policy
</tt></a>
62 , and
<tt>Trigger_Policy
</tt> =
<a href=
"hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger
</tt></a>
63 with
<i>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
2</i></li>
65 </div><div style=
"width: 100%; height: 20px"></div></div>
70 <div id=
"NHM_res_div">
72 <div id=
"NHM_hash_random_int_erase_mem_usage_test">
74 <div id=
"NHM_Native_456_collision-chaing_456_and_probing_456_hash_random_int_erase_test"><div style=
"border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class=
"c1"><a name=
"NHM" id=
"NHM"><img src=
"hash_random_int_erase_mem_usage_test_msvc.png" alt=
"no image" /></a></h6>NHM: Native, collision-chaing, and probing, hash random int erase test -
<a href=
"assoc_performance_tests.html#msvc">msvc++
</a><p>In the above figure, the names in the legends have the following meaning:
</p>
78 <tt>stdext::hash_set
</tt></li>
80 gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set-
81 <a href=
"gp_hash_table.html"><tt>gp_hash_table
</tt></a>
82 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mask_range_hashing.html"><tt>direct_mask_range_hashing
</tt></a>
83 ,
<tt>Resize_Policy
</tt> =
<a href=
"hash_standard_resize_policy.html"><tt>hash_standard_resize_policy
</tt></a>
84 with
<tt>Size_Policy
</tt> =
<a href=
"hash_exponential_size_policy.html"><tt>hash_exponential_size_policy
</tt></a>
85 , and
<tt>Trigger_Policy
</tt> =
<a href=
"hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger
</tt></a>
86 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>
89 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-
90 <a href=
"cc_hash_table.html"><tt>cc_hash_table
</tt></a>
91 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mod_range_hashing.html"><tt>direct_mod_range_hashing
</tt></a>
92 , and
<tt>Resize_Policy
</tt> =
<a href=
"hash_standard_resize_policy.html"><tt>hash_standard_resize_policy
</tt></a>
93 with
<tt>Size_Policy
</tt> =
<a href=
"hash_prime_size_policy.html"><tt>hash_prime_size_policy
</tt></a>
94 , and
<tt>Trigger_Policy
</tt> =
<a href=
"hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger
</tt></a>
95 with
<i>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
1</i></li>
97 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-
98 <a href=
"cc_hash_table.html"><tt>cc_hash_table
</tt></a>
99 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mask_range_hashing.html"><tt>direct_mask_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_exponential_size_policy.html"><tt>hash_exponential_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>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
2</i></li>
105 </div><div style=
"width: 100%; height: 20px"></div></div>
110 <div id=
"NHM_res_div">
112 <div id=
"NHM_hash_random_int_erase_mem_usage_test">
114 <div id=
"NHM_Native_456_collision-chaing_456_and_probing_456_hash_random_int_erase_test"><div style=
"border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class=
"c1"><a name=
"NHM" id=
"NHM"><img src=
"hash_random_int_erase_mem_usage_test_msvc.png" alt=
"no image" /></a></h6>NHM: Native, collision-chaing, and probing, hash random int erase test -
<a href=
"assoc_performance_tests.html#msvc">msvc++
</a><p>In the above figure, the names in the legends have the following meaning:
</p>
118 <tt>stdext::hash_set
</tt></li>
120 gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set-
121 <a href=
"gp_hash_table.html"><tt>gp_hash_table
</tt></a>
122 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mask_range_hashing.html"><tt>direct_mask_range_hashing
</tt></a>
123 ,
<tt>Resize_Policy
</tt> =
<a href=
"hash_standard_resize_policy.html"><tt>hash_standard_resize_policy
</tt></a>
124 with
<tt>Size_Policy
</tt> =
<a href=
"hash_exponential_size_policy.html"><tt>hash_exponential_size_policy
</tt></a>
125 , and
<tt>Trigger_Policy
</tt> =
<a href=
"hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger
</tt></a>
126 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>
129 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set-
130 <a href=
"cc_hash_table.html"><tt>cc_hash_table
</tt></a>
131 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mod_range_hashing.html"><tt>direct_mod_range_hashing
</tt></a>
132 , and
<tt>Resize_Policy
</tt> =
<a href=
"hash_standard_resize_policy.html"><tt>hash_standard_resize_policy
</tt></a>
133 with
<tt>Size_Policy
</tt> =
<a href=
"hash_prime_size_policy.html"><tt>hash_prime_size_policy
</tt></a>
134 , and
<tt>Trigger_Policy
</tt> =
<a href=
"hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger
</tt></a>
135 with
<i>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
1</i></li>
137 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set-
138 <a href=
"cc_hash_table.html"><tt>cc_hash_table
</tt></a>
139 with
<tt>Comb_Hash_Fn
</tt> =
<a href=
"direct_mask_range_hashing.html"><tt>direct_mask_range_hashing
</tt></a>
140 , and
<tt>Resize_Policy
</tt> =
<a href=
"hash_standard_resize_policy.html"><tt>hash_standard_resize_policy
</tt></a>
141 with
<tt>Size_Policy
</tt> =
<a href=
"hash_exponential_size_policy.html"><tt>hash_exponential_size_policy
</tt></a>
142 , and
<tt>Trigger_Policy
</tt> =
<a href=
"hash_load_check_resize_trigger.html"><tt>hash_load_check_resize_trigger
</tt></a>
143 with
<i>α<sub>min
</sub></i> =
<i>1/
8</i> and
<i>α<sub>max
</sub></i> =
<i>1/
2</i></li>
145 </div><div style=
"width: 100%; height: 20px"></div></div>
150 <div id=
"NHL_res_div">
152 <div id=
"NHL_hash_random_int_erase_mem_usage_test">
154 <div id=
"NHL_Native_456_collision-chaing_456_and_probing_456_hash_random_int_erase_test"><div style =
"border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class=
"c1"><a name=
"NHL" id=
"NHL"><img src=
"hash_random_int_erase_mem_usage_test_local.png" alt=
"no image" /></a></h6>NHL: Native, collision-chaing, and probing, hash random int erase test -
<a href =
"assoc_performance_tests.html#local">local
</a></div><div style =
"width: 100%; height: 20px"></div></div>
159 <h2><a name=
"observations" id=
"observations">Observations
</a></h2>
160 <p>STL hash-based containers act very differently than trees in
161 this respect. When erasing numerous keys from an STL
162 associative-container, the resulting memory user varies greatly
163 depending on whether the container is tree-based or hash-based.
164 As noted in
<a href=
"motivation.html#assoc_methods">Motivation::Choice of
165 Methods
</a> , this is a fundamental consequence of the STL's
166 associative containers' interface, it is not due to a specific
168 <p>(See
<a href=
"priority_queue_text_pop_mem_usage_test.html">Priority Queue
169 Text
<tt>pop
</tt> Memory Use Test
</a> for a similar phenomenon
170 regarding priority queues.)
</p>