2026-09-05 · 8 min read

JavaScript code review exercise: correct output, billions of comparisons

In 2017, someone noticed that pushing to a Mercurial repository got slower the more heads it had. The culprit was a single line that computed new heads by checking if h not in oldheads, where oldheads was a Python list. Linear scan inside a loop over every head. The fix was wrapping that list in set(). One word, and the quadratic blowup disappeared. I think about that fix every time I review JavaScript that nests .some() inside .filter(), because it is the same bug wearing a different syntax, and I keep approving PRs that have it.

This is a JavaScript code review exercise built around exactly that pattern: a five-line function that returns correct results on every input, passes every unit test you write, and blocks a production worker for minutes at real data sizes. It is a worked example with a full solution, from the initial diff through the review comment, the fix, and the verification. The bug is O(n×m) complexity hidden inside readable array methods, and the exercise trains the one multiplication you should do on every loop-inside-a-loop before you hit approve.

The pattern is common enough to have its own Tumblr, cataloguing real cases from the Linux kernel to Rust's standard library. It keeps showing up because it reads like English, returns correct results, and nothing in your test suite will ever flag it, because your test suite runs on twenty items. I once watched a nightly sync job go from "finishes before anyone gets to the office" to "still running when the morning standup starts" after a single quarter of customer growth. The job itself had not changed in months. The dataset had roughly doubled, and because the core loop was quadratic, the runtime had quadrupled. That is the signature of this bug class: it does not break, it slows down, and by the time it is slow enough to notice, you are debugging at 3 AM with an angry Slack channel open.

The setup

A nightly job flags catalog items whose SKU is absent from the latest supplier feed. The requirements are short:

1. Flag catalog items whose SKU is absent from the latest supplier feed.
2. Comparison is by exact SKU.
3. The comparison must run in linear time in the two input sizes. The job shares a worker with webhook processing and must not stall it.

The context matters: production runs about 80,000 catalog items and 60,000 supplier feed rows. Both arrive as in-memory arrays from the job runner. The job runs on the same Node worker that serves webhook callbacks, so any synchronous CPU work blocks the event loop and queues up everything else.

The PR

Seven lines. Reads beautifully. Does exactly what was asked: for each catalog item, check whether any feed row has a matching SKU; if not, keep it. If you run this with ten catalog items and eight feed rows, it returns instantly and correctly. Ship it?

Walkthrough starts below. If you want to try the exercise first, stop here.

Five lines, what could go wrong

Look at lines 2 through 4. catalog.filter() iterates every catalog item. For each one, feed.some() iterates the feed array looking for a matching SKU. If the item is present in the feed, some() short-circuits on the first hit. But if the item is missing from the feed, some() walks the entire feed array before returning false.

Now multiply the sizes. The catalog has 80,000 items. The feed has 60,000 rows. In the worst case, where many catalog items are not in the feed, each missing item triggers a full scan of all 60,000 feed rows. Even in an average case with a moderate number of missing items, you are looking at hundreds of millions of comparisons. The theoretical worst case, where every catalog item is missing, is 80,000 × 60,000 = 4.8 billion string comparisons in a single synchronous pass.

That is not a number that shows up in your test. Your test has five catalog items and three feed rows, and it finishes in microseconds, because 5 × 3 is 15. The function returns the correct answer in both cases. The only difference is that one of them monopolizes the event loop for seconds or minutes while doing it.

The Monday morning version of this bug

Here is what actually happens in production. The nightly job kicks off at 2 AM. While flagMissingItems runs, the Node event loop is blocked. That means every webhook callback that arrives during those minutes sits in the TCP backlog. The upstream system retries. Some of those retries arrive while the job is still running, so they queue up too. By the time the function returns, the worker has a thundering herd of retry traffic on top of the original webhooks, and depending on how the upstream handles timeouts, some of those webhooks may have been marked as failed on the sender's side already.

The requirement said "must run in linear time" and "must not stall the worker." This code violates both. It runs in O(n×m) time, and because it is a single synchronous expression, every CPU cycle it burns is a cycle the event loop cannot spend on anything else.

Nothing in the code is wrong in the "returns incorrect results" sense. Every item it flags is genuinely missing. Every item it keeps is genuinely present. The correctness is perfect. The complexity is not.

The comment you would leave

Verdict: request changes

This is a single-issue PR, and the issue is a blocker. The third requirement explicitly asks for linear time, and the implementation is quadratic. The function works correctly, but correctness is not the question. The question is whether this function can run at production scale without starving the worker, and it cannot.

The fix

Build a Set of feed SKUs in one pass over the feed, then filter the catalog with an O(1) .has() lookup instead of an O(m) .some() scan:

The Set constructor iterates the feed once (O(m)). The filter iterates the catalog once, and each .has() lookup is O(1) amortized under the standard hash-table assumption. Total: O(n+m) instead of O(n×m).

Two lines replace three, and the code is arguably more readable. This is one of the rare cases where the faster version is also the shorter version.

Proving it on a small case

You do not need to run 80,000 items to see the difference. You can count comparisons on a tiny worst case where no catalog item appears in the feed:

With 3 items and 2 feed rows, the difference is trivial: 6 versus 5. Now scale it. With 80,000 and 60,000, the quadratic version does up to 4,800,000,000 comparisons. The linear version does 140,000. That is not a percentage improvement; it is a different category of operation.

And both versions return the same result: [{sku:'A'},{sku:'B'},{sku:'C'}]. Every test you write will pass on both. The only test that distinguishes them is one that counts comparisons or measures time at scale, and nobody writes that test for a seven-line function.

The habit worth keeping

Every time you see a lookup method inside a loop, do the multiplication. .includes() inside .filter(). .find() inside .map(). .some() inside .forEach(). The inner method is always O(n) over the collection it searches, and the outer method calls it once per element. Multiply the two sizes and ask yourself whether you are comfortable with that number in production. If either collection can grow, the answer is almost always "build a Set or a Map first." It is one extra line, it makes the intent clearer, and it turns a latent scaling problem into a non-issue.

AI code generators are especially prone to this pattern because the .some() version reads more like the English description of the task ("check if some feed row matches"), and models optimize for readability over runtime characteristics. The code that reads like a sentence is the code that blocks your event loop.