| 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. |