Awesome

CRDT benchmarks

A collection of reproducible benchmarks. PRs are welcome.

# Install Node.js https://nodejs.org
npm i
# Run all benchmarks (takes quite a long time)
npm start
# Run all benchmarks using bun
npm start:bun
# Run a specific benchmark (e.g. yjs)
cd benchmarks/yjs && npm start
# Run a specific benchmark in the browser
cd benchmarks/yjs && npm start:browser
# print collected results
npm run table

Benchmarks

B1: No conflicts

Simulate two clients. One client modifies a text object and sends update messages to the other client. We measure the time to perform the task (time), the amount of data exchanged (avgUpdateSize), the size of the encoded document after the task is performed (docSize), the time to parse the encoded document (parseTime), and the memory used to hold the decoded document (memUsed).

B2: Two users producing conflicts

Simulate two clients. Both start with a synced text object containing 100 characters. Both clients modify the text object in a single transaction and then send their changes to the other client. We measure the time to sync concurrent changes into a single client (time), the size of the update messages (updateSize), the size of the encoded document after the task is performed (docSize), the time to parse the encoded document (parseTime), and the memory used to hold the decoded document (memUsed).

B3: Many conflicts

Simulate √N concurrent actions. We measure the time to perform the task and sync all clients (time), the size of the update messages (updateSize), the size of the encoded document after the task is performed (docSize), the time to parse the encoded document (parseTime), and the memory used to hold the decoded document (memUsed). The logarithm of N was chosen because √N concurrent actions may result in up to √N^2 - 1 conflicts (apply action 1: 0 conlict; apply action2: 1 conflict, apply action 2: 2 conflicts, ..).

B4: Real-world editing dataset

Replay a real-world editing dataset. This dataset contains the character-by-character editing trace of a large-ish text document, the LaTeX source of this paper: https://arxiv.org/abs/1608.03960

Source: https://github.com/automerge/automerge-perf/tree/master/edit-by-index

• 182,315 single-character insertion operations
• 77,463 single-character deletion operations
• 259,778 operations totally
• 104,852 characters in the final document

We simulate one client replaying all changes and storing each update. We measure the time to replay the changes and extract the content (time), the size of all update messages (updateSize), the size of the encoded document after the task is performed (docSize), the time to encode the document (encodeTime), the time to parse the encoded document and extract the content (parseTime), and the memory used to hold the decoded document in memory (memUsed).

** For now we replay all actions in a single transaction, otherwise Automerge is running out of memory.

[B4 x 100] Real-world editing dataset 100 times

Replay the [B4] dataset one hundred times. The final document has a size of over 10 million characters. As comparison, the book "Game of Thrones: A Song of Ice and Fire" is only 1.6 million characters long (including whitespace).

• 18,231,500 single-character insertion operations
• 7,746,300 single-character deletion operations
• 25,977,800 operations totally
• 10,485,200 characters in the final document

Results

Notes

• The benchmarks were performed on a desktop computer "Intel® Core™ i5-8400 CPU @ 2.80GHz × 6" and Node 20.5.0.
• There is a more exchaustive benchmark at the bottom that only runs benchmarks on Yjs.
• memUsed only approximates the amount of memory used. We run the JavaScript garbage collector and use the heap-size difference before and after the benchmark is performed. If the heap is highly fragmented, the heap size might be larger than the actual amount of data stored in the heap. In some cases this even leads to a memUsed of less than zero.
• memUsed does not measure the memory usage of the wasm runtime.
• Automerge can perform the B4 benchmark in about 1 second (see time) if all changes are applied within a single change transaction. However, our benchmarks test individual edits that generate individual update events as this more closely simulates actual user behavior. See #21
• Note that parseTime is significantly higher with automerge and loro when the initial document is not empty (e.g. when syncing content from a remote server).
• Loro has a concept named snapshot, which can significantly reduce loading time as it contains the operations and the in-memory representation of the document. Note that this feature is only useful in applications that persist the document in regular intervals (which has it's own set of drawbacks, as encoding will block the ui). We enabled this feature by default. You can disable/enable this feature in ./benchmarks/loro/factory.js.

Older benchmark results that include automerge & delta-crdts

Development

Modify the N variable in benchmarks/utils.js to increase the difficulty.

License

The MIT License © Kevin Jahns

Except for /b4-editing-trace.js © Martin Kleppmann