1 // { dg-options "-std=gnu++0x" }
3 // Copyright (C) 2011-2013 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 begining 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::__uset_hashtable<std::string, std::hash<std::string>,
182 std::equal_to<std::string>,
183 std::allocator<std::string>,
184 std::__uset_traits<cache>>;
187 using __tr1_str_uset =
188 std::tr1::__unordered_set<std::string, std::hash<std::string>,
189 std::equal_to<std::string>,
190 std::allocator<std::string>,
195 bench<__tr1_uset<false>>(
196 "std::tr1::unordered_set<int> without hash code cached");
197 bench<__tr1_uset<true>>(
198 "std::tr1::unordered_set<int> with hash code cached");
199 bench<__uset<false>>(
200 "std::unordered_set<int> without hash code cached");
202 "std::unordered_set<int> with hash code cached");
203 bench<std::unordered_set<int>>(
204 "std::unordered_set<int> default cache");
205 bench_str<__tr1_str_uset<false>>(
206 "std::tr1::unordered_set<string> without hash code cached");
207 bench_str<__tr1_str_uset<true>>(
208 "std::tr1::unordered_set<string> with hash code cached");
209 bench_str<__str_uset<false>>(
210 "std::unordered_set<string> without hash code cached");
211 bench_str<__str_uset<true>>(
212 "std::unordered_set<string> with hash code cached");
213 bench_str<std::unordered_set<std::string>>(
214 "std::unordered_set<string> default cache");