1 files changed, 140 insertions, 0 deletions
diff --git a/src/document/bench.rs b/src/document/bench.rs
index 9cb72a7..1bb13ee 100644
--- a/src/document/bench.rs
+++ b/src/document/bench.rs
@@ -18,6 +18,14 @@
 //! the actor's changes up to it (each of the documents' actors writes a hundredth of
 //! their changes). And, for scale, the misplaced-author check the node makes on the
 //! same input (`changes::misplaced_author`).
+//!
+//! `change_paths`: what knowing every received change's paths would cost, to judge it by
+//! rules by path (`future-work.md`, Write protection by checking changes): each
+//! change's operations decoded, and each object they name followed up to the root as
+//! the change left it (`store::changed_by`, so every node finds the same paths). Against
+//! receiving a sync message of many changes and loading a document of many changes, as
+//! above, each change writing a value three levels deep; and decoding alone, the part
+//! that grows with the change rather than with its objects.
 
 use std::time::{Duration, Instant};
 
@@ -432,3 +440,135 @@ fn bench_change_signatures() {
         );
     }
 }
+
+/// A document of `changes` changes, each writing `servers/<region>/<n>/cpu` (4 regions,
+/// 50 servers each), by `actors` actors in turn.
+fn nested(changes: usize, actors: usize) -> Document {
+    let mut doc = Document::new();
+    let per = changes.div_ceil(actors.max(1));
+    for i in 0..changes {
+        if i % per == 0 {
+            doc.set_actor(automerge::ActorId::random());
+        }
+        let path = [
+            "servers".to_owned(),
+            format!("region{}", i % 4),
+            format!("{}", (i / 4) % 50),
+            "cpu".to_owned(),
+        ];
+        transact(&mut doc, UnixMillis(1), &WRITER, |doc| {
+            store::write_path(doc, &path, &serde_json::json!(i))
+        })
+        .expect("write");
+    }
+    doc
+}
+
+/// Costs of knowing the paths of `doc`'s changes, besides `base`: decoding them as the
+/// document rebuilds them, and their paths so (`store::changed_by`); and decoding them
+/// from the bytes they came as, and their paths so (`store::changed_by_decoded`).
+fn path_costs(workload: &str, base: Duration, doc: &Document) {
+    let hashes: Vec<ChangeHash> = doc.get_changes(&[]).iter().map(|c| c.hash()).collect();
+    let raw: Vec<(ChangeHash, Vec<u8>)> = doc
+        .get_changes(&[])
+        .iter()
+        .map(|change| (change.hash(), change.raw_bytes().to_vec()))
+        .collect();
+    let decode_bytes = median(3, || {
+        let started = Instant::now();
+        for (_, bytes) in &raw {
+            std::hint::black_box(
+                automerge::Change::from_bytes(bytes.clone())
+                    .expect("change")
+                    .decode(),
+            );
+        }
+        started.elapsed()
+    });
+    let paths_bytes = median(3, || {
+        let started = Instant::now();
+        for (hash, bytes) in &raw {
+            let change = automerge::Change::from_bytes(bytes.clone())
+                .expect("change")
+                .decode();
+            std::hint::black_box(store::changed_by_decoded(doc, hash, change, InLists::Index));
+        }
+        started.elapsed()
+    });
+    let decode = median(3, || {
+        let started = Instant::now();
+        for hash in &hashes {
+            std::hint::black_box(doc.get_change_by_hash(hash).expect("change").decode());
+        }
+        started.elapsed()
+    });
+    let paths = median(3, || {
+        let started = Instant::now();
+        for hash in &hashes {
+            std::hint::black_box(store::changed_by(doc, hash, InLists::Index));
+        }
+        started.elapsed()
+    });
+    report_signatures(
+        workload,
+        base,
+        &[
+            ("decoding", decode),
+            ("paths", paths),
+            ("from bytes: decoding", decode_bytes),
+            ("paths", paths_bytes),
+        ],
+    );
+}
+
+#[test]
+#[ignore = "a benchmark: cargo benchmarks"]
+fn bench_change_paths() {
+    println!();
+    // Catching up: one sync message of that many changes received.
+    for changes in [1_000, 10_000] {
+        let sender = nested(changes, changes / 100);
+        let mut receiver_state = sync::State::new();
+        let opening = Document::new()
+            .generate_sync_message(&mut receiver_state)
+            .expect("an opening");
+        let mut sender_doc = sender.clone();
+        let mut sender_state = sync::State::new();
+        sender_doc
+            .receive_sync_message(&mut sender_state, opening)
+            .expect("opening");
+        let message = sender_doc
+            .generate_sync_message(&mut sender_state)
+            .expect("the changes")
+            .encode();
+        let receive = median(5, || {
+            let mut doc = Document::new();
+            let mut state = receiver_state.clone();
+            let message = sync::Message::decode(&message).expect("decode");
+            let started = Instant::now();
+            doc.receive_sync_message(&mut state, message)
+                .expect("receive");
+            started.elapsed()
+        });
+        path_costs(
+            &format!("one sync message of {changes} changes"),
+            receive,
+            &sender,
+        );
+    }
+    // Joining, or starting from the file: a document of that many changes loaded.
+    for changes in [10_000, 100_000] {
+        let doc = nested(changes, changes / 100);
+        let bytes = super::save(&doc);
+        let load = median(3, || {
+            let started = Instant::now();
+            std::hint::black_box(super::load(&bytes).expect("load"));
+            started.elapsed()
+        });
+        path_costs(
+            &format!("a document of {changes} changes loaded"),
+            load,
+            &doc,
+        );
+    }
+}