1 /******************************************************************************
2 ** $Header: svn+ssh://jmmcg@svn.code.sf.net/p/libjmmcg/code/trunk/libjmmcg/examples/intrusive_parallel.cpp 2358 2018-10-22 23:59:23Z jmmcg $
3 **
4 ** Copyright (c) 2011 by J.M.McGuiness, coder@hussar.me.uk
5 **
6 ** This library is free software; you can redistribute it and/or
7 ** modify it under the terms of the GNU Lesser General Public
8 ** License as published by the Free Software Foundation; either
9 ** version 2.1 of the License, or (at your option) any later version.
10 **
11 ** This library is distributed in the hope that it will be useful,
12 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ** Lesser General Public License for more details.
15 **
16 ** You should have received a copy of the GNU Lesser General Public
17 ** License along with this library; if not, write to the Free Software
18 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20
21 #include "stdafx.h"
22
23 #include "core/stats_output.hpp"
24
25 #define BOOST_TEST_MODULE libjmmcg_tests
26 #include <boost/test/included/unit_test.hpp>
27
28 #include "core/intrusive.hpp"
29 #include "core/thread_wrapper.hpp"
30
31 #include "core/ave_deviation_meter.hpp"
32
33 #include <chrono>
34 #include <set>
35
36 using namespace jmmcg;
37 using namespace ppd;
38
39 using lock_t=api_lock_traits<platform_api, heavyweight_threading>;
40 using timed_results_t=ave_deviation_meter<double>;
41
42 struct data final : public intrusive::node_details_itf<lock_t>, public sp_counter_type<typename intrusive::node_details_itf<lock_t>::atomic_ctr_t::value_type, lock_t> {
43 typedef sp_counter_type<intrusive::node_details_itf<lock_t>::atomic_ctr_t::value_type, lock_t> base_t;
44 typedef typename base_t::lock_traits lock_traits;
45 typedef typename base_t::atomic_ctr_t atomic_ctr_t;
46 typedef typename base_t::deleter_t deleter_t;
47
48 const int i;
49
50 explicit data(int j) noexcept(true)
51 : i(j) {}
52 ~data() noexcept(true) {}
53
54 tstring
55 to_string() const noexcept(false) {
56 tostringstream ss;
57 ss<<"i="<<i;
58 return ss.str();
59 }
60 };
61
62 template<unsigned short N, class Cont, template<class> class Ins>
63 struct add_thread final : public wrapper<platform_api, heavyweight_threading> {
64 typedef wrapper<platform_api, heavyweight_threading> base_t;
65 typedef Cont container_type;
66
67 const typename container_type::size_type num_elems;
68
69 std::vector<typename container_type::value_type> colln;
70 Ins<container_type> inserting;
71
72 add_thread(const typename container_type::size_type n, Ins<container_type> const &c) noexcept(true)
73 : base_t(), num_elems(n), inserting(c) {
74 colln.reserve(num_elems);
75 typename container_type::size_type elem=0;
76 std::generate_n(
77 std::back_inserter(colln),
78 num_elems,
79 [&elem, this]() -> typename container_type::value_type {
80 // Ensure that each element in the container is distinguishable.
81 return typename container_type::value_type(new typename container_type::value_type::value_type(N*num_elems+(++elem)));
82 }
83 );
84 }
85 ~add_thread() noexcept(true) {
86 this->delete_thread();
87 }
88
89 bool worker_fn(typename base_t::thread_context_t &) override {
90 std::copy_n(colln.begin(), num_elems, inserting);
91 return true;
92 }
93 };
94
95 template<class Cont>
96 struct pop_thread final : public wrapper<platform_api, heavyweight_threading> {
97 typedef wrapper<platform_api, heavyweight_threading> base_t;
98 typedef Cont container_type;
99
100 const typename container_type::size_type num_elems;
101
102 container_type &cont;
103
104 pop_thread(const typename container_type::size_type n, container_type &c) noexcept(true)
105 : base_t(), num_elems(n), cont(c) {
106 }
107 ~pop_thread() noexcept(true) {
108 this->delete_thread();
109 }
110
111 bool worker_fn(typename base_t::thread_context_t &) override {
112 for (typename container_type::size_type i=0; i<num_elems; ++i) {
113 assert(!cont.empty());
114 cont.pop_front();
115 }
116 return true;
117 }
118 };
119
120 BOOST_AUTO_TEST_SUITE(instrusive_parallel_tests)
121
122 BOOST_AUTO_TEST_SUITE(stack)
123
124 typedef intrusive::stack<data, lock_t> container_type;
125
126 BOOST_AUTO_TEST_SUITE(performance, *boost::unit_test::fixture<jmmcg::stats_to_csv::wrapper>(std::string("intrusive_parallel.csv")))
127
128 /**
129 \test <a href="./examples/intrusive_parallel.svg">Graph</a> of performance results for heavyweight intrusive-container operations.
130 ==========================================================================================
131 Results for 100*10000 repetitions.
132 */
133 BOOST_AUTO_TEST_CASE(push)
134 {
135 #ifdef JMMCG_PERFORMANCE_TESTS
136 const container_type::size_type num_tests=100;
137 #else
138 const container_type::size_type num_tests=1;
139 #endif
140
141 const std::pair<timed_results_t, bool> timed_results(compute_average_deviation<timed_results_t::value_type>(
142 2.0,
143 num_tests,
144 []() {
145 #ifdef JMMCG_PERFORMANCE_TESTS
146 const container_type::size_type num_items=10000;
147 #else
148 const container_type::size_type num_items=1000;
149 #endif
150 container_type s;
151 std::chrono::high_resolution_clock::time_point t1, t2;
152 {
153 // Add a shed-load of elements in parallel to an empty container_type.
154 add_thread<1, container_type, std::front_insert_iterator> thread1(num_items, std::front_inserter(s));
155 add_thread<2, container_type, std::front_insert_iterator> thread2(num_items, std::front_inserter(s));
156 add_thread<3, container_type, std::front_insert_iterator> thread3(num_items, std::front_inserter(s));
157 add_thread<4, container_type, std::front_insert_iterator> thread4(num_items, std::front_inserter(s));
158 {
159 t1=std::chrono::high_resolution_clock::now();
160 thread1.create_running();
161 thread2.create_running();
162 thread3.create_running();
163 thread4.create_running();
164 do {
165 api_threading_traits<platform_api, heavyweight_threading>::sleep(100);
166 } while (thread1.is_running() || thread2.is_running() || thread3.is_running() || thread4.is_running());
167 // Added all of the elements. Now make sure the container_type is correctly created.
168 t2=std::chrono::high_resolution_clock::now();
169 }
170 }
171 // Checks relating to the integrity of the container_type....
172 BOOST_CHECK(!s.empty());
173 BOOST_CHECK_EQUAL(s.size(), 4*num_items); // O.k. the atomic-counter based size() is correct.
174 BOOST_CHECK_EQUAL(s.size_n(), 4*num_items); // Woo-hoo so is the actual size of the list in nodes.
175 // Check that the reference count of each of the member-elements is correct.
176 for (auto const &iter : s) {
177 BOOST_CHECK_GE(iter->sp_count(), 1); // Must be greater than zero, for the reference in the list. The exact value will be related to the implementation of "for (...)" and the BOOST_... method.
178 BOOST_CHECK_EQUAL(iter->sp_count(), 3); // Check that there is no difference between the reference counts on each node, as they should all be the same.
179 }
180 {
181 std::set<int> check_list_integrity;
182 std::transform(
183 s.begin(),
184 s.end(),
185 std::inserter(check_list_integrity, check_list_integrity.begin()),
186 [](container_type::value_type const &v) {
187 return v->i;
188 }
189 );
190 BOOST_CHECK_EQUAL(check_list_integrity.size(), 4*num_items); // O.k. the correct number of elements were actually inserted, i.e. no incorrectly duplicated elements (each element is distinguishable via the address and the member "i").
191 }
192 return timed_results_t::value_type(4*1000000/static_cast<double>(std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count()))/num_items;
193 }
194 ));
195 #ifdef JMMCG_PERFORMANCE_TESTS
196 stats_to_csv::handle->stats<<timed_results.first.to_csv()<<std::flush;
197 BOOST_CHECK(!timed_results.second);
198 #endif
199 }
200
201 /**
202 \test <a href="./examples/intrusive_parallel.svg">Graph</a> of performance results for heavyweight intrusive-container operations.
203 ==========================================================================================
204 Results for 100*10000 repetitions.
205 */
206 BOOST_AUTO_TEST_CASE(pop)
207 {
208 #ifdef JMMCG_PERFORMANCE_TESTS
209 const container_type::size_type num_tests=100;
210 #else
211 const container_type::size_type num_tests=1;
212 #endif
213
214 const std::pair<timed_results_t, bool> timed_results(compute_average_deviation<timed_results_t::value_type>(
215 2.0,
216 num_tests,
217 []() {
218 #ifdef JMMCG_PERFORMANCE_TESTS
219 const container_type::size_type num_items=10000;
220 #else
221 const container_type::size_type num_items=1000;
222 #endif
223 container_type s;
224 container_type::size_type elem=0;
225 std::chrono::high_resolution_clock::time_point t1, t2;
226 std::generate_n(
227 std::front_inserter(s),
228 4*num_items,
229 [&elem]() {
230 // Ensure that each element in the container is distinguishable.
231 return container_type::value_type(new container_type::value_type::value_type(++elem));
232 }
233 );
234 {
235 // Delete all of the elements from the container_type in parallel.
236 pop_thread<container_type> thread1(num_items, s);
237 pop_thread<container_type> thread2(num_items, s);
238 pop_thread<container_type> thread3(num_items, s);
239 pop_thread<container_type> thread4(num_items, s);
240 {
241 t1=std::chrono::high_resolution_clock::now();
242 thread1.create_running();
243 thread2.create_running();
244 thread3.create_running();
245 thread4.create_running();
246 do {
247 api_threading_traits<platform_api, heavyweight_threading>::sleep(100);
248 } while (thread1.is_running() || thread2.is_running() || thread3.is_running() || thread4.is_running());
249 // container_type should now be empty.
250 t2=std::chrono::high_resolution_clock::now();
251 }
252 }
253 // Check the container_type is actually empty...
254 BOOST_CHECK(s.empty());
255 BOOST_CHECK_EQUAL(s.size(), container_type::size_type());
256 BOOST_CHECK_EQUAL(s.size_n(), container_type::size_type());
257 return timed_results_t::value_type(4*1000000/static_cast<double>(std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count()))/num_items;
258 }
259 ));
260 #ifdef JMMCG_PERFORMANCE_TESTS
261 stats_to_csv::handle->stats<<timed_results.first.to_csv()<<std::flush;
262 BOOST_CHECK(!timed_results.second);
263 #endif
264 }
265
266 BOOST_AUTO_TEST_SUITE_END()
267
268 BOOST_AUTO_TEST_SUITE(slist)
269
270 typedef intrusive::slist<data, lock_t> container_type;
271
272 /**
273 \test <a href="./examples/intrusive_parallel.svg">Graph</a> of performance results for heavyweight intrusive-container operations.
274 ==========================================================================================
275 Results for 100*10000 repetitions.
276 */
277 BOOST_AUTO_TEST_CASE(push_front)
278 {
279 #ifdef JMMCG_PERFORMANCE_TESTS
280 const container_type::size_type num_tests=100;
281 #else
282 const container_type::size_type num_tests=1;
283 #endif
284
285 const std::pair<timed_results_t, bool> timed_results(compute_average_deviation<timed_results_t::value_type>(
286 2.0,
287 num_tests,
288 []() {
289 #ifdef JMMCG_PERFORMANCE_TESTS
290 const container_type::size_type num_items=10000;
291 #else
292 const container_type::size_type num_items=1000;
293 #endif
294 container_type s;
295 std::chrono::high_resolution_clock::time_point t1, t2;
296 {
297 // Add a shed-load of elements in parallel to an empty container_type.
298 add_thread<1, container_type, std::front_insert_iterator> thread1(num_items, std::front_inserter(s));
299 add_thread<2, container_type, std::front_insert_iterator> thread2(num_items, std::front_inserter(s));
300 add_thread<3, container_type, std::front_insert_iterator> thread3(num_items, std::front_inserter(s));
301 add_thread<4, container_type, std::front_insert_iterator> thread4(num_items, std::front_inserter(s));
302 {
303 t1=std::chrono::high_resolution_clock::now();
304 thread1.create_running();
305 thread2.create_running();
306 thread3.create_running();
307 thread4.create_running();
308 do {
309 api_threading_traits<platform_api, heavyweight_threading>::sleep(100);
310 } while (thread1.is_running() || thread2.is_running() || thread3.is_running() || thread4.is_running());
311 // Added all of the elements. Now make sure the container_type is correctly created.
312 t2=std::chrono::high_resolution_clock::now();
313 }
314 }
315 // Checks relating to the integrity of the container_type....
316 BOOST_CHECK(!s.empty());
317 BOOST_CHECK_EQUAL(s.size(), 4*num_items); // O.k. the atomic-counter based size() is correct.
318 BOOST_CHECK_EQUAL(s.size_n(), 4*num_items); // Woo-hoo so is the actual size of the list in nodes.
319 // Check that the reference count of each of the member-elements is correct.
320 for (auto const &iter : s) {
321 BOOST_CHECK_GE(iter->sp_count(), 1); // Must be greater than zero, for the reference in the list. The exact value will be related to the implementation of "for (...)" and the BOOST_... method.
322 BOOST_CHECK_EQUAL(iter->sp_count(), 3); // Check that there is no difference between the reference counts on each node, as they should all be the same.
323 }
324 {
325 std::set<int> check_list_integrity;
326 std::transform(
327 s.begin(),
328 s.end(),
329 std::inserter(check_list_integrity, check_list_integrity.begin()),
330 [](container_type::value_type const &v) {
331 return v->i;
332 }
333 );
334 BOOST_CHECK_EQUAL(check_list_integrity.size(), 4*num_items); // O.k. the correct number of elements were actually inserted, i.e. no incorrectly duplicated elements (each element is distinguishable via the address and the member "i").
335 }
336 BOOST_CHECK(s.penultimate_reachable_from_prefront());
337 return timed_results_t::value_type(4*1000000/static_cast<double>(std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count()))/num_items;
338 }
339 ));
340 #ifdef JMMCG_PERFORMANCE_TESTS
341 stats_to_csv::handle->stats<<timed_results.first.to_csv()<<std::flush;
342 BOOST_CHECK(!timed_results.second);
343 #endif
344 }
345 /* TODO - race condition...
346 BOOST_AUTO_TEST_CASE(push_back)
347 {
348 const container_type::size_type num_items=1000;
349 container_type s;
350
351 {
352 // Add a shed-load of elements in parallel to an empty container_type.
353 add_thread<1, container_type, std::back_insert_iterator> thread1(num_items, std::back_inserter(s));
354 add_thread<2, container_type, std::back_insert_iterator> thread2(num_items, std::back_inserter(s));
355 add_thread<3, container_type, std::back_insert_iterator> thread3(num_items, std::back_inserter(s));
356 add_thread<4, container_type, std::back_insert_iterator> thread4(num_items, std::back_inserter(s));
357 {
358 thread1.create_running();
359 thread2.create_running();
360 thread3.create_running();
361 thread4.create_running();
362 do {
363 api_threading_traits<platform_api, heavyweight_threading>::sleep(100);
364 } while (thread1.is_running() || thread2.is_running() || thread3.is_running() || thread4.is_running());
365 // Added all of the elements. Now make sure the container_type is correctly created.
366 }
367 }
368 BOOST_CHECK(!s.empty());
369 BOOST_CHECK_EQUAL(s.size(), 4*num_items);
370 BOOST_CHECK_EQUAL(s.size_n(), 4*num_items);
371 // Check that the reference count of each of the member-elements is correct.
372 for (auto const &iter : s) {
373 BOOST_CHECK_GE(static_cast<typename container_type::value_type::value_type::atomic_ctr_t::value_type const &>(iter->get()), 1); // Must be greater than zero, for the reference in the list. The exact value will be related to the implementation of "for (...)" and the BOOST_... method.
374 BOOST_CHECK_EQUAL(static_cast<typename container_type::value_type::value_type::atomic_ctr_t::value_type const &>(iter->get()), 3); // Check that there is no difference between the reference counts on each node, as they should all be the same.
375 }
376 {
377 std::set<int> check_list_integrity;
378 std::transform(
379 s.begin(),
380 s.end(),
381 std::inserter(check_list_integrity, check_list_integrity.begin()),
382 [](container_type::value_type const &v) {
383 return v->i;
384 }
385 );
386 BOOST_CHECK_EQUAL(check_list_integrity.size(), 4*num_items); // O.k. the correct number of elements were actually inserted, i.e. no incorrectly duplicated elements (each element is distinguishable via the address and the member "i").
387 }
388 BOOST_CHECK(s.penultimate_reachable_from_prefront());
389 }
390 */
391 /**
392 \test <a href="./examples/intrusive_parallel.svg">Graph</a> of performance results for heavyweight intrusive-container operations.
393 ==========================================================================================
394 Results for 100*10000 repetitions.
395 */
396 BOOST_AUTO_TEST_CASE(pop_front)
397 {
398 #ifdef JMMCG_PERFORMANCE_TESTS
399 const container_type::size_type num_tests=100;
400 #else
401 const container_type::size_type num_tests=1;
402 #endif
403
404 const std::pair<timed_results_t, bool> timed_results(compute_average_deviation<timed_results_t::value_type>(
405 2.0,
406 num_tests,
407 []() {
408 #ifdef JMMCG_PERFORMANCE_TESTS
409 const container_type::size_type num_items=10000;
410 #else
411 const container_type::size_type num_items=1000;
412 #endif
413 container_type s;
414 container_type::size_type elem=0;
415 std::chrono::high_resolution_clock::time_point t1, t2;
416 std::generate_n(
417 std::front_inserter(s),
418 4*num_items,
419 [&elem]() -> container_type::value_type {
420 // Ensure that each element in the container is distinguishable.
421 return container_type::value_type(new container_type::value_type::value_type(++elem));
422 }
423 );
424 {
425 // Delete all of the elements from the container_type in parallel.
426 pop_thread<container_type> thread1(num_items, s);
427 pop_thread<container_type> thread2(num_items, s);
428 pop_thread<container_type> thread3(num_items, s);
429 pop_thread<container_type> thread4(num_items, s);
430 {
431 t1=std::chrono::high_resolution_clock::now();
432 thread1.create_running();
433 thread2.create_running();
434 thread3.create_running();
435 thread4.create_running();
436 do {
437 api_threading_traits<platform_api, heavyweight_threading>::sleep(100);
438 } while (thread1.is_running() || thread2.is_running() || thread3.is_running() || thread4.is_running());
439 // container_type should now be empty.
440 t2=std::chrono::high_resolution_clock::now();
441 }
442 }
443 // Check the container_type is actually empty...
444 BOOST_CHECK(s.empty());
445 BOOST_CHECK_EQUAL(s.size(), container_type::size_type());
446 BOOST_CHECK_EQUAL(s.size_n(), container_type::size_type());
447 return timed_results_t::value_type(4*1000000/static_cast<double>(std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count()))/num_items;
448 }
449 ));
450 #ifdef JMMCG_PERFORMANCE_TESTS
451 stats_to_csv::handle->stats<<timed_results.first.to_csv()<<std::flush;
452 BOOST_CHECK(!timed_results.second);
453 #endif
454 }
455
456 BOOST_AUTO_TEST_SUITE_END()
457
458 BOOST_AUTO_TEST_SUITE_END()
459
460 BOOST_AUTO_TEST_SUITE_END()