1 // { dg-options "-std=gnu++11" }
3 // Copyright (C) 2011-2016 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
21 #include <tr1/unordered_set>
22 #include <unordered_set>
23 #include <testsuite_performance.h>
27 // Bench using an unordered_set<int>. Hash functor for int is quite
28 // predictable so it helps bench very specific use cases.
29 template<typename _ContType
>
30 void bench(const char* desc
)
32 using namespace __gnu_test
;
35 resource_counter resource
;
37 const int nb
= 200000;
38 start_counters(time
, resource
);
41 for (int i
= 0; i
!= nb
; ++i
)
44 stop_counters(time
, resource
);
45 std::ostringstream ostr
;
46 ostr
<< desc
<< ": first insert";
47 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
49 start_counters(time
, resource
);
51 // Here is the worst erase use case when hashtable implementation was
52 // something like vector<forward_list<>>. Erasing from the end was very
53 // costly because we need to return the iterator following the erased
54 // one, as the hashtable is getting emptier at each step there are
55 // more and more empty bucket to loop through to reach the end of the
56 // container and find out that it was in fact the last element.
57 for (int j
= nb
- 1; j
>= 0; --j
)
64 stop_counters(time
, resource
);
66 ostr
<< desc
<< ": erase from iterator";
67 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
69 start_counters(time
, resource
);
71 // This is a worst insertion use case for the current implementation as
72 // we insert an element at the beginning of the hashtable and then we
73 // insert starting at the end so that each time we need to seek up to the
74 // first bucket to find the first non-empty one.
76 for (int i
= nb
- 1; i
>= 0; --i
)
79 stop_counters(time
, resource
);
81 ostr
<< desc
<< ": second insert";
82 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
84 start_counters(time
, resource
);
86 for (int j
= nb
- 1; j
>= 0; --j
)
89 stop_counters(time
, resource
);
91 ostr
<< desc
<< ": erase from key";
92 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
95 // Bench using unordered_set<string> that show how important it is to cache
96 // hash code as computing string hash code is quite expensive compared to
97 // computing it for int.
98 template<typename _ContType
>
99 void bench_str(const char* desc
)
101 using namespace __gnu_test
;
104 resource_counter resource
;
106 const int nb
= 200000;
107 // First generate once strings that are going to be used throughout the
109 std::ostringstream ostr
;
110 std::vector
<std::string
> strs
;
112 for (int i
= 0; i
!= nb
; ++i
)
115 ostr
<< "string #" << i
;
116 strs
.push_back(ostr
.str());
119 start_counters(time
, resource
);
122 for (int i
= 0; i
!= nb
; ++i
)
125 stop_counters(time
, resource
);
127 ostr
<< desc
<< ": first insert";
128 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
130 start_counters(time
, resource
);
132 for (int j
= nb
- 1; j
>= 0; --j
)
134 auto it
= us
.find(strs
[j
]);
139 stop_counters(time
, resource
);
141 ostr
<< desc
<< ": erase from iterator";
142 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
144 start_counters(time
, resource
);
147 for (int i
= nb
- 1; i
>= 0; --i
)
150 stop_counters(time
, resource
);
152 ostr
<< desc
<< ": second insert";
153 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
155 start_counters(time
, resource
);
157 for (int j
= nb
- 1; j
>= 0; --j
)
160 stop_counters(time
, resource
);
162 ostr
<< desc
<< ": erase from key";
163 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
169 std::__uset_hashtable
<int, std::hash
<int>, std::equal_to
<int>,
171 std::__uset_traits
<cache
>>;
175 std::tr1::__unordered_set
<int, std::hash
<int>, std::equal_to
<int>,
181 std::_Hashtable
<int, int, std::allocator
<int>,
182 std::__detail::_Identity
,
183 std::equal_to
<int>, std::hash
<int>,
184 std::__detail::_Mask_range_hashing
,
185 std::__detail::_Default_ranged_hash
,
186 std::__detail::_Power2_rehash_policy
,
187 std::__uset_traits
<cache
>>;
191 std::__uset_hashtable
<std::string
, std::hash
<std::string
>,
192 std::equal_to
<std::string
>,
193 std::allocator
<std::string
>,
194 std::__uset_traits
<cache
>>;
197 using __tr1_str_uset
=
198 std::tr1::__unordered_set
<std::string
, std::hash
<std::string
>,
199 std::equal_to
<std::string
>,
200 std::allocator
<std::string
>,
205 std::_Hashtable
<std::string
, std::string
, std::allocator
<std::string
>,
206 std::__detail::_Identity
,
207 std::equal_to
<std::string
>, std::hash
<std::string
>,
208 std::__detail::_Mask_range_hashing
,
209 std::__detail::_Default_ranged_hash
,
210 std::__detail::_Power2_rehash_policy
,
211 std::__uset_traits
<cache
>>;
215 bench
<__tr1_uset
<false>>(
216 "std::tr1::unordered_set<int> without hash code cached");
217 bench
<__tr1_uset
<true>>(
218 "std::tr1::unordered_set<int> with hash code cached");
219 bench
<__uset
<false>>(
220 "std::unordered_set<int> without hash code cached");
222 "std::unordered_set<int> with hash code cached");
223 bench
<std::unordered_set
<int>>(
224 "std::unordered_set<int> default cache");
225 bench
<__uset2
<false>>(
226 "std::unordered_set2<int> without hash code cached");
227 bench
<__uset2
<true>>(
228 "std::unordered_set2<int> with hash code cached");
229 bench_str
<__tr1_str_uset
<false>>(
230 "std::tr1::unordered_set<string> without hash code cached");
231 bench_str
<__tr1_str_uset
<true>>(
232 "std::tr1::unordered_set<string> with hash code cached");
233 bench_str
<__str_uset
<false>>(
234 "std::unordered_set<string> without hash code cached");
235 bench_str
<__str_uset
<true>>(
236 "std::unordered_set<string> with hash code cached");
237 bench_str
<std::unordered_set
<std::string
>>(
238 "std::unordered_set<string> default cache");
239 bench_str
<__str_uset2
<false>>(
240 "std::unordered_set2<string> without hash code cached");
241 bench_str
<__str_uset2
<true>>(
242 "std::unordered_set2<string> with hash code cached");