bench: change paths

Finding the paths changes touch, from documents and from raw change
bytes, measured before M6 is built.

Auth plan M6 (measure first).

3 files changed, 155 insertions, 3 deletions

diff --git a/docs/development.md b/docs/development.md
index 002d92c..2fb7ab5 100644
--- a/docs/development.md
+++ b/docs/development.md
@@ -18,7 +18,8 @@ needs at least one: a transport left out takes its tests and dependencies with i
 nor arti; among Mycelium's tests is a swarm simulated on its envelope).
 
 The benchmarks are ignored tests named `bench_*`: the document's (writes and sync
-messages, and what signing and checking every change would cost: `bench_change_signatures`;
+messages, what signing and checking every change would cost: `bench_change_signatures`,
+and knowing every change's paths: `bench_change_paths`;
 `document/bench.rs`), the remakes' replay (`remake/bench.rs`), and what
 passing changes on costs over the simulated network (`simtest/bench.rs`: messages and
 bytes per write by kind, propagation delays, for a full mesh, a writer behind NAT (in a full mesh, and in a partial one), two
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,
+        );
+    }
+}
diff --git a/src/document/store.rs b/src/document/store.rs
index 2e27b44..31c4824 100644
--- a/src/document/store.rs
+++ b/src/document/store.rs
@@ -93,8 +93,19 @@ pub(crate) fn changed_by(
     hash: &automerge::ChangeHash,
     lists: InLists,
 ) -> Option<Vec<Vec<String>>> {
-    use automerge::legacy::{Key, ObjectId};
     let change = doc.get_change_by_hash(hash)?.decode();
+    Some(changed_by_decoded(doc, hash, change, lists))
+}
+
+/// [`changed_by`] of a change already decoded (`change`, whose hash is `hash`), as from
+/// the bytes it came as: what the document rebuilding it would cost spared.
+pub(crate) fn changed_by_decoded(
+    doc: &Automerge,
+    hash: &automerge::ChangeHash,
+    change: automerge::ExpandedChange,
+    lists: InLists,
+) -> Vec<Vec<String>> {
+    use automerge::legacy::{Key, ObjectId};
     let heads = [*hash];
     // Each object's path as it was after the change, and whether that is a list's (as
     // `InLists::Whole` names what is inside one).
@@ -127,7 +138,7 @@ pub(crate) fn changed_by(
         }
         paths.insert(path);
     }
-    Some(paths.into_iter().collect())
+    paths.into_iter().collect()
 }
 
 /// Whether one path is within the other (a change at either touches both).