DEV Community

RAXXO Studios
RAXXO Studios

Posted on Originally published at raxxo.shop

I Timed Three Ways to Deduplicate an Array, Only One Scales

  • I benchmarked three ways to dedupe an array in Node 22, at sizes from 500 to 40,000 items

  • A Set-based dedupe took 4.27ms at 40,000 items, filter plus indexOf took 1,229.68ms on the same input

  • The gap is invisible under 2,000 items, then widens fast once one approach turns out to be O(n squared)

  • One of the three is the only version I would ship today, the other two I'm done writing from memory

I keep a small pile of "obviously fine" utility functions that nobody questions until a dataset grows past the size it was written for. Array deduplication is one of them, so I actually timed the three ways I have written it over the years instead of trusting my memory of which one was fast.

The Three Ways I Actually Wrote This

The first is the one most people reach for without thinking: [...new Set(arr)]. It builds a Set, which only keeps unique values, then spreads it back into an array. One pass, one data structure doing the work it was designed for.

The second is arr.filter((item, idx) => arr.indexOf(item) === idx), which keeps an item only if its first occurrence is the current index. It reads cleanly in a code review, almost too cleanly, which is exactly why it is dangerous. Every single call to indexOf scans the array from the start looking for a match, and filter calls it once per item. That is a nested scan hiding behind a one-liner.

The third is a reduce that builds up a result array and checks includes before pushing: arr.reduce((acc, item) => { if (!acc.includes(item)) acc.push(item); return acc; }, []). Same shape as the second one. includes on a plain array has to walk it looking for a match, so the cost grows the same way indexOf does, just spelled differently.

I wrote all three the same day years ago, picked whichever one matched the surrounding code style, and never benchmarked any of them until this week. That is a confession, not a recommendation.

None of the three is wrong, exactly. They all return the same array. That's what made trusting one over the other for years feel harmless.

What I Actually Measured

I ran all three against arrays of growing size, each one built with a fixed ratio of unique values so the output size scaled predictably with the input. Node 22.22.0, process.hrtime.bigint() around each call, same machine, same run.

At 500 items, all three finish in well under a millisecond apart, close enough that you would never notice in a real request. At 2,000 items, the Set version is still under a millisecond. The filter and reduce versions are already past 3.8 milliseconds each, roughly 24 times slower.

At 5,000 items, Set dedupe finished in 0.54ms. Filter plus indexOf took 17.52ms, reduce plus includes took 17.06ms, both of them already more than 30 times slower than the Set version and climbing.

By 10,000 items, Set dedupe finished in 0.90ms. Filter plus indexOf took 68.69ms. Reduce plus includes took 74.06ms. Nobody notices a 70 millisecond function on a 10,000 item array in local testing, because local testing usually runs it once.

Doubling the input roughly quadrupled the slower two, every time. That ratio is the tell.

At 20,000 items, Set dedupe was at 1.75ms. Filter plus indexOf had climbed to 359.41ms, reduce plus includes to 374.07ms. The Set version barely moved across the whole range I tested. The other two kept doubling their own doubling.

I pushed one more size to see where it actually hurts: 40,000 items. Set dedupe: 4.27ms. Filter plus indexOf: 1,229.68ms. That is over a full second spent doing work a different one-liner does in four milliseconds, and the only thing that changed between the two functions is which data structure they lean on to check "have I seen this before."

Why the Gap Opens the Way It Does

This isn't a story about one function being written badly. indexOf and includes on a plain array are doing exactly what they are supposed to do: scan linearly until they find a match or run out of array. That is fine, genuinely fine, when you call it once. The problem is calling it once per item in the array you are deduplicating, which turns a single linear scan into a scan nested inside another pass over the same array. That is the textbook shape of an O(n squared) algorithm, and it behaves exactly like one: fine at small n, then a cliff.

A Set's lookup is close to constant time, so wrapping a dedupe in one gives you a single pass that checks membership in roughly the same amount of work no matter how big the Set already is. That is the entire difference. It isn't a smarter algorithm in some abstract sense, it's a different data structure being asked to do the one thing it is actually built for.

Same question, asked a different way, answered at a different cost.

It's worth saying plainly: none of this is secret knowledge. Big-O complexity is one of the first things taught in any algorithms course, and I could have recited the difference between a Set lookup and an array scan correctly on a test the same week I shipped the slower version anyway. What that teaching rarely covers is how ordinary the code looks on both sides of the line. A filter that happens to call indexOf doesn't announce itself as the exponent in a performance problem. It just looks like a filter.

I'd seen this pattern before in a different shape, the same cliff that shows up once a recursive function runs past the depth it was built for: code that looks identical at a small scale and falls apart at a bigger one, with nothing in a quick read of the source warning you which side of that line you're standing on.

Where This Kind of Bug Likes to Hide

None of this shows up in a code review, and that's the part worth sitting with. A reduce-plus-includes dedupe and a Set-based dedupe return the exact same output for the exact same input, every time. Nothing about reading the call site tells you which one is quietly quadratic, because the complexity lives one layer down, inside a method name that looks identical whether it's backed by a Set or a plain array.

It also won't show up in a quick local test, because a quick local test almost always uses a small, convenient input. The failure mode here isn't a crash or a wrong answer, it's a function that works perfectly on every input you tried and then takes a full second on the one input you didn't, usually because that input only shows up later, after the code's already been trusted for months.

I don't think the fix is reviewing every dedupe call more carefully. I think it's picking the version that can't go quadratic in the first place and defaulting to it, the same way I lean on a sorted lookup once a list crosses a size where linear scanning starts to cost something: decide once, at the point you write the function, instead of re-litigating it every time an input happens to grow.

Bottom Line

If you dedupe an array and the input is small, truly small, all three approaches are the same function as far as anyone will ever notice. The moment that input can grow, and almost everything you write eventually touches a bigger input than the one you tested with, filter-plus-indexOf and reduce-plus-includes are the same quiet liability wearing two different outfits.

I use [...new Set(arr)] now, by default, every time, and I don't reach for the other two even when the input looks small enough that it wouldn't matter yet. Not because four milliseconds versus 1,229 milliseconds always makes a difference, most of the time it genuinely doesn't, but because I have no reliable way to know, while I'm writing the function, which inputs it will see a year from now. The cheap habit costs nothing today and saves a real debugging session later. That trade is worth taking every single time it's offered.

I'd also stop assuming a one-line utility is automatically safe just because it fits on one line. Short code and fast code are two different claims, and nothing about a function's length tells you which one you're actually getting. The only way I found out which of my three dedupe functions belonged in that second category was to stop guessing and run the numbers, which took less time than writing this sentence took.

Top comments (0)