-
Notifications
You must be signed in to change notification settings - Fork 7
/
Copy pathP0783-SimplifyingStdFutureContinuations.html
261 lines (211 loc) · 19.9 KB
/
P0783-SimplifyingStdFutureContinuations.html
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<!-- saved from url=(0072)file:///Users/lwh/Dropbox%20(Facebook)/C++/Mailings/2017-06/p0667r0.html -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>P0783: Continuations without overcomplicating the future</title>
<style type="text/css">
html { line-height: 135%; }
ins { background-color: #DFD; }
del { background-color: #FDD; }
</style>
</head>
<body>
<table>
<tbody><tr>
<th>Doc. No.:</th>
<td>WG21/P0783</td>
</tr>
<tr>
<th>Date:</th>
<td>2017-09-11</td>
</tr>
<tr>
<th>Authors:</th><td>Lee Howes <a href="mailto:[email protected]">[email protected]</a>, Andrii Grynenko <a href="mailto:[email protected]">[email protected]</a>, Jay Feldblum <a href="mailto:[email protected]">[email protected]</a></td>
</tr>
<tr>
<th>Reply-to:</th>
<td>Lee Howes</td>
</tr>
<tr>
<th>Email:</th>
<td><a href="mailto:[email protected]">[email protected]</a></td>
</tr>
<tr>
<th>Audience:</th>
<td>SG1</td>
</tr>
</tbody></table>
<h1>P0783: Continuations without overcomplicating the future</h1>
<h2>Background</h2>
<p>In the Concurrency TS, <code>std::future</code> was augmented with support for continuations.
However, the feedback leading up to and during the July 2017 meeting in Toronto made clear that the specification for continuation support in the TS was insufficient.
The absence of support for executors made the behavior of continuations attached to futures hard to understand and hard to control. LWG2533 expressed concern about where the continuation is run, and other papers including P0667, P0679 and P0701 pointed out more areas of improvement.
Much of this feedback relates to the ongoing work on executors that is as yet incomplete but is detailed in P0443.
The continuation elements of the Concurrency TS were subsequently not merged into the C++20 standard draft at Toronto.
<p>At Facebook, like at many companies, we have considerable experience using continuations on futures.
The open source <a href="https://github.com/facebook/folly">Folly</a> library encapsulates a set of primitives widely used within Facebook.
Folly Futures supports executors and continuations.
From the widespread use of Folly Futures inside Facebook we have learned many lessons.
The most important lesson is very similar to that expressed in LWG2533: that it must be specified, and defined precisely, where a continuation is run when attached to a future.
In the absence of a strong rule, there is an inherent under-specification or non-determinism:
<ul>
<li>If the future is complete at the time of attaching the continuation, is it run in the calling thread-of-execution that attaches the continuation?</li>
<li>If the future is incomplete at the time of attaching the continuation, is it possible for the continuation to run in the thread-of-execution that completes the future to which the continutation is attached?</li>
<li>Does the continuation always run in a well-defined thread-of-execution, whatever the completion state is of the future? If yes, to achieve this, the thread-of-execution has to be guaranteed to survive long enough for the continuation to run.</li>
</ul>
<p>Our experience at Facebook leads us to believe that a known executor should always be available at the point of attaching a continuation to a future, and where the continuation runs should be explicitly defined by the rules of that executor.
In this way, and as long as the lifetime of the executor can be guaranteed, the behavior of continuations attached to futures is understandable and controllable.
Executor lifetimes have partly been considered by making them value types in P0443. Recent experience in Folly, where they are not value types, validates the design decision to make them value types.
(The management of executor lifetimes is out of scope of this paper; that question should be clarified in the ongoing specification of executors.)
<p>Always requiring an executor at the point of continuation attachment, as in calls to the proposed <code>std::future::then</code> (as shorthand, <code>.then</code>), is possible but clumsy.
During discussions in Toronto more than one person expressed a wish to allow a default executor, which would be used if none was provided to the call to <code>.then</code>.
If this is to be allowed then there arise further questions:
<ul>
<li>Should the default executor be a global default? If so, this will be suboptimal for cases where it makes more sense to allow the continuation to run on the same thread-of-execution as that which completes the future.</li>
<li>Should an executor be attached to the future or instead to its core (shared state)? If the latter, a continuation attached with <code>.then</code> would run on the same thread-of-execution as the completion of the future.</li>
</ul>
<p>Something close to the second option here is often used in Facebook's libraries.
An asynchronous library will typically require an executor to be passed in, and the library will ensure that the future it returns to callers across the library boundary will complete on the caller-provided executor, regardless of whether any further work is to be performed on that caller-provided executor.
The asynchronous library will typically attach an empty continuation to the passed executor to make this guarantee.
This action has runtime cost, and cognative load for the user because executor parameters need to be widespread and intrude in places where they are not relevant.
<p>Take a simple example of a library that gets a future and passes it into some other library:
<pre>
void myForwardingFunction() {
Executor e;
auto future = LibraryA::getFromSomewhere(e, params);
LibraryB::sendToSomewhere(future);
}
</pre>
<p>In this case, why did <code>myForwardingFunction</code> need to know about an executor at all?
It would be difficult to choose an executor here that guarantees forward progress but which does not impose a high cost such as might arise in construction of a thread, ensuring presence of an additional thread pool, etc.
In practice, <code>LibraryB</code> would use its own internal executor to run the continuation it attaches, but this is not something that <code>LibraryA</code> can rely on while providing a safe separation of concerns across the library boundary.
<p>Yet this approach is common to ensure that, in any inter-library interaction, both the caller and the callee can protect themselves from having the other's work run on their threads.
On the one hand, a nonblocking-IO library may not want its callers to enqueue arbitrary work on the library's internal nonblocking-IO thread pool, at the risk of starving incoming work of unblocked threads to service incoming requests.
On the other hand, a function that is running work on an inline executor may want to ensure that the library to which it is passing a future will definitely not run whatever work it has to do on the caller's thread.
In either case, the extra executor adds cost even if it never runs any additional tasks. The extra executor would be unnecessary under the hypothesis of well-behaved code.
<h2>A simpler addition to std::future</h2>
We propose continuing to treat <code>std::future</code> as the vocabulary type for potentially asynchronous execution.
We should not require that <code>std::future</code> make available any user-visible executor; we should minimise the set of cases where it is unclear on what executor work will run.
<p>Instead, we propose modifying <code>std::future</code> to add a <code>.via()</code> method that takes an executor.
<code>std::future::via</code> should consume the <code>std::future</code> and return a new future type.
<p>This new future type is yet to be defined but should embody some of the same capabilities that are in <code>std::experimental::future</code> or <code>folly::Future</code>.
In particular, it should add support for continuations using <code>.then</code> methods, as most people expect.
We will call this new future type <code>magic_future</code> here, in the knowledge that this name is not what we really want, to avoid bikeshedding about the naming here.
<code>magic_future</code> should store its executor internally, such that it is well-defined to add an overload of <code>.then</code> that takes no executor.
We would argue against adding any <code>.then</code> overloads that take an executor, because these overloads would lead to confusion about executor stickiness. Chaining calls to <code>.then</code> after calls to <code>.via</code> is just as readable and efficient: <code>someFuture.via(SomeExecutor{}).then(...)</code>.
It is open to discussion whether this method should be restricted to r-value futures.
We should additionally add a conversion, possibly implicit, from <code>magic_future</code> to <code>std::future</code>.
<p>Therefore we might aim for something similar to:
<pre>
template<class T>
class future {
...
// Primary r-value via method
template<class ExecutorT>
std::magic_future<T> via(ExecutorT executor) &&;
// Optional l-value via method
template<class ExecutorT>
std::magic_future<T> via(ExecutorT executor) const &;
};
template<class T>
class magic_future{
...
// Implicit conversion to std::future
operator std::future<T>() &&;
// r-value executor-less addition of continuation and return new future
template<class FunctionT>
magic_future<T> then(FunctionT task) &&;
// Optional r-value then operation with executor and l-value then operations
template<class ExecutorT, class FunctionT>
magic_future<T> then(FunctionT task) const &;
template<class ExecutorT, class FunctionT>
magic_future<T> then(ExecutorT executor, FunctionT task) const &;
template<class ExecutorT, class FunctionT>
magic_future<T> then(ExecutorT executor, FunctionT task) &&;
};
</pre>
<p>In this world, <code>std::future</code> stays as the vocabulary type, with general day to day use unchanged. Our forwarding function as described above simplifies:
<pre>
void myForwardingFunction() {
auto future = LibraryA::getFromSomewhere(params);
LibraryB::sendToSomewhere(future);
}
</pre>
<p>We no longer need to tell <code>LibraryA</code> what executor to complete its future on. <code>myForwardingFunction</code> does not need to know about executors at all. <code>LibraryA</code> did some work; <code>LibraryB</code> will do more work dependent on <code>LibraryA</code>'s work.
The forwarder should not incur any cognative load or runtime cost to construct an executor that exists purely to protect <code>LibraryA</code> from its callers.
<p>As <code>std::future</code> will be carrying potentially unexecuted tasks, its core will likely have to carry a type-erased executor.
This appears to be an implementation detail. Moreover, it is probably also safe to share the same core, with continuation support, between <code>std::future</code> and <code>std::magic_future</code> making the required set of conversion operations low-to-zero cost.
We have implemented this in Folly by adding a <code>folly::SemiFuture</code> representing the continuation-free <code>std::future</code> and the original, continuation-enabled, <code>folly::Future</code> as a derived type having the functionality that we would expect of <code>magic_future</code>.
<h2>Templating the new future</h2>
If we continue to use <code>std::future</code> as the vocabulary type for APIs, we can consider templating our new <code>magic_future</code> on the executor type, both for efficiency and for interface precision.
So our new future then becomes typed:
<pre>
template<class T, class ExecutorT> class magic_future;
</pre>
<p>The executor-parameterized future type means we do not pass a future that supports continuations and yet has an unknown executor type, and hence an unknown set of capabilities, across library boundaries unless we explicitly do so with a polymorphic executor.
This is important because it also means we do not pass a future that supports continuations and has an unknown forward progress guarantee for those continuations, as forward progress guarantees vary between executor types.
<p>In the Concurrency TS design, we pass the completed future to the continuation. In Folly Futures, the primary interface is to pass a <code>folly::Try</code> type that wraps either the value or the exception with which the future was completed.
Instead we should either pass a future type parameterized by the executor, or to simplify the argument list and to avoid implying the full set of future capabilities, optionally pass a separate executor to the continuation:
<pre>
f.then([](ExecutorT e, auto result){/*...*/});
</pre>
<p>If the future is templated on the executor type we can use this information in the continuation. For example, if we want to enqueue work on the same executor as the current task is running on:
<pre>
f.then([](ExecutorT e, auto value){e.execute([](ExecutorT e){/*...*/});});
</pre>
<p>With the precise type of the executor we can use the interface more flexibly - for example, by using knowledge about the structure of the executor type hierarchy:
<pre>
f.then([](ThreadPoolThreadExecutor& e, auto value){
doWorkA(value);
ThreadPoolExecutor tpe = e.getParentPool();
tpe.execute([value](ThreadPoolThreadExecutor e){doWorkB(value);});
});
</pre>
<p>In this case we know we are running on a member thread of a thread pool.
We use this knowledge to get an executor representing the entire pool, or a strongly typed context from which we can get a member executor.
We defer knowledge of which thread ultimately runs the task to the runtime; once our task starts, we have a thread pool thread executor. Importantly for this example, the functions <code>doWorkA</code> and <code>doWorkB</code> run in the same thread pool, but may run in different threads within the single thread pool.
<p>Note that we can default this type to be the polymophic executor <code>magic_polymorphic_executor</code> (likewise, named so as to avoid bikeshedding over the name here, although likely based on the polymorphic wrappers proposed in P0443R2), which would provide us minimal information about the executor in the task.
We may also allow converting a <code>std::magic_future<T, ExecutorT></code> to a <code>std::magic_future<T, OtherExecutorT></code> whenever <code>ExecutorT</code> is convertible to <code>OtherExecutorT</code>, and make all executors convertible to <code>magic_polymorphic_executor</code>.
<p>We believe that by separating the two future types into the existing <code>std::future</code> extended with <code>std::future::via</code> and a new <code>magic_future</code>, rather than attempting drastically to widen the interface of <code>std::future</code>, we have much more flexibility in the design choices we can make.
<h2>Boost blocking and deferred execution</h2>
In p0679r0 Torvald Riegel expressed a desire to ensure that continuations and result extraction for futures provide boost-blocking guarantees.
<code>folly::Future</code> and its executors do not provide this: we require a call to <code>.getVia</code> to ensure that a callback that has no currently known executor gets one, and chains of continuations with undriven executors will not execute.
<p>In looking at whether we can produce a continuation-less version of <code>folly::Future</code> we saw a common case where a library wants to do some work on its own executor, and wants also to do some work on a caller-provided executor.
For example, much of Facebook's networking library code will perform nonblocking-IO on an internal nonblocking-IO executor, but will deserialize messages on a caller-provided executor.
This causes problems in practice where users find such libraries harder to learn, as it is not obvious at the call site what the purpose of the caller-provided executor is.
<p>With good boost-blocking support we can avoid this.
<code>std::future::get</code> should boost-block on the executor attached to the future.
<code>std::future::via</code> similarly leads to boosting, but does so by ensuring that a task is added to the provided executor that drives, if necessary, the previously attached executor to ensure earlier tasks complete.
In this way a whole chain of inline executors may be provided that drive each other in turn until the work is completed.
<p>Assuming we have some deferred/manual executor type named <code>magic_deferred_executor</code> (same caveat about naming) that guarantees not to execute work immediately but to run it when the executor is driven later via the <code>.magic_drive</code> member function (same caveat about naming), we can ensure when we return a future from a library we can defer work until the caller calls <code>.get</code> or chains work through an executor of their choice.
This means code like the following can be made to work:
<pre>
std::future<T> LibraryA::getFromSomewhere(Params params) {
magic_future tf = getRawNetworkData(params);
return tf.via(magic_deferred_executor{}).then([](auto buffer){ return deserialize(buffer); });
}
int main() {
auto f = getFromSomewhere(Params{});
// Deserialization will happen some time after this point
auto resultFuture = f.via(ThreadedExecutor{});
// ...
return 0;
}
</pre>
<p>This gives us control of what runs where, but with a simple, safe API for interacting between libraries.
<code>.then</code> need not boost-block here, as that behaviour is a property of the executors, and any application of boost-blocking is thus defined by points at which executors are connected together - with the clarification that a call to <code>f.get()</code> is logically equivalent to <code>magic_deferred_executor e; auto f2 = f.via(e); e.magic_drive(); f2.get();</code>.
<p>Boost-blocking of executors still has to be considered carefully, of course, to avoid recursive driving behaviour.
We merely use a <code>magic_drive()</code> method as a potential interface for this that internals of futures would use.
<p>A requirement arising from this is that any executor attached to a <code>std::future</code> should, in context, be boost-blocking at a minimum, or the work will never complete.
For any user of a <code>std::future</code>, it is reasonable to expect that the future will complete eventually, but that the calling thread might have to do some additional work inline to achieve this.
<h2>Adding support for coroutines</h2>
A future that represents an asynchronous operation but provides only a synchronous <code>.get</code> operation is a reasonable design to interact with coroutines.
Code that uses Folly Fibers, which is based on <code>boost::context</code>, appears synchronous in that it uses <code>.get()</code> on the future and the internal context switching is hidden behind the interface.
Similarly, it is reasonable to extend the basic synchronous interface to the future to be awaitable and to work with <code>co_await</code>.
In both these cases, information about the calling executor can be implicit in the calling context, either because it is really synchronous on a single executor in the case of a fiber or because the calling coroutine frame can carry information about where it is executing.
We therefore are less likely to see issues with enqueuing a continuation onto an unexpected executor.
<h2>In summary</h2>
<p>We argue that <code>std::future</code> should not be extended with continuations.
It should remain a simple, wait-only type that serves a concrete purpose of synchronously waiting on potentially asynchronous work.
We should extend <code>std::future</code> only to allow it to convert in the presence of an executor into a more sophisticated future type and to add the approriate requirements for forward progress guarantees.
This is extensibile and flexible, and enables specialization based on the provided executor.
</p></body></html>