Performance

Copied from go-crdt/crdt docs/performance.md at 8aefdc0 (v0.55.3). This page is a copy: when the two differ, the one in the crdt repository is the measurement and this is a stale transcript of it.

On the trace everybody publishes against

The sequential editing traces at josephg/editing-traces are the common yardstick for text CRDTs — Yjs, Automerge and diamond-types all report against them. automerge-paper is the canonical one: 259 778 single-character edits recorded from someone actually writing a paper, ending in 104 852 characters with 77 463 tombstones.

Apple M4 Max, Go 1.26.4, darwin/arm64:

Reproduce it, and check the result against the recorded final text:

curl -sLO https://raw.githubusercontent.com/josephg/editing-traces/master/sequential_traces/automerge-paper.json.gz
CRDT_TRACE=automerge-paper.json.gz go test -run TestEditingTrace -v
CRDT_TRACE=automerge-paper.json.gz go test -run '^$' -bench EditingTrace -benchtime 5x

The replay is a correctness test before it is a benchmark: a quarter of a million edits at positions a real person chose, with the answer known in advance, plus a snapshot round trip and a full reload. CI runs it on every change.

Measured against other implementations

The numbers above are ours. Setting them beside the figures other projects publish would compare four machines, so the other implementations were run here instead: same machine, same trace, same protocol, on 2026-08-16.

Every implementation is driven the way its own published benchmark drives it, and every run rebuilds the document and compares it against the endContent recorded in the trace before any time is reported — a replay that produces the wrong text fails rather than printing a number. Verification is outside the clock. The harness is in docs/comparison/: one file with one timing loop and one adapter per library, so the measurement cannot differ between them.

Apple M4 Max (16 cores, 128 GiB), macOS 26.6.2, Go 1.26.4 darwin/arm64, Node v26.4.0. Twelve interleaved rounds of docs/comparison/paired.js — one replay per arm in rotation, each process staying warm — on a machine whose load1 fell from 4.7 to 3.1 across the run and never rose above 6.7. The × column is the median of the per-round ratios, which is what pairing buys; the min–max column is the spread of the raw times.

diamond-types is still faster than we are, by about a tenth, and that is the result. It is the fastest text CRDT anyone has published and it stays that way here. Its one wide round — 31.4 ms against a median of 18.5 — is its native module warming up on the first round; every later round is within 17.7–20.2 ms.

The honest reading is that we are in its range on this trace, and ahead of everything else measured. What that costs in a property rather than throughput is the section after next.

What re-taking it showed

The table this replaces was taken in blocks — each library its own command, its own stretch of wall-clock time — before paired.js existed. Re-taking it is how three things came out.

The instrument reproduces what did not change. diamond-types and automerge-wasm are the same versions as before and land on the same numbers: 18.4 → 18.5 ms and 8 262 → 8 247 ms. Yjs moved one patch release and 3 079 → 3 101 ms. Nothing here says the new protocol measures differently from the old one, which is what makes the two rows that did move worth reading.

Automerge is 6.9× faster than it was, and the old figure was right when it was taken. 3.4.1 published at 26 492 ms; 3.5.0 reads 3 875 ms. Installed side by side and run alternately on this machine, 3.4.1 reads 26 843–28 731 ms and 3.5.0 reads 3 997–4 016 ms, so the change is the library’s and not ours. It also reverses the bottom of the table: the JS wrapper is now twice as fast as the raw WebAssembly binding it wraps, where it used to be three times slower.

Loro reads 186 ms where 692 ms was published, and the version is not the reason. loro-crdt moved 1.14.1 → 1.16.3, so that was the first thing to check: 1.14.1 reinstalled and run today reads 198–216 ms. The adapter has been touched by exactly one commit — the one that introduced this harness and published that table — and Node is the same v26.4.0, and the published protocol (--runs 10) reproduces at 192 ms. So: not the version, not the adapter, not the runtime, not the protocol.

What is left is the state of the machine during that block, and the published row carries the mark of it — its spread was 573–1007 ms, a factor of 1.76, where every other row in that table spanned 1.02 to 1.34. Contention of the right size does reach that magnitude: under twelve busy loops loro barely moves (191 → 197 ms), but under thirty-two, three times oversubscribed, it reads 397–551 ms. That is the neighbourhood of the published figure without being a proof of it, and it is as far as this can be taken — the run itself is not repeatable.

That is the third thing a block design cost this document, after the Fugue row being 14% out and the diamond-types comparison being made across two sessions. This one is the worst of the three and the least visible: a single row 3.5× too slow while every row around it was correct, which is exactly what giving each library its own stretch of time allows and exactly what nothing in the output says.

What non-interleaving costs

The table above prices throughput. This row prices a property.

crdt is an RGA, which is proved free of forward interleaving and exhibits the backward kind — type a word, move the cursor back, type another, and somebody else’s concurrent word can land between yours. See doc.go and TestTwoOfYourCharactersStayTogetherWhenYouTypeForwards. Fugue (Weidner & Kleppmann, The Art of the Fugue) is proved free of both, and list-positions is its authors’ implementation.

