]>
Commit | Line | Data |
---|---|---|
7adcbafe | 1 | // Copyright (C) 2013-2022 Free Software Foundation, Inc. |
41349aec FD |
2 | // |
3 | // This file is part of the GNU ISO C++ Library. This library is free | |
4 | // software; you can redistribute it and/or modify it under the | |
5 | // terms of the GNU General Public License as published by the | |
6 | // Free Software Foundation; either version 3, or (at your option) | |
7 | // any later version. | |
8 | ||
9 | // This library is distributed in the hope that it will be useful, | |
10 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
12 | // GNU General Public License for more details. | |
13 | ||
14 | // You should have received a copy of the GNU General Public License along | |
15 | // with this library; see the file COPYING3. If not see | |
16 | // <http://www.gnu.org/licenses/>. | |
17 | ||
52066eae | 18 | // { dg-do run { target c++11 } } |
41349aec FD |
19 | |
20 | #include <testsuite_performance.h> | |
21 | ||
22 | #include <sstream> | |
23 | #include <string> | |
24 | #include <vector> | |
25 | #include <unordered_set> | |
26 | ||
27 | namespace | |
28 | { | |
29 | const int sz = 2000000; | |
30 | const std::string pattern = "test string #"; | |
31 | const int nb_copies = 100; | |
32 | ||
33 | // Special std::string hasher based on std::hash<std::string> but not tag as | |
34 | // slow so that hash code is not cached. It is easier to show impact of | |
35 | // hinting in this context. | |
36 | struct hasher | |
37 | { | |
38 | std::size_t | |
39 | operator()(const std::string& str) const noexcept | |
40 | { | |
41 | //std::istringstream istr(str.substr(pattern.size())); | |
42 | //std::size_t str_index; | |
43 | //istr >> str_index; | |
44 | //return str_index; | |
45 | std::hash<std::string> std_hasher; | |
46 | return std_hasher(str); | |
47 | } | |
48 | }; | |
49 | ||
50 | using ums_t = std::unordered_multiset<std::string, hasher>; | |
51 | ||
52 | void | |
53 | insert_with_perfect_hint1(const std::vector<std::string>& strs, | |
54 | ums_t& ms) | |
55 | { | |
56 | std::vector<typename ums_t::iterator> hints; | |
57 | hints.reserve(strs.size()); | |
58 | for (auto str : strs) | |
59 | hints.push_back(ms.insert(str)); | |
60 | ||
61 | for (int j = 1; j != nb_copies; ++j) | |
62 | for (std::size_t i = 0; i != strs.size(); ++i) | |
63 | ms.insert(hints[i], strs[i]); | |
64 | } | |
65 | ||
66 | void | |
67 | insert_with_perfect_hint2(const std::vector<std::string>& strs, | |
68 | ums_t& ms) | |
69 | { | |
70 | std::vector<typename ums_t::iterator> hints; | |
71 | hints.reserve(strs.size()); | |
72 | for (auto str : strs) | |
73 | hints.push_back(ms.insert(str)); | |
74 | ||
75 | for (std::size_t i = 0; i != strs.size(); ++i) | |
76 | for (int j = 1; j != nb_copies; ++j) | |
77 | ms.insert(hints[i], strs[i]); | |
78 | } | |
79 | ||
80 | // Always insert with the result of the previous insertion. The result of | |
81 | // the previous insertion will never be followed by an equivalent node | |
82 | // resulting in a re-computation of its hash code which is expensive. | |
83 | void | |
84 | insert_with_good_hint(const std::vector<std::string>& strs, | |
85 | ums_t& ms) | |
86 | { | |
87 | std::vector<typename ums_t::iterator> hints; | |
88 | hints.reserve(strs.size()); | |
89 | for (auto str : strs) | |
90 | hints.push_back(ms.insert(str)); | |
91 | ||
92 | for (int j = 1; j != nb_copies; ++j) | |
93 | for (std::size_t i = 0; i != strs.size(); ++i) | |
94 | hints[i] = ms.insert(hints[i], strs[i]); | |
95 | } | |
96 | ||
97 | // Note that the following use case is particularly bad especially compared to | |
98 | // the solution without hint because without hint the first insertion will put | |
99 | // it first in the bucket and following insertions will detect it and insert | |
100 | // just before. By giving a hint insertion will be done just after forcing to | |
101 | // check if it has no impact on the following bucket. | |
102 | void | |
103 | insert_with_bad_hint(const std::vector<std::string>& strs, | |
104 | ums_t& ms) | |
105 | { | |
106 | std::vector<typename ums_t::iterator> hints; | |
107 | hints.reserve(strs.size()); | |
108 | for (auto str : strs) | |
109 | hints.push_back(ms.insert(str)); | |
110 | ||
111 | for (std::size_t i = 0; i != strs.size(); ++i) | |
112 | for (int j = 1; j != nb_copies; ++j) | |
113 | hints[i] = ms.insert(hints[i], strs[i]); | |
114 | } | |
115 | ||
116 | void | |
117 | insert_without_hint1(const std::vector<std::string>& strs, | |
118 | ums_t& ms) | |
119 | { | |
120 | std::vector<typename ums_t::iterator> hints; | |
121 | hints.reserve(strs.size()); | |
122 | for (auto str : strs) | |
123 | hints.push_back(ms.insert(str)); | |
124 | ||
125 | for (int j = 1; j != nb_copies; ++j) | |
126 | for (std::size_t i = 0; i != strs.size(); ++i) | |
127 | hints[i] = ms.insert(strs[i]); | |
128 | } | |
129 | ||
130 | // This version is the best one if you insert all equivalent elements at the | |
131 | // same time. It demonstrates that most of the time it is better not to give | |
132 | // any hint unless you have written a benchmark for your application showing | |
133 | // that it does have a positive effect. | |
134 | void | |
135 | insert_without_hint2(const std::vector<std::string>& strs, | |
136 | ums_t& ms) | |
137 | { | |
138 | std::vector<typename ums_t::iterator> hints; | |
139 | hints.reserve(strs.size()); | |
140 | for (auto str : strs) | |
141 | hints.push_back(ms.insert(str)); | |
142 | ||
143 | for (std::size_t i = 0; i != strs.size(); ++i) | |
144 | for (int j = 1; j != nb_copies; ++j) | |
145 | hints[i] = ms.insert(strs[i]); | |
146 | } | |
147 | ||
148 | void | |
149 | insert_with_any_hint1(const std::vector<std::string>& strs, | |
150 | ums_t& ms) | |
151 | { | |
152 | std::vector<typename ums_t::iterator> hints; | |
153 | hints.reserve(strs.size()); | |
154 | for (auto str : strs) | |
155 | hints.push_back(ms.insert(ms.begin(), str)); | |
156 | ||
157 | std::size_t offset = strs.size() / 2; | |
158 | for (int j = 1; j != nb_copies; ++j) | |
159 | for (std::size_t i = 0; i != strs.size(); ++i) | |
160 | { | |
161 | ms.insert(hints[(i + offset) % hints.size()], strs[i]); | |
162 | ++offset; | |
163 | } | |
164 | } | |
165 | ||
166 | void | |
167 | insert_with_any_hint2(const std::vector<std::string>& strs, | |
168 | ums_t& ms) | |
169 | { | |
170 | std::vector<typename ums_t::iterator> hints; | |
171 | hints.reserve(strs.size()); | |
172 | for (auto str : strs) | |
173 | hints.push_back(ms.insert(ms.begin(), str)); | |
174 | ||
175 | std::size_t offset = strs.size() / 2; | |
176 | for (std::size_t i = 0; i != strs.size(); ++i) | |
177 | for (int j = 1; j != nb_copies; ++j) | |
178 | { | |
179 | ms.insert(hints[(i + offset) % hints.size()], strs[i]); | |
180 | ++offset; | |
181 | } | |
182 | } | |
183 | } | |
184 | ||
185 | int main() | |
186 | { | |
187 | using namespace __gnu_test; | |
188 | ||
189 | const int nb_iter = 10; | |
190 | ||
191 | std::vector<std::string> strs; | |
192 | strs.reserve(sz / nb_copies); | |
193 | ||
194 | for (int i = 0; i != sz / nb_copies; ++i) | |
195 | { | |
196 | std::ostringstream osstr; | |
197 | osstr << pattern << i; | |
198 | strs.push_back(osstr.str()); | |
199 | } | |
200 | ||
201 | ums_t ms; | |
202 | // Use a large load factor to make the context ideal for using hint because we | |
203 | // will have many elements per bucket. | |
204 | ms.max_load_factor(10.0f); | |
205 | ms.reserve(sz); | |
206 | ||
207 | // Warm up. | |
208 | { | |
209 | for (auto str : strs) | |
210 | for (int j = 0; j != nb_copies; ++j) | |
211 | ms.insert(str); | |
212 | } | |
213 | ||
214 | time_counter time_no_hint1, time_any_hint1, time_bad_hint, time_perfect_hint1; | |
215 | time_counter time_no_hint2, time_any_hint2, time_good_hint, time_perfect_hint2; | |
216 | resource_counter resource_no_hint1, resource_any_hint1, resource_bad_hint, | |
217 | resource_perfect_hint1; | |
218 | resource_counter resource_no_hint2, resource_any_hint2, resource_good_hint, | |
219 | resource_perfect_hint2; | |
220 | ||
221 | for (int i = 0; i != nb_iter; ++i) | |
222 | { | |
223 | // Bad hint | |
224 | { | |
225 | ms.clear(); | |
226 | start_counters(time_bad_hint, resource_bad_hint); | |
227 | insert_with_bad_hint(strs, ms); | |
228 | stop_counters(time_bad_hint, resource_bad_hint); | |
229 | } | |
230 | ||
231 | // No hint | |
232 | { | |
233 | ms.clear(); | |
234 | start_counters(time_no_hint1, resource_no_hint1); | |
235 | insert_without_hint1(strs, ms); | |
236 | stop_counters(time_no_hint1, resource_no_hint1); | |
237 | } | |
238 | ||
239 | // Any hint | |
240 | { | |
241 | ms.clear(); | |
242 | start_counters(time_any_hint1, resource_any_hint1); | |
243 | insert_with_any_hint1(strs, ms); | |
244 | stop_counters(time_any_hint1, resource_any_hint1); | |
245 | } | |
246 | ||
247 | // Good hint | |
248 | { | |
249 | ms.clear(); | |
250 | start_counters(time_good_hint, resource_good_hint); | |
251 | insert_with_good_hint(strs, ms); | |
252 | stop_counters(time_good_hint, resource_good_hint); | |
253 | } | |
254 | ||
255 | // No hint | |
256 | { | |
257 | ms.clear(); | |
258 | start_counters(time_no_hint2, resource_no_hint2); | |
259 | insert_without_hint2(strs, ms); | |
260 | stop_counters(time_no_hint2, resource_no_hint2); | |
261 | } | |
262 | ||
263 | // Perfect hint | |
264 | { | |
265 | ms.clear(); | |
266 | start_counters(time_perfect_hint2, resource_perfect_hint2); | |
267 | insert_with_perfect_hint2(strs, ms); | |
268 | stop_counters(time_perfect_hint2, resource_perfect_hint2); | |
269 | } | |
270 | ||
271 | // Any hint | |
272 | { | |
273 | ms.clear(); | |
274 | start_counters(time_any_hint2, resource_any_hint2); | |
275 | insert_with_any_hint2(strs, ms); | |
276 | stop_counters(time_any_hint2, resource_any_hint2); | |
277 | } | |
278 | ||
279 | // Perfect hint | |
280 | { | |
281 | ms.clear(); | |
282 | start_counters(time_perfect_hint1, resource_perfect_hint1); | |
283 | insert_with_perfect_hint1(strs, ms); | |
284 | stop_counters(time_perfect_hint1, resource_perfect_hint1); | |
285 | } | |
286 | } | |
287 | ||
288 | std::ostringstream ostr; | |
289 | ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies | |
290 | << " insertions w/o hint"; | |
291 | report_performance(__FILE__, ostr.str().c_str(), | |
292 | time_no_hint1, resource_no_hint1); | |
293 | ||
294 | ostr.str(""); | |
295 | ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies | |
296 | << " insertions with any hint"; | |
297 | report_performance(__FILE__, ostr.str().c_str(), | |
298 | time_any_hint1, resource_any_hint1); | |
299 | ||
300 | ostr.str(""); | |
301 | ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies | |
302 | << " insertions with good hint"; | |
303 | report_performance(__FILE__, ostr.str().c_str(), | |
304 | time_good_hint, resource_good_hint); | |
305 | ||
306 | ostr.str(""); | |
307 | ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies | |
308 | << " insertions with perfect hint"; | |
309 | report_performance(__FILE__, ostr.str().c_str(), | |
310 | time_perfect_hint1, resource_perfect_hint1); | |
311 | ||
312 | ostr.str(""); | |
313 | ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies | |
314 | << " insertions w/o hint"; | |
315 | report_performance(__FILE__, ostr.str().c_str(), | |
316 | time_no_hint2, resource_no_hint2); | |
317 | ||
318 | ostr.str(""); | |
319 | ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies | |
320 | << " insertions with any hint"; | |
321 | report_performance(__FILE__, ostr.str().c_str(), | |
322 | time_any_hint2, resource_any_hint2); | |
323 | ||
324 | ostr.str(""); | |
325 | ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies | |
326 | << " insertions with bad hint"; | |
327 | report_performance(__FILE__, ostr.str().c_str(), | |
328 | time_bad_hint, resource_bad_hint); | |
329 | ||
330 | ostr.str(""); | |
331 | ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies | |
332 | << " insertions with perfect hint"; | |
333 | report_performance(__FILE__, ostr.str().c_str(), | |
334 | time_perfect_hint2, resource_perfect_hint2); | |
335 | return 0; | |
336 | } |