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