So: what would that guarantee cost? It is the list-positions row in the table above — 173 ms against our 20 ms, 8.74×. Four runs on four occasions put it at 8.13×, 8.40×, 8.60× and 8.74×, and they line up the way the section below predicts: the lowest came from the block control and the highest from the quietest machine, because contention costs our shorter arm more than it costs Fugue’s and so pulls the ratio down.

About an order of magnitude, then, and — worth saying because the Fugue paper compares itself to Yjs — roughly eighteen times faster than Yjs while doing more.

Two things this does not measure. It crosses languages: Fugue here is JavaScript and we are Go, the same caveat the Runs on column carries for every other row. And its saved document is JSON — 493 KB against our 260 KB of binary — which compares encodings, not designs, so it is left out of the size table below.

The first version of this row said 9.6×, and that was 14% too high

It was measured by running bench.js fugue, then bench.js yjs, then the Go benchmark: each arm its own command, each its own stretch of wall-clock time. The machine was busy, the text said so, and it excused itself on the reasoning that whatever the machine was doing landed on all three alike.

It does not land on all three alike. That is worth more than the row it corrects.

Under twelve busy loops, interleaved so that every arm meets the same machine:

Contention costs us twice what it costs Fugue, so a busy machine moves the ratio by a third — towards Fugue. Four things follow.

A busy machine flatters whatever you are slower than. The penalty fell hardest on the fastest arm and least on the slowest — ours ×2.04, Fugue ×1.28, Yjs ×1.23 — so contention shrinks a lead rather than distributing itself. A comparison run on a loaded workstation understates whoever is winning, and the error is not noise: it has a direction.

Most of that is the length of the window, not the language. A 21 ms measurement loses a whole scheduling quantum where a 180 ms one absorbs it, and the fastest implementation necessarily has the shortest window. Timing eight consecutive replays under one clock — --repeats ours=8, so our sample lasts 168 ms like Fugue’s — takes our inflation from ×2.04 to ×1.42 and the ratio from 5.4× back to 7.6×. That is more than half of the gap, and it is not all of it: at equal window length we still lose somewhat more than Fugue does.

The minimum recovers some of the rest, and the literature says why it cannot recover all of it. Chen and Revels model the environment as adding delay and never removing it (Robust benchmarking in noisy environments, IEEE HPEC 2016, the strategy in Julia’s BenchmarkTools): if every error term is positive then the smallest sample is the one with the least error in it, which is why they estimate with the minimum rather than the mean or the median. On the contended run the minimum does pull the ratio from 5.4× back to 7.4× without any change to how the arms are driven. But their equation (9) is the reason it stops there — repetition removes a delay that sometimes fires, not one that fires on every execution, and a starved CPU is the second kind. 7.4× is still 12% short of 8.4×. The minimum is a better estimator, not a substitute for a machine with a spare core.

A load average cannot label a measurement. It is an exponential average over a minute, so it lags in both directions. The first round of the contended run read load1 10.69, a value the uncontended block control had spent its whole run inside, while the twelve busy loops were already there and every arm was already slow: ours 27.5 ms against 19.9–21.8, Fugue 215 ms against 171–191. paired.js records load1 beside every timing so a reader can see what it said, not so a result can be justified by it.

Why it survived: this document already had the habit, for the comparison it makes often. Every measurement of one of our releases against another says how it was taken — beside the release before it on the same machine in one session, and the UTF-16 pair alternately, build against build. It was the comparisons with other implementations, made rarely, that were left to whatever the machine was doing. The discipline was there; it had simply never been pointed outward.

One thing this does not say: that running each implementation as its own command is wrong. --block does exactly that with the same processes and the same code, and on a machine whose load is steady it agrees with the interleaved form to within the spread — 8.1× against 8.4×. Blocks are not wrong; they are unprotected, and nothing in their output says which of the two they were. The table above them was taken that way, before paired.js existed, and has not been re-run.

Document size, where we do badly

Encoding the replayed document:

Re-verified on 2026-09-30, and every row reproduces. Sizes do not depend on what the machine was doing, so this half of the comparison was never exposed to what the timing table above had to be re-taken for — and saying so is only worth anything because it was checked: diamond-types at 108 996 bytes, Yjs at 159 929 and 311 038, ours at 259 890, all to the byte.

Each row is labelled with the version that produced it — including when the pin moves under it, as loro-crdt has twice. The harness installs 1.16.4 today; it encodes this document into the same 251 391 bytes as 1.16.3, to the byte, and a paired run against it replays in 188.7 ms, inside the 185.1–213.4 ms the table above records. Neither row is re-taken for it, because a row measured on a different day under a different load is the thing this page spent #132 removing.

Two other versions have moved without moving a format either. Automerge 3.5.0 encodes this document into exactly the same 129 103 bytes as 3.4.1 — the 6.9× it gained in speed cost nothing and bought nothing here — and loro 1.16.3 lands 33 bytes from 1.15.1 on a 251 KB document. So the table is current to within those 33 bytes, not merely correct as taken.

