• This repository has been archived on 22/Nov/2023
  • Stars
    star
    130
  • Rank 277,575 (Top 6 %)
  • Language
    Rust
  • Created almost 5 years ago
  • Updated about 3 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

self adjusting computations in rust

Anchors: Self-Adjusting Computitons in Rust
Crates.io Package Docs

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

More Repositories

1

wargo

Easy Rust to WebAssembly
JavaScript
261
star
2

backtalk

HTTP/Websockets API microframework
Rust
158
star
3

flexblocks

A CSS layout library
CSS
76
star
4

crudite

it's like a blockchain but for collaborative editing of json documents
Rust
41
star
5

emoji-shell

A 🐚 powered by emoji, written in Rust
Rust
38
star
6

middleman-php

Parse PHP files in Middleman
Ruby
35
star
7

mortalical

A calendar of your entire life
Ruby
20
star
8

mortalitab

Replace your new tab page with a personal reminder that you will die
JavaScript
16
star
9

doorbot

Opens the door to Recurse Center with a text
Ruby
11
star
10

learnllvm

Toy compiler with Rust and LLVM
Rust
7
star
11

scrape-bncollege

Scrapes bncollege.com
Python
7
star
12

wargo-loader

JavaScript
7
star
13

alfred-quicknote

A fast way to access your notes from Alfred
Ruby
7
star
14

cashin

A miniature payment form
CSS
6
star
15

arena-graph

fast and dangerous arena-allocated graphs
Rust
4
star
16

webbing

DOM APIs for Rust+Emscripten
Rust
3
star
17

radio-replay

Rust
3
star
18

backtalk-old2

Build web APIs in Rust
Rust
3
star
19

plotter-quine

Rust
3
star
20

cargo-wasm

Run cargo commands with emcc automatically installed
Rust
3
star
21

Stalkernet

Web scraper for Stalkernet.
Python
2
star
22

qr

toy qr encoder written from scratch in python
Python
2
star
23

pagelapse

Generate timelapses of websites
Ruby
2
star
24

testcommit

2
star
25

farmhouse

Arduino
2
star
26

wattt

Web Assembly Tobject TcapabiliTies
1
star
27

wargo-loader-example

JavaScript
1
star
28

pinboard-to-instapaper

A quick script to import bookmarks from Pinboard to Instapaper
Ruby
1
star
29

markov

Rust
1
star
30

fightclub

A programming competition server
JavaScript
1
star
31

learning-graphics

In which Robert teaches himself graphics programming in Rust
Rust
1
star
32

lodo

A game built with a bunch of LEDs and pressure plates
Go
1
star
33

datastore-sys

protobuf derived code for connecting to GCP's Datastore
Rust
1
star
34

gql

defunct, feel free to ignore
Rust
1
star
35

tinyrenderer

Rust
1
star
36

cryptopals

Solutions to the crypto challenges in Go
Go
1
star
37

meow2

1
star
38

rapidwrap

Fast text wrapping in the browser
JavaScript
1
star
39

img

Images used in various Github readmes
1
star
40

platformer

A game in progress
JavaScript
1
star