Flexible Scheduling of JavaScript Promises

• Download source - 6.6 KB

Introduction

Promises in JavaScript are useful for handling many asynchronous tasks. The standard functions Promise.prototype.then() and Promise.all() are used for scheduling tasks that are to be executed sequentially and in parallel fashion, respectively.

Suppose, however, that we are to perform many asynchronous tasks, some of which depend on others. In this case, Promise.all() will not work because of the interdependencies, and Promise.prototype.then() will be highly inefficient because we will be executing tasks sequentially when that is unnecessary.

In this article, we present a simple function that handles the general case of optimal scheduling of a network of interdependent JavaScript promises (i.e., a directed acyclic graph of asynchronous tasks and dependencies between them).

Background: Promise.prototype.then() and Promise.all()

The JavaScript language provides built-in mechanisms to combine multiple asynchronous tasks into a single promise. We discuss two of them.

Promise.prototype.then()

Perhaps the most important way of combining promises is by using Promise.prototype.then() [reference]. It allows one promise to be chained to another, so that the two asynchronous tasks are executed sequentially.

One can use then() to form longer chains of sequentially executed asynchronous tasks. The output of one will be fed as input to the next. Here's an example of promise chaining:

// promise that resolves after t milliseconds
// with no value
function sleep(t) {
	return new Promise((resolve, reject) => {
		setTimeout(() => {
			console.log("resolved", t);
			resolve();
		}, t);
	});
}

sleep(3000)
.then((value) => { return sleep(2000); })
.then((value) => { return sleep(1000); })
.then((value) => { console.log("done!"); });

In a picture, this is what Promise.prototype.then() is used for:

Promise.all()

Another way of combining promises is using Promise.all() [reference]. It allows one to create a promise out of a list (well, iterable) of promises that:

• gets rejected as soon as one of the supplied promises gets rejected
• gets resolved when all of the supplied promises have resolved

In particular, all of the supplied promises represent tasks that are run in parallel. Here's an example of the use of Promise.all():

// promise that resolves after t milliseconds
// with no value
function sleep(t) {
	return new Promise((resolve, reject) => {
		setTimeout(() => {
			console.log("resolved", t);
			resolve();
		}, t);
	});
}

Promise.all([sleep(3000), sleep(2000), sleep(1000)])
.then((value) => { console.log("done!"); })

In a picture, this is what Promise.all() is used for:

Generalizing: Directed Acyclic Graphs of Tasks

The function we write in this article generalizes both chaining of promises (using Promise.prototype.then()) and simultaneous execution of promises (using Promise.all()). It allows the efficient execution of a network of tasks, or if you want, of a dependency graph of tasks. In other words, the function we're writing is suited for the above kinds of situations, but also for this one:

Function Arguments

We will call the function promiseDAG() (DAG stands for directed acyclic graph). It will look like this:

function promiseDAG(callbacks, dag) {
    ...
}

The supplied arguments are:

• callbacks: a list of functions, each of which returns a promise when called
  These are the asynchronous tasks that we want to execute, and they are the nodes in the directed acyclic graph.
• dag: a list of lists, specifying the interdependencies between the tasks
  These specify the edges in the directed acyclic graph (and they determine which arguments will be supplied to the callbacks).

If n callbacks are provided, then dag should be a list of n lists of integers. The i'th of these lists should be a list of indices into callbacks, specifying on which tasks the i'th one depends. For example, if dag[i] contains the integer j, then the directed acyclic graph has an edge from the j'th tasks to the i'th task.

The network shown above is executed by doing the following:

// each of these should return a promise that executes the task
function task0() {
	return ...
}
function task1(value0) {
	return ...
}
function task2(value0) {
	return ...
}
function task3(value1, value2) {
	return ...
}
function task4(value2) {
	return ...
}

var p = promiseDAG([task0, task1, task2, task3, task4], [[], [0], [0], [1,2], [2]]);

Function Behavior

When promiseDAG() is called, any tasks that have no incoming edges (i.e., that don't depend on other tasks) are started. Whenever a task completes, any tasks that have all of their prerequisites completed are now started. The arguments that are supplied to a callback are precisely the values that its prerequisites resolved with, in the same order as they were specified in dag.

Note. When a JavaScript function gets called with more arguments than it accepts, the superfluous arguments are silently ignored. This means that if taskB depends on taskA, but doesn't need to know the value that taskA resolved with, you can just indicate the dependency in the directed acyclic graph, but write taskB() as a function without arguments.

When all tasks have been completed successfully, the promise returned by promiseDAG() gets resolved. The value of the returned promise is then a list of the same length as callbacks, containing the returned values of all the resolved promises of the tasks, in order.

As soon as any of the tasks fail, the promise returned by promiseDAG() gets rejected. The error will be the same one that the failed task got rejected with. No new tasks will be started anymore (although the tasks that are currently running will continue to run, since there is no way to cancel a pending promise).

Inner Workings of the Function

Let's go over the internals of promiseDAG(). The function is structured as follows:

function promiseDAG(callbacks, dag) {
    return new Promise((resolve, reject) => {
        var N = callbacks.length;
        var counts = dag.map((x) => x.length);
        // extra variables here

        function handleResolution(promise, i, value) {
            ...
        }

        function handleRejection(promise, i, error) {
            ...
        }

        // start all tasks that have no incoming arrows
        for(let i=0; i<N; ++i) {
            if(counts[i] > 0) {
                continue;
            }
            var promise = callbacks[i]();
            promise.then(
                (value) => { handleResolution(promise, i, value); },
                (error) => { handleRejection(promise, i, error); });
        }
    });
}

The function handleResolution() will register the value that a promise resolved with, and starts any promises that now have their prerequisites satisfied (unless a promise had already been rejected earlier, in which case no new tasks are started).

The function handleRejection() will simply reject the promise that was constructed by promiseDAG(), passing on the error unmodified.

Using the Code: An Example

Suppose you’re running a website with a video of the day. When a user visits the site, the following things need to happen:

1. Log in the user
2. Fetch the user’s settings
3. Parse the user’s settings into JSON
4. Load the video of the day (which is only available to registered users)
5. Change the page’s background color according to the user’s settings
6. Play the video, if the user has auto-play enabled

The tasks and their interdependencies are illustrated here:

Here is how to use promiseDAG() for this graph of tasks:

function login() {
	return ... // a promise that resolves to the username on successful login
}

function fetchSettings(username) {
	return fetch('./settings/' + username, {method: 'get'});
}

// the argument received here is a Response from fetch
function parseSettings(settings) {
	return settings.json();
}

// ignore the username argument, since we don't need it
function loadVideo() {
	return new Promise((resolve, reject) => {
		var video = document.createElement("video");
		video.addEventListener("canplay", resolve(video)); // resolve when ready to play
		video.src = "video.mp4";
	});
}

// the argument received here is the settings as JSON
async function setBackground(settings) {
	document.body.style.background = settings.favoritecolor;
}

async function play(video, settings) {
	if(settings.autoplay) {
		video.play();
	}
}

promiseDAG([login,         // 0
            fetchSettings, // 1
            parseSettings, // 2
            loadVideo,     // 3
            setBackground, // 4
            play,          // 5
            ],
           [[],
            [0],
            [1],
            [0],
            [2],
            [3,2], // match order of arguments
            ]);

Updates & Demo

I wrote this code a while ago when I was learning about JavaScript promises. Besides being available for download with this article, it is hosted on GitHub.

There is a demo page using promiseDAG() here. It graphically shows a directed acyclic graph of promises (which in this case are simple timeouts), and their status. The demo code is also included with this article.