1/*
2 Copyright (c) 2005-2019 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15*/
16
17#define HARNESS_DEFAULT_MIN_THREADS 0
18#define HARNESS_DEFAULT_MAX_THREADS 4
19
20#define __TBB_EXTRA_DEBUG 1 // for concurrent_hash_map
21#include "tbb/combinable.h"
22#include "tbb/task_scheduler_init.h"
23#include "tbb/parallel_for.h"
24#include "tbb/blocked_range.h"
25#include "tbb/tick_count.h"
26#include "tbb/tbb_allocator.h"
27#include "tbb/tbb_thread.h"
28
29#include <cstring>
30#include <vector>
31#include <utility>
32
33#include "harness_assert.h"
34#include "harness.h"
35#include "test_container_move_support.h"
36
37#if __TBB_GCC_WARNING_SUPPRESSION_PRESENT
38#pragma GCC diagnostic ignored "-Wuninitialized"
39#endif
40
41static tbb::atomic<int> construction_counter;
42static tbb::atomic<int> destruction_counter;
43
44const int REPETITIONS = 10;
45const int N = 100000;
46const double EXPECTED_SUM = (REPETITIONS + 1) * N;
47
48//
49// A minimal class
50// Define: default and copy constructor, and allow implicit operator&
51// also operator=
52//
53
54class minimal {
55private:
56 int my_value;
57public:
58 minimal(int val=0) : my_value(val) { ++construction_counter; }
59 minimal( const minimal &m ) : my_value(m.my_value) { ++construction_counter; }
60 minimal& operator=(const minimal& other) { my_value = other.my_value; return *this; }
61 minimal& operator+=(const minimal& other) { my_value += other.my_value; return *this; }
62 operator int() const { return my_value; }
63 ~minimal() { ++destruction_counter; }
64 void set_value( const int i ) { my_value = i; }
65 int value( ) const { return my_value; }
66};
67
68//// functors for initialization and combine
69
70template <typename T>
71struct FunctorAddFinit {
72 T operator()() { return 0; }
73};
74
75template <typename T>
76struct FunctorAddFinit7 {
77 T operator()() { return 7; }
78};
79
80template <typename T>
81struct FunctorAddCombine {
82 T operator()(T left, T right ) const {
83 return left + right;
84 }
85};
86
87template <typename T>
88struct FunctorAddCombineRef {
89 T operator()(const T& left, const T& right ) const {
90 return left + right;
91 }
92};
93
94template <typename T>
95T my_combine( T left, T right) { return left + right; }
96
97template <typename T>
98T my_combine_ref( const T &left, const T &right) { return left + right; }
99
100template <typename T>
101class CombineEachHelper {
102public:
103 CombineEachHelper(T& _result) : my_result(_result) {}
104 void operator()(const T& new_bit) { my_result += new_bit; }
105 CombineEachHelper& operator=(const CombineEachHelper& other) {
106 my_result = other;
107 return *this;
108 }
109private:
110 T& my_result;
111};
112
113template <typename T>
114class CombineEachHelperCnt {
115public:
116 CombineEachHelperCnt(T& _result, int& _nbuckets) : my_result(_result), nBuckets(_nbuckets) {}
117 void operator()(const T& new_bit) { my_result += new_bit; ++nBuckets; }
118 CombineEachHelperCnt& operator=(const CombineEachHelperCnt& other) {
119 my_result = other.my_result;
120 nBuckets = other.nBuckets;
121 return *this;
122 }
123private:
124 T& my_result;
125 int& nBuckets;
126};
127
128template <typename T>
129class CombineEachVectorHelper {
130public:
131 typedef std::vector<T, tbb::tbb_allocator<T> > ContainerType;
132 CombineEachVectorHelper(T& _result) : my_result(_result) { }
133 void operator()(const ContainerType& new_bit) {
134 for(typename ContainerType::const_iterator ci = new_bit.begin(); ci != new_bit.end(); ++ci) {
135 my_result += *ci;
136 }
137 }
138 CombineEachVectorHelper& operator=(const CombineEachVectorHelper& other) {
139 my_result=other.my_result;
140 return *this;
141 }
142
143private:
144 T& my_result;
145};
146
147//// end functors
148
149// parallel body with a test for first access
150template <typename T>
151class ParallelScalarBody: NoAssign {
152
153 tbb::combinable<T> &sums;
154
155public:
156
157 ParallelScalarBody ( tbb::combinable<T> &_sums ) : sums(_sums) { }
158
159 void operator()( const tbb::blocked_range<int> &r ) const {
160 for (int i = r.begin(); i != r.end(); ++i) {
161 bool was_there;
162 T& my_local = sums.local(was_there);
163 if(!was_there) my_local = 0;
164 my_local += 1 ;
165 }
166 }
167
168};
169
170// parallel body with no test for first access
171template <typename T>
172class ParallelScalarBodyNoInit: NoAssign {
173
174 tbb::combinable<T> &sums;
175
176public:
177
178 ParallelScalarBodyNoInit ( tbb::combinable<T> &_sums ) : sums(_sums) { }
179
180 void operator()( const tbb::blocked_range<int> &r ) const {
181 for (int i = r.begin(); i != r.end(); ++i) {
182 sums.local() += 1 ;
183 }
184 }
185
186};
187
188template< typename T >
189void RunParallelScalarTests(const char *test_name) {
190
191 tbb::task_scheduler_init init(tbb::task_scheduler_init::deferred);
192 for (int p = MinThread; p <= MaxThread; ++p) {
193
194 if (p == 0) continue;
195 REMARK(" Testing parallel %s on %d thread(s)...\n", test_name, p);
196 init.initialize(p);
197
198 tbb::tick_count t0;
199 T combine_sum(0);
200 T combine_ref_sum(0);
201 T combine_finit_sum(0);
202 T combine_each_sum(0);
203 T copy_construct_sum(0);
204 T copy_assign_sum(0);
205#if __TBB_ETS_USE_CPP11
206 T move_construct_sum(0);
207 T move_assign_sum(0);
208#endif
209 for (int t = -1; t < REPETITIONS; ++t) {
210 if (Verbose && t == 0) t0 = tbb::tick_count::now();
211
212 // test uninitialized parallel combinable
213 tbb::combinable<T> sums;
214 tbb::parallel_for( tbb::blocked_range<int>( 0, N, 10000 ), ParallelScalarBody<T>( sums ) );
215 combine_sum += sums.combine(my_combine<T>);
216 combine_ref_sum += sums.combine(my_combine_ref<T>);
217
218 // test parallel combinable preinitialized with a functor that returns 0
219 FunctorAddFinit<T> my_finit_decl;
220 tbb::combinable<T> finit_combinable(my_finit_decl);
221 tbb::parallel_for( tbb::blocked_range<int>( 0, N, 10000 ), ParallelScalarBodyNoInit<T>( finit_combinable ) );
222 combine_finit_sum += finit_combinable.combine(my_combine<T>);
223
224 // test another way of combining the elements using CombineEachHelper<T> functor
225 CombineEachHelper<T> my_helper(combine_each_sum);
226 sums.combine_each(my_helper);
227
228 // test copy constructor for parallel combinable
229 tbb::combinable<T> copy_constructed(sums);
230 copy_construct_sum += copy_constructed.combine(my_combine<T>);
231
232 // test copy assignment for uninitialized parallel combinable
233 tbb::combinable<T> assigned;
234 assigned = sums;
235 copy_assign_sum += assigned.combine(my_combine<T>);
236
237#if __TBB_ETS_USE_CPP11
238 // test move constructor for parallel combinable
239 tbb::combinable<T> moved1(std::move(sums));
240 move_construct_sum += moved1.combine(my_combine<T>);
241
242 // test move assignment for uninitialized parallel combinable
243 tbb::combinable<T> moved2;
244 moved2=std::move(finit_combinable);
245 move_assign_sum += moved2.combine(my_combine<T>);
246#endif
247 }
248 // Here and below comparison for equality of float numbers succeeds
249 // as the rounding error doesn't accumulate and doesn't affect the comparison
250 ASSERT( EXPECTED_SUM == combine_sum, NULL);
251 ASSERT( EXPECTED_SUM == combine_ref_sum, NULL);
252 ASSERT( EXPECTED_SUM == combine_finit_sum, NULL);
253 ASSERT( EXPECTED_SUM == combine_each_sum, NULL);
254 ASSERT( EXPECTED_SUM == copy_construct_sum, NULL);
255 ASSERT( EXPECTED_SUM == copy_assign_sum, NULL);
256#if __TBB_ETS_USE_CPP11
257 ASSERT( EXPECTED_SUM == move_construct_sum, NULL);
258 ASSERT( EXPECTED_SUM == move_assign_sum, NULL);
259#endif
260 REMARK(" done parallel %s, %d, %g, %g\n", test_name, p, static_cast<double>(combine_sum),
261 ( tbb::tick_count::now() - t0).seconds());
262 init.terminate();
263 }
264}
265
266template <typename T>
267class ParallelVectorForBody: NoAssign {
268
269 tbb::combinable< std::vector<T, tbb::tbb_allocator<T> > > &locals;
270
271public:
272
273 ParallelVectorForBody ( tbb::combinable< std::vector<T, tbb::tbb_allocator<T> > > &_locals ) : locals(_locals) { }
274
275 void operator()( const tbb::blocked_range<int> &r ) const {
276 T one = 1;
277
278 for (int i = r.begin(); i < r.end(); ++i) {
279 locals.local().push_back( one );
280 }
281 }
282
283};
284
285template< typename T >
286void RunParallelVectorTests(const char *test_name) {
287
288 tbb::task_scheduler_init init(tbb::task_scheduler_init::deferred);
289
290 typedef std::vector<T, tbb::tbb_allocator<T> > ContainerType;
291
292 for (int p = MinThread; p <= MaxThread; ++p) {
293
294 if (p == 0) continue;
295 REMARK(" Testing parallel %s on %d thread(s)... \n", test_name, p);
296 init.initialize(p);
297
298 tbb::tick_count t0;
299 T defaultConstructed_sum(0);
300 T copyConstructed_sum(0);
301 T copyAssigned_sum(0);
302#if __TBB_ETS_USE_CPP11
303 T moveConstructed_sum(0);
304 T moveAssigned_sum(0);
305#endif
306 for (int t = -1; t < REPETITIONS; ++t) {
307 if (Verbose && t == 0) t0 = tbb::tick_count::now();
308
309 typedef typename tbb::combinable< ContainerType > CombinableType;
310
311 // test uninitialized parallel combinable
312 CombinableType vs;
313 tbb::parallel_for( tbb::blocked_range<int> (0, N, 10000), ParallelVectorForBody<T>( vs ) );
314 CombineEachVectorHelper<T> MyCombineEach(defaultConstructed_sum);
315 vs.combine_each(MyCombineEach); // combine_each sums all elements of each vector into the result
316
317 // test copy constructor for parallel combinable with vectors
318 CombinableType vs2(vs);
319 CombineEachVectorHelper<T> MyCombineEach2(copyConstructed_sum);
320 vs2.combine_each(MyCombineEach2);
321
322 // test copy assignment for uninitialized parallel combinable with vectors
323 CombinableType vs3;
324 vs3 = vs;
325 CombineEachVectorHelper<T> MyCombineEach3(copyAssigned_sum);
326 vs3.combine_each(MyCombineEach3);
327
328#if __TBB_ETS_USE_CPP11
329 // test move constructor for parallel combinable with vectors
330 CombinableType vs4(std::move(vs2));
331 CombineEachVectorHelper<T> MyCombineEach4(moveConstructed_sum);
332 vs4.combine_each(MyCombineEach4);
333
334 // test move assignment for uninitialized parallel combinable with vectors
335 vs4=std::move(vs3);
336 CombineEachVectorHelper<T> MyCombineEach5(moveAssigned_sum);
337 vs4.combine_each(MyCombineEach5);
338#endif
339 }
340
341 double ResultValue = defaultConstructed_sum;
342 ASSERT( EXPECTED_SUM == ResultValue, NULL);
343 ResultValue = copyConstructed_sum;
344 ASSERT( EXPECTED_SUM == ResultValue, NULL);
345 ResultValue = copyAssigned_sum;
346 ASSERT( EXPECTED_SUM == ResultValue, NULL);
347#if __TBB_ETS_USE_CPP11
348 ResultValue = moveConstructed_sum;
349 ASSERT( EXPECTED_SUM == ResultValue, NULL);
350 ResultValue = moveAssigned_sum;
351 ASSERT( EXPECTED_SUM == ResultValue, NULL);
352#endif
353 REMARK(" done parallel %s, %d, %g, %g\n", test_name, p, ResultValue, ( tbb::tick_count::now() - t0).seconds());
354 init.terminate();
355 }
356}
357
358void
359RunParallelTests() {
360 REMARK("Running RunParallelTests\n");
361 RunParallelScalarTests<int>("int");
362 RunParallelScalarTests<double>("double");
363 RunParallelScalarTests<minimal>("minimal");
364 RunParallelVectorTests<int>("std::vector<int, tbb::tbb_allocator<int> >");
365 RunParallelVectorTests<double>("std::vector<double, tbb::tbb_allocator<double> >");
366}
367
368template <typename T>
369void
370RunAssignmentAndCopyConstructorTest(const char *test_name) {
371 REMARK(" Testing assignment and copy construction for combinable<%s>...\n", test_name);
372
373 // test creation with finit function (combine returns finit return value if no threads have created locals)
374 FunctorAddFinit7<T> my_finit7_decl;
375 tbb::combinable<T> create1(my_finit7_decl);
376 ASSERT(7 == create1.combine(my_combine<T>), "Unexpected combine result for combinable object preinitialized with functor");
377
378 // test copy construction with function initializer
379 tbb::combinable<T> copy1(create1);
380 ASSERT(7 == copy1.combine(my_combine<T>), "Unexpected combine result for copy-constructed combinable object");
381
382 // test copy assignment with function initializer
383 FunctorAddFinit<T> my_finit_decl;
384 tbb::combinable<T> assign1(my_finit_decl);
385 assign1 = create1;
386 ASSERT(7 == assign1.combine(my_combine<T>), "Unexpected combine result for copy-assigned combinable object");
387
388#if __TBB_ETS_USE_CPP11
389 // test move construction with function initializer
390 tbb::combinable<T> move1(std::move(create1));
391 ASSERT(7 == move1.combine(my_combine<T>), "Unexpected combine result for move-constructed combinable object");
392
393 // test move assignment with function initializer
394 tbb::combinable<T> move2;
395 move2=std::move(copy1);
396 ASSERT(7 == move2.combine(my_combine<T>), "Unexpected combine result for move-assigned combinable object");
397#endif
398
399 REMARK(" done\n");
400
401}
402
403void
404RunAssignmentAndCopyConstructorTests() {
405 REMARK("Running assignment and copy constructor tests:\n");
406 RunAssignmentAndCopyConstructorTest<int>("int");
407 RunAssignmentAndCopyConstructorTest<double>("double");
408 RunAssignmentAndCopyConstructorTest<minimal>("minimal");
409}
410
411void
412RunMoveSemanticsForStateTrackableObjectTest() {
413 REMARK("Testing move assignment and move construction for combinable<Harness::StateTrackable>...\n");
414
415 tbb::combinable< Harness::StateTrackable<true> > create1;
416 ASSERT(create1.local().state == Harness::StateTrackable<true>::DefaultInitialized,
417 "Unexpected value in default combinable object");
418
419 // Copy constructing of the new combinable causes copying of stored values
420 tbb::combinable< Harness::StateTrackable<true> > copy1(create1);
421 ASSERT(copy1.local().state == Harness::StateTrackable<true>::CopyInitialized,
422 "Unexpected value in copy-constructed combinable object");
423
424 // Copy assignment also causes copying of stored values
425 tbb::combinable< Harness::StateTrackable<true> > copy2;
426 ASSERT(copy2.local().state == Harness::StateTrackable<true>::DefaultInitialized,
427 "Unexpected value in default combinable object");
428 copy2=create1;
429 ASSERT(copy2.local().state == Harness::StateTrackable<true>::CopyInitialized,
430 "Unexpected value in copy-assigned combinable object");
431
432#if __TBB_ETS_USE_CPP11
433 // Store some marked values in the initial combinable object
434 create1.local().state = Harness::StateTrackableBase::Unspecified;
435
436 // Move constructing of the new combinable must not cause copying of stored values
437 tbb::combinable< Harness::StateTrackable<true> > move1(std::move(create1));
438 ASSERT(move1.local().state == Harness::StateTrackableBase::Unspecified, "Unexpected value in move-constructed combinable object");
439
440 // Move assignment must not cause copying of stored values
441 copy1=std::move(move1);
442 ASSERT(copy1.local().state == Harness::StateTrackableBase::Unspecified, "Unexpected value in move-assigned combinable object");
443
444 // Make the stored values valid again in order to delete StateTrackable object correctly
445 copy1.local().state = Harness::StateTrackable<true>::MoveAssigned;
446#endif
447
448 REMARK("done\n");
449}
450
451#include "harness_barrier.h"
452
453Harness::SpinBarrier sBarrier;
454
455struct Body : NoAssign {
456 tbb::combinable<int>* locals;
457 const int nthread;
458 const int nIters;
459 Body( int nthread_, int niters_ ) : nthread(nthread_), nIters(niters_) { sBarrier.initialize(nthread_); }
460
461 void operator()(int thread_id ) const {
462 bool existed;
463 sBarrier.wait();
464 for(int i = 0; i < nIters; ++i ) {
465 existed = thread_id & 1;
466 int oldval = locals->local(existed);
467 ASSERT(existed == (i > 0), "Error on first reference");
468 ASSERT(!existed || (oldval == thread_id), "Error on fetched value");
469 existed = thread_id & 1;
470 locals->local(existed) = thread_id;
471 ASSERT(existed, "Error on assignment");
472 }
473 }
474};
475
476void
477TestLocalAllocations( int nthread ) {
478 ASSERT(nthread > 0, "nthread must be positive");
479#define NITERATIONS 1000
480 Body myBody(nthread, NITERATIONS);
481 tbb::combinable<int> myCombinable;
482 myBody.locals = &myCombinable;
483
484 NativeParallelFor( nthread, myBody );
485
486 int mySum = 0;
487 int mySlots = 0;
488 CombineEachHelperCnt<int> myCountCombine(mySum, mySlots);
489 myCombinable.combine_each(myCountCombine);
490
491 ASSERT(nthread == mySlots, "Incorrect number of slots");
492 ASSERT(mySum == (nthread - 1) * nthread / 2, "Incorrect values in result");
493}
494
495void
496RunLocalAllocationsTests() {
497 REMARK("Testing local() allocations\n");
498 for(int i = 1 <= MinThread ? MinThread : 1; i <= MaxThread; ++i) {
499 REMARK(" Testing local() allocation with nthreads=%d...\n", i);
500 for(int j = 0; j < 100; ++j) {
501 TestLocalAllocations(i);
502 }
503 REMARK(" done\n");
504 }
505}
506
507int TestMain () {
508 if (MaxThread > 0) {
509 RunParallelTests();
510 }
511 RunAssignmentAndCopyConstructorTests();
512 RunMoveSemanticsForStateTrackableObjectTest();
513 RunLocalAllocationsTests();
514 return Harness::Done;
515}
516
517