Myers vs patience vs histogram diff is a choice about which equal items stay aligned. In OneDiff 1.0.1, Myers finds the fewest deleted plus inserted items unless it reaches a set search limit. Patience uses items unique in both ranges as anchors (equal items kept aligned), while histogram can also use repeated but uncommon items. Choose by the alignment you want readers to see, not just the edit count.
OneDiff is a free, open-source .NET text diff and document comparison library made by Recursive AI, licensed under MIT OR Apache-2.0 in version 1.0.1 (NuGet; GitHub).
dotnet add package RecursiveAI.OneDiff --version 1.0.1In a .NET 10 console project, replace Program.cs with this snippet and run dotnet run to select histogram and print the changed lines:
using System; using OneDiff; var settings = new DiffSettings { Algorithm = DiffAlgorithm.Histogram }; var diff = Diff.Lines( "red\n", "blue\n", settings); foreach (var edit in diff.Script.Edits) { var text = edit.Kind == EditKind.Insert ? diff.NewSpan(edit) : diff.OldSpan(edit); Console.Write($"{edit.Kind}: "); Console.Write(text.ToString()); }
Delete: red Insert: blue
These are OneDiff’s implementations of the three algorithms; their output is not guaranteed to match Git’s.
The quick snippet selects an algorithm; jump to the C# example for a side-by-side comparison of all three on inputs where their outputs differ.
What each algorithm keeps aligned
A diff splits input into items, also called tokens: lines, words, characters, or values in a sequence. An edit script is the ordered list of equal, deleted, and inserted runs that describes the change. The examples below use whole lines. A replacement counts as a deletion plus an insertion.
An anchor is an equal item or run that the algorithm keeps aligned while it compares the text on either side. The following rules describe OneDiff 1.0.1, not every implementation bearing these names.
- Myers: choose it for the fewest inserted and deleted items. It finds a minimum edit script unless capped. Ties are deterministic, not selected for readability. Myers rules.
- Patience: try it when a unique heading or code line should stay aligned, even if that requires more edits. It uses items occurring exactly once in both current ranges, keeping the largest set whose order agrees. It falls back to Myers where there are no candidates. Patience rules.
- Histogram: try it when useful landmarks repeat and patience has no unique item to use. It grows matching runs from shared items occurring at most 64 times in the old range, preferring a run containing a rarer item. Histogram rules.
Myers: minimum edits, not a readability score
For Myers, “minimum” means the smallest sum of deleted and inserted items. It does not mean the smallest displayed patch, the fewest change blocks, or the alignment a reviewer would choose. Several scripts can have the same minimum edit count.
OneDiff removes a common beginning and ending before the search. Its Myers implementation uses memory linear in the input and makes the same tie choices for the same input. The pinned Myers documentation explicitly separates those choices from readability cleanup.
In the first example below, three identical repeat lines switch sides with one anchor line. Keeping the three repeated lines aligned requires only two edits: insert anchor at the start and delete it at the end. That is the minimum, even if a reader regards anchor as the section that should stay in place.
Patience: unique items become landmarks
Patience looks for items that appear once on each side of the current comparison. It chooses an ordered set of those matches, then compares the gaps between them. “Ordered” means that the kept matches never cross: their positions increase in both texts. This is the increasing subsequence rule.
In the unique-anchor example, patience keeps anchor aligned. It deletes three repeat lines before it and inserts three after it: six changed lines rather than Myers’ two. Neither result loses text; they tell different stories about what stayed in place.
Uniqueness is checked within each range being processed, not just once for the whole file. If a range has no unique shared item, OneDiff finishes it with Myers. The second input repeats anchor twice, so neither line value is unique; patience produces the same edit rows as Myers for that input.
Histogram: uncommon items can repeat
Histogram does not require an item to occur exactly once. In OneDiff 1.0.1, it counts occurrences in the old range, grows equal runs from eligible matches, and scores each run by its rarest item. On equal scores, a longer run wins; further ties favor the earlier new position, then the earlier old position. These are version-specific rules.
In the second example, anchor appears twice and repeat appears three times on the old side. Histogram keeps the two anchor lines aligned. Myers and patience instead keep the three repeat lines aligned. This demonstrates a different alignment, not a universal winner.
The 64-occurrence limit is fixed in this release. If shared items exist but every one occurs more than 64 times in the old range, OneDiff uses Myers for that range. If the ranges share no items, it emits a deletion followed by an insertion. The limit is not a general definition of histogram diff.
C# example: compare all three algorithms
This complete program runs on .NET 10 with the released RecursiveAI.OneDiff package, version 1.0.1. It compares two in-memory inputs without reading files. Start a console project:
dotnet new console -n DiffAlgorithms --framework net10.0 cd DiffAlgorithms dotnet add package RecursiveAI.OneDiff --version 1.0.1
Replace Program.cs with the following code, then run dotnet run. long.MaxValue requests an unbounded search for the first two cases; the last case deliberately sets the work cap to zero. The reconstruction checks verify that the old spans recover the old text and the new spans recover the new text.
using System; using System.Text; using OneDiff; Compare("Unique anchor", "repeat\nrepeat\nrepeat\nanchor\n", "anchor\nrepeat\nrepeat\nrepeat\n", long.MaxValue); Compare("Repeated anchor", "repeat\nrepeat\nrepeat\nanchor\nanchor\n", "anchor\nanchor\nrepeat\nrepeat\nrepeat\n", long.MaxValue); Compare("Zero work cap", "repeat\nrepeat\nrepeat\nanchor\nanchor\n", "anchor\nanchor\nrepeat\nrepeat\nrepeat\n", 0); static void Compare(string name, string oldText, string newText, long maxWork) { Console.WriteLine(name); foreach (DiffAlgorithm algorithm in Enum.GetValues<DiffAlgorithm>()) { TextDiff diff = Diff.Lines(oldText, newText, new DiffSettings { Algorithm = algorithm, MaxWork = maxWork }); int changedLines = 0; var oldResult = new StringBuilder(); var newResult = new StringBuilder(); var edits = new StringBuilder(); foreach (Edit edit in diff.Script.Edits) { oldResult.Append(diff.OldSpan(edit)); newResult.Append(diff.NewSpan(edit)); if (edit.Kind != EditKind.Equal) changedLines += edit.OldLength + edit.NewLength; string text = (edit.Kind == EditKind.Insert ? diff.NewSpan(edit) : diff.OldSpan(edit)).ToString(); edits.Append($" {edit.Kind}[{text.Replace("\n", "|")}]"); } if (oldResult.ToString() != oldText || newResult.ToString() != newText) throw new InvalidOperationException("Reconstruction failed."); Console.WriteLine($"{algorithm}: changed={changedLines}, " + $"capped={diff.Diagnostic.CostCapReached}, work={diff.Diagnostic.Work}"); Console.WriteLine(edits.ToString().TrimStart()); } }
Exact program output follows. A vertical bar (|) represents a newline. changed counts inserted plus deleted lines; Equal rows show what stayed aligned.
Unique anchor Myers: changed=2, capped=False, work=12 Insert[anchor|] Equal[repeat|repeat|repeat|] Delete[anchor|] Patience: changed=6, capped=False, work=8 Delete[repeat|repeat|repeat|] Equal[anchor|] Insert[repeat|repeat|repeat|] Histogram: changed=6, capped=False, work=15 Delete[repeat|repeat|repeat|] Equal[anchor|] Insert[repeat|repeat|repeat|] Repeated anchor Myers: changed=4, capped=False, work=18 Insert[anchor|anchor|] Equal[repeat|repeat|repeat|] Delete[anchor|anchor|] Patience: changed=4, capped=False, work=28 Insert[anchor|anchor|] Equal[repeat|repeat|repeat|] Delete[anchor|anchor|] Histogram: changed=6, capped=False, work=19 Delete[repeat|repeat|repeat|] Equal[anchor|anchor|] Insert[repeat|repeat|repeat|] Zero work cap Myers: changed=10, capped=True, work=2 Delete[repeat|repeat|repeat|anchor|anchor|] Insert[anchor|anchor|repeat|repeat|repeat|] Patience: changed=10, capped=True, work=10 Delete[repeat|repeat|repeat|anchor|anchor|] Insert[anchor|anchor|repeat|repeat|repeat|] Histogram: changed=10, capped=True, work=10 Delete[repeat|repeat|repeat|anchor|anchor|] Insert[anchor|anchor|repeat|repeat|repeat|]
Work caps change the guarantee, not the target text
OneDiff’s default work cap is 2^31 (2,147,483,648) steps. DiffSettings.MaxWork changes it, and TextDiff.Diagnostic.CostCapReached reports whether it stopped the search early. A step is an algorithm-specific unit of work, not a millisecond: Myers counts search diagonals and matched items, while the anchor-based algorithms count scanned and compared items. See the work-cap rules.
Once capped, already solved parts remain, while unsearched parts become one deletion followed by one insertion. The result still describes the new text correctly, but Myers’ minimum-edit guarantee no longer applies. Patience and histogram do not promise minimum edits even when uncapped.
The zero-cap case replaces all five lines, giving ten changed lines. Its reported work is nonzero and can exceed the configured cap. Do not treat MaxWork as an exact operation ceiling or a deadline. The diagnostic also counts shared beginnings and endings trimmed before search, which are not charged against the cap; its public API documentation calls work an estimate, not a time. Use CostCapReached to identify a capped result rather than comparing work counters across algorithms.
Does this match Git’s diff algorithms?
Git’s version 2.6.7 diff-options manual lists Myers, minimal, patience, and histogram as separate choices. It describes histogram as extending patience to support low-occurrence common elements. Those names provide useful context, but do not establish identical edit rows or identical tuning rules between Git and OneDiff.
In particular, Git’s manual lists minimal separately from its basic greedy Myers option. The minimum-edit guarantee discussed here belongs to OneDiff 1.0.1’s documented Myers implementation when its cap is not reached. The example is not a test of Git output.
Choose using representative inputs
- Need minimum inserted and deleted items? Use Myers and inspect
CostCapReachedbefore relying on minimality. - Need unique landmarks to stay aligned? Compare patience’s output with Myers on real changes, including reordered sections.
- Need landmarks that repeat? Try histogram, including inputs where frequent boilerplate surrounds uncommon lines.
Keep the token choice fixed while comparing algorithms. A line diff and a word diff minimize different items. Also keep line endings in mind: OneDiff line tokens retain their terminators, so a final line with a newline differs from one without it, as the line-token rules explain.
For package setup, use the OneDiff getting-started guide. The algorithm reference covers the lower-level sequence APIs, and the OneDiff overview covers patches, merges, and document comparison. Browse Recursive AI’s libraries for the other public packages.