package par_incr

  1. Overview
  2. Docs

Module Par_incrSource

A simple library for parallel incremental computations. Based on "Efficient Parallel Self-Adjusting Computation".

How it works

  • Define Var.t with certain values.
  • Perform Var.watch operation on Var.t and change it to incremental.
  • Every incremental signifies a computation in itself.
  • Use different combinators provided by the library on the incrementals and make even bigger incrementals.
  • Obtain value of a certain incremental by running it (a run operation is provided by the library).
  • Running an 'a incremental returns a 'a computation.
  • When we change some Var.t (done with Var.set operation), it marks all dependent computations dirty.
  • Running propagate operation on a dirty computation updates its value efficiently.
  • Destroy (with destroy_comp operation) computation when its no more required.

Par_incr Module Documentation

Sourcetype 'a t

A 'a t holds a value of type 'a. This type is opaque and we don't expose any mechanism to change this or modify it. Computations happens by chaining together various combinators provided by the library, all of which operate on 'a t.

Sourcetype 'a incremental := 'a t

Type 'a incremental is an alias for 'a t.

Sourcetype 'a computation

A 'a computation holds everything necessary to store a computation.

Sourcetype executor = {
  1. run : 'a. (unit -> 'a) -> 'a;
  2. par_do : 'a 'b. (unit -> 'a) -> (unit -> 'b) -> 'a * 'b;
}

An executor is something that has to be passed while initially running the computation. The reason behind this is, we want to support multiple ways to run computations in parallel and library users can use the one that is best for them.

Suppose you have your own scheduler built on top of Domains and you don't want to use Domainslib for running tasks. You can very well use it as long as you provide these two run and par_do functions.

If however you want to use Domainslib, you would have an executor which would look roughly like this:

module T = Domainslib.Task
let pool = T.setup_pool ~num_domains:(Domain.recommended_domain_count () / 2) ()
let par_runner f = T.run pool f
let par_do l r =
  let lres = T.async pool l in
  let rres = r () in
  (T.await pool lres, rres)
let executor = {run = par_runner; par_do}
Sourcemodule Cutoff : sig ... end
Sourcemodule Var : sig ... end

Defines the type and various operations for modifiable values.

Sourceval return : 'a -> 'a t

return x returns an instance of 'a incremental from x of type 'a.

Sourceval map : ?cutoff:'b Cutoff.t -> fn:('a -> 'b) -> 'a t -> 'b t

map ~fn a maps the internal value of a to fn. Default cutoff is Phys_equal.

Sourceval map2 : ?cutoff:'c Cutoff.t -> ?mode:[ `Par | `Seq ] -> fn:('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

map2 ~fn ?(mode=`Seq) a b is a convenient function to map over two incrementals. If mode is `Seq, it computes a and b sequentially, but if it is `Par, computing a and b happens in parallel (it's ran with executors par_do function). Default cutoff is Phys_equal.

Sourceval combine : 'a t -> 'b t -> ('a * 'b) t

combine a b is useful function to combine two incremental's into one.

Sourceval bind : fn:('a -> 'b t) -> 'a t -> 'b t

bind ~fn a calls fn with the value of a and returns that. This lets us build computations that are more dynamic in nature. This is the monadic bind operation for incrementals.

Sourceval par : left:'a t -> right:'b t -> ('a * 'b) t

par ~left:a ~right:b computes a and b in parallel and gives us the result as a new incremental with both values stored as tuple. This uses executors par_do function to run left and right in parallel.

Sourceval delay : (unit -> 'a t) -> 'a t

delay f lets us have incrementals that are lazily evaluated.

Sourceval value : 'a computation -> 'a

value c returns the value/result associated with the computation c.

Sourceval run : executor:executor -> 'a t -> 'a computation

run ~executor t evaluates t with the provided executor. This stores the result of the computation as well as all the data structures associated with it.

Sourceval propagate : 'a computation -> unit

propagate c will propagate the changes to all the Var.t that the computation c depended on. If there are no changes, it will not do any extra work and returns back right away.

Sourceval dump_tree : string -> 'a computation -> unit

dump_tree file c will dump the computation tree associated with c into file. It dumps the tree in D2 format. See the instructions for viewing the files.

Sourceval destroy_comp : 'a computation -> unit

destroy_comp c will destroy the computation associated with c. After destroying, calling propagate on c will result in an exception. It's necessary to destroy computations that are no longer needed. A computation will be taking up memory and doing unnecessary work if not destroyed.

Sourcemodule Debug : sig ... end
Sourcemodule Syntax : sig ... end

Introduces some convenient operators for map, bind, combine and par operations.