]>
Commit | Line | Data |
---|---|---|
99dee823 | 1 | // Copyright (C) 2012-2021 Free Software Foundation, Inc. |
d4a7f7a1 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 } } |
d4a7f7a1 FD |
19 | |
20 | #include <testsuite_performance.h> | |
21 | #include <random> | |
22 | #include <sstream> | |
23 | #include <tr1/unordered_set> | |
5b3be7cf FD |
24 | #include <unordered_set> |
25 | ||
26 | #define USE_MY_FOO 1 | |
d4a7f7a1 FD |
27 | |
28 | struct Foo | |
29 | { | |
5b3be7cf FD |
30 | #if USE_MY_FOO |
31 | ||
d4a7f7a1 FD |
32 | typedef std::random_device::result_type _Type; |
33 | _Type bar; | |
34 | _Type baz; | |
35 | _Type meh; | |
36 | ||
37 | void | |
38 | init(std::random_device& randev) | |
39 | { | |
40 | bar = randev(); | |
41 | baz = randev(); | |
42 | meh = randev(); | |
43 | } | |
44 | ||
5b3be7cf FD |
45 | #else |
46 | ||
47 | int bar; | |
48 | int baz; | |
49 | int meh; | |
50 | ||
51 | Foo() | |
52 | { bar = random(); baz = random(); meh = random(); } | |
53 | Foo(const Foo&) = default; | |
54 | ||
55 | #endif | |
56 | ||
d4a7f7a1 FD |
57 | std::size_t |
58 | hash() const noexcept | |
59 | { return std::size_t(bar ^ baz ^ meh); } | |
60 | ||
61 | inline bool | |
62 | operator==(const Foo& other) const | |
63 | { return other.bar == bar && other.baz == baz && other.meh == meh; } | |
64 | }; | |
65 | ||
66 | struct HashFunction | |
67 | { | |
68 | template<typename T> | |
69 | std::size_t operator()(const T& t) const noexcept | |
70 | { return t.hash(); } | |
71 | }; | |
72 | ||
5b3be7cf FD |
73 | const int sz = 300000; |
74 | ||
d4a7f7a1 | 75 | template<typename _ContType> |
5b3be7cf FD |
76 | void |
77 | bench(const char* container_desc, const typename _ContType::value_type* foos) | |
d4a7f7a1 FD |
78 | { |
79 | using namespace __gnu_test; | |
80 | ||
5b3be7cf FD |
81 | _ContType s; |
82 | ||
d4a7f7a1 FD |
83 | time_counter time; |
84 | resource_counter resource; | |
d4a7f7a1 FD |
85 | start_counters(time, resource); |
86 | ||
87 | for (int i = 0; i != sz ; ++i) | |
5b3be7cf | 88 | s.insert(foos[i]); |
d4a7f7a1 FD |
89 | |
90 | stop_counters(time, resource); | |
91 | std::ostringstream ostr; | |
5b3be7cf FD |
92 | ostr << container_desc << sz << " insertion attempts, " |
93 | << s.size() << " inserted"; | |
d4a7f7a1 FD |
94 | report_performance(__FILE__, ostr.str().c_str(), time, resource); |
95 | ||
96 | // Try to insert again to check performance of collision detection | |
d4a7f7a1 FD |
97 | const int nb_loop = 10; |
98 | start_counters(time, resource); | |
99 | ||
100 | for (int j = 0; j != nb_loop; ++j) | |
101 | for (int i = 0; i != sz; ++i) | |
102 | s.insert(foos[i]); | |
103 | ||
104 | stop_counters(time, resource); | |
105 | ostr.str(""); | |
106 | ostr << container_desc << nb_loop << " times insertion of " | |
5b3be7cf | 107 | << sz << " elements"; |
d4a7f7a1 FD |
108 | report_performance(__FILE__, ostr.str().c_str(), time, resource); |
109 | } | |
110 | ||
111 | template<bool cache> | |
112 | using __tr1_uset = std::tr1::__unordered_set<Foo, HashFunction, | |
113 | std::equal_to<Foo>, | |
114 | std::allocator<Foo>, | |
115 | cache>; | |
116 | template<bool cache> | |
117 | using __tr1_umset = std::tr1::__unordered_multiset<Foo, HashFunction, | |
118 | std::equal_to<Foo>, | |
119 | std::allocator<Foo>, | |
120 | cache>; | |
121 | template<bool cache> | |
122 | using __uset = std::__uset_hashtable<Foo, HashFunction, | |
123 | std::equal_to<Foo>, | |
124 | std::allocator<Foo>, | |
125 | std::__uset_traits<cache>>; | |
126 | template<bool cache> | |
127 | using __umset = std::__umset_hashtable<Foo, HashFunction, | |
128 | std::equal_to<Foo>, | |
129 | std::allocator<Foo>, | |
732eb076 FD |
130 | std::__umset_traits<cache>>; |
131 | ||
132 | template<bool cache> | |
133 | using __uset2 = | |
134 | std::_Hashtable<Foo, Foo, std::allocator<Foo>, | |
135 | std::__detail::_Identity, | |
136 | std::equal_to<Foo>, HashFunction, | |
137 | std::__detail::_Mask_range_hashing, | |
138 | std::__detail::_Default_ranged_hash, | |
139 | std::__detail::_Power2_rehash_policy, | |
140 | std::__uset_traits<cache>>; | |
141 | ||
142 | template<bool cache> | |
143 | using __umset2 = | |
144 | std::_Hashtable<Foo, Foo, std::allocator<Foo>, | |
145 | std::__detail::_Identity, | |
146 | std::equal_to<Foo>, HashFunction, | |
147 | std::__detail::_Mask_range_hashing, | |
148 | std::__detail::_Default_ranged_hash, | |
149 | std::__detail::_Power2_rehash_policy, | |
150 | std::__umset_traits<cache>>; | |
d4a7f7a1 FD |
151 | |
152 | int main() | |
153 | { | |
5b3be7cf FD |
154 | using namespace __gnu_test; |
155 | ||
156 | { | |
157 | int bars[sz]; | |
158 | for (int i = 0; i != sz; ++i) | |
159 | bars[i] = i; | |
160 | bench<std::tr1::unordered_set<int>>( | |
161 | "std::tr1::unordered_set<int> ", bars); | |
162 | bench<std::unordered_set<int>>( | |
163 | "std::unordered_set<int> ", bars); | |
164 | } | |
165 | ||
166 | Foo foos[sz]; | |
167 | #if USE_MY_FOO | |
168 | { | |
169 | std::random_device randev; | |
170 | for (int i = 0; i != sz; ++i) | |
171 | foos[i].init(randev); | |
172 | } | |
173 | #endif | |
174 | ||
175 | time_counter time; | |
176 | resource_counter resource; | |
177 | start_counters(time, resource); | |
178 | ||
179 | bench<__tr1_uset<false>>( | |
180 | "std::tr1::unordered_set without hash code cached ", foos); | |
181 | bench<__tr1_uset<true>>( | |
182 | "std::tr1::unordered_set with hash code cached ", foos); | |
183 | bench<__tr1_umset<false>>( | |
184 | "std::tr1::unordered_multiset without hash code cached ", foos); | |
185 | bench<__tr1_umset<true>>( | |
186 | "std::tr1::unordered_multiset with hash code cached ", foos); | |
187 | ||
188 | stop_counters(time, resource); | |
189 | report_performance(__FILE__, "tr1 benches", time, resource); | |
190 | ||
191 | start_counters(time, resource); | |
192 | bench<__uset<false>>( | |
193 | "std::unordered_set without hash code cached ", foos); | |
194 | bench<__uset<true>>( | |
195 | "std::unordered_set with hash code cached ", foos); | |
196 | bench<__umset<false>>( | |
197 | "std::unordered_multiset without hash code cached ", foos); | |
198 | bench<__umset<true>>( | |
199 | "std::unordered_multiset with hash code cached ", foos); | |
200 | ||
201 | stop_counters(time, resource); | |
202 | report_performance(__FILE__, "std benches", time, resource); | |
203 | ||
732eb076 FD |
204 | start_counters(time, resource); |
205 | bench<__uset2<false>>( | |
206 | "std::unordered_set2 without hash code cached ", foos); | |
207 | bench<__uset2<true>>( | |
208 | "std::unordered_set2 with hash code cached ", foos); | |
209 | bench<__umset2<false>>( | |
210 | "std::unordered_multiset2 without hash code cached ", foos); | |
211 | bench<__umset2<true>>( | |
212 | "std::unordered_multiset2 with hash code cached ", foos); | |
213 | ||
214 | stop_counters(time, resource); | |
215 | report_performance(__FILE__, "std2 benches", time, resource); | |
216 | ||
5b3be7cf FD |
217 | bench<std::unordered_set<Foo, HashFunction>>( |
218 | "std::unordered_set default cache ", foos); | |
219 | bench<std::unordered_multiset<Foo, HashFunction>>( | |
220 | "std::unordered_multiset default cache ", foos); | |
d4a7f7a1 | 221 | } |