change benchmark to pascal's triangle and add invalidation ones

3 files changed, 130 insertions, 72 deletions

diff --git a/incria/Cargo.toml b/incria/Cargo.toml
index f22bd7b..2dbe28a 100644
--- a/incria/Cargo.toml
+++ b/incria/Cargo.toml
@@ -10,6 +10,10 @@ tokio = { version = "1.28.1", features = ["sync", "rt"] }
 tokio = { version = "1.28.1", features = ["macros", "sync", "rt-multi-thread"] }
 criterion = { version = "0.4", features = ["async_tokio"] }
 
+[[test]]
+name = "pascal"
+path = "benches/pascal.rs"
+
 [[bench]]
-name = "spreadsheet"
+name = "pascal"
 harness = false
\ No newline at end of file
diff --git a/incria/benches/pascal.rs b/incria/benches/pascal.rs
new file mode 100644
index 0000000..3c06de1
--- /dev/null
+++ b/incria/benches/pascal.rs
@@ -0,0 +1,125 @@
+use std::{future::Future, pin::Pin, sync::OnceLock};
+
+use criterion::{criterion_group, criterion_main, BatchSize, Criterion};
+use incria::{
+    deps,
+    thunk::{Thunk, ThunkMapper},
+    Mapper,
+};
+
+type Key = (isize, isize);
+type Value = usize;
+
+#[derive(Debug, Default)]
+struct PascalThunk;
+
+impl Thunk<Key, Value> for PascalThunk {
+    fn compute(&self, key: Key) -> Pin<Box<dyn Future<Output = Value> + Send + '_>> {
+        Box::pin(async move {
+            if key.1 > key.0 || key.0 < 0 {
+                0 // anything outside the triangle is 0
+            } else if key == (0, 0) {
+                1
+            } else {
+                let (left, below) = ((key.0 - 1, key.1 - 1), (key.0 - 1, key.1));
+                // let (left, below) =
+                //     join!(pascal_mapping().get(&left), pascal_mapping().get(&below));
+
+                let left = *pascal_mapping().get(&left).await;
+                let below = *pascal_mapping().get(&below).await;
+                let val = left + below;
+
+                if val > 10_000 {
+                    1
+                } else {
+                    val
+                }
+            }
+        })
+    }
+}
+
+type PascalMapping = ThunkMapper<Key, Value, PascalThunk>;
+static PASCAL_MAPPING: OnceLock<PascalMapping> = OnceLock::new();
+fn pascal_mapping() -> &'static PascalMapping {
+    PASCAL_MAPPING.get_or_init(PascalMapping::default)
+}
+
+fn criterion_benchmark(c: &mut Criterion) {
+    benchmarks_with_n(c, 5);
+    benchmarks_with_n(c, 10);
+    benchmarks_with_n(c, 40);
+}
+
+fn benchmarks_with_n(c: &mut Criterion, n: isize) {
+    let target_cell = (n, n / 2);
+    c.bench_function(&format!("pascal fresh (n = {})", n), |b| {
+        b.to_async(tokio::runtime::Runtime::new().unwrap())
+            .iter(|| do_calc(&target_cell));
+    });
+    c.bench_function(&format!("pascal fully invalidated (n = {})", n), |b| {
+        b.to_async(tokio::runtime::Runtime::new().unwrap())
+            .iter_batched(
+                || do_then_invalidate(target_cell, (0, 0)),
+                |_| do_calc(&target_cell),
+                BatchSize::SmallInput,
+            );
+    });
+    c.bench_function(&format!("pascal 1/2 invalidated (n = {})", n), |b| {
+        b.to_async(tokio::runtime::Runtime::new().unwrap())
+            .iter_batched(
+                || do_then_invalidate(target_cell, (n / 2, n / 2)),
+                |_| do_calc(&target_cell),
+                BatchSize::SmallInput,
+            );
+    });
+    c.bench_function(&format!("pascal 1 invalidated (n = {})", n), |b| {
+        b.to_async(tokio::runtime::Runtime::new().unwrap())
+            .iter_batched(
+                || do_then_invalidate(target_cell, target_cell),
+                |_| do_calc(&target_cell),
+                BatchSize::SmallInput,
+            );
+    });
+}
+
+#[inline(always)]
+async fn do_calc(key: &Key) {
+    drop(deps::with_node_id(deps::next_node_id(), pascal_mapping().get(key)).await);
+}
+
+#[inline(always)]
+async fn do_then_invalidate(eval: Key, inval: Key) {
+    // Do calculation
+    do_calc(&eval).await;
+
+    // Invalidate the root
+    deps::mark_dirty(pascal_mapping().dep_id(&inval).await.unwrap());
+}
+
+criterion_group!(benches, criterion_benchmark);
+criterion_main!(benches);
+
+#[tokio::test]
+async fn test_pascal_triangle_correct() {
+    assert_eq!(
+        *deps::with_node_id(deps::next_node_id(), pascal_mapping().get(&(0, 0))).await,
+        1,
+        "unique non-zero entry at (0, 0)"
+    );
+    assert_eq!(
+        *deps::with_node_id(deps::next_node_id(), pascal_mapping().get(&(0, 1))).await,
+        0,
+        "numbers outside triangle are 0"
+    );
+    assert_eq!(
+        *deps::with_node_id(deps::next_node_id(), pascal_mapping().get(&(4, 2))).await,
+        6,
+        "correct value for (4, 2)"
+    );
+    assert_eq!(
+        *deps::with_node_id(deps::next_node_id(), pascal_mapping().get(&(8, 4))).await,
+        70,
+        "correct value for (8, 4)"
+    );
+}
diff --git a/incria/benches/spreadsheet.rs b/incria/benches/spreadsheet.rs
deleted file mode 100644
index ada4b22..0000000
--- a/incria/benches/spreadsheet.rs
+++ /dev/null
@@ -1,71 +0,0 @@
-use std::{future::Future, pin::Pin, sync::OnceLock};
-
-use criterion::{black_box, criterion_group, criterion_main, Criterion};
-use incria::{
-    deps,
-    thunk::{Thunk, ThunkMapper},
-    Mapper,
-};
-
-type Key = (usize, usize);
-type Value = usize;
-
-#[derive(Debug, Default)]
-struct CellThunk;
-
-impl Thunk<Key, Value> for CellThunk {
-    fn compute(&self, key: Key) -> Pin<Box<dyn Future<Output = Value> + Send + '_>> {
-        Box::pin(async move {
-            if key.0 > 0 {
-                let prev1 = *cell_mapping().get(&(key.0 - 1, key.1 - 1)).await;
-                let prev2 = *cell_mapping().get(&(key.0 - 1, key.1)).await;
-                let prev3 = *cell_mapping().get(&(key.0 - 1, key.1 + 1)).await;
-                let val = prev1 + prev2 + prev3;
-
-                if val > 10_000 {
-                    1
-                } else {
-                    val
-                }
-            } else {
-                1
-            }
-        })
-    }
-}
-
-fn calc_raw(key: Key) -> Value {
-    if key.0 > 0 {
-        let prev1 = calc_raw((key.0 - 1, key.1 - 1));
-        let prev2 = calc_raw((key.0 - 1, key.1));
-        let prev3 = calc_raw((key.0 - 1, key.1 + 1));
-        let val = prev1 + prev2 + prev3;
-
-        if val > 10_000 {
-            1
-        } else {
-            val
-        }
-    } else {
-        1
-    }
-}
-
-type CellMapping = ThunkMapper<Key, Value, CellThunk>;
-static CELL_MAPPING: OnceLock<CellMapping> = OnceLock::new();
-fn cell_mapping() -> &'static CellMapping {
-    CELL_MAPPING.get_or_init(CellMapping::default)
-}
-
-fn criterion_benchmark(c: &mut Criterion) {
-    c.bench_function("spreadsheet non-incria (n = 5)", |b| {
-        b.iter(|| calc_raw(black_box((5, 5))));
-    });
-    c.bench_function("spreadsheet fresh (n = 5)", |b| {
-        b.to_async(tokio::runtime::Runtime::new().unwrap())
-            .iter(|| deps::with_node_id(deps::next_node_id(), cell_mapping().get(&(5, 5))));
-    });
-}
-
-criterion_group!(benches, criterion_benchmark);
-criterion_main!(benches);