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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file modify_test.hpp
  44  * Contains a modify performance test.
  45  */
  46
  47 #ifndef PB_DS_JOIN_TEST_HPP
  48 #define PB_DS_JOIN_TEST_HPP
  49
  50 #include <performance/time/timing_test_base.hpp>
  51 #include <ext/pb_ds/detail/type_utils.hpp>
  52 #include <performance/io/xml_formatter.hpp>
  53 #include <common_type/priority_queue/string_form.hpp>
  54 #include <iterator>
  55
  56 namespace pb_ds
  57 {
  58
  59   namespace test
  60   {
  61
  62     namespace detail
  63     {
  64
  65       template<typename It, class Cntnr, class Tag>
  66       class push_functor
  67       {
  68       public:
  69         push_functor(It ins_it_b,  It ins_it_e) : m_ins_it_b(ins_it_b),
  70                                                   m_ins_it_e(ins_it_e)
  71         { }
  72
  73         void
  74         operator()(std::size_t resolution)
  75         {
  76           for (std::size_t i = 0; i < resolution; ++i)
  77             {
  78               Cntnr c;
  79
  80               typedef std::vector< typename Cntnr::point_iterator> it_vec_t;
  81
  82               it_vec_t m_a_its;
  83
  84               for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
  85                 m_a_its.push_back(c.push((typename Cntnr::const_reference)(ins_it->first)));
  86             }
  87         }
  88
  89       private:
  90         const It m_ins_it_b;
  91         const It m_ins_it_e;
  92       };
  93
  94       template<typename It, class Cntnr, class Tag>
  95       class push_modify_functor
  96       {
  97       public:
  98         push_modify_functor(It ins_it_b,  It ins_it_e,  typename Cntnr::value_type mod_val) : m_ins_it_b(ins_it_b),
  99                                                                                               m_ins_it_e(ins_it_e),
 100                                                                                               m_mod_val(mod_val)
 101         { }
 102
 103         void
 104         operator()(std::size_t resolution)
 105         {
 106           for (std::size_t i = 0; i < resolution; ++i)
 107             {
 108               Cntnr c;
 109
 110               typedef std::vector< typename Cntnr::point_iterator> it_vec_t;
 111
 112               it_vec_t m_a_its;
 113
 114               for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 115                 m_a_its.push_back(c.push((typename Cntnr::const_reference)(ins_it->first)));
 116
 117               typename it_vec_t::iterator mod_it = m_a_its.begin();
 118
 119               while (mod_it != m_a_its.end())
 120                 c.modify(*mod_it++, m_mod_val);
 121             }
 122         }
 123
 124       private:
 125         const It m_ins_it_b;
 126         const It m_ins_it_e;
 127
 128         const typename Cntnr::value_type m_mod_val;
 129       };
 130
 131       template<typename It, class Cntnr>
 132       class push_functor<
 133         It,
 134         Cntnr,
 135         pb_ds::binary_heap_tag>
 136       {
 137       public:
 138         push_functor(It ins_it_b,  It ins_it_e) : m_ins_it_b(ins_it_b),
 139                                                   m_ins_it_e(ins_it_e)
 140         { }
 141
 142         void
 143         operator()(std::size_t resolution)
 144         {
 145           for (std::size_t i = 0; i < resolution; ++i)
 146             {
 147               Cntnr c;
 148
 149               for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 150                 c.push((typename Cntnr::const_reference)(ins_it->first));
 151             }
 152         }
 153
 154       private:
 155         const It m_ins_it_b;
 156         const It m_ins_it_e;
 157       };
 158
 159       template<typename It, class Cntnr>
 160       class push_modify_functor<
 161         It,
 162         Cntnr,
 163         pb_ds::binary_heap_tag>
 164       {
 165       public:
 166         push_modify_functor(It ins_it_b,  It ins_it_e,  typename Cntnr::value_type mod_val) : m_ins_it_b(ins_it_b),
 167                                                                                               m_ins_it_e(ins_it_e),
 168                                                                                               m_mod_val(mod_val)
 169         { }
 170
 171         void
 172         operator()(std::size_t resolution)
 173         {
 174           for (std::size_t i = 0; i < resolution; ++i)
 175             {
 176               Cntnr c;
 177
 178               It ins_it;
 179
 180               for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 181                 c.push((typename Cntnr::const_reference)(ins_it->first));
 182
 183               for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 184                 {
 185                   bool modified = false;
 186
 187                   for (typename Cntnr::iterator it = c.begin(); !modified&&  it != c.end(); ++it)
 188                     if (*it == ins_it->first)
 189                       {
 190                         c.modify(it, m_mod_val);
 191
 192                         modified = true;
 193                       }
 194                 }
 195             }
 196         }
 197
 198       private:
 199         const It m_ins_it_b;
 200         const It m_ins_it_e;
 201
 202         const typename Cntnr::value_type m_mod_val;
 203       };
 204
 205       template<typename It, class Cntnr>
 206       class push_functor<
 207         It,
 208         Cntnr,
 209         pb_ds::test::native_pq_tag>
 210       {
 211       public:
 212         push_functor(It ins_it_b,  It ins_it_e) : m_ins_it_b(ins_it_b),
 213                                                   m_ins_it_e(ins_it_e)
 214         { }
 215
 216         void
 217         operator()(std::size_t resolution)
 218         {
 219           for (std::size_t i = 0; i < resolution; ++i)
 220             {
 221               Cntnr c;
 222
 223               for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 224                 c.push((typename Cntnr::const_reference)(ins_it->first));
 225             }
 226         }
 227
 228       private:
 229         const It m_ins_it_b;
 230         const It m_ins_it_e;
 231       };
 232
 233       template<typename It, class Cntnr>
 234       class push_modify_functor<
 235         It,
 236         Cntnr,
 237         pb_ds::test::native_pq_tag>
 238       {
 239       public:
 240         push_modify_functor(It ins_it_b,  It ins_it_e,  typename Cntnr::value_type mod_val) : m_ins_it_b(ins_it_b),
 241                                                                                               m_ins_it_e(ins_it_e),
 242                                                                                               m_mod_val(mod_val)
 243         { }
 244
 245         void
 246         operator()(std::size_t resolution)
 247         {
 248           for (std::size_t i = 0; i < resolution; ++i)
 249             {
 250               Cntnr c;
 251
 252               It ins_it;
 253
 254               for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 255                 c.push((typename Cntnr::const_reference)(ins_it->first));
 256
 257               for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
 258                 c.modify(ins_it->first, m_mod_val);
 259             }
 260         }
 261
 262       private:
 263         const It m_ins_it_b;
 264         const It m_ins_it_e;
 265
 266         const typename Cntnr::value_type m_mod_val;
 267       };
 268
 269     } // namespace detail
 270
 271 #define PB_DS_CLASS_T_DEC                       \
 272     template<typename It>
 273
 274 #define PB_DS_CLASS_C_DEC                               \
 275     modify_test<                                        \
 276                                                 It>
 277
 278     template<typename It>
 279     class modify_test : private pb_ds::test::detail::timing_test_base
 280     {
 281     public:
 282       modify_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, bool m_modify_up);
 283
 284       template<typename Cntnr>
 285       void
 286       operator()(pb_ds::detail::type_to_type<Cntnr>);
 287
 288     private:
 289       modify_test(const modify_test& );
 290
 291       template<typename Cntnr>
 292       void
 293       modify(pb_ds::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e);
 294
 295     private:
 296       const It m_ins_b;
 297
 298       const size_t m_ins_vn;
 299       const size_t m_ins_vs;
 300       const size_t m_ins_vm;
 301
 302       const bool m_modify_up;
 303     };
 304
 305     PB_DS_CLASS_T_DEC
 306     PB_DS_CLASS_C_DEC::
 307     modify_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, bool modify_up) :
 308       m_ins_b(ins_b),
 309       m_ins_vn(ins_vn),
 310       m_ins_vs(ins_vs),
 311       m_ins_vm(ins_vm),
 312       m_modify_up(modify_up)
 313     { }
 314
 315     PB_DS_CLASS_T_DEC
 316     template<typename Cntnr>
 317     void
 318     PB_DS_CLASS_C_DEC::
 319     operator()(pb_ds::detail::type_to_type<Cntnr>)
 320     {
 321       xml_result_set_performance_formatter res_set_fmt(
 322                                                        string_form<Cntnr>::name(),
 323                                                        string_form<Cntnr>::desc());
 324
 325       for (size_t size_i = 0; m_ins_vn + size_i*  m_ins_vs < m_ins_vm; ++size_i)
 326         {
 327           const size_t v = m_ins_vn + size_i*  m_ins_vs;
 328
 329           It ins_it_b = m_ins_b;
 330           It ins_it_e = m_ins_b;
 331           std::advance(ins_it_e, v);
 332
 333           pb_ds::test::detail::push_functor<It, Cntnr, typename Cntnr::container_category>
 334             push_fn(ins_it_b, ins_it_e);
 335
 336           const double push_res =
 337             pb_ds::test::detail::timing_test_base::operator()(push_fn);
 338
 339           typename Cntnr::value_type mod_val = ins_it_b->first;
 340
 341           {
 342             Cntnr mod_val_container;
 343             for (It mod_val_it = ins_it_b; mod_val_it != ins_it_e; ++mod_val_it)
 344               {
 345                 typename Cntnr::value_type pot = mod_val_it->first;
 346
 347                 if (m_modify_up == mod_val_container.get_cmp_fn()(mod_val, pot))
 348                   mod_val = pot;
 349               }
 350           }
 351
 352           pb_ds::test::detail::push_modify_functor<It, Cntnr, typename Cntnr::container_category>
 353             push_modify_fn(ins_it_b, ins_it_e, mod_val);
 354
 355           const double push_modify_res =
 356             pb_ds::test::detail::timing_test_base::operator()(push_modify_fn);
 357
 358           const double effective_delta = std::max(
 359                                                   push_modify_res - push_res,
 360                                                   pb_ds::test::detail::timing_test_base::min_time_res());
 361
 362           res_set_fmt.add_res(v, effective_delta / v);
 363         }
 364     }
 365
 366     PB_DS_CLASS_T_DEC
 367     template<typename Cntnr>
 368     void
 369     PB_DS_CLASS_C_DEC::
 370     modify(pb_ds::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e)
 371     {
 372       Cntnr cntnr;
 373
 374       for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
 375         cntnr.modify((typename Cntnr::const_reference)(*ins_it));
 376     }
 377
 378 #undef PB_DS_CLASS_T_DEC
 379
 380 #undef PB_DS_CLASS_C_DEC
 381
 382   } // namespace test
 383
 384 } // namespace pb_ds
 385
 386 #endif // #ifndef PB_DS_JOIN_TEST_HPP
 387