Motivation

Last week we were discussing, among many other things, ways to speed up Firefox during startup. One obvious option was to move more of our I/O off of the main thread. This in turn involves making more code asynchronous, and asynchronous code is simply harder to manage. Mike Shaver mentioned something about "futures" as a possible way to handle the extra complexity, and then the discussion moved on to something else.

What exactly is a future anyway?

I'm not exactly an expert, but I've not just used futures, I've written my own implementations in JavaScript and even Object Pascal (in hindsight I'm not sure the latter was a good idea, but it was certainly an interesting exercise). Futures seem esoteric, but they really shouldn't be -- the idea is really quite simple. In this post I'll try to explain what futures are and how they can be used to make asynchronous programming easier.

In the simplest form, a future works like an IOU. I can't give you the money you've asked for right now, but I can give you this IOU. At some point in the future, you can give me the IOU and I'll give you the money -- if I have it. If I don't have it yet, then you can wait until I do. I get paid on Friday.

Alternatively there's the dry cleaner metaphor. You drop your clothes off on Monday and the clerk gives you a ticket that you can use later to reclaim your clothes after they've been cleaned. The clothes will be ready on Tuesday morning, but if you show up too early, you'll have to wait. On the other hand, if there's no hurry, you can just do other stuff on Tuesday and show up on Wednesday with a reasonable expectation that they'll be ready when you arrive. You'll just hand your ticket over, collect your clothes, and be on your way.

A future is similar to the IOU (or the dry cleaning ticket). It gives you a way to represent the result of a computation that has not yet completed, and it allows you to access that result once it becomes available. So you can call a function which starts some asynchronous process but doesn't wait for it to finish. Nevertheless the function can return you a useful result: a future which can be used to claim the real result later.

A simple example

Of course if you ask for the result too soon, you'll have to wait. On the other hand, if the result becomes available before you want it, then it will wait for you.

Here's an example of what this might look like in pseudo-JavaScript:

function doStuff() {

var cleanClothesFuture = dryCleaner.dropOff(dirtyClothes);

runErrands();

work();

eat();

watchTv();

sleep();

var cleanClothes = cleanClothesFuture.get(); // block if the result is not ready yet

}

Compare this to the traditional way we'd handled this in JavaScript, using a callback:

var cleanClothes = null;

function doStuff() {

dryCleaner.dropOff(dirtyClothes, function (clothes) { cleanClothes = clothes; });

runErrands();

work();

eat();

watchTv();

sleep();

}

A more complicated example

These examples are not one hundred percent semantically identical, but they should be close enough to illustrate the point. I contend that the first function is easier to write, easier to read, and easier to reason about. I also contend that the difference isn't enough to get excited about. It's when things get more complicated that futures become really useful.

Imagine that I have a web page that sends an AJAX request to a server and then displays the results in an IFRAME -- and furthermore does it automatically on page load. I have to wait for both the AJAX request to return data and for the IFRAME to finish loading -- only then can I display the results. This can be done fairly simply using callbacks:

function showData(dataUrl, iframeUrl) {

var data = null;

var iframeBody = null;

tryToShowData

{ if (data && iframeBody) { showDataInIframe(data, iframeBody); } }

requestDataFromServer(dataUrl, function (response) {data = response.data; tryToShowData() });

insertIframeBody(iframeUrl, function (iframeDoc) {iframeBody = iframeDoc.body; tryToShowData() });

}

Now, imagine the same thing done with futures:

function showData(dataUrl, iframeUrl) {var dataFuture = requestDataFromServer(dataUrl);var iframeBodyFuture = insertIframeBody(iframeUrl);showDataInIframe(dataFuture.get(), iframeBodyFuture.get());

callAsap

callAsap()

Again, these two examples are not semantically equivalent -- notably there's no blocking in the first example. Now let's imagine that we had a way to turn an ordinary function into a new function which takes futures as arguments and which returns a future in turn. As soon as all the future arguments became available, the base function would be called automatically -- and once the base function completed, its result would be accessible through the future returned earlier. I'll call this capability "": call a function as soon as possible after all of its future arguments become available. Using, the previous example might be rewritten as:

function showData(dataUrl, iframeUrl) {

var dataFuture = requestDataFromServer(dataUrl);

var iframeBodyFuture = insertIframeBody(iframeUrl);

showDataInIframe.callAsap(dataFuture, iframeBodyFuture);

}

showDataInFrame

callAsap()

In this case we don't care about the return value for. This example is much closer in behavior to the earlier callback-based example. In fact, themethod would be implemented with callbacks underneath, but they would all be nicely abstracted away under the hood.

callAsap()

One of the nice things aboutis that it can nicely handle cases where you are waiting on more than one future. Imagine that you've asynchronously requested data from two different servers:

function showData(dataUrl1, dataUrl2, iframeUrl) {

var dataFuture1 = requestDataFromServer(dataUrl1);

var dataFuture2 = requestDataFromServer(dataUrl2);

showDataInIframe.callAsap(dataFuture1, dataFuture2, iframeBodyFuture);

}

Arrays of futures

This segues nicely into the next topic: Arrays of futures.

Imagine if you have not one, or two, or three futures, but rather an arbitrary number of futures. What we'd really like to have is a way to take an array of futures and produce from it a single future for an array of concrete values. Something like:

function showData(dataUrlArray, iframeUrls) {

// The "dataFutureArray" is a concrete array of futures.

var dataFutureArray = requestDataFromServers(dataUrlArray);

// The "dataArrayFuture" is a future for a concrete array of concrete values.

Future.createArrayFuture(dataFutureArray);

showDataInIframe.callAsap(dataArrayFuture, iframeBodyFuture);

}

var dataArrayFuture =

An advanced example

What this example might look like rewritten in callback style is left as an exercise to the reader.

OK, now for a more elaborate example. Imagine a function which retrieves the first page of Google search results for a particular query, and then goes through and re-orders the results based on its own ranking system. Furthermore, imagine that this ranking is computed based on the contents of each web page. We'll need to to make requests to many different servers for many different web pages. This will be fastest if we issue all the requests at once.

function search(query) {

// Take a concrete search result and return a future to a

// [searchResult, ranking] pair.

function requestWebPageAndRanking(searchResult) {

var webPageFuture = requestWebPage(searchResult.url);

var rankingFuture = computeRankingFromContent.callAsap(webPageFuture);

return Future.createArrayFuture([webPageFuture, relevanceFuture]);

}

// Take a concrete array of search results and return a future to

// an array of [searchResult, ranking] pairs, sorted by ranking.

function requestSearchResultsSortedByRanking(searchResultArray) {

var

rankingArrayFuture

=

Future.createArrayFuture(

[requestWebPageAndRanking(searchResult) for (searchResult in searchResultArray)]

);

return sortArraysByKeyIndex.callAsap(

rankingArrayFuture

, 1);

}

// Request search results, re-rank them, and then display them.

var searchResultArrayFuture = requestGoogleResults(query);

var

sortedRankingArrayFuture =

requestSearchResultsSortedByRanking

.callAsap(searchResultArrayFuture);

showSearchResults

.callAsap(sortedRankingArrayFuture);

}

In all fairness, this is not as simple as a synchronous blocking implementation. Keeping your arrays of futures and futures of arrays straight is a little bit taxing. Imagine what a callback model might look like, however, with callbacks inside callbacks. One advantage of using futures is that you can often write traditional blocking code and then in straightforward fashion translate that code into asynchronous code using futures.

Notes, in no particular order