This is what the comparison was for. At 0.4.0 ours was between eight and twenty-four times larger than anyone else’s, because Snapshot wrote one record per character while everyone else writes runs. Version 2 of the format writes runs too, which took it to 620 KB.

† diamond-types compresses its text inside its own format, so its first column is not an uncompressed figure. Cargo.toml has default = ["lz4", "storage"], and src/list/encoding/encode_oplog.rs puts content in a ContentCompressed chunk for any document over twenty bytes:

// Right now I'm compressing content whenever len > 20.
const MIN_COMPRESSED_LEN: usize = 20;

Its text — the part that is 182 KB of plain characters in ours — is LZ4’d in there. That is corroborated by its gzip ratio: 1.17× on a document whose largest component is English prose is what is left when the prose is already compressed. (The crate’s defaults are what is quoted; the feature flags the diamond-types-node build uses were not checked.)

So the first column compares one format that compresses the biggest thing in the file against five that do not, under a single heading. The second column is the one that compares the same operation applied to everybody.

Uncompressed is not the only column, and the other one says something else

Uncompressed we are third of six at version 8, behind diamond-types and Automerge; at version 6 we were last. Through gzip we are fourth of six, ahead of Automerge and Loro, and within a quarter of diamond-types. Both numbers are true; this page reported only the first one for several releases, which overstated the gap.

The ratio is the part worth reading. Automerge does not compress at all: 129 103 bytes in, 129 161 out. It grows by 58 bytes, which is gzip’s header on a stream with nothing left to find. diamond-types manages 1.17×, Loro 1.30×.

Ours was 4.13× and is now 2.31×, and what is left of it is the text: the structure is 78 KB with next to nothing in it for a compressor to find, and the 182 KB of English prose beside it is not.

Run-length encoding is not a technique to weigh here, it is the baseline: the diamond-types encoding module opens by saying it “is modelled after the run-length encoding in Automerge and Yjs”, so all three implementations ahead of us use it and the fastest and smallest says so in its first paragraph.

The 4.13× was a direct measurement of how much redundancy version 6 left in the file, and it was the same finding as the field-by-field accounting below arrived at from the other side: three columns held one repeated value and cost 15% of the file, because there was one encoding here where Automerge picks between a run-length, a boolean and a delta encoder per column. Its 1.00× is what those look like from outside. Version 8 picks per column too, and those three columns now cost twelve bytes between them.

Where it matters depends on who is storing the bytes. gitstore writes through git, which deflates every object; pgstore writes a bytea, which Postgres compresses once it is large enough. Both collect most of that 4.13× without anyone doing anything. DirStore and MemoryStore do not, and neither does a transport. See issue #88.

What the gap actually was

This page used to say the rest was the text: “ours is 182 KB of characters written plainly, which already exceeds their whole document.” That was true and it was not the answer. If the text is 182 KB of 620, something else is 438 KB, and 438 KB is four times diamond-types’ entire document — so compressing the text would have left most of the gap standing.

That has since been measured rather than reasoned about, on version 6:

Of the 362 KB a general-purpose compressor removes from this file, the text is 133 KB of it and the structure 230 KB. The text is the largest single component of the file and it is not where most of the removable redundancy is; those are different questions. Compressing the text is worth 1.38× on its own — worth having, and much less work — but the columns are where the larger share sits. This is the same conclusion the paragraph above reached in 2026 by subtraction, with the number attached.

TestSnapshotBudget accounts for every byte Snapshot writes, by the field that wrote it. On the same document, under version 2:

The deletions were the largest thing in the file, larger than the text, and on their own nearly three times diamond-types’ whole document. Half of that — 148 KB — was one field: the sequence number of the operation that did the deleting, written in full at three bytes each, 50 276 times.

Version 3 writes it as a signed step from the last sequence number that site deleted with. A person deleting text works through it rather than jumping about, so the step is usually one byte. Measured before it was built, on this trace:

which is what took the document from 620 KB to 527 KB.

Then the same question, of what was left

With the deletions halved, the three fields under them were 116 KB between them, and the same measurement answered the same way:

The clocks are the interesting one: 10 824 bytes is one byte per run, and it is not a coincidence. A clock can never fall below its own sequence number — a site’s clock advances at least once per operation it issues — so the distance between them is small, unsigned, and needs no sign bit. Writing it that way also means a snapshot can no longer express a clock the loader would have had to refuse: the invariant moved out of a check and into the format.

Version 4 writes all three. 527 KB to 478 KB, and 620 KB to 478 KB since the runs were introduced — a 23% cut in two steps, both of them measured first.

What is left is mostly the text: 182 KB of it, 38% of the file, written plainly because this package has no dependencies and a compressor is a dependency. The deletions are still 43%, but three quarters of that is now the offsets and spans themselves rather than the identities attached to them.

The document size gap is an encoding, not a compressor

