libstdc++-v3/testsuite/util/performance/priority_queue/timing/modify_test.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2013 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 terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20
  21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  22
  23 // Permission to use, copy, modify, sell, and distribute this software
  24 // is hereby granted without fee, provided that the above copyright
  25 // notice appears in all copies, and that both that copyright notice
  26 // and this permission notice appear in supporting documentation. None
  27 // of the above authors, nor IBM Haifa Research Laboratories, make any
  28 // representation about the suitability of this software for any
  29 // purpose. It is provided "as is" without express or implied
  30 // warranty.
  31
  32 /**
  33  * @file modify_test.hpp
  34  * Contains a modify performance test.
  35  */
  36
  37 #ifndef PB_DS_JOIN_TEST_HPP
  38 #define PB_DS_JOIN_TEST_HPP
  39
  40 #include <performance/time/timing_test_base.hpp>
  41 #include <ext/pb_ds/detail/type_utils.hpp>
  42 #include <performance/io/xml_formatter.hpp>
  43 #include <common_type/priority_queue/string_form.hpp>
  44 #include <iterator>
  45
  46 namespace __gnu_pbds
  47 {
  48   namespace test
  49   {
  50     namespace detail
  51     {
  52       // Primary templates.
  53       template<typename It, class Cntnr, class Tag>
  54       class push_functor
  55       {
  56       public:
  57         push_functor(It ins_it_b,  It ins_it_e)
  58         : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
  59         { }
  60
  61         void
  62         operator()(std::size_t resolution)
  63         {
  64           typedef typename Cntnr::point_iterator point_iterator;
  65           typedef typename Cntnr::const_reference const_reference;
  66           for (std::size_t i = 0; i < resolution; ++i)
  67             {
  68               Cntnr c;
  69               typedef std::vector<point_iterator> it_vec_t;
  70               it_vec_t m_a_its;
  71               for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
  72                 m_a_its.push_back(c.push(const_reference(ins_it->first)));
  73             }
  74         }
  75
  76       private:
  77         const It m_ins_it_b;
  78         const It m_ins_it_e;
  79       };
  80
  81       template<typename It, class Cntnr, class Tag>
  82       class push_modify_functor
  83       {
  84       private:
  85         typedef typename Cntnr::point_iterator point_iterator;
  86         typedef typename Cntnr::const_reference const_reference;
  87         typedef typename Cntnr::value_type value_type;
  88
  89       public:
  90         push_modify_functor(It ins_it_b, It ins_it_e, value_type mod_val)
  91         : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val)
  92         { }
  93
  94         void
  95         operator()(std::size_t resolution)
  96         {
  97           for (std::size_t i = 0; i < resolution; ++i)
  98             {
  99               Cntnr c;
 100               typedef std::vector<typename Cntnr::point_iterator> it_vec_t;
 101               it_vec_t m_a_its;
 102               for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 103                 m_a_its.push_back(c.push(const_reference(ins_it->first)));
 104
 105               typename it_vec_t::iterator mod_it = m_a_its.begin();
 106               while (mod_it != m_a_its.end())
 107                 c.modify(*mod_it++, m_mod_val);
 108             }
 109         }
 110
 111       private:
 112         const It m_ins_it_b;
 113         const It m_ins_it_e;
 114         const value_type m_mod_val;
 115       };
 116
 117       // Specializations.
 118       template<typename It, class Cntnr>
 119       class push_functor<It, Cntnr, __gnu_pbds::binary_heap_tag>
 120       {
 121       public:
 122         push_functor(It ins_it_b,  It ins_it_e)
 123         : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
 124         { }
 125
 126         void
 127         operator()(std::size_t resolution)
 128         {
 129           typedef typename Cntnr::const_reference const_reference;
 130           for (std::size_t i = 0; i < resolution; ++i)
 131             {
 132               Cntnr c;
 133               for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 134                 c.push(const_reference(ins_it->first));
 135             }
 136         }
 137
 138       private:
 139         const It m_ins_it_b;
 140         const It m_ins_it_e;
 141       };
 142
 143       template<typename It, class Cntnr>
 144       class push_functor<It, Cntnr, __gnu_pbds::test::native_pq_tag>
 145       {
 146       public:
 147         push_functor(It ins_it_b,  It ins_it_e)
 148         : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
 149         { }
 150
 151         void
 152         operator()(std::size_t resolution)
 153         {
 154           typedef typename Cntnr::const_reference const_reference;
 155           for (std::size_t i = 0; i < resolution; ++i)
 156             {
 157               Cntnr c;
 158
 159               for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 160                 c.push(const_reference(ins_it->first));
 161             }
 162         }
 163
 164       private:
 165         const It m_ins_it_b;
 166         const It m_ins_it_e;
 167       };
 168
 169
 170       template<typename It, class Cntnr>
 171       class push_modify_functor<It, Cntnr, __gnu_pbds::binary_heap_tag>
 172       {
 173       private:
 174         typedef typename Cntnr::iterator iterator;
 175         typedef typename Cntnr::const_reference const_reference;
 176         typedef typename Cntnr::value_type value_type;
 177
 178       public:
 179         push_modify_functor(It ins_it_b, It ins_it_e, value_type mod_val)
 180         : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val)
 181         { }
 182
 183         void
 184         operator()(std::size_t resolution)
 185         {
 186           for (std::size_t i = 0; i < resolution; ++i)
 187             {
 188               Cntnr c;
 189               It ins_it;
 190               for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 191                 c.push(const_reference(ins_it->first));
 192
 193               for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 194                 {
 195                   bool modified = false;
 196                   for (iterator it = c.begin(); !modified && it != c.end(); ++it)
 197                     if (*it == ins_it->first)
 198                       {
 199                         c.modify(it, m_mod_val);
 200                         modified = true;
 201                       }
 202                 }
 203             }
 204         }
 205
 206       private:
 207         const It m_ins_it_b;
 208         const It m_ins_it_e;
 209         const value_type m_mod_val;
 210       };
 211
 212       template<typename It, class Cntnr>
 213       class push_modify_functor<It, Cntnr, __gnu_pbds::test::native_pq_tag>
 214       {
 215       private:
 216         typedef typename Cntnr::value_type value_type;
 217         typedef typename Cntnr::const_reference const_reference;
 218
 219       public:
 220         push_modify_functor(It ins_it_b,  It ins_it_e, value_type mod_val)
 221         : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val)
 222         { }
 223
 224         void
 225         operator()(std::size_t resolution)
 226         {
 227           for (std::size_t i = 0; i < resolution; ++i)
 228             {
 229               Cntnr c;
 230               It ins_it;
 231               for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 232                 c.push(const_reference(ins_it->first));
 233               for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 234                 c.modify(ins_it->first, m_mod_val);
 235             }
 236         }
 237
 238       private:
 239         const It m_ins_it_b;
 240         const It m_ins_it_e;
 241         const value_type m_mod_val;
 242       };
 243     } // namespace detail
 244
 245     template<typename It>
 246     class modify_test : private __gnu_pbds::test::detail::timing_test_base
 247     {
 248     public:
 249       modify_test(It b, size_t vn, size_t vs, size_t vm, bool modify_up)
 250       : m_ins_b(b), m_ins_vn(vn), m_ins_vs(vs), m_ins_vm(vm),
 251       m_modify_up(modify_up)
 252       { }
 253
 254       template<typename Cntnr>
 255       void
 256       operator()(Cntnr);
 257
 258     private:
 259       modify_test(const modify_test&);
 260
 261       template<typename Cntnr>
 262       void
 263       modify(Cntnr, It ins_it_b, It ins_it_e)
 264       {
 265         typedef typename Cntnr::const_reference const_reference;
 266         Cntnr cntnr;
 267         for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
 268           cntnr.modify(const_reference(*ins_it));
 269       }
 270
 271       const It m_ins_b;
 272       const size_t m_ins_vn;
 273       const size_t m_ins_vs;
 274       const size_t m_ins_vm;
 275       const bool m_modify_up;
 276     };
 277
 278     template<typename It>
 279     template<typename Cntnr>
 280     void
 281     modify_test<It>::
 282     operator()(Cntnr)
 283     {
 284       typedef typename Cntnr::value_type value_type;
 285       typedef typename Cntnr::container_category container_category;
 286       typedef typename Cntnr::const_reference const_reference;
 287       typedef detail::timing_test_base timing_test_base;
 288       typedef detail::push_functor<It, Cntnr, container_category> psh_fnct;
 289       typedef detail::push_modify_functor<It, Cntnr, container_category> psh_mod_fnct;
 290       typedef xml_result_set_performance_formatter formatter_type;
 291       formatter_type res_set_fmt(string_form<Cntnr>::name(),
 292                                  string_form<Cntnr>::desc());
 293
 294       for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
 295         {
 296           const size_t v = m_ins_vn + i * m_ins_vs;
 297           It b = m_ins_b;
 298           It e = m_ins_b;
 299           std::advance(e, v);
 300
 301           psh_fnct psh_fn(b, e);
 302           const double psh_res = timing_test_base::operator()(psh_fn);
 303
 304           value_type val = b->first;
 305           {
 306             Cntnr mod_val_container;
 307             for (It mod_val_it = b; mod_val_it != e; ++mod_val_it)
 308               {
 309                 value_type pot = mod_val_it->first;
 310                 if (m_modify_up == mod_val_container.get_cmp_fn()(val, pot))
 311                   val = pot;
 312               }
 313           }
 314
 315           psh_mod_fnct psh_mod_fn(b, e, val);
 316           const double psh_mod_res = timing_test_base::operator()(psh_mod_fn);
 317
 318           const double min_res = double(timing_test_base::min_time_res());
 319           const double effective_delta = std::max(psh_mod_res - psh_res,
 320                                                   min_res);
 321
 322           res_set_fmt.add_res(v, effective_delta / v);
 323         }
 324     }
 325   } // namespace test
 326 } // namespace __gnu_pbds
 327
 328 #endif
 329