matthewhammer

Demand-driven change propagation

If you have a DAG where for each node, you have some local computation (internal to the node) and some external dependencies (other nodes in the DAG that I’ll call the “successors”) and some dependents (other DAG nodes that I’ll call the “predecessors”) then we can consider doing change propagation over this via Adapton’s demand-driven algorithm:

— Dirty the graph (perhaps in parallel) when a reference cell (e.g., input cell) changes, by traversing all dependent (predecessor) edges and marking them dirty. An invariant is that if an edge is dirty, all preceding edges are dirty too, so we can stop dirtying early.

— Clean the graph on demand (of a node in the DAG) by traversing its successor edges that are dirty, until we reach a node that depends directly on a changed input. Re-evaluate that node. If its return value changes, then we need to re-evaluate its predecessors, and so on. Change propagation here is demand-driven, and follows the original order of execution (fo

matthewhammer

825166bc46 (HEAD -> master) HEAD@{0}: rebase finished: returning to refs/heads/master
825166bc46 (HEAD -> master) HEAD@{1}: rebase: -Z profile-queries: compute 'self' duration; order final summary by 'self' duration, not 'total' duration
763e8ba4b0 HEAD@{2}: rebase: -Z profile-query-and-key, separate from -Z profile-query; query key is string option
40e26f2776 HEAD@{3}: rebase: -Z profile-queries includes dep_graph.with_task uses in output
06be62b0bb HEAD@{4}: rebase: count timed passes in totals; minor CSS stuff
adf3845811 HEAD@{5}: rebase: -Z profile-queries: remove panic when channel is unset
8591d0dc3f HEAD@{6}: rebase: profiling with -Z profile-queries recognizes -Z time-passes
0148826367 HEAD@{7}: rebase: tidy: trailing ws
f723e016d2 HEAD@{8}: rebase: comments from @michaelwoerister
9615098a94 HEAD@{9}: rebase: clean up and fixes, thanks to comments from @kennytm; moved dump logic to profile mod

matthewhammer

4dfdd3d3fc HEAD@{0}: reset: moving to HEAD~10
d105172a10 HEAD@{1}: rebase -i (finish): returning to refs/heads/master
d105172a10 HEAD@{2}: rebase -i (start): checkout refs/remotes/origin/master
d105172a10 HEAD@{3}: rebase: aborting
580ab1ef6f HEAD@{4}: rebase -i (pick): Update release notes for 1.19.0
4545f18562 HEAD@{5}: rebase -i (pick): Allow remote testing remotely when `TEST_DEVICE_ADDR` is set
814f1ea446 HEAD@{6}: rebase -i (pick): Add empty MIR pass for non-lexical lifetimes
d573b9605a HEAD@{7}: rebase -i (pick): Fix checking for missing stability annotations
773ace032f HEAD@{8}: rebase -i (pick): explanatory error on `--print target-spec-json` without unstable options
06f7c0df4c HEAD@{9}: rebase -i (pick): reorder span labels

matthewhammer

error[E0275]: overflow evaluating the requirement `rustc::ty::ExistentialPredicate<'_>: std::marker::Sync`
   --> src/librustc_driver/driver.rs:968:13
    |
968 |             thread::spawn(move||profile_queries_thread(rx));
    |             ^^^^^^^^^^^^^
    |
    = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
    = note: required because it appears within the type `[rustc::ty::ExistentialPredicate<'_>]`
    = note: required because it appears within the type `rustc::ty::Slice<rustc::ty::ExistentialPredicate<'_>>`
    = note: required because it appears within the type `&rustc::ty::Slice<rustc::ty::ExistentialPredicate<'_>>`

matthewhammer

#[macro_use] 
extern crate adapton;

use adapton::macros::*;
use adapton::engine::*;

fn main() {

    manage::init_dcg();

matthewhammer

(* The 'Name Term' sublanguage of Typed Adapton. *)
(* See: https://arxiv.org/pdf/1610.00097v2.pdf
        Figure 6 (top) 
    and Figure 8 (top) 
*)

Inductive sort : Set := 
  | Arr  : sort -> sort -> sort
  | Nm   : sort
  | Prod : sort -> sort -> sort

matthewhammer

Will, Dakota, Allan
20161026 -- Wed

Q: Why clean "aggressively"?
-----------------------------

Informal definition: "Aggressive cleaning", which Adapton (PLDI 2014)
implements, consists of several aspects of the design of the DCG,
which work together to help avoid needless re-evaluation:

matthewhammer

module Inc = Incremental_lib.Incremental.Make ()
open Inc

let make init =
    let num = 4 in
    let den_v = Var.create init in
    let den = Var.watch den_v in

    (* computes "if den = 0 then 0 else num / den" *)
    let div = bind den (fun den -> return (num / den)) in

matthewhammer

(* Doubly linked list node *)
type 'a dlln = { mutable data : 'a ;
                 mutable prev : 'a dlln ;
                 mutable next : 'a dlln }

(* Look ma, a cycle can be initialized without any NULL pointers! *)
let rec singleton : int dlln =
  { data = 0 ;
    prev = singleton ;
    next = singleton }