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