Array Diff Performance Benchmarks

Ordered array comparison is linear: it compares element i on the left with element i on the right, so 50,000 elements complete in 5.67 milliseconds. Order-insensitive comparison is quadratic: every unmatched element is scored against every remaining candidate on the other side, so 4,000 elements take 89 seconds — roughly 15,800 times longer for an array only 8% the size. The measured exponent is O(n^2.077), which means cost rises about fourfold each time the array doubles.

These are measurements of the engine this site actually ships, not estimates. The harness loads js/parser.js and js/differ.js byte-identically to what a browser receives.

Why ignoring order is quadratic

When order matters, position is the identity: index 4 on the left is compared with index 4 on the right, and one pass settles it. When order does not matter, there is no positional identity, so the engine has to work out which element on the right corresponds to each element on the left.

It does that by scoring similarity for every candidate pair and keeping the best match above a threshold. For an array of n elements that is on the order of n²/2 comparisons, and each individual comparison is itself not free — for strings it runs a Levenshtein distance, which is O(k²) in the string length. That nested cost is why the string benchmark at 1,000 elements (9.85 s) is nearly twice the object benchmark at the same size (5.19 s), despite strings being the simpler data type.

What this means in practice

The practical ceiling for order-insensitive comparison is a few thousand elements, not the 50,000 the input validator permits. Above roughly 2,000 elements you are waiting tens of seconds; at 10,000 the fit projects around 10 minutes, and at 50,000 it projects to several hours. The tool will accept those inputs because the 50,000-element cap applies to parsing, not to the comparison strategy.

If your arrays are large and order genuinely does not matter, sort both sides on a stable key first and then run an ordered comparison. That turns an O(n²) problem into an O(n log n) sort plus a linear pass, and it is what Sort and Compare Arrays does. If your elements have a natural identifier, keying on it is better still.

Method

Each data point is the median of repeated runs against arrays of objects with roughly 2% of elements modified — a realistic edit, rather than a best case of no changes or a worst case of everything changed. Every run is preceded by an untimed warmup pass so JIT compilation is not attributed to the first measurement, and by a forced garbage collection so heap deltas mean something. Runs long enough to cost tens of seconds are measured once rather than repeated; variance at those durations is far below the signal.

Two rows in the table are marked with an asterisk. Those are projected, not measured: they come from a least-squares fit of log₂(t) against log₂(n) over the five measured object-array points, extrapolated to sizes that would take hours to run. They are labelled as projections everywhere they appear, and the raw data behind every figure is published at /benchmarks.json.

Numbers are machine-specific. The environment for this run is recorded in the table caption and in the JSON. Re-run the harness yourself with npm run benchmark; the source is tools/benchmark.js in the repository.

Frequently asked questions