]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
aa118a03 | 3 | // Copyright (C) 2005-2014 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | |
748086b7 JJ |
17 | // along with this library; see the file COPYING3. If not see |
18 | // <http://www.gnu.org/licenses/>. | |
4569a895 | 19 | |
4569a895 AT |
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 | ||
5e11f978 | 46 | namespace __gnu_pbds |
4569a895 | 47 | { |
4569a895 AT |
48 | namespace test |
49 | { | |
4569a895 AT |
50 | namespace detail |
51 | { | |
382a1351 | 52 | // Primary templates. |
4569a895 AT |
53 | template<typename It, class Cntnr, class Tag> |
54 | class push_functor | |
55 | { | |
56 | public: | |
3441f106 BK |
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) | |
4569a895 AT |
59 | { } |
60 | ||
61 | void | |
62 | operator()(std::size_t resolution) | |
63 | { | |
3441f106 BK |
64 | typedef typename Cntnr::point_iterator point_iterator; |
65 | typedef typename Cntnr::const_reference const_reference; | |
4569a895 AT |
66 | for (std::size_t i = 0; i < resolution; ++i) |
67 | { | |
68 | Cntnr c; | |
3441f106 | 69 | typedef std::vector<point_iterator> it_vec_t; |
4569a895 | 70 | it_vec_t m_a_its; |
4569a895 | 71 | for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) |
3441f106 | 72 | m_a_its.push_back(c.push(const_reference(ins_it->first))); |
4569a895 AT |
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 | { | |
3441f106 BK |
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 | ||
4569a895 | 89 | public: |
3441f106 BK |
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) | |
4569a895 AT |
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; | |
3441f106 | 100 | typedef std::vector<typename Cntnr::point_iterator> it_vec_t; |
4569a895 | 101 | it_vec_t m_a_its; |
4569a895 | 102 | for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) |
3441f106 | 103 | m_a_its.push_back(c.push(const_reference(ins_it->first))); |
4569a895 AT |
104 | |
105 | typename it_vec_t::iterator mod_it = m_a_its.begin(); | |
4569a895 AT |
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; | |
3441f106 | 114 | const value_type m_mod_val; |
4569a895 AT |
115 | }; |
116 | ||
382a1351 | 117 | // Specializations. |
4569a895 | 118 | template<typename It, class Cntnr> |
5e11f978 | 119 | class push_functor<It, Cntnr, __gnu_pbds::binary_heap_tag> |
4569a895 AT |
120 | { |
121 | public: | |
3441f106 BK |
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) | |
4569a895 AT |
124 | { } |
125 | ||
126 | void | |
127 | operator()(std::size_t resolution) | |
128 | { | |
3441f106 | 129 | typedef typename Cntnr::const_reference const_reference; |
4569a895 AT |
130 | for (std::size_t i = 0; i < resolution; ++i) |
131 | { | |
132 | Cntnr c; | |
4569a895 | 133 | for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) |
3441f106 | 134 | c.push(const_reference(ins_it->first)); |
4569a895 AT |
135 | } |
136 | } | |
137 | ||
138 | private: | |
139 | const It m_ins_it_b; | |
140 | const It m_ins_it_e; | |
141 | }; | |
142 | ||
382a1351 | 143 | template<typename It, class Cntnr> |
5e11f978 | 144 | class push_functor<It, Cntnr, __gnu_pbds::test::native_pq_tag> |
382a1351 BK |
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 | ||
4569a895 | 170 | template<typename It, class Cntnr> |
5e11f978 | 171 | class push_modify_functor<It, Cntnr, __gnu_pbds::binary_heap_tag> |
4569a895 | 172 | { |
3441f106 BK |
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 | ||
4569a895 | 178 | public: |
3441f106 BK |
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) | |
4569a895 AT |
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; | |
4569a895 | 189 | It ins_it; |
4569a895 | 190 | for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) |
3441f106 | 191 | c.push(const_reference(ins_it->first)); |
4569a895 AT |
192 | |
193 | for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) | |
194 | { | |
195 | bool modified = false; | |
3441f106 | 196 | for (iterator it = c.begin(); !modified && it != c.end(); ++it) |
4569a895 AT |
197 | if (*it == ins_it->first) |
198 | { | |
199 | c.modify(it, m_mod_val); | |
4569a895 AT |
200 | modified = true; |
201 | } | |
202 | } | |
203 | } | |
204 | } | |
205 | ||
206 | private: | |
207 | const It m_ins_it_b; | |
208 | const It m_ins_it_e; | |
3441f106 | 209 | const value_type m_mod_val; |
4569a895 AT |
210 | }; |
211 | ||
4569a895 | 212 | template<typename It, class Cntnr> |
5e11f978 | 213 | class push_modify_functor<It, Cntnr, __gnu_pbds::test::native_pq_tag> |
4569a895 | 214 | { |
3441f106 BK |
215 | private: |
216 | typedef typename Cntnr::value_type value_type; | |
217 | typedef typename Cntnr::const_reference const_reference; | |
218 | ||
4569a895 | 219 | public: |
3441f106 BK |
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) | |
4569a895 AT |
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; | |
4569a895 | 230 | It ins_it; |
4569a895 | 231 | for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) |
3441f106 | 232 | c.push(const_reference(ins_it->first)); |
4569a895 AT |
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; | |
3441f106 | 241 | const value_type m_mod_val; |
4569a895 | 242 | }; |
4569a895 AT |
243 | } // namespace detail |
244 | ||
4569a895 | 245 | template<typename It> |
5e11f978 | 246 | class modify_test : private __gnu_pbds::test::detail::timing_test_base |
4569a895 AT |
247 | { |
248 | public: | |
3441f106 BK |
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 | { } | |
4569a895 AT |
253 | |
254 | template<typename Cntnr> | |
255 | void | |
3441f106 | 256 | operator()(Cntnr); |
4569a895 AT |
257 | |
258 | private: | |
3441f106 | 259 | modify_test(const modify_test&); |
4569a895 AT |
260 | |
261 | template<typename Cntnr> | |
262 | void | |
3441f106 BK |
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 | } | |
4569a895 | 270 | |
4569a895 | 271 | const It m_ins_b; |
4569a895 AT |
272 | const size_t m_ins_vn; |
273 | const size_t m_ins_vs; | |
274 | const size_t m_ins_vm; | |
4569a895 AT |
275 | const bool m_modify_up; |
276 | }; | |
277 | ||
3441f106 | 278 | template<typename It> |
4569a895 AT |
279 | template<typename Cntnr> |
280 | void | |
3441f106 BK |
281 | modify_test<It>:: |
282 | operator()(Cntnr) | |
4569a895 | 283 | { |
3441f106 BK |
284 | typedef typename Cntnr::value_type value_type; |
285 | typedef typename Cntnr::container_category container_category; | |
286 | typedef typename Cntnr::const_reference const_reference; | |
382a1351 BK |
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; | |
3441f106 BK |
290 | typedef xml_result_set_performance_formatter formatter_type; |
291 | formatter_type res_set_fmt(string_form<Cntnr>::name(), | |
292 | string_form<Cntnr>::desc()); | |
4569a895 | 293 | |
3441f106 BK |
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; | |
382a1351 | 297 | It b = m_ins_b; |
3441f106 BK |
298 | It e = m_ins_b; |
299 | std::advance(e, v); | |
4569a895 | 300 | |
382a1351 BK |
301 | psh_fnct psh_fn(b, e); |
302 | const double psh_res = timing_test_base::operator()(psh_fn); | |
4569a895 | 303 | |
3441f106 | 304 | value_type val = b->first; |
4569a895 AT |
305 | { |
306 | Cntnr mod_val_container; | |
3441f106 | 307 | for (It mod_val_it = b; mod_val_it != e; ++mod_val_it) |
4569a895 | 308 | { |
3441f106 BK |
309 | value_type pot = mod_val_it->first; |
310 | if (m_modify_up == mod_val_container.get_cmp_fn()(val, pot)) | |
311 | val = pot; | |
4569a895 AT |
312 | } |
313 | } | |
314 | ||
382a1351 BK |
315 | psh_mod_fnct psh_mod_fn(b, e, val); |
316 | const double psh_mod_res = timing_test_base::operator()(psh_mod_fn); | |
4569a895 | 317 | |
382a1351 BK |
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); | |
4569a895 AT |
321 | |
322 | res_set_fmt.add_res(v, effective_delta / v); | |
323 | } | |
324 | } | |
4569a895 | 325 | } // namespace test |
5e11f978 | 326 | } // namespace __gnu_pbds |
4569a895 | 327 | |
3441f106 | 328 | #endif |
4569a895 | 329 |