From 2aa2fb8c757c9595084960804a128ea701b17356 Mon Sep 17 00:00:00 2001 From: tv Date: Sat, 7 Nov 2026 22:35:21 +0100 Subject: 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). --- src/document/bench.rs | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/document/store.rs | 15 +++++- 2 files changed, 153 insertions(+), 2 deletions(-) (limited to 'src') 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///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 = doc.get_changes(&[]).iter().map(|c| c.hash()).collect(); + let raw: Vec<(ChangeHash, Vec)> = 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>> { - 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> { + 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). -- cgit v1.3.1