1 // Copyright (C) 2013 Free Software Foundation, Inc.
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)
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.
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/>.
18 // { dg-options "-std=gnu++11" }
20 #include <testsuite_performance.h>
25 #include <unordered_set>
29 const int sz
= 2000000;
30 const std::string pattern
= "test string #";
31 const int nb_copies
= 100;
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.
39 operator()(const std::string
& str
) const noexcept
41 //std::istringstream istr(str.substr(pattern.size()));
42 //std::size_t str_index;
45 std::hash
<std::string
> std_hasher
;
46 return std_hasher(str
);
50 using ums_t
= std::unordered_multiset
<std::string
, hasher
>;
53 insert_with_perfect_hint1(const std::vector
<std::string
>& strs
,
56 std::vector
<typename
ums_t::iterator
> hints
;
57 hints
.reserve(strs
.size());
59 hints
.push_back(ms
.insert(str
));
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
]);
67 insert_with_perfect_hint2(const std::vector
<std::string
>& strs
,
70 std::vector
<typename
ums_t::iterator
> hints
;
71 hints
.reserve(strs
.size());
73 hints
.push_back(ms
.insert(str
));
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
]);
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.
84 insert_with_good_hint(const std::vector
<std::string
>& strs
,
87 std::vector
<typename
ums_t::iterator
> hints
;
88 hints
.reserve(strs
.size());
90 hints
.push_back(ms
.insert(str
));
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
]);
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.
103 insert_with_bad_hint(const std::vector
<std::string
>& strs
,
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
));
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
]);
117 insert_without_hint1(const std::vector
<std::string
>& strs
,
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
));
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
]);
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.
135 insert_without_hint2(const std::vector
<std::string
>& strs
,
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
));
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
]);
149 insert_with_any_hint1(const std::vector
<std::string
>& strs
,
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
));
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
)
161 ms
.insert(hints
[(i
+ offset
) % hints
.size()], strs
[i
]);
167 insert_with_any_hint2(const std::vector
<std::string
>& strs
,
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
));
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
)
179 ms
.insert(hints
[(i
+ offset
) % hints
.size()], strs
[i
]);
187 using namespace __gnu_test
;
189 const int nb_iter
= 10;
191 std::vector
<std::string
> strs
;
192 strs
.reserve(sz
/ nb_copies
);
194 for (int i
= 0; i
!= sz
/ nb_copies
; ++i
)
196 std::ostringstream osstr
;
197 osstr
<< pattern
<< i
;
198 strs
.push_back(osstr
.str());
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
);
209 for (auto str
: strs
)
210 for (int j
= 0; j
!= nb_copies
; ++j
)
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
;
221 for (int i
= 0; i
!= nb_iter
; ++i
)
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
);
234 start_counters(time_no_hint1
, resource_no_hint1
);
235 insert_without_hint1(strs
, ms
);
236 stop_counters(time_no_hint1
, resource_no_hint1
);
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
);
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
);
258 start_counters(time_no_hint2
, resource_no_hint2
);
259 insert_without_hint2(strs
, ms
);
260 stop_counters(time_no_hint2
, resource_no_hint2
);
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
);
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
);
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
);
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
);
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
);
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
);
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
);
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
);
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
);
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
);
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
);