fast-myers-diff

Fast-Myers-Diff

This is a fast, compact, memory efficient implementation of the O(ND) Myers diff algorithm. Minified and including type definitions, the published library is less than 4KB.

This implementation improves on a naive implementation of Myers recursive algorithm in several ways:

• By using circular buffers for k-line computations, we achieve bounds of O(min(N,M) + D) space and O(min(N,M) * D) time, where N and M are the lengths of the input sequences and D is the number of differences.
• The original recursive algorithm is replaced by an iterative version with a minimal stack storing the altered parameters for right-recursion. All other recursive calls are tail calls replaced with simple jumps (via break or continue). Huge inputs may blow the heap, but you'll never overflow the stack!
• Allocation is minimized by pre-allocating buffer space to be re-used by each simulated recursive call, re-using stack slots, and tracking indices into the original inputs. The core diff algorithm performs no slice operations or other copying of data. This also minimizes garbage production and GC pause time.
• Buffers are allocated contiguously (using typed arrays) to improve cache locality.
• Buffers use the smallest numeric type possible for the input length; note that this results in discontinuous bumps in memory usage at input sizes of 256 and 65536.

Because the core algorithm does not slice or copy data, it depends only on being able to compare elements of the inputs at arbitrary indices. Thus, it automatically operates equally well on any indexable type--strings, basic arrays, or any flavor of typed array. Additionally, the library permits optimizing total application memory usage by producing output in the form of generators, rather than forcing you to accumulate the full output up-front.

Comparison With Other Lbraries

• myers-diff is focused on strings and does the tokenization internally, supporting 'words', 'chars' or 'line' compare modes as well as custom regular expressions.
• fast-diff is specialized on character mode, using substrings instead of comparing characters one by one.
• fast-myers-diff: is type agnostic and uses an iterative implementation.

All three libraries have the ability to compute character differences between strings.

Interface

The library exports the following interface:

type GenericIndexable = {
    [key: number]: unknown;
    readonly length: number;
};
type Indexable = string | unknown[] | TypedArray | GenericIndexable;
interface Sliceable extends GenericIndexable {
    slice(start: number, end?: number): this;
}

declare function diff_rec<T extends Indexable>(xs: T, i: number, N: number, ys: T, j: number, M: number): Generator<Vec4>;
declare function diff<T extends Indexable>(xs: T, ys: T): Generator<[number, number, number, number]>;
declare function lcs<T extends Indexable>(xs: T, ys: T): Generator<[number, number, number]>;

declare function calcPatch<T extends Sliceable>(xs: T, ys: T): Generator<[number, number, T]>;
declare function applyPatch<T extends Sliceable>(xs: T, patch: Iterable<[number, number, T]>): Generator<T>;

diff_rec(xs, i, N, ys, j, M) is the core of the library; given two indexable sequences, xs and ys, starting indices i and j, and slice-lengths N and M (i.e., the remaining length after the starting index), it produces a sequence of quadruples [sx, ex, sy, ey], where [sx, ex) indicates a range to delete from xs and [sy, ey) indicates a range from ys to replace the deleted material with. Simple deletions are indicated when sy === ey and simple insertions when sx === ex.

diff(xs, ys) is a wrapper around diff_rec which checks for common affixes (reducing the memory consumption and time spent in the core diff algorithm) and calculates i, j, N, and M automatically.

lcs(xs, ys) calls diff internally, but pre-processes the output to produce triples of the form [sx, sy, l], where sx and sy are the starting idices in xs and ys respectively of an aligned common substring, and l is the length of said substring. Indexing into the original input sequences can be used to retrieve the actual Longest Common Subsequence from this information, but the lcs function itself does not attempt to take slices of the inputs.

calcPatch(xs, ys) is a thin wrapper over diff(xs, ys) which replaces the [sy, ey) indices with the relevant slice of ys. This can be used to reconstitute ys given xs. Once again, pure insertions are indicated when sx === ex, but pure deletions are indicated by an empty slice--i.e., an empty string, a zero-length array, etc. The insert slices are of the same type as the original ys. If ys is a string or an array, they are produced with the slice methods of strings or arrays, which will result in a shallow copy. If ys is a typed array, slices will be produced with TypedArray.prototype.subarray, which re-uses the existing underlying memory.

applyPatch(xs, patch) takes the output of calcPatch(xs, ys) and uses it to reconstitute the original elements of ys. The output is not, however, a single reconstituted Indexable, but a sequence of chunks taken alternately from xs and from the patch data. This is done for two reasons:

• It avoids special-case code for joining each possible Indexable type;
• As with all of the other library functions, it permits stream processing without deciding for you to allocate enough memory to hold the entire result at once.

diff_rec, diff and lcs will also work with custom container types, as long as your container objects have a numeric length property. calcPatch and applyPatch will work with custom types provided that they also implement a suitable slice(start[, end]) method.

Empirical results

The table below gives the number of operations per second reported by benchmark on a Windows 10 with Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz.

input	fast-myers-diff	fast-diff-1.2.0	myers-diff-2.0.1	fast-myers-diff-2.0.0
10, +100, -100	1,139 ops/sec	2,724 ops/sec	768 ops/sec	1,115 ops/sec
10, +4, -200	4,217 ops/sec	9,094 ops/sec	875 ops/sec	4,119 ops/sec
100, +10, -10	40,825 ops/sec	14,531 ops/sec	1,049 ops/sec	42,327 ops/sec
100, +20, -0	43,265 ops/sec	18,649 ops/sec	976 ops/sec	44,582 ops/sec
100, +0, -20	45,387 ops/sec	15,867 ops/sec	988 ops/sec	48,545 ops/sec
10, +1000, -1000	12.06 ops/sec	32.86 ops/sec	7.23 ops/sec	Not supported
10000, +100, -100	587 ops/sec	99.70 ops/sec	0.23 ops/sec	Not supported
10000, +200, -0	685 ops/sec	95.26 ops/sec	0.23 ops/sec	Not supported
10000, +0, -200	705 ops/sec	106 ops/sec	0.24 ops/sec	Not supported
10000, +10, -10	2,905 ops/sec	64.11 ops/sec	0.28 ops/sec	Not supported
10000, +20, -0	3,378 ops/sec	68.45 ops/sec	0.26 ops/sec	Not supported
10000, +0, -20	3,730 ops/sec	59.50 ops/sec	0.27 ops/sec	Not supported

The fast-myers-diff: 2.0.0 used Uint8Array to save indices, so it can handle correctly only inputs with added length less than 256.

The fast-diff is faster than fast-myers-diff for inputs in which the longest common string is a small portion of the sequences. For differences of 20% fast-myers-diff is about 6x faster, for differences of 2% about 50x faster.