Debian Codegraph @

third-party/tbb/rfcs/experimental/blocked_nd_range_ctad/README.md

raw
1 # Enabling CTAD for blocked_nd_range
2
3 ## Introduction
4
5 `oneapi::tbb::blocked_nd_range` class was introduced as a representation for recursively divisible N-dimensional range for oneTBB parallel algorithms.
6 This document proposes extending its API with the deduction guides since C++17 to allow dropping the explicit template arguments specification while
7 creating the object if they can be determined using the arguments provided:
8
9 ```cpp
10 oneapi::tbb::blocked_range<int> range1(0, 100);
11 oneapi::tbb::blocked_range<int> range2(0, 200);
12 oneapi::tbb::blocked_range<int> range3(0, 300);
13
14 // Since 3 ranges of type int are provided, the type of nd_range
15 // can be deduced as oneapi::tbb::blocked_nd_range<int, 3>
16 oneapi::tbb::blocked_nd_range nd_range(range1, range2, range3);
17 ```
18
19 ## Proposal
20
21 ### Supported constructors
22
23 The `oneapi::tbb::blocked_nd_range` supports the following set of constructors:
24
25 ```cpp
26 template <typename T, unsigned int N>\
27 class blocked_nd_range {
28 public:
29 using value_type;
30 using dim_range_type = blocked_range<value_type>;
31 using size_type = typename dim_range_type::size_type;
32
33 blocked_nd_range(const dim_range_type& dim0, /*exactly N arguments of type const dim_range_type&*/); // [1]
34 blocked_nd_range(const value_type (&dim_size)[N], size_type grainsize = 1); // [2]
35 blocked_nd_range(blocked_nd_range& r, split); // [3]
36 blocked_nd_range(blocked_nd_range& r, proportional_split proportion); // [4]
37 };
38 ```
39
40 The constructor `[1]` is intended to create an n-dimensional interval by providing N one-dimensional ranges. Each element represents the
41 dimension of the N-dimensional interval being constructed.
42 It also allows to construct these one-dimensional intervals in-place from braced-inclosed initializer lists:
43
44 ```cpp
45 // Passing blocked_range objects itself
46 tbb::blocked_range<int> dim_range(0, 100);
47
48 tbb::blocked_nd_range<int, 2> nd_range_1(dim_range, tbb::blocked_range<int>(0, 200));
49
50 // Constructing in-place from braced-init-lists
51 tbb::blocked_nd_range<int, 2> nd_range_2({0, 100}, {0, 200, 5});
52
53 // Combined approach
54 tbb::blocked_nd_range<int, 2> nd_range_3(dim_range, {0, 200, 5});
55 ```
56
57 The constructor `[2]` is intended to create an interval by providing a C-array each element of which represents a size of the corresponding
58 dimension of the interval being created. This constructor also allows to pass braced-init-list instead of the array from stack:
59
60 ```cpp
61 // Passing array object itself
62 int sizes[3] = {100, 200, 300};
63
64 // Constructing the 3-dim range [0, 100), [0, 200), [0, 300)
65 tbb::blocked_nd_range<int, 3> nd_range_1(sizes);
66
67 // Using the grainsize - each dim range will have grainsize 5
68 tbb::blocked_nd_range<int, 3> nd_range_2(sizes, 5);
69
70 // Passing the braced-init-list
71 tbb::blocked_nd_range<int, 3> nd_range_3({100, 200, 300});
72 ```
73
74 In case of passing the template arguments explicitly, using a braced-init-list in both constructors `[1]` and `[2]` does not introduce any
75 ambiguity since if the number of braced-init lists provided is always equal to the number of dimensions of the range for constructor `[1]` and
76 the number of elements in the braced-init list equal to the number of dimensions for constructor `[2]`.
77
78 Constructors `[3]` and `[4]` are intended to split the range into two parts. They are part of _Range_ Named Requirements and used internally in the
79 implementation of oneTBB parallel algorithms.
80
81 ### Proposed deduction guides
82
83 This paper proposes to add explicit deduction guides for `blocked_nd_range` class:
84
85 ```cpp
86 // [g1]
87 template <typename Value, typename... Values>
88 blocked_nd_range(blocked_range<Value>, blocked_range<Values>...)
89 -> blocked_nd_range<Value, 1 + sizeof...(Values)>;
90 ```
91
92 This deduction guide corresponds to the constructor `[1]` for the case of passing _N_ `blocked_range` objects itself.
93 It only participates in overload resolution if all of the types in `Values` are same as `Value`.
94
95 To cover the case while blocked_ranges are passed as braced-init-lists, it is proposed to add a deduction guide taking
96 a set of C-array objects.
97
98 There are currently two options how to define the deduction guide (or a function) taking the braced-init-list
99 of any type- C-array and `std::initializer_list`. The issue with `std::initializer_list` is that it does not allow
100 tracking the size in compile-time.
101
102 ```cpp
103 // [g2]
104 template <typename Value, unsigned int... Ns>
105 blocked_nd_range(const Value (&...)[Ns])
106 -> blocked_nd_range<Value, sizeof...(Ns)>;
107 ```
108
109 This deduction guide only participates in overload resolution if
110 1. the number of C-arrays provided is more than 1 (`sizeof...(Ns) > 1`),
111 2. Each C-array has the size 2 or 3.
112
113 The first constraint is intended to disambiguate between `[1]` and `[2]`.
114 See [separate section](#ambiguity-while-passing-the-single-braced-init-list-of-size-2-or-3) for more details.
115
116 The second constraint is intended to accept only the braced-init-lists that can be used to initialize the `blocked_range` object.
117 Currently it supports the constructor with 2 parameters, taking _begin_ and _end_ of the interval, and the constructor with 3 parameters, taking
118 additional _grainsize_ parameter.
119
120 The important limitation of the deduction guide `[g2]` is that all of the elements in the braced-init-list should be of the same type.
121 It would be impossible to use this constructor for initializing the `blocked_range` objects of types that are not convertible to `size_type`
122 together with the grainsize:
123
124 ```cpp
125 std::vector<int> vector;
126
127 // OK, deduced as blocked_nd_range<iterator, 1>
128 blocked_nd_range range1({vector.begin(), vector.end()});
129
130 // FAIL, all items in braced-init-lists should be objects of the same type
131 // It is impossible to provide grainsize as iterator since iterator is not convertible to size_type
132 blocked_nd_range range({vector.begin(), vector.end(), /*grainsize = */5});
133 ```
134
135 For the constructor `[2]`, the following deduction guide is proposed:
136
137 ```cpp
138 // [g3]
139 template <typename Value, unsigned int N>
140 blocked_nd_range(const Value (&)[N])
141 ```
142
143 For service constructors `[3]` and `[4]`, the following guides are proposed:
144
145 ```cpp
146 // [g4]
147 template <typename Value, unsigned int N>
148 blocked_nd_range(blocked_nd_range<Value, N>, split)
149 -> blocked_nd_range<Value, N>;
150
151 // [g5]
152 template <typename Value, unsigned int N>
153 blocked_nd_range(blocked_nd_range<Value, N>, proportional_split)
154 -> blocked_nd_range<Value, N>;
155 ```
156
157 From the specification perspective, such a deduction guides can be generated as implicit deduction guides, in the same manner as copy and move constructors.
158 But the current oneTBB implementation, these deduction guides are not generated implicitly, so the explicit guides are required.
159 Guides `[g4]` and `[g5]` are not proposed to be a part of the spec, only a part of oneTBB implementation.
160
161 ## Open Questions
162
163 ### Ambiguity while passing the single braced-init-list of size 2 or 3
164
165 While using the CTAD with `blocked_nd_range`, there is an ambiguity between two approaches while using a single braced-init-list of size 2 or 3:
166
167 ```cpp
168 blocked_nd_range range1({10, 20});
169 blocked_nd_range range2({10, 20, 5});
170 ```
171
172 Since the template arguments for `blocked_nd_range` are not specified, there can be two possible resolutions:
173 1. Be interpreted as one-dimensional range _[10, 20)_ (with grainsize 1 or 5). In this case it should be deduced as `blocked_nd_range<int, 1>` and
174 constructed using the constructor `[1]`.
175 2. Be interpreted as two (or three) dimensional range _[0, 10)_, _[0, 20)_ (and _[0, 5)_). In this case it should be deduced as `blocked_nd_range<int, 3>`
176 and constructed using the constructor `[2]`.
177
178 Since it is unclear which resolution should be chosen, current proposal is not to support such use-case in CTAD and require the user to either explicitly
179 specialize the template arguments, or to use array or `blocked_range` type itself to initialize the object.
180
181 ### Passing single C-array object of size 2 or 3
182
183 Another interesting issue that should be resolved, is passing the single C-array object of size 2 or 3 to the constructor:
184
185 ```cpp
186 int array[2] = {100, 200};
187 tbb::blocked_nd_range range(array);
188 ```
189
190 Since the `blocked_range` is not constructible from C-array and the braced-init-list is not used, the user expects the range to be deduced as
191 `blocked_nd_range<int, 2>` and the constructor `[2]` to be used.
192
193 If we add one more explicit deduction guide to support the code above, the single braced-init-list of size 2 or 3 would also match on this guide.
194
195 There are the following options how this issue can be resolved:
196 * Add a new deduction guide to support the code above. The downside of this approach is that it makes the ambiguity, discussed in the
197 [previous section](#ambiguity-while-passing-the-single-braced-init-list-of-size-2-or-3) to be resolved also and always result in 2 or 3-dimensional
198 range. If the user provided the single braced-init-list to have one-dimensional range, he would face the unexpected behavior without any diagnostics.
199 * Document the code above as limitation and do not support it. The downside is that the code above is considered valid, but
200 cannot be supported because of the implementation of CTAD and current set of constructors.
201 * Support the use-case above but do not support CTAD for braced-init-lists at all. The major downside is that the user would
202 need to always specify the exact type `tbb::blocked_range` while using the braced-init-list construction.
203
204 ### Using the constructor `[1]` with "mixed" arguments
205
206 There is a limitation of the deduction guides proposed if the constructor `[1]` is used with both arguments of exact `tbb::blocked_range` type
207 and the braced-init-lists:
208
209 ```cpp
210 tbb::blocked_range<int> dim_range(0, 100);
211 tbb::blocked_nd_range nd_range(dim_range, {0, 200}, {0, 300}, dim_range);
212 ```
213
214 These arguments would not match nether on the `[g1]` not `[g2]` and it is unclear how to define the deduction guide that covers this case.
215 Current proposal is to keep this scenario a limitation for using the CTAD and always require using the consistent set of parameters - or
216 the set of braced-init-lists or the set of `tbb::blocked_range` objects.
217
218 ## Exit criteria
219
220 The following conditions need to be met to move the feature from experimental to fully supported:
221 * Collecting feedback on user experience confirming the choices made on the open questions and limitations:
222 * Preference of multi-dimensional range while deducing from the C-array or braced-init-list of size 2 or 3.
223 See [separate section](#passing-single-c-array-object-of-size-2-or-3) for more details.
224 * Limitation for the deduction from the braced-init-list to accept only the lists of items of the same type.
225 * Limitation for the deduction guide `1` in case of mixing `blocked_range` objects and braced-init-lists.
226 See [separate section](#using-the-constructor-1-with-mixed-arguments) for more details.
227 * The corresponding oneTBB specification update should be done backed by the user feedback provided.