1 /*
2     Copyright (c) 2017-2021 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/test.h"
18 #include "common/utils.h"
19 #include "common/utils_assert.h"
20 #include "common/utils_concurrency_limit.h"
21 
22 //! \file conformance_blocked_rangeNd.cpp
23 //! \brief Test for [preview] functionality
24 
25 #define TBB_PREVIEW_BLOCKED_RANGE_ND 1
26 #include "oneapi/tbb/blocked_rangeNd.h"
27 #include "oneapi/tbb/parallel_for.h"
28 #include "oneapi/tbb/global_control.h"
29 
30 #include <algorithm> // std::for_each
31 #include <array>
32 
33 // AbstractValueType class represents Value concept's requirements in the most abstract way
34 class AbstractValueType {
35     int value;
36     AbstractValueType() {}
37 public:
38     friend AbstractValueType MakeAbstractValue(int i);
39     friend int GetValueOf(const AbstractValueType& v);
40 };
41 
42 int GetValueOf(const AbstractValueType& v) { return v.value; }
43 
44 AbstractValueType MakeAbstractValue(int i) {
45     AbstractValueType x;
46     x.value = i;
47     return x;
48 }
49 
50 // operator- returns amount of elements of AbstractValueType between u and v
51 std::size_t operator-(const AbstractValueType& u, const AbstractValueType& v) {
52     return GetValueOf(u) - GetValueOf(v);
53 }
54 
55 bool operator<(const AbstractValueType& u, const AbstractValueType& v) {
56     return GetValueOf(u) < GetValueOf(v);
57 }
58 
59 AbstractValueType operator+(const AbstractValueType& u, std::size_t offset) {
60     return MakeAbstractValue(GetValueOf(u) + int(offset));
61 }
62 
63 template<typename range_t, unsigned int N>
64 struct range_utils {
65     using val_t = typename range_t::value_type;
66 
67     template<typename EntityType, std::size_t DimSize>
68     using data_type = std::array<typename range_utils<range_t, N - 1>::template data_type<EntityType, DimSize>, DimSize>;
69 
70     template<typename EntityType, std::size_t DimSize>
71     static void init_data(data_type<EntityType, DimSize>& data) {
72         std::for_each(data.begin(), data.end(), range_utils<range_t, N - 1>::template init_data<EntityType, DimSize>);
73     }
74 
75     template<typename EntityType, std::size_t DimSize>
76     static void increment_data(const range_t& range, data_type<EntityType, DimSize>& data) {
77         auto begin = data.begin() + range.dim(N - 1).begin();
78         // same as "auto end = out.begin() + range.dim(N - 1).end();"
79         auto end = begin + range.dim(N - 1).size();
80         for (auto i = begin; i != end; ++i) {
81             range_utils<range_t, N - 1>::template increment_data<EntityType, DimSize>(range, *i);
82         }
83     }
84 
85     template<typename EntityType, std::size_t DimSize>
86     static void check_data(const range_t& range, data_type<EntityType, DimSize>& data) {
87         auto begin = data.begin() + range.dim(N - 1).begin();
88         // same as "auto end = out.begin() + range.dim(N - 1).end();"
89         auto end = begin + range.dim(N - 1).size();
90         for (auto i = begin; i != end; ++i) {
91             range_utils<range_t, N - 1>::template check_data<EntityType, DimSize>(range, *i);
92         }
93     }
94 
95 // BullseyeCoverage Compile C++ with GCC 5.4 warning suppression
96 // Sequence points error in braced initializer list
97 #if __GNUC__ && !defined(__clang__) && !defined(__INTEL_COMPILER)
98 #pragma GCC diagnostic push
99 #pragma GCC diagnostic ignored "-Wsequence-point"
100 #endif
101     template<typename input_t, std::size_t... Is>
102     static range_t make_range(std::size_t shift, bool negative, val_t(*gen)(input_t), oneapi::tbb::detail::index_sequence<Is...>) {
103         return range_t( { { gen(negative ? -input_t(Is + shift) : 0), gen(input_t(Is + shift)), Is + 1} ... } );
104     }
105 #if __GNUC__ && !defined(__clang__) && !defined(__INTEL_COMPILER)
106 #pragma GCC diagnostic pop
107 #endif
108 
109     static bool is_empty(const range_t& range) {
110         if (range.dim(N - 1).empty()) { return true; }
111         return range_utils<range_t, N - 1>::is_empty(range);
112     }
113 
114     static bool is_divisible(const range_t& range) {
115         if (range.dim(N - 1).is_divisible()) { return true; }
116         return range_utils<range_t, N - 1>::is_divisible(range);
117     }
118 
119     static void check_splitting(const range_t& range_split, const range_t& range_new, int(*get)(const val_t&), bool split_checker = false) {
120         if (get(range_split.dim(N - 1).begin()) == get(range_new.dim(N - 1).begin())) {
121             REQUIRE(get(range_split.dim(N - 1).end()) == get(range_new.dim(N - 1).end()));
122         }
123         else {
124             REQUIRE((get(range_split.dim(N - 1).end()) == get(range_new.dim(N - 1).begin()) && !split_checker));
125             split_checker = true;
126         }
127         range_utils<range_t, N - 1>::check_splitting(range_split, range_new, get, split_checker);
128     }
129 
130 };
131 
132 template<typename range_t>
133 struct range_utils<range_t, 0> {
134     using val_t = typename range_t::value_type;
135 
136     template<typename EntityType, std::size_t DimSize>
137     using data_type = EntityType;
138 
139     template<typename EntityType, std::size_t DimSize>
140     static void init_data(data_type<EntityType, DimSize>& data) { data = 0; }
141 
142     template<typename EntityType, std::size_t DimSize>
143     static void increment_data(const range_t&, data_type<EntityType, DimSize>& data) { ++data; }
144 
145     template<typename EntityType, std::size_t DimSize>
146     static void check_data(const range_t&, data_type<EntityType, DimSize>& data) {
147         REQUIRE(data == 1);
148     }
149 
150     static bool is_empty(const range_t&) { return false; }
151 
152     static bool is_divisible(const range_t&) { return false; }
153 
154     static void check_splitting(const range_t&, const range_t&, int(*)(const val_t&), bool) {}
155 };
156 
157 // We need MakeInt function to pass it into make_range as factory function
158 // because of matching make_range with AbstractValueType and other types too
159 int MakeInt(int i) { return i; }
160 
161 template<unsigned int DimAmount>
162 void SerialTest() {
163     static_assert((oneapi::tbb::blocked_rangeNd<int, DimAmount>::ndims() == oneapi::tbb::blocked_rangeNd<AbstractValueType, DimAmount>::ndims()),
164                          "different amount of dimensions");
165 
166     using range_t = oneapi::tbb::blocked_rangeNd<AbstractValueType, DimAmount>;
167     using utils_t = range_utils<range_t, DimAmount>;
168 
169     // Generate empty range
170     range_t r = utils_t::make_range(0, true, &MakeAbstractValue, oneapi::tbb::detail::make_index_sequence<DimAmount>());
171 
172     utils::AssertSameType(r.is_divisible(), bool());
173     utils::AssertSameType(r.empty(), bool());
174     utils::AssertSameType(range_t::ndims(), 0U);
175 
176     REQUIRE((r.empty() == utils_t::is_empty(r) && r.empty()));
177     REQUIRE(r.is_divisible() == utils_t::is_divisible(r));
178 
179     // Generate not-empty range divisible range
180     r = utils_t::make_range(1, true, &MakeAbstractValue, oneapi::tbb::detail::make_index_sequence<DimAmount>());
181     REQUIRE((r.empty() == utils_t::is_empty(r) && !r.empty()));
182     REQUIRE((r.is_divisible() == utils_t::is_divisible(r) && r.is_divisible()));
183 
184     range_t r_new(r, oneapi::tbb::split());
185     utils_t::check_splitting(r, r_new, &GetValueOf);
186 
187     SerialTest<DimAmount - 1>();
188 }
189 template<> void SerialTest<0>() {}
190 
191 template<unsigned int DimAmount>
192 void ParallelTest() {
193     using range_t = oneapi::tbb::blocked_rangeNd<int, DimAmount>;
194     using utils_t = range_utils<range_t, DimAmount>;
195 
196     // Max size is                                 1 << 20 - 1 bytes
197     // Thus size of one dimension's elements is    1 << (20 / DimAmount - 1) bytes
198     typename utils_t::template data_type<unsigned char, 1 << (20 / DimAmount - 1)> data;
199     utils_t::init_data(data);
200 
201     range_t r = utils_t::make_range((1 << (20 / DimAmount - 1)) - DimAmount, false, &MakeInt, oneapi::tbb::detail::make_index_sequence<DimAmount>());
202 
203     oneapi::tbb::parallel_for(r, [&data](const range_t& range) {
204         utils_t::increment_data(range, data);
205     });
206 
207     utils_t::check_data(r, data);
208 
209     ParallelTest<DimAmount - 1>();
210 }
211 template<> void ParallelTest<0>() {}
212 
213 //! Testing blocked_rangeNd construction
214 //! \brief \ref interface
215 TEST_CASE("Construction") {
216     oneapi::tbb::blocked_rangeNd<int, 1>{ { 0,13,3 } };
217 
218     oneapi::tbb::blocked_rangeNd<int, 1>{ oneapi::tbb::blocked_range<int>{ 0,13,3 } };
219 
220     oneapi::tbb::blocked_rangeNd<int, 2>(oneapi::tbb::blocked_range<int>(-8923, 8884, 13), oneapi::tbb::blocked_range<int>(-8923, 5, 13));
221 
222     oneapi::tbb::blocked_rangeNd<int, 2>({ -8923, 8884, 13 }, { -8923, 8884, 13 });
223 
224     oneapi::tbb::blocked_range<int> r1(0, 13);
225 
226     oneapi::tbb::blocked_range<int> r2(-12, 23);
227 
228     oneapi::tbb::blocked_rangeNd<int, 2>({ { -8923, 8884, 13 }, r1});
229 
230     oneapi::tbb::blocked_rangeNd<int, 2>({ r2, r1 });
231 
232     oneapi::tbb::blocked_rangeNd<int, 2>(r1, r2);
233 
234     oneapi::tbb::blocked_rangeNd<AbstractValueType, 4>({ MakeAbstractValue(-3), MakeAbstractValue(13), 8 },
235                                                { MakeAbstractValue(-53), MakeAbstractValue(23), 2 },
236                                                { MakeAbstractValue(-23), MakeAbstractValue(33), 1 },
237                                                { MakeAbstractValue(-13), MakeAbstractValue(43), 7 });
238 }
239 
240 static const std::size_t N = 4;
241 
242 //! Testing blocked_rangeNd interface
243 //! \brief \ref interface \ref requirement
244 TEST_CASE("Serial test") {
245     SerialTest<N>();
246 }
247 
248 //! Testing blocked_rangeNd interface with parallel_for
249 //! \brief \ref requirement
250 TEST_CASE("Parallel test") {
251     for ( auto concurrency_level : utils::concurrency_range() ) {
252         oneapi::tbb::global_control control(oneapi::tbb::global_control::max_allowed_parallelism, concurrency_level);
253         ParallelTest<N>();
254     }
255 }
256 
257 //! Testing blocked_rangeNd with proportional splitting
258 //! \brief \ref interface \ref requirement
259 TEST_CASE("blocked_rangeNd proportional splitting") {
260     oneapi::tbb::blocked_rangeNd<int, 2> original{{0, 100}, {0, 100}};
261     oneapi::tbb::blocked_rangeNd<int, 2> first(original);
262     oneapi::tbb::proportional_split ps(3, 1);
263     oneapi::tbb::blocked_rangeNd<int, 2> second(first, ps);
264 
265     int expected_first_end = static_cast<int>(
266         original.dim(0).begin() + ps.left() * (original.dim(0).end() - original.dim(0).begin()) / (ps.left() + ps.right())
267     );
268     if (first.dim(0).size() == second.dim(0).size()) {
269         // Splitting was made by cols
270         utils::check_range_bounds_after_splitting(original.dim(1), first.dim(1), second.dim(1), expected_first_end);
271     } else {
272         // Splitting was made by rows
273         utils::check_range_bounds_after_splitting(original.dim(0), first.dim(0), second.dim(0), expected_first_end);
274     }
275 }
276