At version 4 a real document encodes to 478 KB where diamond-types takes 109 KB, and this page used to put that down to the text being written plainly. It is not the text. Compressing the snapshot as it stands takes it to 148 KB — still a third bigger than their whole document — because the fields are interleaved: a compressor looking for repetition sees a run’s identity beside its text beside its deletions.

Written one field at a time, each column is a stream of similar numbers, and a compressor is very good at those. The same document, same fields, same step encodings, laid out in columns and compressed per column:

Against diamond-types’ 111 616 bytes that is 87%. The deletion fields are the sharpest: 206 KB to 18, because a column of small gaps and spans repeats itself in a way the same numbers scattered between other fields do not.

Which compressor, measured rather than assumed

Every one of these is pure Go. Same columns, best setting of each:

brotli wins on every column, including the small-varint streams where it would be least expected. Two settings were measured rather than guessed: the window must be at least 2^20 — at 2^16 it costs 2.4 KB, and past 2^20 nothing changes — and compressing per column beats one stream, 96 703 against 97 811, so the column boundaries are worth more than the redundancy across them.

That is the one dependency worth taking: it buys 14% against the next best, where zstd’s advantage was one column.

And what it costs, which decides the setting

brotli’s top quality is very slow. The ladder, per column, on the same 478 KB:

Quality 5 is already ahead of them, at seven milliseconds. The cliff is between 9 and 10: fourteen milliseconds becomes a hundred and sixty-seven, for seven kilobytes. So q9 is the setting to default to — ahead of diamond-types, and costing about what zstd costs — and q11 is for an archive that is written once.

Decompression does not have this problem: 2 ms, 292 MB/s, and that is the side that runs whenever a document is opened.

This is also the honest answer to whether one of our own compressors should be used instead. go-compressions/deflate accelerates match extension with SIMD, but DEFLATE’s density is what it is — 112 KB here — so the SIMD buys time on a format that cannot reach the number. Where a SIMD brotli encoder would pay is exactly the q10 and q11 rows, and what it would buy there is the 167 or 425 milliseconds rather than any bytes. q9 does not need it.

What is not decided by this

Snapshot says the same state is the same bytes, and every format change so far has kept that. A compressor’s output is deterministic for a build and not promised across versions of the library, so compression belongs beside the format rather than inside it: the canonical form stays the columnar bytes, and whoever stores or sends them compresses. A plain whole-blob compression of the columnar layout gives 97 811 rather than 96 703, which is the price of keeping the boundary in the right place.

And so, version 5

The format writes the columns. Each is length-prefixed, so whoever stores a snapshot can take them apart and compress them one at a time. Measured on the same document: 115 KB with the standard library’s flate, against 148 for version 4, and about 106 with brotli at quality 9 — under diamond-types’ 109, with the one dependency and without it we are level.

Small documents pay a little for it: nine column lengths is nine bytes, so the version 2 fixture grows from 96 bytes to 105. This is a format for documents, and a document with two runs in it is not the one the 478 KB came from.

And so, version 8

Version 5 gave every field a column and left every column one encoding, which is a uvarint per value however many times that value is the same one. Version 8 gives a column groups: a run is a count and a value, and everything else is a literal stretch. It also splits the deletion fields, which version 5 wrote as one column of gap, span, site and step over and over, into four columns of one kind of number each — interleaved, no two neighbours are alike and nothing repeats.

On automerge-paper, 478 474 bytes to 259 890, and the three columns that started issue #88 from 71 924 bytes to twelve:

The threshold is measured rather than chosen. A run costs a count and a value; leaving a pair in the literals costs the two values and nothing else, while writing it as a run also costs the two group headers that cutting the literal stretch in half needs. Over these twelve columns a threshold of two costs 266 270 bytes, three costs 259 840, four 259 808 and six 261 016. Three is where it turns, and it is the smallest number at which no column here is larger than writing it out plainly would have been — the two that are, run and origin sequence steps, are three and four bytes larger.

What this does not buy is compressed bytes. Compressed per column, which is what a store does, version 6 is 112 211 bytes with the standard library’s flate and version 8 is 110 487: 1.5%. Whole-blob gzip goes 115 897 to 112 522. A general-purpose compressor was already finding almost all of this; what version 8 changes is the size of a snapshot nobody has compressed, which is what DirStore, MemoryStore and every transport hold, and it halves it.

The compressed text chunk, and why nothing writes one

diamond-types LZ4s its text for any document over twenty bytes, and the obvious next step here is the same thing with compress/flate. A version 8 column says in its first byte how it is stored, and the reader understands a deflated one, so a peer or a later release can send one without this build refusing the snapshot. Nothing here sends one. The numbers are why:

It halves a snapshot nobody compresses and costs 25 bytes to everybody who does. And it costs the promise directly above: Snapshot says the same state is the same bytes, and two replicas on different builds of Go would stop agreeing about a document they both hold. So the reader learns it and the writer does not, which is the same order #83 shipped OpSuperseded in. Writing it is one constant, and it wants a caller that stores snapshots raw and does not need them comparable — which is a decision about callers rather than about the format.

Memory

