1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2021 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: push_functor(It ins_it_b,It ins_it_e)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 operator ()(std::size_t resolution)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: push_modify_functor(It ins_it_b,It ins_it_e,value_type mod_val)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 operator ()(std::size_t resolution)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: push_functor(It ins_it_b,It ins_it_e)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 operator ()(std::size_t resolution)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: push_functor(It ins_it_b,It ins_it_e)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 operator ()(std::size_t resolution)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: push_modify_functor(It ins_it_b,It ins_it_e,value_type mod_val)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 operator ()(std::size_t resolution)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: push_modify_functor(It ins_it_b,It ins_it_e,value_type mod_val)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 operator ()(std::size_t resolution)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: modify_test(It b,size_t vn,size_t vs,size_t vm,bool modify_up)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 modify(Cntnr,It ins_it_b,It ins_it_e)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>:: operator ()(Cntnr)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 330