Does Lwt utilise data dependencies to increase paralleism

Question

I'm trying to work out what specifically lwt is doing in a couple of examples:

If I have:

let%lwt x = f () in
let%lwt y = g () in
return ()

Does this run f then g, or since y doesn't rely on x will it run both in parallel?

Answer 1

In your code, no, because you are using Lwt.t as monad, rather than as an applicative.

Monads

You're probably already familiar with asynchronous IO and the functions Lwt.bind : 'a Lwt.t -> ('a -> 'b Lwt.t) -> 'b Lwt.t and Lwt.return : 'a -> 'a Lwt.t. Just in case, though, I will give a brief recap:

• Lwt.bind promise callback awaits promise, and upon resolution, calls callback with the result, getting back another promise.
• Lwt.return data creates a promise that resolves to data.

A monad is a generic type 'a t that has some function bind : 'a t -> ('a -> 'b t) -> 'b t and some function return : 'a -> 'a t. (These functions must also follow certain laws, but I digress.) Obviously, the type 'a Lwt.t with the functions Lwt.bind and Lwt.return form a monad.

Monads are a common functional programming pattern when one wants to represent some kind of "effect" or "computation," in this case asynchronous IO. Monads are powerful because the bind function lets later computations depend on the results of earlier ones. If m : 'a t represents some computation that results in 'a, and f : 'a -> 'b t is a function that uses an 'a to perform a computation that results in a 'b, then bind m f makes f depend on the result of m.

In the case of Lwt.bind promise callback, callback depends on the result of promise. The code in callback cannot run until promise is resolved.

When you write

let%lwt x = f () in
let%lwt y = g () in
return ()

you are really writing Lwt.bind (f ()) (fun x -> Lwt.bind (g ()) (fun y -> return ())). Because g () is inside the callback, it is not run until f () is resolved.

Applicatives

A functional programming pattern related to the monad is the applicative. An applicative is a generic type 'a t with a function map : ('a -> 'b) -> 'a t -> 'b t, the function return : 'a -> 'a t, and a function both : 'a t * 'b t -> ('a * 'b) t. Unlike monads, however, applicatives need not have bind : 'a t -> ('a -> 'b t) -> 'b t, meaning that with applicatives alone, later computations cannot depend on previous ones. All monads are applicatives, but not all applicatives are monads.

Because g () does not depend on the result of f (), your code can be rewritten to use both:

let (let*) = bind
let (and*) = both

let* x = f ()
and* y = g () in
return ()

This code translates to bind (fun (x, y) -> return ()) (both (f ()) (g ())). f () and g () appear outside the callback to bind, meaning that they are run immediately and can await in parallel. both combines f () and g () into a single promise.

The (let*) and (and*) operators are new to OCaml 4.08. If you are using an earlier version of OCaml, you can just write the translation directly.

• Lwt.both in the documentation
• The Lwt home page contains a code snippit using let* and and*
• "Binding operators" (let* and and*) in the OCaml manual

Answer 2

That particular example runs f () and g () in sequence, i.e. g () doesn't start until after the promise returned by f () is resolved.

The way to see this is, when looking at

let%lwt x = e in
e'

to realize that e' becomes the body of a callback, that will run only when x is available. So, in the code in the question, Lwt first sees:

(* Do this first. *)
let%lwt x = f () in

(* Do this once is available. *)
let%lwt y = g () in
return ()

and, once x is available, it is left with

(* Do this next. *)
let%lwt y = g () in

(* Do this once y is available. *)
return ()

To avoid this serialization, call f () and g () first, without any intervening let%lwt, bind variables to the promises x', y' these functions return, and wait on the promises:

let x' = f () in
let y' = g () in
let%lwt x = x' in
let%lwt y = y' in
return ()

(And to answer the title, Lwt does not use data dependencies. I don't think a library could have access to this kind of data dependency information).