libstdc++-v3/testsuite/performance/23_containers/insert_erase/41975.cc

   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
  25 namespace
  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
 167 template<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
 173 template<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
 179 template<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
 186 template<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
 193 int 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 }