1 /*
2     Copyright (c) 2005-2023 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 #include "common/parallel_for_each_common.h"
18 #include "common/concepts_common.h"
19 #include <vector>
20 #include <iterator>
21 
22 //! \file test_parallel_for_each.cpp
23 //! \brief Test for [algorithms.parallel_for_each]
24 
25 #if __TBB_CPP20_PRESENT
26 // Fancy iterator type that models the C++20 iterator type
27 // that defines the real iterator category using iterator_concept type
28 // and iterator_category is always std::input_iterator_type
29 // Similar iterators are used by C++20 ranges (e.g. std::ranges::iota_view::iterator)
30 // parallel_for_each algorithm should detect such iterators with respect to iterator_concept value
31 
32 template <typename T, typename Category>
33 struct cpp20_iterator {
34     static_assert(std::derived_from<Category, std::forward_iterator_tag>,
35                   "cpp20_iterator should be of at least forward iterator category");
36 
37     using iterator_concept = Category;
38     using iterator_category = std::input_iterator_tag;
39     using value_type = T;
40     using difference_type = std::ptrdiff_t;
41 
42     cpp20_iterator() = default;
43     explicit cpp20_iterator(T* ptr) : my_ptr(ptr) {}
44 
45     T& operator*() const { return *my_ptr; }
46 
47     cpp20_iterator& operator++() {
48         ++my_ptr;
49         return *this;
50     }
51 
52     cpp20_iterator operator++(int) {
53         auto it = *this;
54         ++*this;
55         return it;
56     }
57 
58     cpp20_iterator& operator--()
59         requires std::derived_from<Category, std::bidirectional_iterator_tag>
60     {
61         --my_ptr;
62         return *this;
63     }
64 
65     cpp20_iterator operator--(int)
66         requires std::derived_from<Category, std::bidirectional_iterator_tag>
67     {
68         auto it = *this;
69         --*this;
70         return it;
71     }
72 
73     cpp20_iterator& operator+=(difference_type n)
74         requires std::derived_from<Category, std::random_access_iterator_tag>
75     {
76         my_ptr += n;
77         return *this;
78     }
79 
80     cpp20_iterator& operator-=(difference_type n)
81         requires std::derived_from<Category, std::random_access_iterator_tag>
82     {
83         my_ptr -= n;
84         return *this;
85     }
86 
87     T& operator[](difference_type n) const
88         requires std::derived_from<Category, std::random_access_iterator_tag>
89     {
90         return my_ptr[n];
91     }
92 
93     friend bool operator==(const cpp20_iterator&, const cpp20_iterator&) = default;
94 
95     friend auto operator<=>(const cpp20_iterator&, const cpp20_iterator&)
96         requires std::derived_from<Category, std::random_access_iterator_tag> = default;
97 
98     friend cpp20_iterator operator+(cpp20_iterator i, difference_type n)
99         requires std::derived_from<Category, std::random_access_iterator_tag>
100     {
101         return cpp20_iterator(i.my_ptr + n);
102     }
103 
104     friend cpp20_iterator operator+(difference_type n, cpp20_iterator i)
105         requires std::derived_from<Category, std::random_access_iterator_tag>
106     {
107         return i + n;
108     }
109 
110     friend cpp20_iterator operator-(cpp20_iterator i, difference_type n)
111         requires std::derived_from<Category, std::random_access_iterator_tag>
112     {
113         return cpp20_iterator(i.my_ptr - n);
114     }
115 
116     friend difference_type operator-(const cpp20_iterator& x, const cpp20_iterator& y) {
117         return x.my_ptr - y.my_ptr;
118     }
119 private:
120     T* my_ptr = nullptr;
121 }; // class cpp20_iterator
122 #endif // __TBB_CPP20_PRESENT
123 
124 //! Test forward access iterator support
125 //! \brief \ref error_guessing \ref interface
126 TEST_CASE("Forward iterator support") {
127     for ( auto concurrency_level : utils::concurrency_range() ) {
128         tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level);
129         for(size_t depth = 0; depth <= depths_nubmer; ++depth) {
130             g_tasks_expected = 0;
131             for (size_t i=0; i < depth; ++i)
132                 g_tasks_expected += FindNumOfTasks(g_depths[i].value());
133             TestIterator_Modifiable<utils::ForwardIterator<value_t>>(depth);
134         }
135     }
136 }
137 
138 //! Test random access iterator support
139 //! \brief \ref error_guessing \ref interface
140 TEST_CASE("Random access iterator support") {
141     for ( auto concurrency_level : utils::concurrency_range() ) {
142         tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level);
143         for(size_t depth = 0; depth <= depths_nubmer; ++depth) {
144             g_tasks_expected = 0;
145             for (size_t i=0; i < depth; ++i)
146                 g_tasks_expected += FindNumOfTasks(g_depths[i].value());
147             TestIterator_Modifiable<value_t*>(depth);
148         }
149     }
150 }
151 
152 //! Test const random access iterator support
153 //! \brief \ref error_guessing \ref interface
154 TEST_CASE("Const random access iterator support") {
155     for ( auto concurrency_level : utils::concurrency_range() ) {
156         tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level);
157         for(size_t depth = 0; depth <= depths_nubmer; ++depth) {
158             g_tasks_expected = 0;
159             for (size_t i=0; i < depth; ++i)
160                 g_tasks_expected += FindNumOfTasks(g_depths[i].value());
161             TestIterator_Const<utils::ConstRandomIterator<value_t>>(depth);
162         }
163     }
164 
165 }
166 
167 //! Test container based overload
168 //! \brief \ref error_guessing \ref interface
169 TEST_CASE("Container based overload - forward iterator based container") {
170     container_based_overload_test_case<utils::ForwardIterator>(/*expected_value*/1);
171 }
172 
173 //! Test container based overload
174 //! \brief \ref error_guessing \ref interface
175 TEST_CASE("Container based overload - random access iterator based container") {
176     container_based_overload_test_case<utils::RandomIterator>(/*expected_value*/1);
177 }
178 
179 // Test for iterators over values convertible to work item type
180 //! \brief \ref error_guessing \ref interface
181 TEST_CASE("Using with values convertible to work item type") {
182     for ( auto concurrency_level : utils::concurrency_range() ) {
183         tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level);
184         using Iterator = size_t*;
185         for(size_t depth = 0; depth <= depths_nubmer; ++depth) {
186             g_tasks_expected = 0;
187             for (size_t i=0; i < depth; ++i)
188                 g_tasks_expected += FindNumOfTasks(g_depths[i].value());
189             // Test for iterators over values convertible to work item type
190             TestIterator_Common<Iterator>(depth);
191             TestBody<FakeTaskGeneratorBody_RvalueRefVersion, Iterator>(depth);
192             TestBody<TaskGeneratorBody_RvalueRefVersion, Iterator>(depth);
193         }
194     }
195 }
196 
197 //! Testing workers going to sleep
198 //! \brief \ref resource_usage \ref stress
199 TEST_CASE("That all workers sleep when no work") {
200     const std::size_t N = 100000;
201     std::vector<std::size_t> vec(N, 0);
202 
203     tbb::parallel_for_each(vec.begin(), vec.end(), [&](std::size_t& in) {
204         for (int i = 0; i < 1000; ++i) {
205             ++in;
206         }
207     });
208     TestCPUUserTime(utils::get_platform_max_threads());
209 }
210 
211 #if __TBB_CPP20_CONCEPTS_PRESENT
212 
213 template <typename Iterator, typename Body>
214 concept can_call_parallel_for_each_with_iterator = requires( Iterator it, const Body& body, tbb::task_group_context ctx ) {
215     tbb::parallel_for_each(it, it, body);
216     tbb::parallel_for_each(it, it, body, ctx);
217 };
218 
219 template <typename ContainerBasedSequence, typename Body>
220 concept can_call_parallel_for_each_with_cbs = requires( ContainerBasedSequence cbs,
221                                                         const ContainerBasedSequence const_cbs,
222                                                         const Body& body, tbb::task_group_context ctx ) {
223     tbb::parallel_for_each(cbs, body);
224     tbb::parallel_for_each(cbs, body, ctx);
225     tbb::parallel_for_each(const_cbs, body);
226     tbb::parallel_for_each(const_cbs, body, ctx);
227 };
228 
229 using CorrectCBS = test_concepts::container_based_sequence::Correct;
230 
231 template <typename Body>
232 concept can_call_parallel_for_each =
233     can_call_parallel_for_each_with_iterator<CorrectCBS::iterator, Body> &&
234     can_call_parallel_for_each_with_cbs<CorrectCBS, Body>;
235 
236 template <typename Iterator>
237 using CorrectBody = test_concepts::parallel_for_each_body::Correct<decltype(*std::declval<Iterator>())>;
238 
239 void test_pfor_each_iterator_constraints() {
240     using CorrectIterator = typename std::vector<int>::iterator; // random_access_iterator
241     using IncorrectIterator = std::ostream_iterator<int>; // output_iterator
242     static_assert(can_call_parallel_for_each_with_iterator<CorrectIterator, CorrectBody<CorrectIterator>>);
243     static_assert(!can_call_parallel_for_each_with_iterator<IncorrectIterator, CorrectBody<IncorrectIterator>>);
244 }
245 
246 void test_pfor_each_container_based_sequence_constraints() {
247     using namespace test_concepts::container_based_sequence;
248     static_assert(can_call_parallel_for_each_with_cbs<Correct, CorrectBody<Correct::iterator>>);
249     static_assert(!can_call_parallel_for_each_with_cbs<NoBegin, CorrectBody<NoBegin::iterator>>);
250     static_assert(!can_call_parallel_for_each_with_cbs<NoEnd, CorrectBody<NoEnd::iterator>>);
251 }
252 
253 void test_pfor_each_body_constraints() {
254     using namespace test_concepts::parallel_for_each_body;
255     static_assert(can_call_parallel_for_each<Correct<int>>);
256     static_assert(can_call_parallel_for_each<WithFeeder<int>>);
257     static_assert(!can_call_parallel_for_each<NoOperatorRoundBrackets<int>>);
258     static_assert(!can_call_parallel_for_each<WithFeederNoOperatorRoundBrackets<int>>);
259     static_assert(!can_call_parallel_for_each<OperatorRoundBracketsNonConst<int>>);
260     static_assert(!can_call_parallel_for_each<WithFeederOperatorRoundBracketsNonConst<int>>);
261     static_assert(!can_call_parallel_for_each<WrongInputOperatorRoundBrackets<int>>);
262     static_assert(!can_call_parallel_for_each<WithFeederWrongFirstInputOperatorRoundBrackets<int>>);
263     static_assert(!can_call_parallel_for_each<WithFeederWrongSecondInputOperatorRoundBrackets<int>>);
264 }
265 
266 //! \brief \ref error_guessing
267 TEST_CASE("parallel_for_each constraints") {
268     test_pfor_each_iterator_constraints();
269     test_pfor_each_container_based_sequence_constraints();
270     test_pfor_each_body_constraints();
271 }
272 
273 #endif // __TBB_CPP20_CONCEPTS_PRESENT
274 
275 #if __TBB_CPP20_PRESENT
276 
277 struct no_copy_move {
278     no_copy_move() = default;
279 
280     no_copy_move(const no_copy_move&) = delete;
281     no_copy_move(no_copy_move&&) = delete;
282 
283     no_copy_move& operator=(const no_copy_move&) = delete;
284     no_copy_move& operator=(no_copy_move&&) = delete;
285 
286     int item = 0;
287 };
288 
289 template <typename Category>
290 void test_with_cpp20_iterator() {
291     constexpr std::size_t n = 1'000'000;
292 
293     no_copy_move elements[n];
294 
295     cpp20_iterator<no_copy_move, Category> begin(elements);
296     cpp20_iterator<no_copy_move, Category> end(elements + n);
297 
298     oneapi::tbb::parallel_for_each(begin, end, [](no_copy_move& element) {
299         element.item = 42;
300     });
301 
302     for (std::size_t index = 0; index < n; ++index) {
303         CHECK(elements[index].item == 42);
304     }
305 }
306 
307 //! \brief \ref error_guessing \ref regression
308 TEST_CASE("parallel_for_each with cpp20 iterator") {
309     // Test that parallel_for_each threats ignores iterator_category type
310     // if iterator_concept type is defined for iterator
311 
312     // For input iterators parallel_for_each requires element to be
313     // copyable or movable so since cpp20_iterator is at least forward
314     // parallel_for_each should work with cpp20_iterator
315     // on non-copyable and non-movable type
316 
317     // test cpp20_iterator implementation
318     using cpp20_forward_iterator = cpp20_iterator<int, std::forward_iterator_tag>;
319     using cpp20_bidirectional_iterator = cpp20_iterator<int, std::bidirectional_iterator_tag>;
320     using cpp20_random_access_iterator = cpp20_iterator<int, std::random_access_iterator_tag>;
321 
322     static_assert(std::forward_iterator<cpp20_forward_iterator>);
323     static_assert(!std::bidirectional_iterator<cpp20_forward_iterator>);
324 
325     static_assert(std::bidirectional_iterator<cpp20_bidirectional_iterator>);
326     static_assert(!std::random_access_iterator<cpp20_bidirectional_iterator>);
327 
328     static_assert(std::random_access_iterator<cpp20_random_access_iterator>);
329 
330     test_with_cpp20_iterator<std::forward_iterator_tag>();
331     test_with_cpp20_iterator<std::bidirectional_iterator_tag>();
332     test_with_cpp20_iterator<std::random_access_iterator_tag>();
333 }
334 
335 #endif // __TBB_CPP20_PRESENT
336