forked from dhollman/address-of-paper
-
Notifications
You must be signed in to change notification settings - Fork 0
/
paper.bs
193 lines (135 loc) · 11.2 KB
/
paper.bs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
<pre class='metadata'>
Title: Restricting address reliance of function objects given to parallel algorithms
Shortname: D0???
Revision: 0
Audience: SG1
Status: D
Group: WG21
Warning: Not Ready
URL: http://wg21.link/p0????
Editor: David S. Hollman, Sandia National Labs, [email protected]
Editor: Jonathan Lifflander, Sandia National Labs, [email protected]
Editor: Michael Wong, CodePlay, [email protected]
Editor: Detlef Vollmann, Vollmann Engineering, [email protected]
Abstract: Address NB comment CH 11 in [[P0488R0]]
Date: 2016-11-09
Markup Shorthands: markdown yes
Toggle Diffs: yes
Repository: dhollman/address-of-paper
</pre>
Background {#bg}
================
National Body comment CH11 from [[P0488R0]] states:
<blockquote>
Comments: It may be useful to copy objects to a separate space for non-sequenced policies.
Proposed Change: Add explicit allowance for non-sequenced policies to copy the objects
they work on.
</blockquote>
Discussion in SG1 at Issaquah on this comment led to the suggestion that, at minimum, wording should be added to some or all of the parallel algorithms forbidding the reliance on the `addressof` operation for arguments to the function objects passed to a *parallel algorithm* [algorithms.parallel.defns]. A straw pole revealed unanimous agreement that a paper exploring this idea should be written.
In particular, it was suggested that we examine the consequences of expanding or elaborating on the clause in [algorithms.parallel.user] to include language relating to the forbidding of reliance on the `addressof` operator for arguments to certain function objects (particularly the ones called out in this section).
Approach {#appr}
========
In general, the consequences of this new restriction should be considered in the context of each overloaded library function in [[N4604]] that takes an execution policy and at least one user-defined function object. For many of these, we will attempt to propose at least two options, one that tries to be more conservative with respect to potential for different behavior compared to the serial (i.e., `ExecutionPolicy`-free) overload, and one that tries to be more flexible with respect to implementer freedom, but allowing for different behavior from the serial overload in some (potentially far-fetched) cases. For some algorithms, we may also propose one or more middle-ground options.
<!---
Potential Blanket Restrictions {#blanket}
------------------------------
TODO potentially omit any discussion of copying
The primary purpose of the amendments proposed herein is to allow implementers the freedom to copy values to be passed to the user-defined function objects in order to enable certain performance optimizations. It was generally agreed in the Issaquah discussion that this very quickly becomes counterproductive in the case of objects with non-trivial copy constructors (referencing *trivially copyable* from clause 9, paragraph 6). Thus, a safer definition of these restrictions would restrict the `addressof` forbiddance to arguments of *trivially copyable* type. This has the advantage that inconsistency between the
-->
issue: TODO (perhaps?) consider the implications of restricting the `addressof` forbiddance to arguments of *trivially copyable* type (or reference to *trivially copyable* type)
Discussion {#discuss}
==========
issue: TODO broad discussion of the half-dozen or so general categories of use cases
issue: TODO discuss the general problem that, even in the algorithms that do not take function object arguments, `operator==` or `operator!=` (for instance) could rely on the address of their arguments.
`all_of` [alg.all_of] {#all_of}
---------------------
The sorts of `Predicate` function objects that could be passed to `all_of` that could rely on the address of the argument are very esoteric. One use case that could have a `Predicate` reliant on the `addressof` the argument would be one that takes a modulus of that address to query consistency in the alignment of all items in a range (though there are probably better ways to do this).
Another use would be to check if all of the objects in a range fall in between two addresses (for instance, to copy all elements with one `memcpy` invocation).
### Conservative approach
It would potentially be sufficient to preserve the alignment of the first element in the input range as well as the relative offsets of addresses of the other elements compared to the first, though this is unlikely to be widely important. The second possible corner case would not necessarily be addressed by this approach.
### Flexible approach
Forbid any reliance on `addressof` operations on the argument to `Predicate`.
`any_of` [alg.any_of] {#any_of}
---------------------
Similar to [[#all_of]].
`none_of` [alg.none_of] {#none_of}
---------------------
Similar to [[#all_of]].
`for_each` [alg.foreach] {#foreach}
----------------------
The function object passed to `for_each` is not included in [algorithms.parallel.user], therefore the proposed changes would not apply to `for_each`.
`find` [alg.find] {#find}
-------------------------
The algorithms `find_if` and `find_if_not` both take `Predicate` arguments. In addition to the use cases in [[#all_of]] where the user might want to find an object with an address outside of a particular range or with a particular alignment, it may be desirable to check the containment of a non-equality-comparable ([equalitycomparable] in [[N4604]]) object in a given range. We do not see an easy way to provide a conservative approach that preserves the correct behavior in this case.
### Conservative approach
Under the same constraints as [[#all_of]], some (but not all) possible corner cases could be handled. There is no easy way that we can conceive of to constrain the proposed restriction to enable the non-equality-comparable containment use case. It may be worth excluding `find_*` functions from the `addressof` restriction for this reason.
### Flexible approach
Forbid any reliance on `addressof` operations on the argument to `Predicate`. `Predicate`s like compare-by-address (as described above) would need to be run in serial or with a layer of indirection until more user-defined flexibility on the `addressof` behavior could be added to the language by some means.
`find_end` [alg.find.end] {#find_end}
-------------------------
Since `find_end` operates on two different sequences, the analogs of the use cases in [[#find]] constitute a lot more esoteric use cases. Whereas it is easy to envision a `Predicate` to `find_if` that is, for instance, a lambda that captures a reference to a desired value and compares its address to that of the argument passed to `Predicate`, the analogous use case that takes a `BinaryPredicate` is more likely to do something like compare the addresses of the arguments to *each other*, which is much more easily handled by the conservative approach
### Conservative approach
For `find_end` and most other algorithms that take a `BinaryPredicate` function argument, it could be reasonable to provide a restriction intermediate to that of [[#find]] in which the relationship between the addresses of the arguments in any given call to the `BinaryPredicate` remains unchanged (but allow the relationships between addresses of arguments in different calls to be completely unconstrained).
### Less conservative approach
A slightly weaker restriction that still covers a lot of the use cases is to require only that the equality relationship on the addresses of the arguments be preserved. This gives the implementation much more flexibility since it need not allocate memory the side of the distance between the argument addresses in order to make the call safely. This approach also covers most of the use cases for most of the algorithms requiring `BinaryPredicate` function objects.
### Flexible approach
The flexible approach of completely forbidding `addressof` operations on arguments to `find_end` and most other algorithms that take a `BinaryPredicate` has pretty much the same drawbacks as the other algorithms, with the caveat that the conservative approach is less restrictive and exposes much of the functionality (thus making the flexible approach slightly less appealing).
`find_first` [alg.find.first.of] {#find_first}
-------------------------
Similar to [[#find_end]]
`adjacent_find` [alg.adjacent.find] {#adjacent_find}
-------------------------
Similar to [[#find_end]]
`count` [alg.count] {#count}
-------------------
The major concerns surrounding `count` are similar to those of [[#any_of]]
`mismatch` [mismatch] {#mismatch}
---------------------
Similar to [[#find_end]]
`equal` [alg.equal] {#equal}
---------------------
Similar to [[#find_end]]
`search` [alg.search] {#search}
---------------------
Similar to [[#find_end]]
`copy_if` [alg.copy] {#copy_if}
--------------------------
Similar to [[#all_of]], except that the alignment argument is a bit weaker here.
`transform` [alg.transform] {#transform}
-----------------------
We could not come up with a reasonable use case for which `transform` would need a `UnaryOperation` that depends on the address of its argument.
`replace_if` [alg.replace]
--------------------------
Similar to [[#find]]
`replace_copy_if` [alg.replace]
--------------------------
Similar to [[#find]]
`remove_if` [alg.remove]
--------------------------
Similar to [[#find]]
`remove_copy_if` [alg.remove]
--------------------------
Similar to [[#find]]
`unique` [alg.unique]
---------------------
Similar to [[#find_end]]
`unique_copy` [alg.unique]
---------------------
Similar to [[#find_end]]
`partition` [alg.partition]
---------------------------
`partition` and related functions (`is_partitioned`, `stable_partition`, `partition_copy`) have a specific reasonable use case: radix sort binning. We cannot come up with a reasonable conservative approach that works for this use case.
`sort` [alg.sort] {#sort}
--------------------
The most compelling use case for `sort` with a `Compare` operation that relies on the addresses of its arguments is the sorting of locks for the purpose of deadlock avoidance. We acknowledge that this is a legitimate use case and therefore suggest we consider explicitly excluding `sort` from the `addressof` restriction. The conservative approach suggested for [[#find_end]] and other algorithms that take a `BinaryPredicate` would cover this use case, though, as well as most of the other cases that take `Compare` function objects.
`stable_sort` [stable.sort]
-----------------------------
Similar to [[#sort]]
advisement: There are more algorithms that could be considered in this section, but we feel we’ve covered most of the broad categories of use cases. If SG1 feels it is necessary, we can extend this to include subsections for the rest of the parallel algorithms in [[N4604]]
Proposed Wording {#word}
================
Change paragraph 1 of [algorithms.parallel.user] to:
<blockquote>
Function objects passed into parallel algorithms as objects of type `Predicate`, `BinaryPredicate`, `Compare`, <ins>UnaryOperation</ins> and `BinaryOperation` shall not directly or indirectly modify objects via their arguments <ins>or rely on the address of the objects unless otherwise specified for a specific algorithm.</ins>
</blockquote>
issue: TODO: wording for specific sections where blanket change doesn't make sense, as recommended by SG1 following discussion