Only where it can be read honestly. Yjs is JavaScript, so heapUsed after a forced collection is its document; Automerge, Loro and diamond-types keep theirs in WebAssembly linear memory, which process.memoryUsage() does not see, so there is no figure for them here rather than a bad one.

Per visible character, because that is the only count the two agree on: the document ends with 104 852 characters, and we additionally hold 77 463 tombstones, which is where the per-stored-character figure at the top of this page comes from. Yjs’s default gc: true discards deleted content, so the gc: false row is the closer comparison — and we are below both.

Re-taken on 2026-09-30. Yjs reproduces — 5 680 KiB against the 5 678 first published, and the gc: false row lands on 7 256, the bottom of the 7255–7573 that was recorded then. Ours grew, from 4 034 KiB at 0.4.0 to 4 541 today, and the two sections below account for it: the index over runs, and the second summary for UTF-16 offsets, which took a block header from 144 bytes to 160 and the document from 4 372 KiB to 4 541. That growth was measured when it was made rather than discovered here; what this table had wrong was only that it went on quoting 0.4.0 while the rest of the page had moved on.

We are still below both Yjs rows, by less than the old number claimed: 44.3 bytes per visible character against 55.5 and 70.9.

Ours read 4 541, 4 541 and 4 547 KiB over three runs — an earlier version of this paragraph said it “varied by not one byte”, which was true of 0.4.0 and is not true now. Yjs read 5 680, 5 680 and 5 998 (gc: true) and 7 256 three times (gc: false).

What this does not say

• These libraries do not all do the same job. Automerge maintains a whole JSON document with history, rich-text marks and branch metadata; Yjs and Loro carry several shared types. This is a text CRDT. A trace of single-character text edits is the workload they all publish against, but it flatters the implementation that does least.
• Yjs is JavaScript and the rest are compiled. That it is 128× slower than compiled code on a tight per-character loop is not a defect in Yjs.
• The Yjs figure here is faster than the 5 714 ms dmonad publishes for the same benchmark, on newer hardware and without the update observer his harness registers. Our encoded size for Yjs, 159 929 bytes, matches his published docSize exactly, which is the check that this harness reproduces his.
• Automerge 3.4.1 measured slower than the 14 326 ms dmonad publishes, on faster hardware — he pins @automerge/automerge@^2.1.10. That was left uninvestigated here, and 3.5.0 has since settled it in the other direction: 3 875 ms, well under his figure, measured against 3.4.1 alternately on this machine at 26 843–28 731 ms. The automerge-wasm row is the same trace against Automerge’s Rust core with the JavaScript document wrapper removed; at 3.4.1 that removed about two thirds of the cost, and at 3.5.0 it adds cost — the wrapper is now twice as fast as the raw binding.
• Wrapping the whole Yjs replay in a single doc.transact makes it slower, 9 406 ms against the 3 079 ms the same session measured for the per-edit form, so the form used here is both what Yjs’s own benchmark does and the faster of the two.
• One Automerge.change per edit, rather than one for the trace, costs about 101 µs/edit over the first 20 000 edits — Automerge’s own benchmark batches, and this is why.

Reproduce all of it:

cd docs/comparison && npm install
CRDT_TRACE=…/automerge-paper.json.gz node --expose-gc bench.js yjs --runs 10

Ten thousand clients on one file

The trace above is one person typing. This is the other question: what happens when ten thousand of them are on the same document and the network is broken.

TestAHundredClientsAndABrokenNetwork is a hundred by default and takes its size from the environment. What it does to them: partitions lasting several rounds, batches that never arrive at all, delivery shuffled and duplicated, clients that arrive long after the session started and are welcomed with a snapshot, clients that lose their connection and go on typing, clients that come back and have to be reconciled in both directions, clients that close the tab for good, processes restarted from a snapshot, and replicas throwing away what they were holding back. Everybody types near the front, so the same characters are contended.

The claim, checked two ways: once the network heals, every client holds a byte-identical snapshot, and each agrees with itself — the index against the list it indexes, the counters against the blocks they count.

The test refuses to pass if the chaos did not happen: no losses, no duplicates, no restarts, no reconciliations, nobody joining, disconnecting, reconnecting or leaving, no offline edits, no deletions, or an empty document all fail it.

Ten thousand clients do not each hold a connection to the other nine thousand nine hundred and ninety-nine, so the harness has what a real deployment has: a hub they sync against, which arbitrates nothing and is a replica like any other. Without it the run still converges and proves less — every client edits its own almost-empty copy and they meet once at the end. With it, three quarters of the edits land on a document somebody else has already been writing.

What actually grows with the number of clients

A replica’s memory is a function of the document, not of how many people are editing it: ten thousand clients each hold one document, and the document is the same size whoever holds it. (The 26.9 GiB above is this harness holding ten thousand of them in one process.)

One thing does grow. A version vector carries an entry per site that has ever written, it is exchanged on every sync, and OpsSince walks it:

