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 #ifdef _USE_TR1
  22 #  include <tr1/unordered_set>
  23 #else
  24 #  include <unordered_set>
  25 #endif
  26 #include <testsuite_performance.h>
  27
  28 namespace
  29 {
  30   // Bench using an unordered_set<int>. Hash functor for int is quite
  31   // predictable so it helps bench very specific use cases.
  32   template<bool use_cache>
  33     void bench()
  34     {
  35       using namespace __gnu_test;
  36       std::ostringstream ostr;
  37       ostr << "unordered_set<int> " << (use_cache ? "with" : "without")
  38            << " cache";
  39       const std::string desc = ostr.str();
  40
  41       time_counter time;
  42       resource_counter resource;
  43
  44       const int nb = 200000;
  45       start_counters(time, resource);
  46
  47 #ifdef _USE_TR1
  48       std::tr1::__unordered_set<int, std::hash<int>, std::equal_to<int>,
  49                                 std::allocator<int>,
  50                                 use_cache> us;
  51 #else
  52       std::__uset_hashtable<int, std::hash<int>, std::equal_to<int>,
  53                             std::allocator<int>,
  54                             std::__uset_traits<use_cache>> us;
  55 #endif
  56       for (int i = 0; i != nb; ++i)
  57           us.insert(i);
  58
  59       stop_counters(time, resource);
  60       ostr.str("");
  61       ostr << desc << ": first insert";
  62       report_performance(__FILE__, ostr.str().c_str(), time, resource);
  63
  64       start_counters(time, resource);
  65
  66       // Here is the worst erase use case when hashtable implementation was
  67       // something like vector<forward_list<>>. Erasing from the end was very
  68       // costly because we need to return the iterator following the erased
  69       // one, as the hashtable is getting emptier at each step there are
  70       // more and more empty bucket to loop through to reach the end of the
  71       // container and find out that it was in fact the last element.
  72       for (int j = nb - 1; j >= 0; --j)
  73         {
  74           auto it = us.find(j);
  75           if (it != us.end())
  76             us.erase(it);
  77         }
  78
  79       stop_counters(time, resource);
  80       ostr.str("");
  81       ostr << desc << ": erase from iterator";
  82       report_performance(__FILE__, ostr.str().c_str(), time, resource);
  83
  84       start_counters(time, resource);
  85
  86       // This is a worst insertion use case for the current implementation as
  87       // we insert an element at the begining of the hashtable and then we
  88       // insert starting at the end so that each time we need to seek up to the
  89       // first bucket to find the first non-empty one.
  90       us.insert(0);
  91       for (int i = nb - 1; i >= 0; --i)
  92         us.insert(i);
  93
  94       stop_counters(time, resource);
  95       ostr.str("");
  96       ostr << desc << ": second insert";
  97       report_performance(__FILE__, ostr.str().c_str(), time, resource);
  98
  99       start_counters(time, resource);
 100
 101       for (int j = nb - 1; j >= 0; --j)
 102         us.erase(j);
 103
 104       stop_counters(time, resource);
 105       ostr.str("");
 106       ostr << desc << ": erase from key";
 107       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 108     }
 109
 110   // Bench using unordered_set<string> that show how important it is to cache
 111   // hash code as computing string hash code is quite expensive compared to
 112   // computing it for int.
 113   template<bool use_cache>
 114     void bench_str()
 115     {
 116       using namespace __gnu_test;
 117       std::ostringstream ostr;
 118       ostr << "unordered_set<string> " << (use_cache ? "with" : "without")
 119            << " cache";
 120       const std::string desc = ostr.str();
 121
 122       time_counter time;
 123       resource_counter resource;
 124
 125       const int nb = 200000;
 126       // First generate once strings that are going to be used throughout the
 127       // bench:
 128       std::vector<std::string> strs;
 129       strs.reserve(nb);
 130       for (int i = 0; i != nb; ++i)
 131       {
 132         ostr.str("");
 133         ostr << "string #" << i;
 134         strs.push_back(ostr.str());
 135       }
 136
 137       start_counters(time, resource);
 138
 139 #ifdef _USE_TR1
 140       std::tr1::__unordered_set<std::string, std::hash<std::string>,
 141                                 std::equal_to<std::string>,
 142                                 std::allocator<std::string>,
 143                                 use_cache> us;
 144 #else
 145       std::__uset_hashtable<std::string, std::hash<std::string>,
 146                             std::equal_to<std::string>,
 147                             std::allocator<std::string>,
 148                             std::__uset_traits<use_cache>> us;
 149 #endif
 150       for (int i = 0; i != nb; ++i)
 151         us.insert(strs[i]);
 152
 153       stop_counters(time, resource);
 154       ostr.str("");
 155       ostr << desc << ": first insert";
 156       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 157
 158       start_counters(time, resource);
 159
 160       for (int j = nb - 1; j >= 0; --j)
 161         {
 162           auto it = us.find(strs[j]);
 163           if (it != us.end())
 164             us.erase(it);
 165         }
 166
 167       stop_counters(time, resource);
 168       ostr.str("");
 169       ostr << desc << ": erase from iterator";
 170       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 171
 172       start_counters(time, resource);
 173
 174       us.insert(strs[0]);
 175       for (int i = nb - 1; i >= 0; --i)
 176         us.insert(strs[i]);
 177
 178       stop_counters(time, resource);
 179       ostr.str("");
 180       ostr << desc << ": second insert";
 181       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 182
 183       start_counters(time, resource);
 184
 185       for (int j = nb - 1; j >= 0; --j)
 186         us.erase(strs[j]);
 187
 188       stop_counters(time, resource);
 189       ostr.str("");
 190       ostr << desc << ": erase from key";
 191       report_performance(__FILE__, ostr.str().c_str(), time, resource);
 192     }
 193 }
 194
 195 int main()
 196 {
 197   bench<false>();
 198   bench<true>();
 199   bench_str<false>();
 200   bench_str<true>();
 201   return 0;
 202 }