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