Linear, at about ten nanoseconds a site, which is what a map lookup costs. Said plainly for a deployment: a server telling ten thousand clients “you are up to date” once a second spends about a second of one core doing it, and reads a thirty-kilobyte version for each answer. That is the price of asking “what am I missing” with per-site vectors. It is not a defect and there is nothing cheaper to do inside a call that is handed the vector; batching or sharding it is the job of the protocol above.

A composite’s version is per part and per site, so it multiplies: 1 000 sites cost 4 758 bytes over one part and 47 979 over sixteen. That is the same argument structured.Blocks is built on, measured at the version rather than the part.

Synthetic benchmarks

On a document of 10 000 characters:

go test -run '^$' -bench . -benchmem. The last two arrived with 0.5.0; their 0.4.0 column is the same benchmark run against the release before it.

The 0.5.0 column holds two changes and a busy machine, so it was taken beside the commit before it in the same session, which read 32.9 ns, 291 µs, 607 µs, 24.0 µs and 4.19 B/char. Load is the run-length snapshot format; what the index costs here is under a nanosecond of InsertAtEnd and 4 µs of ApplyRemote.

The today column was taken beside the 0.5.0 one, not quoted across the fifty releases between them: both trees built and run alternately, six rounds each, medians. Measured that way the commit the 0.5.0 column describes reads 34.98 ns, 304.89 µs, 641.27 µs, 25.23 µs and 1.17 ms — within 4–8% of what it published, which is what says the comparison is between the two versions and not between two sessions. Fifty releases cost 15% on ApplyRemote and 16% on Load and nothing anywhere else.

† A benchmark whose answer depended on how long you ran it

ScatteredInsert inserted into a document it never stopped growing: one character per iteration, from the same b.N loop whose length Go chooses by ramping until a second has passed. So its answer was a function of b.N — and therefore of how fast the machine was that day, in the direction nobody expects. A faster machine reaches a larger b.N, inserts into a larger document, and reports a worse figure.

On the commit that first published this row, that same code reads:

The 0.37 µs this table used to quote is the 1000x reading. Nothing was wrong with the measurement; what was wrong was treating it as a quantity the code has. Run the same command on this machine today and it prints 1.3 µs — not because anything regressed, but because a second now buys a million iterations.

The benchmark now rebuilds its document whenever it grows past 110% of benchSize, with the timer stopped, so the thing being measured is an insertion into a document of about ten thousand characters, which is what the row claims. It reads 360–410 ns from a hundred thousand iterations upward, and the default budget is thirty times that.

And there was no regression. With the bounded benchmark run alternately on both trees, the 0.5.0 commit reads 405.8 ns and today reads 410.6 ns — 1.01×. The published 0.37 µs was about right for what it names; it just could not be obtained twice.

What changed, and why

The position mark, and then a list that walks both ways

Finding a rune offset means walking the document. The first measurement was blunt: inserting at the end of a 10 000-character document took 68 052 ns against 218 ns at the start, and the whole difference was the walk. Remembering where the last local edit ended took that to 231 ns.

That mark only helped forwards, which the real trace exposed immediately: a replay that should have taken milliseconds took 2.79 seconds, because half the edits move the cursor back a little and every one of those walked from the start of the document. Blocks now carry a back pointer and the walk goes whichever way it must, and a deletion re-establishes the mark instead of dropping it.

2.79 s → 50 ms on the real trace, a factor of 56, and it is the single change that put this in the same range as the fastest implementations rather than an order of magnitude behind them.

Characters indexed by sequence number, not by identity

Integration finds a character from the identity an operation names. That was a map[ID]*item, and the map cost about as much again as the character it pointed at. It was never needed: a site’s sequence numbers start at one and have no gaps, and Apply refuses an operation until its predecessor has landed, so position in a slice is the sequence number.

107.7 → 73.1 bytes per character, and the write path halved — a map insert per character cost more than all the list work around it.

Run-length blocks

A character used to be a struct of its own: identity, clock, origin pointer, rune, deletion, next. Everything but the rune is derivable. A block is a run of characters one site typed consecutively, and for character k of that run the identity is {site, seq+k}, the clock is clock+k, and the origin is character k-1. A thousand characters typed in a row cost one header and their text.

Blocks are only ever split — by an insertion landing inside one — and extended, by the next character of the same run. There is no merging to do: a new character can never bridge two existing blocks, because that would need the sequence number the right-hand block already holds. Integration walks runs rather than characters, because within a run the clocks ascend, so whichever way the “sorts after the new character” test goes at the first character of a run holds for the whole run.

73.1 → 4.19 bytes per character on a document typed in one run, and the index shrank with it: it now holds one entry per run rather than one per character.

Waiting operations filed under what they are waiting for

A peer that sends a long history back to front used to be quadratic: every arrival rescanned everything still parked. Delivering the real trace in reverse — 337 000 operations, none applicable until the last — took 210 seconds.

Operations now wait in a map keyed by the single operation each needs, so integrating one wakes exactly its dependents. 210 s → 0.30 s.

Deletions stored as stretches

A block used to keep one deletion identity per character as soon as any character in it died — 2289 KiB of the 4015 the real trace occupied, and half of those entries described characters that were still visible.

