1 // { dg-options "-std=gnu++0x" }
3 // Copyright (C) 2011 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 <unordered_set>
22 #include <testsuite_performance.h>
26 // Bench using an unordered_set<int>. Hash functor for int is quite
27 // predictable so it helps bench very specific use cases.
28 template<bool use_cache
>
31 using namespace __gnu_test
;
32 std::ostringstream ostr
;
33 ostr
<< "unordered_set<int> " << (use_cache
? "with" : "without")
35 const std::string desc
= ostr
.str();
38 resource_counter resource
;
40 const int nb
= 200000;
41 start_counters(time
, resource
);
43 std::__unordered_set
<int, std::hash
<int>, std::equal_to
<int>,
44 std::allocator
<int>, use_cache
> us
;
45 for (int i
= 0; i
!= nb
; ++i
)
48 stop_counters(time
, resource
);
50 ostr
<< desc
<< ": first insert";
51 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
53 start_counters(time
, resource
);
55 // Here is the worst erase use case when hashtable implementation was
56 // something like vector<forward_list<>>. Erasing from the end was very
57 // costly because we need to return the iterator following the erased
58 // one, as the hashtable is getting emptier at each step there are
59 // more and more empty bucket to loop through to reach the end of the
60 // container and find out that it was in fact the last element.
61 for (int j
= nb
- 1; j
>= 0; --j
)
68 stop_counters(time
, resource
);
70 ostr
<< desc
<< ": erase from iterator";
71 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
73 start_counters(time
, resource
);
75 // This is a worst insertion use case for the current implementation as
76 // we insert an element at the begining of the hashtable and then we
77 // insert starting at the end so that each time we need to seek up to the
78 // first bucket to find the first non-empty one.
80 for (int i
= nb
- 1; i
>= 0; --i
)
83 stop_counters(time
, resource
);
85 ostr
<< desc
<< ": second insert";
86 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
88 start_counters(time
, resource
);
90 for (int j
= nb
- 1; j
>= 0; --j
)
93 stop_counters(time
, resource
);
95 ostr
<< desc
<< ": erase from key";
96 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
99 // Bench using unordered_set<string> that show how important it is to cache
100 // hash code as computing string hash code is quite expensive compared to
101 // computing it for int.
102 template<bool use_cache
>
105 using namespace __gnu_test
;
106 std::ostringstream ostr
;
107 ostr
<< "unordered_set<string> " << (use_cache
? "with" : "without")
109 const std::string desc
= ostr
.str();
112 resource_counter resource
;
114 const int nb
= 200000;
115 // First generate once strings that are going to be used throughout the
117 std::vector
<std::string
> strs
;
119 for (int i
= 0; i
!= nb
; ++i
)
122 ostr
<< "string #" << i
;
123 strs
.push_back(ostr
.str());
126 start_counters(time
, resource
);
128 std::__unordered_set
<std::string
, std::hash
<std::string
>,
129 std::equal_to
<std::string
>,
130 std::allocator
<std::string
>, use_cache
> us
;
131 for (int i
= 0; i
!= nb
; ++i
)
134 stop_counters(time
, resource
);
136 ostr
<< desc
<< ": first insert";
137 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
139 start_counters(time
, resource
);
141 for (int j
= nb
- 1; j
>= 0; --j
)
143 auto it
= us
.find(strs
[j
]);
148 stop_counters(time
, resource
);
150 ostr
<< desc
<< ": erase from iterator";
151 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
153 start_counters(time
, resource
);
156 for (int i
= nb
- 1; i
>= 0; --i
)
159 stop_counters(time
, resource
);
161 ostr
<< desc
<< ": second insert";
162 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);
164 start_counters(time
, resource
);
166 for (int j
= nb
- 1; j
>= 0; --j
)
169 stop_counters(time
, resource
);
171 ostr
<< desc
<< ": erase from key";
172 report_performance(__FILE__
, ostr
.str().c_str(), time
, resource
);