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

   1 // { dg-options "-std=gnu++0x" }
   2
   3 // Copyright (C) 2011 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 <unordered_set>
  22 #include <testsuite_performance.h>
  23
  24 namespace
  25 {
  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>
  29     void bench()
  30     {
  31       using namespace __gnu_test;
  32       std::ostringstream ostr;
  33       ostr << "unordered_set<int> " << (use_cache ? "with" : "without")
  34            << " cache";
  35       const std::string desc = ostr.str();
  36
  37       time_counter time;
  38       resource_counter resource;
  39
  40       const int nb = 200000;
  41       start_counters(time, resource);
  42
  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)
  46         us.insert(i);
  47
  48       stop_counters(time, resource);
  49       ostr.str("");
  50       ostr << desc << ": first insert";
  51       report_performance(__FILE__, ostr.str().c_str(), time, resource);
  52
  53       start_counters(time, resource);
  54
  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)
  62         {
  63           auto it = us.find(j);
  64           if (it != us.end())
  65             us.erase(it);
  66         }
  67
  68       stop_counters(time, resource);
  69       ostr.str("");
  70       ostr << desc << ": erase from iterator";
  71       report_performance(__FILE__, ostr.str().c_str(), time, resource);
  72
  73       start_counters(time, resource);
  74
  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.
  79       us.insert(0);
  80       for (int i = nb - 1; i >= 0; --i)
  81         us.insert(i);
  82
  83       stop_counters(time, resource);
  84       ostr.str("");
  85       ostr << desc << ": second insert";
  86       report_performance(__FILE__, ostr.str().c_str(), time, resource);
  87
  88       start_counters(time, resource);
  89
  90       for (int j = nb - 1; j >= 0; --j)
  91         us.erase(j);
  92
  93       stop_counters(time, resource);
  94       ostr.str("");
  95       ostr << desc << ": erase from key";
  96       report_performance(__FILE__, ostr.str().c_str(), time, resource);
  97     }
  98
  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>
 103     void bench_str()
 104     {
 105       using namespace __gnu_test;
 106       std::ostringstream ostr;
 107       ostr << "unordered_set<string> " << (use_cache ? "with" : "without")
 108            << " cache";
 109       const std::string desc = ostr.str();
 110
 111       time_counter time;
 112       resource_counter resource;
 113
 114       const int nb = 200000;
 115       // First generate once strings that are going to be used throughout the
 116       // bench:
 117       std::vector<std::string> strs;
 118       strs.reserve(nb);
 119       for (int i = 0; i != nb; ++i)
 120       {
 121         ostr.str("");
 122         ostr << "string #" << i;
 123         strs.push_back(ostr.str());
 124       }
 125
 126       start_counters(time, resource);
 127
 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)
 132         us.insert(strs[i]);
 133
 134       stop_counters(time, resource);
 135       ostr.str("");
 136       ostr << desc << ": first insert";
 137       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 138
 139       start_counters(time, resource);
 140
 141       for (int j = nb - 1; j >= 0; --j)
 142         {
 143           auto it = us.find(strs[j]);
 144           if (it != us.end())
 145             us.erase(it);
 146         }
 147
 148       stop_counters(time, resource);
 149       ostr.str("");
 150       ostr << desc << ": erase from iterator";
 151       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 152
 153       start_counters(time, resource);
 154
 155       us.insert(strs[0]);
 156       for (int i = nb - 1; i >= 0; --i)
 157         us.insert(strs[i]);
 158
 159       stop_counters(time, resource);
 160       ostr.str("");
 161       ostr << desc << ": second insert";
 162       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 163
 164       start_counters(time, resource);
 165
 166       for (int j = nb - 1; j >= 0; --j)
 167         us.erase(strs[j]);
 168
 169       stop_counters(time, resource);
 170       ostr.str("");
 171       ostr << desc << ": erase from key";
 172       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 173     }
 174 }
 175
 176 int main()
 177 {
 178   bench<false>();
 179   bench<true>();
 180   bench_str<false>();
 181   bench_str<true>();
 182   return 0;
 183 }