From c286b93ad2092bea4bb9c1287a0be10a050f1441 Mon Sep 17 00:00:00 2001 From: Hans Fugal Date: Thu, 2 Jul 2015 16:03:25 -0700 Subject: [PATCH] folly/futures Update README.md MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Summary: This is a documentation dump, with updates from the past couple weeks. Most notably, the new information about `Future` replacing `Future`. Reviewed By: @​hannesr Differential Revision: D2211135 --- folly/futures/README.md | 118 +++++++++++++++++++++------------------- 1 file changed, 63 insertions(+), 55 deletions(-) diff --git a/folly/futures/README.md b/folly/futures/README.md index 3f197ca5..67e7085a 100644 --- a/folly/futures/README.md +++ b/folly/futures/README.md @@ -1,3 +1,4 @@ +

Futures

Futures is a framework for expressing asynchronous code in C++ using the Promise/Future pattern.

Overview #

Folly Futures is an async C++ framework inspired by Twitter's Futures implementation in Scala (see also Future.scala, Promise.scala, and friends), and loosely builds upon the existing but anemic Futures code found in the C++11 standard (std::future) and boost::future (especially >= 1.53.0). @@ -36,7 +37,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac Future chain made fulfilling Promise foo(42) -Promise fulfilled

Brief Guide

This brief guide covers the basics. For a more in-depth coverage skip to More Details or the appropriate section.

+Promise fulfilled

Brief Guide

This brief guide covers the basics. For a more in-depth coverage skip to the appropriate section.

Let's begin with an example using an imaginary simplified Memcache client interface:

@@ -118,7 +119,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac throw SomeException("No value"); }); -Future<void> fut3 = fut2 +Future<Unit> fut3 = fut2 .then([](string str) { cout << str << endl; }) @@ -135,7 +136,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac

Futures are partially threadsafe. A Promise or Future can migrate between threads as long as there's a full memory barrier of some sort. Future::then and Promise::setValue (and all variants that boil down to those two calls) can be called from different threads. But, be warned that you might be surprised about which thread your callback executes on. Let's consider an example.

// Thread A
-Promise<void> p;
+Promise<Unit> p;
 auto f = p.getFuture();
 
 // Thread B