A record now covers a whole stretch: characters [from, to) removed by one site’s operations seq, seq+1, …, so the operation that removed character from+k is seq+k. Backspacing over a word is one record rather than one per letter. The contiguity is enforced, not assumed — a deletion joins the record beside it only when its identity continues that record’s sequence.

Measuring first was worth it: the trace’s 77 463 tombstones collapse to 50 276 records, 1.5 characters each, because most are scattered corrections rather than long runs. That put the honest expectation at 2289 → 1178 KiB rather than the larger figure a guess would have promised.

The speed-up was the surprise. 54.6 ms → 24.4 ms on the real trace, because everything that walks a block — the text, the positional search, counting what is visible — now steps over stretches instead of testing characters one at a time.

One simplification fell out and is worth stating, because it looks like a missing case: a deletion can only ever extend the record ending where it lands. It can never fill a gap between two records, or lead into one, because a site’s operations are applied in sequence order — a record whose identities follow this deletion’s cannot already exist.

The snapshot format writes runs

Snapshot wrote one record per character: identity, clock, origin, the character, and its deletion — eight numbers each, twenty-five bytes per visible character of a real document. Comparing against other implementations made it plain that nobody else pays that.

Version 2 writes a run at a time — one header for a stretch one site typed consecutively, then its text, then the stretches of it that have been deleted — because everything about the characters in a run follows from the first one. 2 663 KB → 260 KB on the real trace, 25.4 → 2.5 bytes per visible character, and writing it is twelve times faster.

Version 1 was read until #99, so a document stored by an older build opened; the test for that used a snapshot produced by the v0.4.0 release rather than one this build wrote, because a fixture regenerated by the code it checks proves nothing. It went with the rest of versions 1 to 6: nothing holds those bytes, the project is in development, and every number quoted in this file is a measurement of a format, not a promise to read it.

Two things had to be true for this to work, and one of them was not free. The runs written have to be the same on every replica holding the same operations, or a snapshot stops being a convergence check. The blocks themselves already are — two that continue one another are never adjacent, because a character bridging them would need the sequence number the right-hand one already holds — but their deletion records are not: cutting a block divides a record, and replacing one character’s deletion when two replicas delete it at once cuts another. Writing them joined hides that. The randomised convergence suite found this immediately, by comparing encoded state rather than text.

An index over the runs

The list answers “what follows this” in a step and everything else by walking, which the mark makes cheap only while the next position is near the last one. Two things it is not cheap for, and the second is not a matter of taste:

• a position far from the last edit — a second cursor, a replace-all, a patch dropped into the middle, or simply a peer’s operation arriving between two keystrokes and clearing the mark — walks every run in between;
• integration walks forward from the origin over everything that sorts after the new character, so a peer naming one origin over and over makes the walk the length of the document. collab’s server integrates what its peers send, and peers need not be honest.

The blocks are now the nodes of an AVL tree in document order as well as links in the list, each carrying two summaries of its subtree: the visible characters it holds, which turns a position into a descent, and the block of it that sorts lowest, which turns that integration walk into one too. Measured back to back against the release before it, on the same machine in the same session:

The flood is the one to read twice. Its cost per operation was 2.8 µs at 2500 operations, 5.6 at 5000, 10.2 at 10 000 and 18.5 at 20 000 — doubling with the document, which is the quadratic stated below. It is now 193 ns, 214, 231 and 231: flat, because a subtree whose lowest-sorting block still sorts after the new character holds nothing to stop on and is stepped over whole.

The trace got faster rather than slower because real editing is not as local as the mark assumes: a fifth of the replay was walking.

Both walks keep their heads. Each starts along the list and turns to the tree only after sixteen runs, which is about what a descent costs, so typing pays nothing for the index and never sees it.

Three numbers went the wrong way, and all three are the same number. The index costs 32 bytes a run — three pointers, a count and a height, which takes a block header from Go’s 112-byte size class to its 144-byte one — and on the trace that is 338 KiB. InsertAtStart inserts one character per run at one end, so it pays a walk to the root of the tree per character and nothing else amortises it; it is the index’s worst case by construction. Applying a whole history allocates everything from nothing, and a profile of it is dominated by the allocator rather than by anything in tree.go — the 4% is that 8% of memory, arriving as collector work.

A B-tree holding runs in its leaves, as diamond-types does, would pay for itself here: no per-run node, a depth of four rather than seventeen, and iteration from the leaves. It costs the pointer identity of a block, which the mark, the per-site index and every walk in text.go are written in terms of.

The arithmetic, since it was measured rather than guessed at

A block is 152 bytes, and Go’s size classes here are sixteen bytes apart, so it is allocated in the 160-byte class: eight bytes of every block are paid for and unused. TestBlockFitsItsSizeClass pins this so it cannot drift.

The tail is what decides it. subMin ends at 136; subVis and subSup fill the word to 144 exactly; nsup and height spill past it and cost a whole further word. Five bytes of summary buy sixteen bytes of allocation, on every block.

