#incremental-computation #computation #street

incremental

incremental computations, based on Jane Street's incremental

11 releases

0.2.7 Nov 18, 2024
0.2.6 Nov 14, 2024
0.2.5 Aug 28, 2024
0.2.2 May 6, 2024
0.0.0-0.0.0-0.0.0 Nov 7, 2022

#150 in Algorithms

Download history 396/week @ 2024-08-14 572/week @ 2024-08-21 1007/week @ 2024-08-28 565/week @ 2024-09-04 225/week @ 2024-09-11 224/week @ 2024-09-18 246/week @ 2024-09-25 135/week @ 2024-10-02 149/week @ 2024-10-09 273/week @ 2024-10-16 224/week @ 2024-10-23 62/week @ 2024-10-30 143/week @ 2024-11-06 450/week @ 2024-11-13 417/week @ 2024-11-20 258/week @ 2024-11-27

1,272 downloads per month
Used in incremental-map

MIT license

260KB
6K SLoC

incremental-rs

A port of Jane Street's Incremental library.

  • Pretty rigorous implementation of the basic Incr features, moderately well tested and benchmarked, performs very similarly to the original.
  • Partial implementation of incremental-map

Install

cargo add incremental

Examples

Basic usage:

use incremental::IncrState;

let state = IncrState::new();
let variable = state.var(5);
let times_10 = variable.map(|num| num * 10);
let observer = times_10.observe();

// stabilise will propagate any changes
state.stabilise();
let value = observer.value();
assert_eq!(value, 50);

// now mutate
variable.set(10);
state.stabilise();

// watch as var was propagated through the tree, and reached our observer
assert_eq!(observer.value(), 100);

Subscriptions, and an illustration of how propagation stops when nodes produce the same value as last time:

use incremental::{IncrState, Update};

// A little system to compute the absolute value of an input
// Note that the input could change (e.g. 5 to -5), but the
// output may stay the same (5 both times).
let state = IncrState::new();
let variable = state.var(5i32);
let absolute = variable.map(|num| num.abs());
let observer = absolute.observe();

// set up a subscription.
use std::{cell::RefCell, rc::Rc};
let latest = Rc::new(RefCell::new(None));
let latest_clone = latest.clone();
let subscription_token = observer.subscribe(move |update| {
     *latest_clone.borrow_mut() = Some(update.cloned());
});

// initial stabilisation
state.stabilise();
assert_eq!(observer.value(), 5);
assert_eq!(latest.borrow().clone(), Some(Update::Initialised(5)));

// now mutate, but such that the output of abs() won't change
variable.set(-5);
state.stabilise();
// The subscription function was not called, because the `absolute` node
// produced the same value as last time we stabilised.
assert_eq!(latest.borrow().clone(), Some(Update::Initialised(5)));
assert_eq!(observer.value(), 5);

// now mutate such that the output changes too
variable.set(-10);
state.stabilise();
// The observer did get a new value, and did call the subscription function
assert_eq!(latest.borrow().clone(), Some(Update::Changed(10)));
assert_eq!(observer.value(), 10);

// now unsubscribe. this also implicitly happens if you drop the observer,
// but you can individually unsubscribe particular subscriptions if you wish.
observer.unsubscribe(subscription_token);
// dropping the observer also unloads any part of the computation graph
// that was only running for the purposes of this particular observer
drop(observer);

// now that the observer is dead, we can mutate the variable and nothing will
// happen, like, at all. The absolute value will not be computed.
variable.set(100000000);
let recomputed = state.stats().recomputed;
state.stabilise();
assert_eq!(recomputed, state.stats().recomputed);

Dependencies

~360–770KB
~13K SLoC