1// { dg-options "-std=gnu++11" }
2
3// Copyright (C) 2011-2015 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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/>.
19
20#include <sstream>
21#include <tr1/unordered_set>
22#include <unordered_set>
23#include <testsuite_performance.h>
24
25namespace
26{
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)
31    {
32      using namespace __gnu_test;
33
34      time_counter time;
35      resource_counter resource;
36
37      const int nb = 200000;
38      start_counters(time, resource);
39
40      _ContType us;
41      for (int i = 0; i != nb; ++i)
42	  us.insert(i);
43
44      stop_counters(time, resource);
45      std::ostringstream ostr;
46      ostr << desc << ": first insert";
47      report_performance(__FILE__, ostr.str().c_str(), time, resource);
48
49      start_counters(time, resource);
50
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)
58	{
59	  auto it = us.find(j);
60	  if (it != us.end())
61	    us.erase(it);
62	}
63
64      stop_counters(time, resource);
65      ostr.str("");
66      ostr << desc << ": erase from iterator";
67      report_performance(__FILE__, ostr.str().c_str(), time, resource);
68
69      start_counters(time, resource);
70
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.
75      us.insert(0);
76      for (int i = nb - 1; i >= 0; --i)
77	us.insert(i);
78
79      stop_counters(time, resource);
80      ostr.str("");
81      ostr << desc << ": second insert";
82      report_performance(__FILE__, ostr.str().c_str(), time, resource);
83
84      start_counters(time, resource);
85
86      for (int j = nb - 1; j >= 0; --j)
87	us.erase(j);
88
89      stop_counters(time, resource);
90      ostr.str("");
91      ostr << desc << ": erase from key";
92      report_performance(__FILE__, ostr.str().c_str(), time, resource);
93    }
94
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)
100    {
101      using namespace __gnu_test;
102
103      time_counter time;
104      resource_counter resource;
105
106      const int nb = 200000;
107      // First generate once strings that are going to be used throughout the
108      // bench:
109      std::ostringstream ostr;
110      std::vector<std::string> strs;
111      strs.reserve(nb);
112      for (int i = 0; i != nb; ++i)
113      {
114	ostr.str("");
115	ostr << "string #" << i;
116	strs.push_back(ostr.str());
117      }
118
119      start_counters(time, resource);
120
121      _ContType us;
122      for (int i = 0; i != nb; ++i)
123	us.insert(strs[i]);
124
125      stop_counters(time, resource);
126      ostr.str("");
127      ostr << desc << ": first insert";
128      report_performance(__FILE__, ostr.str().c_str(), time, resource);
129
130      start_counters(time, resource);
131
132      for (int j = nb - 1; j >= 0; --j)
133	{
134	  auto it = us.find(strs[j]);
135	  if (it != us.end())
136	    us.erase(it);
137	}
138
139      stop_counters(time, resource);
140      ostr.str("");
141      ostr << desc << ": erase from iterator";
142      report_performance(__FILE__, ostr.str().c_str(), time, resource);
143
144      start_counters(time, resource);
145
146      us.insert(strs[0]);
147      for (int i = nb - 1; i >= 0; --i)
148	us.insert(strs[i]);
149
150      stop_counters(time, resource);
151      ostr.str("");
152      ostr << desc << ": second insert";
153      report_performance(__FILE__, ostr.str().c_str(), time, resource);
154
155      start_counters(time, resource);
156
157      for (int j = nb - 1; j >= 0; --j)
158	us.erase(strs[j]);
159
160      stop_counters(time, resource);
161      ostr.str("");
162      ostr << desc << ": erase from key";
163      report_performance(__FILE__, ostr.str().c_str(), time, resource);
164    }
165}
166
167template<bool cache>
168  using __uset =
169	      std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
170				    std::allocator<int>,
171				    std::__uset_traits<cache>>;
172
173template<bool cache>
174  using __tr1_uset =
175	      std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
176					std::allocator<int>,
177					cache>;
178
179template<bool cache>
180  using __str_uset =
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>>;
185
186template<bool 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>,
191					cache>;
192
193int main()
194{
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");
201  bench<__uset<true>>(
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");
215  return 0;
216}
217