Performance: merges with many heads and commits with many scattered edits (patch_make O(N·k), candidate diffs)

Start by reading the recordMerge and makePatch paths mentioned in the issue, then inspect the diff-match-patch patch_make implementation and its tests. Compare the proposed work in the stated order: P1, P3, P2, then P4; each item is intended as a separate PR with probes. Done means the selected change meets its stated correctness and replay requirements and includes measurements; the probes are available on request.

Merges with many heads, and commits with many scattered edits in large text, are slow, and their transient memory is high. The cost is mostly in makePatch, through diff-match-patch's patch_make, and recordMerge multiplies it.

Measurements

Each case ran in a fresh Node 26 process with main at bdd325c (plus #25). The figures are wall time and peak RSS (maxRSS).

A db document with string columns, merge3 on records (immer-db codec)

• Shape: 20 records of 256 KiB text (5 MiB in total). Each of 8 heads edits every third line of every record (each head its own lines).

• Applying the 7 remote heads: 17 s; 7 merge3 calls account for 16 s.

• The merge commit: 64 s, in 9 makePatch calls (the patch, plus 8 candidate diffs in recordMerge), about 7 s each.

• Peak RSS: 0.66 GB.

• Scaling at 1 MiB with the same shape:

  heads	apply heads + merge commit
  8	18.6 s
  16	23.0 s
  32	30.7 s

  Peak RSS rises from 0.35 to 0.59 GB.

• Few edits are cheap: the same documents with a few edited records take under 1 s, and less than 0.2 GB, even at 32 heads.

• 0.13.0 behaves the same.

StringDocument with mergeStrings3

• Shape: 380 KB, 8 heads, each editing a third of its lines.
• The merge commit: 7.5 s, and it raises peak RSS by 1.8 GB. Each of the 8 candidate diffs raises it by 0.4 to 0.46 GB.

diff-match-patch alone (diffTimeout 0.2 s), text with k scattered edits

The CPU profile of patch_make (1 MB, 1,000 edits) shows two hot spots:

• patch_addContext_, 67%: for each patch it calls indexOf and lastIndexOf on the whole text, to grow the context until it is unique;
• patch_make itself, 19%: it rebuilds postpatchText with substring and concatenation after every diff.

Both are $O(N \cdot k)$ for a text of length $N$ and $k$ patches.

Proposals (revised after review)

• P1. Bound recordMerge's candidate diffs.
  • Diff at most 2 parents, in a canonical order: for example, the order in which parents is recorded.
  • Each candidate gives either a complete, valid mergePatch or a refusal; never a partial result.
  • Each candidate diffs an exact parent value to the same immutable merged value. The recorded mergeParent and mergePatch must reconstruct that value, with deterministic tie-breaking.
  • The chosen mergePatch is recorded in the patch, and every client replays the recorded result rather than recomputing it, so all clients get the same value.
  • This changes record sizes, so callers that measure a commit before making it should keep using previewCommit.
  • A budget checked between makePatch calls can't bound one pathological call. So either makePatch gets a deterministic work budget of its own (see P3), or the caller runs the merge where it can be stopped.
• P3. A deterministic diff bound (moved earlier).
  • Replace the wall-clock diffTimeout with a work-based bound (for example, counted operations in diff_main's bisect), so that the same inputs always give the same patch on any machine.
  • Today the cutoff depends on CPU speed, so a commit's patch, and its size, aren't reproducible.
• P2. A byte-identical patch_make optimization (in @cocalc/diff-match-patch).
  • Derive the post-patch text from the original texts and offsets, instead of rebuilding it with substring and concatenation after every diff.
  • The output must be byte-identical. Tests compare the old and new implementations on corpora, including repetitive text, and the change is measured.
  • This speeds up only patch_make's assembly; diff_main keeps its own (P3) bound. It doesn't make diffing linear end to end.
• P2b (optional, later). Bound patch_addContext_'s uniqueness search.

  • This changes the context of generated patches in repetitive text, so it would be a separate, versioned change, with these tests:

    • exact reconstruction;
    • mixed-version replay, where old and new clients apply each other's patches;
    • ambiguous fuzzy replay;
    • cross-version golden tests;
    • repetitive text, and insertion and deletion drift;
    • an audit of legacy-history replay that still uses merge3 or fuzzy application.

    Old replay semantics are preserved, or the change in behavior is versioned.

• P4. Byte-based cache sizes for db documents.
  • The value and exact-value caches use count() in sizeCalculation. For a db document that is the number of records, so the 10 M size limit doesn't bound bytes; only the entry limits (100 and 2,000) do.

Order: P1, P3, P2, P4, then P2b (optional). Separate PRs, each with its own probes. The probes are available on request.