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

   1 // Copyright (C) 2012-2019 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-do run { target 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::__umset_traits<cache>>;
 131
 132 template<bool cache>
 133   using __uset2 =
 134               std::_Hashtable<Foo, Foo, std::allocator<Foo>,
 135                               std::__detail::_Identity,
 136                               std::equal_to<Foo>, HashFunction,
 137                               std::__detail::_Mask_range_hashing,
 138                               std::__detail::_Default_ranged_hash,
 139                               std::__detail::_Power2_rehash_policy,
 140                               std::__uset_traits<cache>>;
 141
 142 template<bool cache>
 143   using __umset2 =
 144               std::_Hashtable<Foo, Foo, std::allocator<Foo>,
 145                               std::__detail::_Identity,
 146                               std::equal_to<Foo>, HashFunction,
 147                               std::__detail::_Mask_range_hashing,
 148                               std::__detail::_Default_ranged_hash,
 149                               std::__detail::_Power2_rehash_policy,
 150                               std::__umset_traits<cache>>;
 151
 152 int main()
 153 {
 154   using namespace __gnu_test;
 155
 156   {
 157     int bars[sz];
 158     for (int i = 0; i != sz; ++i)
 159       bars[i] = i;
 160     bench<std::tr1::unordered_set<int>>(
 161         "std::tr1::unordered_set<int> ", bars);
 162     bench<std::unordered_set<int>>(
 163         "std::unordered_set<int> ", bars);
 164   }
 165
 166   Foo foos[sz];
 167 #if USE_MY_FOO
 168   {
 169     std::random_device randev;
 170     for (int i = 0; i != sz; ++i)
 171       foos[i].init(randev);
 172   }
 173 #endif
 174
 175   time_counter time;
 176   resource_counter resource;
 177   start_counters(time, resource);
 178
 179   bench<__tr1_uset<false>>(
 180         "std::tr1::unordered_set without hash code cached ", foos);
 181   bench<__tr1_uset<true>>(
 182         "std::tr1::unordered_set with hash code cached ", foos);
 183   bench<__tr1_umset<false>>(
 184         "std::tr1::unordered_multiset without hash code cached ", foos);
 185   bench<__tr1_umset<true>>(
 186         "std::tr1::unordered_multiset with hash code cached ", foos);
 187
 188   stop_counters(time, resource);
 189   report_performance(__FILE__, "tr1 benches", time, resource);
 190
 191   start_counters(time, resource);
 192   bench<__uset<false>>(
 193         "std::unordered_set without hash code cached ", foos);
 194   bench<__uset<true>>(
 195         "std::unordered_set with hash code cached ", foos);
 196   bench<__umset<false>>(
 197         "std::unordered_multiset without hash code cached ", foos);
 198   bench<__umset<true>>(
 199         "std::unordered_multiset with hash code cached ", foos);
 200
 201   stop_counters(time, resource);
 202   report_performance(__FILE__, "std benches", time, resource);
 203
 204   start_counters(time, resource);
 205   bench<__uset2<false>>(
 206         "std::unordered_set2 without hash code cached ", foos);
 207   bench<__uset2<true>>(
 208         "std::unordered_set2 with hash code cached ", foos);
 209   bench<__umset2<false>>(
 210         "std::unordered_multiset2 without hash code cached ", foos);
 211   bench<__umset2<true>>(
 212         "std::unordered_multiset2 with hash code cached ", foos);
 213
 214   stop_counters(time, resource);
 215   report_performance(__FILE__, "std2 benches", time, resource);
 216
 217   bench<std::unordered_set<Foo, HashFunction>>(
 218         "std::unordered_set default cache ", foos);
 219   bench<std::unordered_multiset<Foo, HashFunction>>(
 220         "std::unordered_multiset default cache ", foos);
 221 }