Shaving that tail was looked at and rejected, which is worth recording so the next person does not look at it again:

• height is an AVL height, computed from its children. It is structural, not a priority that could be derived from the block’s identity and dropped.
• nsup could become a single bit — every use of it outside split is a test against zero — but that alone leaves the block at 148 bytes, which is the same size class. Nothing is saved.
• Reaching 144 means capping subVis or subSup so that height can live in the spare bits. A subtree’s visible count is already int32 for a stated reason: two billion characters is eight gigabytes of text. Capping it lower trades a bounded, honest limit for one that fails as silent corruption.

So the block cannot lose a size class without giving something up, and what it would save is about 4% of what a real document holds.

What the other answer is worth

The B-tree removes the per-run node rather than shrinking it, and that is a different order of answer. TestWhatTheBTreeWouldBuy measures it the same way, by declaring the shapes and asking Go:

The second line drops left, right, up, subMin, subVis, subSup and height; the third drops next and prev as well, since a B-tree iterates from its leaves and the backwards walk those exist for is what the index replaced.

On the real trace that is 676 KiB of the 4 541 the document holds, about 15% — against the 4% shaving the tail would have bought, for a change that gives up nothing. The B-tree’s own internal nodes are not free, but at any sensible branching factor they are a few percent of the leaves.

That was the case for spending a project on it. It was spent, and the prize did not survive contact — see below.

It was built, and it does not pay

The B-tree exists on the perf/btree branch: runs in the leaves, summaries in the parent, the AVL removed, the whole suite green on the real trace, and its answers compared against the AVL’s on 104 852 positions and 10 050 integration walks before either was taken out.

The table above is right about a run: 152 bytes becomes 120, which is the 128-byte class instead of the 160-byte one. What it is wrong about is the sentence that follows it — that the internal nodes are a few percent of the leaves. They are not, because the leaves are not free either. A node carries one entry per thing below it, and an entry is two counts, the lowest-sorting key of what it holds, and a pointer: twenty-four bytes against the thirty-two a run gives back, before the slack of a node that is not full.

That leaves one trade, and it was measured at both ends:

A node sized to what it holds recopies all of its summaries on every insertion, which doubles the allocations of the walk the index exists to protect and cost 22% of its time. A node with room to grow allocates like the AVL and costs more memory than it saves. The saving in the first row is the recopying; they are the same fact read two ways.

Nothing here is an argument against the shape. The depth is five rather than seventeen and the descent is a scan of one cache line. It is an argument that a per-run node costs about what a per-run entry costs, so replacing one with the other buys nothing — and that is worth knowing before anyone spends the project again.

A second summary, for UTF-16 offsets

Addressing the document in UTF-16 code units means turning a count of units into a count of characters, and the obvious way to do that is to walk the document counting. That is O(n) per keystroke, so the index carries a second summary instead — the visible characters of a subtree that take two code units, beside the count of visible characters it already carried — and a conversion becomes a descent.

The cost was measured before it was decided to keep the summary, because one nobody needs is still paid for by everybody. Both builds were run alternately in one session on a machine under a load average of nine, so that whatever the machine was doing landed on both; benchstat, n=14 on the trace and n=12 on the synthetic benchmarks.

Nothing moved by a distinguishable amount, and the trace — which is ASCII, and so should not have moved at all — did not. The two rows that come closest, InsertAtStart and ScatteredInsert at about +6% with p=0.07, are the two benchmarks that allocate one block per character, which is where the memory below is charged rather than the arithmetic.

The memory is exact, and it is the real cost:

The summary is two int32s: the visible supplementary characters below a block, and the supplementary characters the block itself holds, deleted ones included. Sixteen bytes rather than eight, because the header was 141 bytes in Go’s 144-byte size class with three bytes spare — any field, of any width, takes it to the 160-byte class. A single bool would have cost exactly what these two counters cost, which is why they are two counters and not a compromise.

The second of them is what keeps the work off documents with no emoji in them. A block that holds no supplementary character answers every question about UTF-16 units without reading a character, so splitting one or indexing one stays arithmetic instead of becoming a scan. And a document with none anywhere converts in constant time without touching the index at all, because its rune and UTF-16 offsets are equal by construction: InsertAtEndUTF16 measures 44.9 ns against InsertAtEnd’s 48.9, and 46.5 ns on the same document with one emoji added, which is the descent.

Where the memory goes now

Measured on the real trace: 10 824 blocks holding 182 315 characters, of which 77 463 are tombstones, in 4.4 MiB.

The remaining lever is still the block headers, now 160 bytes each.

Complexity

Both logarithms are the tree in tree.go, reached after sixteen runs of walking the list. Nothing an untrusted peer sends can make either of them worse: the tree is an AVL tree, balanced by height rather than by priorities a peer could compute, and a peer that could choose the priorities could choose a list.

Adding a run to the tree costs a walk to its root, which typing amortises over a whole run of characters — the change a keystroke makes is held against the block and carried up when the tree is next read — but which one character per run does not.