1 /*
2 Copyright (c) 2005-2022 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 #ifndef __TBB_test_common_parallel_for_each_common_H
18 #define __TBB_test_common_parallel_for_each_common_H
19
20 #include "config.h"
21
22 #include "oneapi/tbb/parallel_for_each.h"
23 #include "oneapi/tbb/global_control.h"
24
25 #include "test.h"
26 #include "config.h"
27 #include "utils.h"
28 #include "utils_report.h"
29 #include "utils_concurrency_limit.h"
30 #include "iterator.h"
31 #include "cpu_usertime.h"
32
33 #include <vector>
34 #include <forward_list>
35
36 constexpr std::size_t depths_nubmer = 20;
37 static std::atomic<int> g_values_counter;
38
39 class value_t : public utils::NoAfterlife {
40 size_t x;
41 value_t& operator=(const value_t&);
42 public:
value_t(size_t xx)43 value_t(size_t xx) : x(xx) { ++g_values_counter; }
value_t(const value_t & v)44 value_t(const value_t& v) : utils::NoAfterlife(v), x(v.x) { ++g_values_counter; }
value_t(value_t && v)45 value_t(value_t&& v) : x(v.x) { ++g_values_counter; }
~value_t()46 ~value_t() { --g_values_counter; }
value()47 size_t value() const volatile { return x; }
48 };
49
50 static size_t g_tasks_expected = 0;
51 static std::atomic<size_t> g_tasks_observed;
52
FindNumOfTasks(size_t max_depth)53 size_t FindNumOfTasks(size_t max_depth) {
54 if( max_depth == 0 )
55 return 1;
56 return max_depth * FindNumOfTasks( max_depth - 1 ) + 1;
57 }
58
59 //! Simplest form of the parallel_for_each functor object.
60 struct FakeTaskGeneratorBody {
61 //! The simplest form of the function call operator
62 /** It does not allow adding new tasks during its execution. **/
operatorFakeTaskGeneratorBody63 void operator()(value_t depth) const {
64 g_tasks_observed += FindNumOfTasks(depth.value());
65 }
66 };
67
68 /** Work item is passed by reference here. **/
69 struct FakeTaskGeneratorBody_RefVersion {
operatorFakeTaskGeneratorBody_RefVersion70 void operator()(value_t& depth) const {
71 g_tasks_observed += FindNumOfTasks(depth.value());
72 }
73 };
74
75 /** Work item is passed by reference to const here. **/
76 struct FakeTaskGeneratorBody_ConstRefVersion {
operatorFakeTaskGeneratorBody_ConstRefVersion77 void operator()(const value_t& depth) const {
78 g_tasks_observed += FindNumOfTasks(depth.value());
79 }
80 };
81
82 /** Work item is passed by reference to volatile here. **/
83 struct FakeTaskGeneratorBody_VolatileRefVersion {
operatorFakeTaskGeneratorBody_VolatileRefVersion84 void operator()(volatile value_t& depth, tbb::feeder<value_t>&) const {
85 g_tasks_observed += FindNumOfTasks(depth.value());
86 }
87 };
88
89 /** Work item is passed by rvalue reference here. **/
90 struct FakeTaskGeneratorBody_RvalueRefVersion {
operatorFakeTaskGeneratorBody_RvalueRefVersion91 void operator()(value_t&& depth ) const {
92 g_tasks_observed += FindNumOfTasks(depth.value());
93 }
94 };
95
do_work(const value_t & depth,tbb::feeder<value_t> & feeder)96 void do_work(const value_t& depth, tbb::feeder<value_t>& feeder) {
97 ++g_tasks_observed;
98 value_t new_value(depth.value()-1);
99 for(size_t i = 0; i < depth.value(); ++i) {
100 if (i%2) feeder.add( new_value ); // pass lvalue
101 else feeder.add( value_t(depth.value()-1) ); // pass rvalue
102 }
103 }
104
105 //! Standard form of the parallel_for_each functor object.
106 /** Allows adding new work items on the fly. **/
107 struct TaskGeneratorBody {
108 //! This form of the function call operator can be used when the body needs to add more work during the processing
operatorTaskGeneratorBody109 void operator()(value_t depth, tbb::feeder<value_t>& feeder) const {
110 do_work(depth, feeder);
111 }
112 private:
113 // Assert that parallel_for_each does not ever access body constructors
TaskGeneratorBodyTaskGeneratorBody114 TaskGeneratorBody () {}
115 TaskGeneratorBody (const TaskGeneratorBody&);
116 // These functions need access to the default constructor
117 template<class Body, class Iterator> friend void TestBody(size_t);
118 template<class Body, class Iterator> friend void TestBodyMove(size_t);
119 template<class Body, class Iterator> friend void TestBodyWithMove(size_t);
120 };
121
122 /** Work item is passed by reference here. **/
123 struct TaskGeneratorBody_RefVersion {
operatorTaskGeneratorBody_RefVersion124 void operator()(value_t& depth, tbb::feeder<value_t>& feeder) const {
125 do_work(depth, feeder);
126 }
127 };
128
129 /** Work item is passed as const here. Compilers must ignore the const qualifier. **/
130 struct TaskGeneratorBody_ConstVersion {
operatorTaskGeneratorBody_ConstVersion131 void operator()(const value_t depth, tbb::feeder<value_t>& feeder) const {
132 do_work(depth, feeder);
133 }
134 };
135
136 /** Work item is passed by reference to const here. **/
137 struct TaskGeneratorBody_ConstRefVersion {
operatorTaskGeneratorBody_ConstRefVersion138 void operator()(const value_t& depth, tbb::feeder<value_t>& feeder) const {
139 do_work(depth, feeder);
140 }
141 };
142
143 /** Work item is passed by reference to volatile here. **/
144 struct TaskGeneratorBody_VolatileRefVersion {
operatorTaskGeneratorBody_VolatileRefVersion145 void operator()(volatile value_t& depth, tbb::feeder<value_t>& feeder) const {
146 do_work(const_cast<value_t&>(depth), feeder);
147 }
148 };
149
150 /** Work item is passed by reference to const volatile here. **/
151 struct TaskGeneratorBody_ConstVolatileRefVersion {
operatorTaskGeneratorBody_ConstVolatileRefVersion152 void operator()(const volatile value_t& depth, tbb::feeder<value_t>& feeder) const {
153 do_work(const_cast<value_t&>(depth), feeder);
154 }
155 };
156
157 /** Work item is passed by rvalue reference here. **/
158 struct TaskGeneratorBody_RvalueRefVersion {
operatorTaskGeneratorBody_RvalueRefVersion159 void operator()(value_t&& depth, tbb::feeder<value_t>& feeder) const {
160 do_work(depth, feeder);
161 }
162 };
163
164 static value_t g_depths[depths_nubmer] = {0, 1, 2, 3, 4, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2};
165
166 template<class Body, class Iterator>
TestBodyMove(size_t depth)167 void TestBodyMove(size_t depth) {
168 typedef typename std::iterator_traits<Iterator>::value_type value_type;
169 value_type a_depths[depths_nubmer] = {0, 1, 2, 3, 4, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2};
170 Body body;
171 typedef std::move_iterator<Iterator> MoveIterator;
172 MoveIterator mbegin(Iterator{a_depths});
173 MoveIterator mend(Iterator{a_depths + depth});
174 g_tasks_observed = 0;
175 tbb::parallel_for_each(mbegin, mend, body);
176 REQUIRE (g_tasks_observed == g_tasks_expected);
177 }
178
179 template<class Body, class Iterator>
TestBody(size_t depth)180 void TestBody(size_t depth) {
181 typedef typename std::iterator_traits<Iterator>::value_type value_type;
182 value_type a_depths[depths_nubmer] = {0, 1, 2, 3, 4, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2};
183 Body body;
184 Iterator begin(a_depths);
185 Iterator end(a_depths + depth);
186 g_tasks_observed = 0;
187 tbb::parallel_for_each(begin, end, body);
188 REQUIRE (g_tasks_observed == g_tasks_expected);
189 }
190
191 template<class Body, class Iterator>
TestBodyWithMove(size_t depth)192 void TestBodyWithMove(size_t depth) {
193 TestBody<Body, Iterator>(depth);
194 TestBodyMove<Body, Iterator>(depth);
195 }
196
197 template<class Iterator>
TestIterator_Common(size_t depth)198 void TestIterator_Common(size_t depth) {
199 TestBodyWithMove<FakeTaskGeneratorBody, Iterator>(depth);
200 TestBodyWithMove<FakeTaskGeneratorBody_ConstRefVersion, Iterator>(depth);
201 TestBodyWithMove<TaskGeneratorBody, Iterator>(depth);
202 TestBodyWithMove<TaskGeneratorBody_ConstVersion, Iterator>(depth);
203 TestBodyWithMove<TaskGeneratorBody_ConstRefVersion, Iterator>(depth);
204 }
205
206 template<class Iterator>
TestIterator_Const(size_t depth)207 void TestIterator_Const(size_t depth) {
208 TestIterator_Common<Iterator>(depth);
209 TestBody<TaskGeneratorBody_ConstVolatileRefVersion, Iterator>(depth);
210 }
211
212 #if __TBB_CPP14_GENERIC_LAMBDAS_PRESENT
213 template<class Iterator, class GenericBody>
TestGenericLambda(size_t depth,GenericBody body)214 void TestGenericLambda(size_t depth, GenericBody body) {
215 typedef typename std::iterator_traits<Iterator>::value_type value_type;
216 value_type a_depths[depths_nubmer] = {0, 1, 2, 3, 4, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2};
217
218 Iterator begin(a_depths);
219 Iterator end(a_depths + depth);
220 g_tasks_observed = 0;
221 tbb::parallel_for_each(begin, end, body);
222 REQUIRE (g_tasks_observed == g_tasks_expected);
223 }
224
225 template <class Iterator, class GenericBody>
TestGenericLambdaMove(size_t depth,GenericBody body)226 void TestGenericLambdaMove(size_t depth, GenericBody body) {
227 typedef typename std::iterator_traits<Iterator>::value_type value_type;
228 value_type a_depths[depths_nubmer] = {0, 1, 2, 3, 4, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 0, 1, 2};
229
230 typedef std::move_iterator<Iterator> MoveIterator;
231 Iterator begin(a_depths);
232 Iterator end(a_depths + depth);
233 MoveIterator mbegin = std::make_move_iterator(begin);
234 MoveIterator mend = std::make_move_iterator(end);
235 g_tasks_observed = 0;
236 tbb::parallel_for_each(mbegin, mend, body);
237 REQUIRE (g_tasks_observed == g_tasks_expected);
238 }
239
240 template <class Iterator, class GenericBody>
TestGenericLambdaWithMove(size_t depth,GenericBody body)241 void TestGenericLambdaWithMove(size_t depth, GenericBody body) {
242 TestGenericLambda<Iterator>(depth, body);
243 TestGenericLambdaMove<Iterator>(depth, body);
244 }
245
246 template<class Iterator>
TestGenericLambdasCommon(size_t depth)247 void TestGenericLambdasCommon(size_t depth) {
248 TestGenericLambdaWithMove<Iterator>(depth, [](auto item){g_tasks_observed += FindNumOfTasks(item.value());});
249 TestGenericLambdaWithMove<Iterator>(depth, [](const auto item){g_tasks_observed += FindNumOfTasks(item.value());});
250 TestGenericLambda<Iterator>(depth, [](volatile auto& item){g_tasks_observed += FindNumOfTasks(item.value());});
251 TestGenericLambda<Iterator>(depth, [](const volatile auto& item){g_tasks_observed += FindNumOfTasks(item.value());});
252 TestGenericLambda<Iterator>(depth, [](auto& item){g_tasks_observed += FindNumOfTasks(item.value());});
253 TestGenericLambdaWithMove<Iterator>(depth, [](const auto& item){g_tasks_observed += FindNumOfTasks(item.value());});
254 TestGenericLambdaWithMove<Iterator>(depth, [](auto&& item){g_tasks_observed += FindNumOfTasks(item.value());});
255
256 TestGenericLambdaWithMove<Iterator>(depth, [](auto item, auto& feeder){do_work(item, feeder);});
257 TestGenericLambdaWithMove<Iterator>(depth, [](const auto item, auto& feeder){do_work(item, feeder);});
258 TestGenericLambda<Iterator>(depth, [](volatile auto& item, auto& feeder){do_work(const_cast<value_t&>(item), feeder);});
259 TestGenericLambda<Iterator>(depth, [](const volatile auto& item, auto& feeder){do_work(const_cast<value_t&>(item), feeder);});
260 TestGenericLambda<Iterator>(depth, [](auto& item, auto& feeder){do_work(item, feeder);});
261 TestGenericLambdaWithMove<Iterator>(depth, [](const auto& item, auto& feeder){do_work(item, feeder);});
262 TestGenericLambdaWithMove<Iterator>(depth, [](auto&& item, auto& feeder){do_work(item, feeder);});
263 }
264 #endif /*__TBB_CPP14_GENERIC_LAMBDAS_PRESENT*/
265
266 template<class Iterator>
TestIterator_Move(size_t depth)267 void TestIterator_Move(size_t depth) {
268 TestBodyMove<FakeTaskGeneratorBody_RvalueRefVersion, Iterator>(depth);
269 TestBodyMove<TaskGeneratorBody_RvalueRefVersion, Iterator>(depth);
270 }
271
272 template<class Iterator>
TestIterator_Modifiable(size_t depth)273 void TestIterator_Modifiable(size_t depth) {
274 TestIterator_Const<Iterator>(depth);
275 TestIterator_Move<Iterator>(depth);
276 TestBody<FakeTaskGeneratorBody_RefVersion, Iterator>(depth);
277 TestBody<FakeTaskGeneratorBody_VolatileRefVersion, Iterator>(depth);
278 TestBody<TaskGeneratorBody_RefVersion, Iterator>(depth);
279 TestBody<TaskGeneratorBody_VolatileRefVersion, Iterator>(depth);
280 #if __TBB_CPP14_GENERIC_LAMBDAS_PRESENT
281 TestGenericLambdasCommon<Iterator>(depth);
282 #endif
283 }
284
285 std::atomic<std::size_t> task_counter{0};
286
287 template<template <typename> class IteratorModifier>
288 struct generic_iterator_container {
289 using value_type = std::size_t;
290 using container_type = std::vector<value_type>;
291 using iterator_type = IteratorModifier<value_type>;
292
293 static constexpr std::size_t default_size = 100;
294 container_type my_vec;
295 iterator_type my_begin, my_end;
296
generic_iterator_containergeneric_iterator_container297 generic_iterator_container():
298 my_vec (default_size),
299 my_begin {my_vec.data()},
300 my_end {my_vec.data() + my_vec.size()}
301 {}
302
begingeneric_iterator_container303 iterator_type begin() const { return my_begin; }
endgeneric_iterator_container304 iterator_type end() const { return my_end; }
305
validationgeneric_iterator_container306 void validation(std::size_t expected_value) {
307 for (std::size_t i = 0; i < my_vec.size(); i++)
308 REQUIRE_MESSAGE(my_vec[i] == expected_value, "Some element was not produced");
309
310 REQUIRE_MESSAGE(task_counter == my_vec.size(), "Not all elements were produced");
311 task_counter = 0;
312 }
313 };
314
315 struct incremental_functor {
operatorincremental_functor316 void operator()(std::size_t& in) const { ++in; ++task_counter;}
317 };
318
319 struct incremental_functor_const {
operatorincremental_functor_const320 void operator()(const std::size_t&) const { ++task_counter; }
321 };
322
323 template< template<typename> class IteratorModifier, typename Functor = incremental_functor>
container_based_overload_test_case(std::size_t expected_value)324 void container_based_overload_test_case(std::size_t expected_value) {
325 generic_iterator_container<IteratorModifier> container;
326 tbb::parallel_for_each(container, Functor{});
327 container.validation(expected_value);
328 }
329
330 namespace TestMoveSem {
331 struct MovePreferable : utils::Movable {
MovePreferableMovePreferable332 MovePreferable() : Movable(), addtofeed(true) {}
MovePreferableMovePreferable333 MovePreferable(bool addtofeed_) : Movable(), addtofeed(addtofeed_) {}
MovePreferableMovePreferable334 MovePreferable(MovePreferable&& other) : Movable(std::move(other)),
335 addtofeed(other.addtofeed) {};
336 // base class is explicitly initialized in the copy ctor to avoid -Wextra warnings
MovePreferableMovePreferable337 MovePreferable(const MovePreferable& other) : Movable(other) {
338 REPORT("Error: copy ctor preferred.\n");
339 };
340 MovePreferable& operator=(const MovePreferable&) {
341 REPORT("Error: copy assign operator preferred.\n"); return *this;
342 }
343 bool addtofeed;
344 };
345 struct MoveOnly : MovePreferable {
346 MoveOnly( const MoveOnly& ) = delete;
MoveOnlyMoveOnly347 MoveOnly() : MovePreferable() {}
MoveOnlyMoveOnly348 MoveOnly(bool addtofeed_) : MovePreferable(addtofeed_) {}
MoveOnlyMoveOnly349 MoveOnly(MoveOnly&& other) : MovePreferable(std::move(other)) {};
350 };
351 }
352
353 template<typename T>
RecordAndAdd(const T & in,tbb::feeder<T> & feeder)354 void RecordAndAdd(const T& in, tbb::feeder<T>& feeder) {
355 REQUIRE_MESSAGE(in.alive, "Got dead object in body");
356 size_t i = ++g_tasks_observed;
357 if (in.addtofeed) {
358 if (i%2) feeder.add(T(false));
359 else {
360 T a(false);
361 feeder.add(std::move(a));
362 }
363 }
364 }
365
366 // Take an item by rvalue reference
367 template<typename T>
368 struct TestMoveIteratorBody {
operatorTestMoveIteratorBody369 void operator() (T&& in, tbb::feeder<T>& feeder) const { RecordAndAdd(in, feeder); }
370 };
371
372 // Take an item by value
373 template<typename T>
374 struct TestMoveIteratorBodyByValue {
operatorTestMoveIteratorBodyByValue375 void operator() (T in, tbb::feeder<T>& feeder) const { RecordAndAdd(in, feeder); }
376 };
377
378 template<typename Iterator, typename Body>
TestMoveIterator()379 void TestMoveIterator() {
380 typedef typename std::iterator_traits<Iterator>::value_type value_type;
381
382 Body body;
383 const size_t size = 65;
384 g_tasks_observed = 0;
385 value_type a[size];
386 tbb::parallel_for_each(std::make_move_iterator(Iterator(a)), std::make_move_iterator(Iterator(a+size)), body);
387 REQUIRE(size * 2 == g_tasks_observed);
388 }
389
390 template<typename T>
DoTestMoveSemantics()391 void DoTestMoveSemantics() {
392 TestMoveIterator<utils::InputIterator<T>, TestMoveIteratorBody<T>>();
393 TestMoveIterator<utils::ForwardIterator<T>, TestMoveIteratorBody<T>>();
394 TestMoveIterator<utils::RandomIterator<T>, TestMoveIteratorBody<T>>();
395
396 TestMoveIterator<utils::InputIterator<T>, TestMoveIteratorBodyByValue<T>>();
397 TestMoveIterator<utils::ForwardIterator<T>, TestMoveIteratorBodyByValue<T>>();
398 TestMoveIterator<utils::RandomIterator<T>, TestMoveIteratorBodyByValue<T>>();
399 }
400
401 #endif // __TBB_test_common_parallel_for_each_common_H
402