libstdc++-v3/testsuite/performance/23_containers/insert/54075.cc

   1 // Copyright (C) 2012-2013 Free Software Foundation, Inc.
   2 //
   3 // This file is part of the GNU ISO C++ Library.  This library is free
   4 // software; you can redistribute it and/or modify it under the
   5 // terms of the GNU General Public License as published by the
   6 // Free Software Foundation; either version 3, or (at your option)
   7 // any later version.
   8
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13
  14 // You should have received a copy of the GNU General Public License along
  15 // with this library; see the file COPYING3.  If not see
  16 // <http://www.gnu.org/licenses/>.
  17
  18 // { dg-options "-std=c++11" }
  19
  20 #include <testsuite_performance.h>
  21 #include <random>
  22 #include <sstream>
  23 #include <tr1/unordered_set>
  24 #include <unordered_set>
  25
  26 #define USE_MY_FOO 1
  27
  28 struct Foo
  29 {
  30 #if USE_MY_FOO
  31
  32   typedef std::random_device::result_type _Type;
  33   _Type bar;
  34   _Type baz;
  35   _Type meh;
  36
  37   void
  38   init(std::random_device& randev)
  39   {
  40     bar = randev();
  41     baz = randev();
  42     meh = randev();
  43   }
  44
  45 #else
  46
  47   int bar;
  48   int baz;
  49   int meh;
  50
  51   Foo()
  52   { bar = random(); baz = random(); meh = random(); }
  53   Foo(const Foo&) = default;
  54
  55 #endif
  56
  57   std::size_t
  58   hash() const noexcept
  59   { return std::size_t(bar ^ baz ^ meh); }
  60
  61   inline bool
  62   operator==(const Foo& other) const
  63   { return other.bar == bar && other.baz == baz && other.meh == meh; }
  64 };
  65
  66 struct HashFunction
  67 {
  68   template<typename T>
  69     std::size_t operator()(const T& t) const noexcept
  70     { return t.hash(); }
  71 };
  72
  73 const int sz = 300000;
  74
  75 template<typename _ContType>
  76   void
  77   bench(const char* container_desc, const typename _ContType::value_type* foos)
  78   {
  79     using namespace __gnu_test;
  80
  81     _ContType s;
  82
  83     time_counter time;
  84     resource_counter resource;
  85     start_counters(time, resource);
  86
  87     for (int i = 0; i != sz ; ++i)
  88         s.insert(foos[i]);
  89
  90     stop_counters(time, resource);
  91     std::ostringstream ostr;
  92     ostr << container_desc << sz << " insertion attempts, "
  93          << s.size() << " inserted";
  94     report_performance(__FILE__, ostr.str().c_str(), time, resource);
  95
  96     // Try to insert again to check performance of collision detection
  97     const int nb_loop = 10;
  98     start_counters(time, resource);
  99
 100     for (int j = 0; j != nb_loop; ++j)
 101       for (int i = 0; i != sz; ++i)
 102         s.insert(foos[i]);
 103
 104     stop_counters(time, resource);
 105     ostr.str("");
 106     ostr << container_desc << nb_loop << " times insertion of "
 107          << sz << " elements";
 108     report_performance(__FILE__, ostr.str().c_str(), time, resource);
 109   }
 110
 111 template<bool cache>
 112   using __tr1_uset = std::tr1::__unordered_set<Foo, HashFunction,
 113                                                std::equal_to<Foo>,
 114                                                std::allocator<Foo>,
 115                                                cache>;
 116 template<bool cache>
 117   using __tr1_umset = std::tr1::__unordered_multiset<Foo, HashFunction,
 118                                                      std::equal_to<Foo>,
 119                                                      std::allocator<Foo>,
 120                                                      cache>;
 121 template<bool cache>
 122   using __uset = std::__uset_hashtable<Foo, HashFunction,
 123                                        std::equal_to<Foo>,
 124                                        std::allocator<Foo>,
 125                                        std::__uset_traits<cache>>;
 126 template<bool cache>
 127   using __umset = std::__umset_hashtable<Foo, HashFunction,
 128                                          std::equal_to<Foo>,
 129                                          std::allocator<Foo>,
 130                                          std::__uset_traits<cache>>;
 131
 132 int main()
 133 {
 134   using namespace __gnu_test;
 135
 136   {
 137     int bars[sz];
 138     for (int i = 0; i != sz; ++i)
 139       bars[i] = i;
 140     bench<std::tr1::unordered_set<int>>(
 141         "std::tr1::unordered_set<int> ", bars);
 142     bench<std::unordered_set<int>>(
 143         "std::unordered_set<int> ", bars);
 144   }
 145
 146   Foo foos[sz];
 147 #if USE_MY_FOO
 148   {
 149     std::random_device randev;
 150     for (int i = 0; i != sz; ++i)
 151       foos[i].init(randev);
 152   }
 153 #endif
 154
 155   time_counter time;
 156   resource_counter resource;
 157   start_counters(time, resource);
 158
 159   bench<__tr1_uset<false>>(
 160         "std::tr1::unordered_set without hash code cached ", foos);
 161   bench<__tr1_uset<true>>(
 162         "std::tr1::unordered_set with hash code cached ", foos);
 163   bench<__tr1_umset<false>>(
 164         "std::tr1::unordered_multiset without hash code cached ", foos);
 165   bench<__tr1_umset<true>>(
 166         "std::tr1::unordered_multiset with hash code cached ", foos);
 167
 168   stop_counters(time, resource);
 169   report_performance(__FILE__, "tr1 benches", time, resource);
 170
 171   start_counters(time, resource);
 172   bench<__uset<false>>(
 173         "std::unordered_set without hash code cached ", foos);
 174   bench<__uset<true>>(
 175         "std::unordered_set with hash code cached ", foos);
 176   bench<__umset<false>>(
 177         "std::unordered_multiset without hash code cached ", foos);
 178   bench<__umset<true>>(
 179         "std::unordered_multiset with hash code cached ", foos);
 180
 181   stop_counters(time, resource);
 182   report_performance(__FILE__, "std benches", time, resource);
 183
 184   bench<std::unordered_set<Foo, HashFunction>>(
 185         "std::unordered_set default cache ", foos);
 186   bench<std::unordered_multiset<Foo, HashFunction>>(
 187         "std::unordered_multiset default cache ", foos);
 188 }