gdx64 / anchors

self adjusting computations in rust

Features

• Hybrid graph allows both Adapton-style and Incremental-style push updates. For more information on the internals, you can view the accompanying blog post.
• Cloning values in the graph is almost always optional. map and then closures receive immutable references, and return owned values. Alternatively, a refmap closure receives an immutable reference, and returns an immutable reference.
• Still a work in progress, but should be functional (lol) and half-decently fast. Still, expect for there to be major API changes over the next several years.

Example

use crate::singlethread::*;
let mut engine = Engine::new();

// create a couple `Var`s
let (my_name, my_name_updater) = {
    let var = Var::new("Bob".to_string());
    (var.watch(), var)
};
let (my_unread, my_unread_updater) = {
    let var = Var::new(999usize);
    (var.watch(), var)
};

// `my_name` is a `Var`, our first type of `Anchor`. we can pull an `Anchor`'s value out with our `engine`:
assert_eq!(&engine.get(&my_name), "Bob");
assert_eq!(engine.get(&my_unread), 999);

// we can create a new `Anchor` from another one using `map`. The function won't actually run until absolutely necessary.
// also feel free to clone an `Anchor` — the clones will all refer to the same inner state
let my_greeting = my_name.clone().map(|name| {
    println!("calculating name!");
    format!("Hello, {}!", name)
});
assert_eq!(engine.get(&my_greeting), "Hello, Bob!"); // prints "calculating name!"

// we can update a `Var` with its updater. values are cached unless one of its dependencies changes
assert_eq!(engine.get(&my_greeting), "Hello, Bob!"); // doesn't print anything
my_name_updater.set("Robo".to_string());
assert_eq!(engine.get(&my_greeting), "Hello, Robo!"); // prints "calculating name!"

// a `map` can take values from multiple `Anchor`s. just use tuples:
let header = (&my_greeting, &my_unread)
    .map(|greeting, unread| format!("{} You have {} new messages.", greeting, unread));
assert_eq!(
    engine.get(&header),
    "Hello, Robo! You have 999 new messages."
);

// just like a future, you can dynamically decide which `Anchor` to use with `then`:
let (insulting_name, _) = {
    let var = Var::new("Lazybum".to_string());
    (var.watch(), var)
};
let dynamic_name = my_unread.then(move |unread| {
    // only use the user's real name if the have less than 100 messages in their inbox
    if *unread < 100 {
        my_name.clone()
    } else {
        insulting_name.clone()
    }
});
assert_eq!(engine.get(&dynamic_name), "Lazybum");
my_unread_updater.set(50);
assert_eq!(engine.get(&dynamic_name), "Robo");

Observed nodes

You can tell the engine you'd like a node to be observed:

engine.mark_observed(&dynamic_name);

Now when you request it, it will avoid traversing the entire graph quite as frequently, which is useful when you have a large Anchor dependency tree. However, there are some drawbacks:

• any time you get any Anchor, all observed nodes will be brought up to date.
• if one of an observed dependencies is a then, nodes requested by it may be recomputed, even though they aren't strictly necessary.

How fast is it?

You can check out the bench folder for some microbenchmarks. These are the results of running stabilize_linear_nodes_simple, a linear chain of many map nodes each adding 1 to some changing input number. Benchmarks run on my Macbook Air (Intel, 2020) against Anchors 0.5.0 8c9801c, with lto = true.

node count	used `mark_observed`?	total time to `get` end of chain	total time / node count
10	observed	[485.48 ns 491.85 ns 498.49 ns]	49.185 ns
100	observed	[4.1734 us 4.2525 us 4.3345 us]	42.525 ns
1000	observed	[42.720 us 43.456 us 44.200 us]	43.456 ns
10	unobserved	[738.02 ns 752.40 ns 767.86 ns]	75.240 ns
100	unobserved	[6.5952 us 6.7178 us 6.8499 us]	67.178 ns
1000	unobserved	[74.256 us 75.360 us 76.502 us]	75.360 ns

Very roughly, it looks like observed nodes have an overhead of at around ~42-50ns each, and unobserved nodes around 74-76ns each. This could be pretty aggressively improved; ideally we could drop these numbers to the ~15ns per observed node that Incremental achieves.

Also worth mentioning for any incremental program, the slowdowns will probably come from other aspects of the framework that aren't measured with this very simple microbenchmark.

How fast is it on an M1 mac?

Maybe twice as fast?

node count	used `mark_observed`?	total time to `get` end of chain	total time / node count
10	observed	[242.68 ns 242.98 ns 243.37 ns]	24.30 ns
100	observed	[1.9225 us 1.9232 us 1.9239 us]	19.232 ns
1000	observed	[20.421 us 20.455 us 20.489 us]	20.46 ns
10	unobserved	[354.05 ns 354.21 ns 354.37 ns]	35.42
100	unobserved	[3.3810 us 3.3825 us 3.3841 us]	33.83 ns
1000	unobserved	[41.429 us 41.536 us 41.642 us]	41.54 ns

See Also

• https://github.com/Adapton/adapton.rust
• https://github.com/janestreet/incremental
• https://github.com/observablehq/runtime
• https://github.com/salsa-rs/salsa
• https://github.com/MaterializeInc/materialize