@@ -464,7 +465,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 makeFuture()
   .then([]{
     // This will properly wrap the exception
-    return makeFuture<void>(std::runtime_error("ugh"));
+    return makeFuture<Unit>(std::runtime_error("ugh"));
   })
   .onError([](const std::runtime_error& e){
     // ...
@@ -507,7 +508,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
 
collect() #

 
-
collect() is similar to collectAll(), but will terminate early if an exception is raised by any of the input Futures. Therefore, the returned Future is of type std::vector<T>, unless T is void, in which case the returned Future is void. Like collectAll(), input Futures are moved in and are no longer valid, and the resulting Future's vector will contain the results of each input Future in the same order they were passed in (if all are successful). For instance:

+
collect() is similar to collectAll(), but will terminate early if an exception is raised by any of the input Futures. Therefore, the returned Future is of type std::vector<T>. Like collectAll(), input Futures are moved in and are no longer valid, and the resulting Future's vector will contain the results of each input Future in the same order they were passed in (if all are successful). For instance:

 
 
collect(fs).then([](const std::vector<T>& vals){
   for (const auto& val : vals) {
@@ -521,13 +522,12 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 // Or using a Try:
 collect(fs).then([](const Try<std::vector<T>>& t){
  // ...
-});
-
-// If fs are void Futures, there's nothing to take in your callback:
-collect(fs).then([]{
-  // ...
 });

 
+
collect() variadic #

+
+
There is also a variadically templated flavor of collect() that allows you to mix and match different types of Futures. It returns a Future<std::tuple<T1, T2, ...>>.

+
 
collectN() #

 
 
collectN, like collectAll(), takes a collection of Futures, or a pair of iterators thereof, but it also takes a size_t N and will complete once N of the input futures are complete. It returns a Future<std::vector<std::pair<size_t, Try<T>>>>. Each pair holds the index of the corresponding Future in the original collection as well as its result, though the pairs themselves will be in arbitrary order. Like collectAll(), collectN() moves in the input Futures, so your copies are no longer valid. If multiple input futures complete "simultaneously" or are already completed, winners are chosen but the choice is undefined.

@@ -609,7 +609,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
 
unorderedReduce() #

 
-
Like reduce(), but consumes Futures in the collection as soon as they become ready. Use this if your function doesn't depend on the order of the Futures in the input collection. See the tests for examples.

+
Like reduce(), but consumes Futures in the collection as soon as they become ready. Use this if your function doesn't depend on the order of the Futures in the input collection. See the tests for examples.

 
 
window() #

 
@@ -617,7 +617,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
 
It ensures that at any given time, no more than n Futures are being processed.

 
-
Combine with collectAll, reduce or unorderedReduce. See the tests for examples.

+
Combine with collectAll, reduce or unorderedReduce. See the tests for examples.

 
 
Other Possibilities #

 
@@ -633,7 +633,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
So what's the catch? Let's look at the following example of multithreaded Futures code:

 
 
// Thread A
-Promise<void> p;
+Promise<Unit> p;
 auto f = p.getFuture();
 
 // Thread B
@@ -646,16 +646,18 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
 
via() to the rescue #

 
-
Futures have a method called via() which takes an Executor. Executor is a simple interface that requires only the existence of an add(std::function<void()> func) method which must be thread safe and must execute the provided function somehow, though not necessarily immediately. via() guarantees that a callback set on the Future will be executed on the given Executor. For instance:

+
Futures have a method called via() which takes an Executor. Executor is a simple interface that requires only the existence of an add(std::function<void()> func) method which must be thread safe and must execute the provided function somehow, though not necessarily immediately. via() guarantees that a callback set on the Future will be executed on the given Executor. For instance:

 
-
makeFuture()
-  .then(x)
+
makeFutureWith(x)
   .via(exe1).then(y)
   .via(exe2).then(z);

 
 
In this example, y will be executed on exe1, and z will be executed on exe2. This is a fairly powerful abstraction. It not only solves the above race, but gives you clear, concise, and self-documenting control over your execution model. One common pattern is having different executors for different types of work (e.g. an IO-bound pool spinning on event bases doing your network IO and a CPU-bound thread pool for expensive work) and switching between them with via().

 
-
There is also a static function via() that creates a completed Future<void> that is already set up to call back on the provided Executor.

+
There is also a static function via() that creates a completed Future<Unit> that is already set up to call back on the provided Executor, and via(Executor&,Func) returns a Future for executing a function via an executor.

+
+
via(exe).then(a);
+via(exe, a).then(b);

 
 
Or, pass an Executor to then() #

 
@@ -668,7 +670,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
    
 
  • ThreadPoolExecutor is an abstract thread pool implementation that supports resizing, custom thread factories, pool and per-task stats, NUMA awareness, user-defined task expiration, and Codel task expiration. It and its subclasses are under active development. It currently has two implementations:
    • 
 
  • folly's EventBase is an Executor and executes work as a callback in the event loop
    • 
 
  • ManualExecutor only executes work when manually cranked. This is useful for testing.
    • 
@@ -676,29 +678,32 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
  • QueuedImmediateExecutor is similar to InlineExecutor, but work added during callback execution will be queued instead of immediately executed
    • 
 
  • ScheduledExecutor is a subinterface of Executor that supports scheduled (i.e. delayed) execution. There aren't many implementations yet, see T5924392
    • 
 
  • Thrift's ThreadManager is an Executor but we aim to deprecate it in favor of the aforementioned CPUThreadPoolExecutor
    • 
-
  • FutureExecutor wraps another Executor and provides Future<T> addFuture(F func) which returns a Future representing the result of func. This is equivalent to via(executor).then(func) and the latter should probably be preferred.
    • 
+
  • FutureExecutor wraps another Executor and provides Future<T> addFuture(F func) which returns a Future representing the result of func. This is equivalent to futures::async(executor, func) and the latter should probably be preferred.
    •

Timeouts and related features

Futures provide a number of timing-related features. Here's an overview.

Timing implementation #

Timing resolution #

The functions and methods documented below all take a Duration, which is an alias for std::chrono::milliseconds. Why not allow more granularity? Simply put, we can't guarantee sub-millisecond resolution and we don't want to lie to you.

+

Do not use the Duration type directly, that defeats the point of using a std::chrono::duration type. Rather, use the appropriate std::chrono::duration, e.g. std::chrono::seconds or std::chrono::milliseconds.

+

The TimeKeeper interface #

-

Most timing-related methods also optionally take a default implementation uses a folly::HHWheelTimer in a dedicated EventBase thread to manage timeouts.

+

Most timing-related methods also optionally take a TimeKeeper. Implement that interface if you'd like control over how Futures timing works under the hood. If you don't provide a TimeKeeper, a default singleton will be lazily created and employed. The default implementation uses a folly::HHWheelTimer in a dedicated EventBase thread to manage timeouts.

within() #

Future<T>::within() returns a new Future that will complete with the provided exception (by default, a TimedOut exception) if it does not complete within the specified duration. For example:

-
Future<int> foo();
+
using std::chrono::milliseconds;
+Future<int> foo();
 
 // f will complete with a TimedOut exception if the Future returned by foo()
 // does not complete within 500 ms
-f = foo().within(Duration(500));
+f = foo().within(milliseconds(500));
 
 // Same deal, but a timeout will trigger the provided exception instead
-f2 = foo().within(Duration(500), std::runtime_error("you took too long!"));

+f2 = foo().within(millseconds(500), std::runtime_error("you took too long!"));

onTimeout() #

@@ -706,7 +711,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac 
Future<int> foo();
 foo()
-  .onTimeout(Duration(500), []{
+  .onTimeout(milliseconds(500), []{
     // You must maintain the resultant future's type
     // ... handle timeout ...
     return -1;
@@ -716,7 +721,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
The astute reader might notice that this is effectively syntactic sugar for

 
 
foo()
-  .within(Duration(500))
+  .within(milliseconds(500))
   .onError([](const TimedOut& e) {
     // handle timeout
     return -1;
@@ -730,19 +735,19 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
Future<int> foo();
 // Will throw TimedOut if the Future doesn't complete within one second of
 // the get() call
-int result = foo().get(Duration(1000));
+int result = foo().get(milliseconds(1000));
 
 // If the Future doesn't complete within one second, f will remain
 // incomplete. That is, if a timeout occurs, it's as if wait() was
 // never called.
-Future<int> f = foo().wait(Duration(1000));

+Future<int> f = foo().wait(milliseconds(1000));

 
 
delayed() #

 
 
Future<T>::delayed() returns a new Future whose completion is delayed for at least the specified duration. For example:

 
 
makeFuture()
-  .delayed(Duration(1000))
+  .delayed(milliseconds(1000))
   .then([]{
     // This will be executed when the original Future has completed or when
     // 1000ms has elapsed, whichever comes last.
@@ -750,9 +755,9 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac
 
 
futures::sleep() #

 
-
sleep() returns a void Future that will complete after the specified duration. For example:

+
sleep() returns a Future<Unit> that will complete after the specified duration. For example:

 
-
futures::sleep(Duration(1000)).then([]{
+
futures::sleep(milliseconds(1000)).then([]{
   // This will be executed after 1000ms
 });

Interrupts and Cancellations

Interrupts are a mechanism for Future holders to send a signal to Promise holders. Here's how to use them.

Let's say that your Futures code kicks off some long, expensive operation in another thread. A short while later, something comes up that obviates the need for the result of that operation. Are those resources gone forever? Not necessarily. Enter interrupts.

@@ -794,7 +799,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac 
EXPECT_TRUE(isPrime(7).value());
 EXPECT_FALSE(isPrime(8).value());
-

But what if isPrime() is asynchronous (e.g. makes an async call to another service that computes primeness)? It's now likely that you'll call value() before the Future is complete, which will throw a FutureNotReady exception.

+

But what if isPrime() is asynchronous (e.g. makes an async call to another service that computes primeness)? It's now likely that you'll call value() before the Future is complete, which will throw a FutureNotReady exception.

A naive approach is to spin until the Future is complete:

@@ -825,7 +830,7 @@ Although inspired by the C++11 std::future interface, it is not a drop-in replac

getVia() and waitVia() #

-

T Future<T>::getVia(DrivableExecutor*) and Future<T> Future<T>::waitVia(DrivableExecutor*) have the same semantics as get() and wait() except that they drive some Executor until the Future is complete. ManualExecutor. These are simple but useful sugar for the following common pattern:

+

T Future<T>::getVia(DrivableExecutor*) and Future<T> Future<T>::waitVia(DrivableExecutor*) have the same semantics as get() and wait() except that they drive some Executor until the Future is complete. DrivableExecutor is a simple subinterface of Executor that requires the presence of a method drive() which can somehow make progress on the Executor's work. Two commonly helpful implementations are EventBase (where drive() loops on the EventBase) and ManualExecutor. These are simple but useful sugar for the following common pattern:

Given this:

@@ -959,12 +964,12 @@ if you are really sure you need to get more fancy, put on your wizard hat and go

Monads must also satisfy these three axioms:

-
-- Left Identity
-unit a `bind` f ≡ f a
--- Right Identity
-m `bind` unit ≡ m
--- Associativity
-(m `bind` f) `bind` g ≡ m `bind` (\x -> f x `bind` g)
+
-- Left Identity
+unit a `bind` f ≡ f a
+-- Right Identity
+m `bind` unit ≡ m
+-- Associativity
+(m `bind` f) `bind` g ≡ m `bind` (\x -> f x `bind` g)

I won't try to explain that, there are many blog posts and wiki pages that try to do that. Instead, I'll substitute the equivalent Future monad expressions, and the whole thing will (probably) start to make sense. First, a simplified Future type:

@@ -1014,30 +1019,34 @@ m `bind` unit ≡ m

If "associative" doesn't look associative to you, then you are very astute. Congratulations! You win a maths unicorn. The three laws refer to a different formulation of the axioms, in terms of the Kleisli Composition operator (>=>), which basically says compose two monad-making functions in the obvious way.

-
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
+
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
 
--- Left Identity
-unit >=> g ≡ g
--- Right Identity
-f >=> unit ≡ f
--- Associativity
-(f >=> g) >=> h ≡ f >=> (g >=> h)

+-- Left Identity
+unit >=> g ≡ g
+-- Right Identity
+f >=> unit ≡ f
+-- Associativity
+(f >=> g) >=> h ≡ f >=> (g >=> h)

We accidentally implemented this operator, and called it chain. Then we removed it in favor of Future::thenMulti. But it totally existed, so use your imagination:

-
// Left Identity
-chain(makeFuture, g) ≡ g
-// Right Identity
-chain(f, makeFuture) ≡ f
-// Associativity
-chain(chain(f, g), h) ≡ chain(f, chain(g, h)) // and chain(f, g, h)
+
// Left Identity
+chain(makeFuture, g) ≡ g
+// Right Identity
+chain(f, makeFuture) ≡ f
+// Associativity
+chain(chain(f, g), h) ≡ chain(f, chain(g, h)) // and chain(f, g, h)

Further reading #

FAQ

Why not use std::future? #

+

FAQ

What's this Unit thing? I'm confused. #

+ +

If your callback returns void, it will result in a Future<Unit>. Future<void> is illegal. All you need to know is, if you would expect a Future<void> or Promise<void> or Try<void>, type Unit instead of void.

+ +

Why not use std::future? #

No callback support. See also http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3428.pdf

@@ -1057,9 +1066,8 @@ chain(chain(f, g), h) ≡ chain(f, chain(g, h)) // and chain(f, g, h)

People mean two things here, they either mean using continuations (as in CSP) or they mean using generators which require continuations. It's important to know those are two distinct questions, but in our context the answer is the same because continuations are a prerequisite for generators.

-

C++ doesn't directly support continuations very well. But there are some ways to do them in C/C++ that rely on some rather low-level facilities like setjmp and longjmp (among others). So yes, they are possible (cf. Mordor and [[folly/experimental/fibers| -https://github.com/facebook/folly/tree/master/folly/experimental/fibers]]).

+

C++ doesn't directly support continuations very well. But there are some ways to do them in C/C++ that rely on some rather low-level facilities like setjmp and longjmp (among others). So yes, they are possible (cf. Mordor and folly/experimental/fibers).

The tradeoff is memory. Each continuation has a stack, and that stack is usually fixed-size and has to be big enough to support whatever ordinary computation you might want to do on it. So each living continuation requires a relatively large amount of memory. If you know the number of continuations will be small, this might be a good fit. In particular, it might be faster, the code might read cleaner, and debugging stack traces might be much easier.

-

Futures takes the middle road between callback hell and continuations, one which has been trodden and proved useful in other languages. It doesn't claim to be the best model for all situations. Use your tools wisely.

+

Futures takes the middle road between callback hell and continuations, one which has been trodden and proved useful in other languages. It doesn't claim to be the best model for all situations. Use your tools wisely.

\ No newline at end of file -- 2.34.1