/*! * Copyright (c) Microsoft Corporation and contributors. All rights reserved. * Licensed under the MIT License. */ import { strict as assert } from "node:assert"; import { BenchmarkMode, BenchmarkType, benchmarkDuration, benchmarkDurationBatchless, benchmarkIt, currentBenchmarkMode, } from "@fluid-tools/benchmark"; import { FlushMode } from "@fluidframework/runtime-definitions/internal"; import { EmptyKey, rootFieldKey, type NormalizedUpPath } from "../../core/index.js"; import { FormatValidatorBasic } from "../../external-utilities/index.js"; import { TreeCompressionStrategy, jsonableTreeFromFieldCursor, } from "../../feature-libraries/index.js"; import { Tree } from "../../shared-tree/index.js"; import { TreeViewConfiguration } from "../../simple-tree/index.js"; import { configuredSharedTree } from "../../treeFactory.js"; import { makeArray } from "../../util/index.js"; import { type JSDeepTree, LinkedList, WideRoot, deepPath, localFieldKey, makeDeepContentSimple, makeDeepStoredContent, makeJsDeepTree, makeJsWideTreeWithEndValue, makeWideContentWithEndValueSimple, makeWideStoredContentWithEndValue, readDeepCursorTree, readDeepFlexTree, readDeepTreeAsJSObject, readWideCursorTree, readWideFlexTree, readWideTreeAsJSObject, } from "../scalableTestTrees.js"; import { insert } from "../sequenceRootUtils.js"; import { StringArray, TestTreeProviderLite, checkoutWithContent, configureBenchmarkHooks, chunkFromJsonTrees, flexTreeViewWithContent, toJsonableTree, type SharedTreeWithContainerRuntime, fieldCursorFromInsertable, } from "../utils.js"; // number of nodes in test for wide trees const nodesCountWide = [ [1, BenchmarkType.Measurement], ...(currentBenchmarkMode === BenchmarkMode.Performance ? [ [100, BenchmarkType.Perspective], [500, BenchmarkType.Measurement], ] : []), ]; // number of nodes in test for deep trees const nodesCountDeep = [ [1, BenchmarkType.Measurement], ...(currentBenchmarkMode === BenchmarkMode.Performance ? [ [10, BenchmarkType.Perspective], [100, BenchmarkType.Measurement], ] : []), ]; // TODO: ADO#7111 Schema should be fixed to enable schema based encoding. const factory = configuredSharedTree({ jsonValidator: FormatValidatorBasic, treeEncodeType: TreeCompressionStrategy.Uncompressed, }).getFactory(); // TODO: Once the "BatchTooLarge" error is no longer an issue, extend tests for larger trees. describe("SharedTree benchmarks", () => { configureBenchmarkHooks(); describe("Direct JS Object", () => { for (const [numberOfNodes, benchmarkType] of nodesCountDeep) { benchmarkIt({ type: benchmarkType, title: `Deep Tree as JS Object: reads with ${numberOfNodes} nodes`, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { const tree = makeJsDeepTree(numberOfNodes, 1) as JSDeepTree; state.timeAllBatches(() => { const { depth, value } = readDeepTreeAsJSObject(tree); assert.equal(depth, numberOfNodes); assert.equal(value, 1); }); }, }), }); } for (const [numberOfNodes, benchmarkType] of nodesCountWide) { benchmarkIt({ type: benchmarkType, title: `Wide Tree as JS Object: reads with ${numberOfNodes} nodes`, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { const tree = makeJsWideTreeWithEndValue(numberOfNodes, numberOfNodes - 1); let expected = 0; for (let i = 0; i < numberOfNodes; i++) { expected += i; } state.timeAllBatches(() => { const { nodesCount, sum } = readWideTreeAsJSObject(tree); assert.equal(nodesCount, numberOfNodes); assert.equal(sum, expected); }); }, }), }); } describe(`Edit JS Object`, () => { for (const [numberOfNodes, benchmarkType] of nodesCountDeep) { benchmarkIt({ type: benchmarkType, title: `Update value at leaf of ${numberOfNodes} deep tree`, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { const tree = makeJsDeepTree(numberOfNodes, 1) as JSDeepTree; let currentNode: JSDeepTree = tree; while (typeof currentNode !== "number") { if (typeof currentNode.foo === "number") { break; } currentNode = currentNode.foo; } state.timeAllBatches(() => { currentNode.foo = -1; }); const expected = makeJsDeepTree(numberOfNodes, -1); assert.deepEqual(tree, expected); }, }), }); } for (const [numberOfNodes, benchmarkType] of nodesCountWide) { benchmarkIt({ type: benchmarkType, title: `Update value at leaf of ${numberOfNodes} Wide tree`, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { const tree = makeJsWideTreeWithEndValue(numberOfNodes, numberOfNodes - 1); state.timeAllBatches(() => { tree[numberOfNodes - 1] = -1; }); const expected = makeJsWideTreeWithEndValue(numberOfNodes, -1); assert.deepEqual(tree, expected); }, }), }); } }); }); describe("Cursors", () => { for (const [numberOfNodes, benchmarkType] of nodesCountDeep) { benchmarkIt({ type: benchmarkType, title: `Deep Tree with cursor: reads with ${numberOfNodes} nodes`, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { const tree = flexTreeViewWithContent(makeDeepContentSimple(numberOfNodes)); state.timeAllBatches(() => { const { depth, value } = readDeepCursorTree(tree); assert.equal(value, 1); assert.equal(depth, numberOfNodes); }); }, }), }); } for (const [numberOfNodes, benchmarkType] of nodesCountWide) { benchmarkIt({ type: benchmarkType, title: `Wide Tree with cursor: reads with ${numberOfNodes} nodes`, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { let expected = 0; for (let index = 0; index < numberOfNodes; index++) { expected += index; } const tree = flexTreeViewWithContent( makeWideContentWithEndValueSimple(numberOfNodes, numberOfNodes - 1), ); state.timeAllBatches(() => { const { nodesCount, sum } = readWideCursorTree(tree); assert.equal(sum, expected); assert.equal(nodesCount, numberOfNodes); }); }, }), }); } }); describe("FlexTree bench", () => { for (const [numberOfNodes, benchmarkType] of nodesCountDeep) { benchmarkIt({ type: benchmarkType, title: `Deep Tree with Flex Tree: reads with ${numberOfNodes} nodes`, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { const tree = flexTreeViewWithContent(makeDeepContentSimple(numberOfNodes)); state.timeAllBatches(() => { const { depth, value } = readDeepFlexTree(tree); assert.equal(depth, numberOfNodes); assert.equal(value, 1); }); }, }), }); } for (const [numberOfNodes, benchmarkType] of nodesCountWide) { benchmarkIt({ type: benchmarkType, title: `Wide Tree with Flex Tree: reads with ${numberOfNodes} nodes`, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { const expected = ((numberOfNodes - 1) * numberOfNodes) / 2; // Arithmetic sum of [0, numberOfNodes) const tree = flexTreeViewWithContent( makeWideContentWithEndValueSimple(numberOfNodes), ); state.timeAllBatches(() => { const { nodesCount, sum } = readWideFlexTree(tree); assert.equal(sum, expected); assert.equal(nodesCount, numberOfNodes); readWideCursorTree(tree); }); }, }), }); } }); describe("Edit with editor", () => { const setCount = 100; for (const [numberOfNodes, benchmarkType] of nodesCountDeep) { benchmarkIt({ type: benchmarkType, title: `Update value at leaf of ${numberOfNodes} deep tree ${setCount} times`, ...benchmarkDurationBatchless({ benchmarkFn: (state) => { let running: boolean; do { // Setup const tree = checkoutWithContent(makeDeepStoredContent(numberOfNodes)); const path = deepPath(numberOfNodes); // Measure running = state.time(() => { for (let value = 1; value <= setCount; value++) { tree.editor .valueField({ parent: path, field: localFieldKey }) .set(chunkFromJsonTrees([value])); } }); // Cleanup + validation const expected = jsonableTreeFromFieldCursor( fieldCursorFromInsertable( LinkedList, makeJsDeepTree(numberOfNodes, setCount) as LinkedList, ), ); const actual = toJsonableTree(tree); assert.deepEqual(actual, expected); } while (running); }, }), }); } for (const [numberOfNodes, benchmarkType] of nodesCountWide) { benchmarkIt({ type: benchmarkType, title: `Update value at leaf of ${numberOfNodes} wide tree ${setCount} times`, ...benchmarkDurationBatchless({ benchmarkFn: (state) => { let running: boolean; do { // Setup const tree = checkoutWithContent( makeWideStoredContentWithEndValue(numberOfNodes), ); const rootPath: NormalizedUpPath = { detachedNodeId: undefined, parent: undefined, parentField: rootFieldKey, parentIndex: 0, }; const nodeIndex = numberOfNodes - 1; const editor = tree.editor.sequenceField({ parent: rootPath, field: EmptyKey, }); // Measure running = state.time(() => { for (let value = 1; value <= setCount; value++) { editor.remove(nodeIndex, 1); editor.insert(nodeIndex, chunkFromJsonTrees([value])); } }); // Cleanup + validation const expected = jsonableTreeFromFieldCursor( fieldCursorFromInsertable( WideRoot, makeJsWideTreeWithEndValue(numberOfNodes, setCount), ), ); const actual = toJsonableTree(tree); assert.deepEqual(actual, expected); } while (running); }, }), }); } }); describe("acking local commits", () => { const localCommitSize = [1, 25, 100, 500, 1000]; for (const size of localCommitSize) { benchmarkIt({ title: `for ${size} local commit${size === 1 ? "" : "s"}`, ...benchmarkDurationBatchless({ benchmarkFn: (state) => { let running: boolean; do { // Setup const provider = new TestTreeProviderLite(1, factory); // TODO: specify a schema for these trees. const [tree] = provider.trees; for (let i = 0; i < size; i++) { insert(tree.kernel.checkout, i, "test"); } running = state.time(() => { provider.synchronizeMessages(); }); } while (running); }, }), }); } }); // Note that this runs the computation for several peers. // In practice, this computation is distributed across peers, so the actual time reported is // divided by the number of peers. describe("rebasing commits", () => { // Each commit generates 2 ops (one for the changeset and one for the UUID minting const opsPerCommit = 2; const sampleSize = 10; // Number of peers that are generating commits. const peerCounts = [2, 4]; // Number of commits that are generated in the amount of time it takes of a single commit to round-trip. // E.g., 10 is equivalent to all of the following (and more): // - generating 5 edits per second with a 2000ms round-trip time // - generating 10 edits per second with a 1000ms round-trip time // - generating 100 edits per second with a 100ms round-trip time const commitCounts = currentBenchmarkMode === BenchmarkMode.Performance ? [1, 5, 10] : [1, 2]; for (const peerCount of peerCounts) { for (const commitCount of commitCounts) { benchmarkIt({ title: `for ${commitCount} commits per peer for ${peerCount} peers`, correctnessTimeoutMs: 5000, ...benchmarkDuration({ benchmarkFnCustom: async (state) => { let duration: number; do { // Since this setup one collects data from one iteration, assert that this is what is expected. assert.equal(state.iterationsPerBatch, 1); const provider = new TestTreeProviderLite(peerCount, factory); // This is the start of the stream of commits. // Earlier commits are less out of date and therefore not representative. for (let iCommit = 0; iCommit < commitCount; iCommit++) { for (let iPeer = 0; iPeer < peerCount; iPeer++) { const peer = provider.trees[iPeer]; insert(peer.kernel.checkout, 0, `p${iPeer}c${iCommit}`); } } // This block generates commits that are all out of date to the same degree for (let iCommit = 0; iCommit < commitCount; iCommit++) { for (let iPeer = 0; iPeer < peerCount; iPeer++) { provider.synchronizeMessages({ count: opsPerCommit, }); const peer = provider.trees[iPeer]; insert(peer.kernel.checkout, 0, `p${iPeer}c${iCommit}`); } } // This block measures commits that are all out of date to the same degree. // We could theoretically measure the time it takes for a single commit to be processed, // but averaging over multiple commits gives a more stable result. let timeSum = 0; for (let iCommit = 0; iCommit < sampleSize; iCommit++) { for (let iPeer = 0; iPeer < peerCount; iPeer++) { const before = state.timer.now(); provider.synchronizeMessages({ count: opsPerCommit, }); const after = state.timer.now(); timeSum += state.timer.toSeconds(before, after); // We still generate commits because it affects local branch rebasing const peer = provider.trees[iPeer]; insert(peer.kernel.checkout, 0, `p${iPeer}c${iCommit}`); } } // We want the average time it would take one peer to process one incoming edit duration = timeSum / (peerCount * peerCount * sampleSize); } while (state.recordBatch(duration)); }, // Force batch size of 1 minBatchDurationSeconds: 0, }), }); } } }); // In this context "op bunch" refers to a group of ops for the same DDS that are sent by a peer in a single message. describe("Op Bunching", () => { /** * Helper function to setup the sender and receiver trees for the op bunching benchmarks. * @remarks It pauses the processing of both sender and receiver to enable the test to control when the * messages are processed. */ function setupSenderAndReceiver() { const provider = new TestTreeProviderLite( 2, factory, undefined /* useDeterministicSessionIds */, FlushMode.TurnBased, ); const sender = provider.trees[0]; const receiver = provider.trees[1]; sender.containerRuntime.pauseInboundProcessing(); receiver.containerRuntime.pauseInboundProcessing(); return { provider, sender, receiver }; } /** * Helper function to send local commits from a given tree. * In turn based flush mode, the messages won't be sequenced until flush is called explicitly * on the tree's container runtime. * In Immediate flush mode, the messages will be flushed and sequenced immediately. So, this * function will behave similar to 'sequenceLocalCommits'. */ function sendLocalCommits( tree: SharedTreeWithContainerRuntime, count: number, commitPrefix: string, ) { for (let iCommit = 0; iCommit < count; iCommit++) { insert(tree.kernel.checkout, 0, `${commitPrefix}${iCommit}`); } } describe("Rebasing inbound bunch over local changes", () => { // The number of commits in a bunch for a given run of this test suite. const bunchSizes = currentBenchmarkMode === BenchmarkMode.Performance ? [1, 10, 100] : [2]; // Number of local commits to rebase over the inbound bunch const localBranchSizes = currentBenchmarkMode === BenchmarkMode.Performance ? [10, 100] : [2]; // The time taken by each scenario can be broken down into 4 time costs: // 1. Constant factor overhead (we ignore this). // 2. The time taken to rebase inbound commits onto the tip of the trunk. // 3. The time taken to compose all inbound commits from a bunch into a single commit. // 4. The time taken to rebase the local branch over the composed commit from #3. // // For the following timings: // +----------------------+-------------+--------------+ // | | bunchSize:1 | bunchSize:10 | // +----------------------+-------------+--------------+ // | localBranchSize: 10 | t1 | t2 | // | localBranchSize: 100 | t3 | t4 | // +----------------------+-------------+--------------+ // If op bunching is used, the time taken for each scenario is as follows: // t1 = rebase 1 inbound commit onto trunk + compose 1 commit + rebase the local branch of size 10 over one commit // t2 = rebase 10 inbound commits onto trunk + compose 10 commits + rebase the local branch of size 10 over one commit // t3 = rebase 1 inbound commit onto trunk + compose 1 commit + rebase the local branch of size 100 over one commit // t4 = rebase 10 inbound commits onto trunk + compose 10 commits + rebase the local branch of size 100 over one commit // Therefore, if op bunching is used, then t4 should be roughly equal to t3 + t2 - t1. for (const bunchSize of bunchSizes) { for (const localBranchSize of localBranchSizes) { benchmarkIt({ title: `Rebase ${localBranchSize} local commits over ${bunchSize} inbound commits`, correctnessTimeoutMs: 5000, ...benchmarkDurationBatchless({ benchmarkFn: (state) => { let running: boolean; do { const { provider, sender, receiver } = setupSenderAndReceiver(); // Send local commits from the receiver but don't sequence them because we want them to be // in the local branch. sendLocalCommits(receiver, localBranchSize, "r"); // Send and sequence local commits from the sender. These are the commits that should be // bunched together. sendLocalCommits(sender, bunchSize, "s"); sender.containerRuntime.flush(); // Resume the receiver so it can process the bunched commits from the sender. receiver.containerRuntime.resumeInboundProcessing(); // Synchronize the bunched commits. This should force the local branch to be rebased over the bunch. // The receiver will not process its local commits since they were never flushed. running = state.time(() => { provider.synchronizeMessages({ flush: false }); }); } while (running); }, }), }); } } }); describe("Rebasing inbound bunch over trunk changes", () => { // The number of commits in a bunch for a given run of this test suite. const bunchSizes = currentBenchmarkMode === BenchmarkMode.Performance ? [10, 100] : [2]; // Number of local commits to rebase over the inbound bunch const localTrunkSizes = currentBenchmarkMode === BenchmarkMode.Performance ? [1, 10, 100] : [2]; for (const bunchSize of bunchSizes) { for (const localTrunkSize of localTrunkSizes) { benchmarkIt({ title: `Rebase ${bunchSize} inbound commits over ${localTrunkSize} trunk commits`, correctnessTimeoutMs: 5000, ...benchmarkDurationBatchless({ benchmarkFn: (state) => { let running: boolean; do { const { provider, sender, receiver } = setupSenderAndReceiver(); // Send local commits from the receiver and flush them so they are sequenced. These are // the commits that will be in the trunk. sendLocalCommits(receiver, localTrunkSize, "r"); receiver.containerRuntime.flush(); // Send local commits from the sender but don't sequence them yet. We want them to be // sequenced after the receiver has received its local commits and they are in its trunk. // These are sent before the receiver's commits are processed so that their reference // sequence number is older the receiver's commits. sendLocalCommits(sender, bunchSize, "s"); // Synchronize the messages. The receiver will receive its local commits and they will // be in the trunk. receiver.containerRuntime.resumeInboundProcessing(); provider.synchronizeMessages({ flush: false }); // Flush the sender's local commits now to sequence them. These will be rebased by the // receiver over its trunk when it receives them. sender.containerRuntime.flush(); // Synchronize the message. The receiver will received the bunched commits from the // sender which will be rebased over the trunk. running = state.time(() => { provider.synchronizeMessages({ flush: false }); }); } while (running); }, }), }); } } }); }); describe("big transaction composition", () => { const editCounts = currentBenchmarkMode === BenchmarkMode.Performance ? [10, 100, 1000] : [5]; for (const editCount of editCounts) { benchmarkIt({ title: `Compose ${editCount} sequence edits into a single transaction`, correctnessTimeoutMs: 5000, ...benchmarkDurationBatchless({ benchmarkFn: (state) => { let running: boolean; do { const provider = new TestTreeProviderLite( 1, factory, undefined /* useDeterministicSessionIds */, FlushMode.TurnBased, ); const tree = provider.trees[0]; tree.containerRuntime.connected = true; const view = tree.viewWith( new TreeViewConfiguration({ schema: StringArray, }), ); view.initialize([]); running = state.time(() => { Tree.runTransaction(view, () => { for (let iEdit = 0; iEdit < editCount; iEdit++) { view.root.insertAtEnd(`${iEdit}`); } }); }); const actual = [...view.root]; const expected = makeArray(editCount, (index) => `${index}`); assert.deepEqual(actual, expected); } while (running); }, }), }); } }); });