I’m a fan of the mantra, “Make it work, make it right, make it fast.” However, I rarely reach the “Make It Fast” part since most of the code I write doesn’t need to be blazingly fast. This is a sad reality as a software developer who gets satisfaction out of optimizing their code. So whenever there is a performance issue in my code, I get excited because it means I’m able to scratch that optimization itch. Let’s go over a few examples of common operations performed on JavaScript array patterns and how we can make them blazingly fast.
Notes before reading
- The goal of this post isn’t to squeeze every ounce of performance out of your code. It’s to provide methods that are easy to read and understand without needing an in-depth understanding of data structures and algorithms
- Before we jump into optimizing any code, it will be useful for you to read up on maps and sets in JavaScript, since all the examples I’m discussing use them.
- For each operation we are going to be looking at three ways of doing it
- Native JavaScript array methods (filter, reduce, map, etc.).
- Lodash.
- Utilizing maps and sets.
- Each example will include benchmarks, since optimization is useless unless you measure it.
- You’ll notice in most of these examples that Lodash is just as fast if not faster than maps and sets. Despite this, I still chose to include the map and set methods in the case that someone doesn’t want to include a dependency on Lodash.
- I’m only showing immutable operations since most of the work I do benefits from immutable operations.
All of the code used to run these benchmarks can be found here.
Removing Duplicates
Native Array Methods
Code
list.filter((item, pos) => {
return list.indexOf(item) === pos;
});
Benchmarks
Time(ms) | Elements in array |
---|---|
0.06370800733566284 | 10 |
0.00720900297164917 | 100 |
0.24524998664855957 | 1000 |
20.85587501525879 | 10000 |
2028.1058329939842 | 100000 |
202138.53395798802 | 1000000 |
Based on the benchmarks, this code is fast enough up until somewhere between 10,000 and 100,000 records, and unacceptable at any point above that. If this code were running on a browser, your website would be frozen for about three minutes while this is occurring.
Lodash (Primitive Values)
Code
_.uniq(list);
Benchmark
Time(ms) | Elements in array |
---|---|
0.04329100251197815 | 10 |
0.09937500953674316 | 100 |
0.060499995946884155 | 1000 |
0.49754098057746887 | 10000 |
4.50279101729393 | 100000 |
46.793334007263184 | 1000000 |
Whoa! That’s nearly 4,000 times faster once you hit 1,000,000 records! Lodash must be doing something right.
Lodash (Non-Primitive Values)
That improvement is great, but this will only work with primitive values (string, number, boolean, etc.). What if I want to do uniqueness based on a property?
Code
_.uniqBy(list, comparator)
Benchmark
Time(ms) | Elements in array |
---|---|
0.13112500309944153 | 10 |
0.07079198956489563 | 100 |
0.42158299684524536 | 1000 |
5.113041996955872 | 10000 |
12.49974998831749 | 100000 |
73.71970799565315 | 1000000 |
It’s a smidge slower but still under 100 milliseconds!
Set (Primitive Values)
Code
[...new Set(list)]
Simple enough? This works because sets only allow unique values.
Benchmark
Time(ms) | Elements in array |
---|---|
0.008958995342254639 | 10 |
0.005667001008987427 | 100 |
0.0382080078125 | 1000 |
0.36887499690055847 | 10000 |
3.9749999940395355 | 100000 |
43.52562499046326 | 1000000 |
Just as fast as Lodash! Now you don’t need to install yet another npm package!
Map (Primitive Values)
If we try the above example with non-primitive values this won’t work, since sets only identify uniqueness on primitive values. This is where we can use a map!
Code
new Map(list.map((item) => [extractKey(item), item])).values();
Maps work similarly to sets in that key values must be unique. However, their keys map to values!
Benchmark
Time(ms) | Elements in array |
---|---|
0.026500016450881958 | 10 |
0.014999985694885254 | 100 |
0.12958300113677979 | 1000 |
1.3451250195503235 | 10000 |
8.251917004585266 | 100000 |
158.00600001215935 | 1000000 |
This is twice as slow as Lodash. However, if you’re avoiding including unnecessary dependencies, I think this is still acceptable enough to work.
Difference Between Two Lists
Native Array Methods
Code
When I googled “diffing arrays in JavaScript,” the first result that came up on StackOverflow was this:
let difference = arr1.filter(x => !arr2.includes(x));
Let’s benchmark it!
Time(ms) | Elements in array |
---|---|
0.01491701602935791 | 1 |
0.005333006381988525 | 10 |
0.04645800590515137 | 100 |
3.2547500133514404 | 1000 |
313.62366700172424 | 10000 |
31434.29237499833 | 100000 |
3210745.023000002 | 1000000 |
This is definitely not okay. A total of 100,000 records takes 30 seconds, which is very slow. But once you hit 1,000,000, it takes almost an hour. Let’s see if the other methods offer any improvement.
Lodash (Primitive Values)
Code
_.difference(arr1, arr2);
Benchmark
Time(ms) | Elements in array |
---|---|
0.12604200839996338 | 1 |
0.09495800733566284 | 10 |
0.26454201340675354 | 100 |
1.7619580030441284 | 1000 |
11.456708997488022 | 10000 |
30.76341700553894 | 100000 |
376.1795829832554 | 1000000 |
Much better. Even with a million records, we didn’t even break a second!
Lodash (Non-Primitive Values)
Code
Again in this example, if we try this method with no primitive values it won’t work. Thankfully, Lodash provides a solution.
_.differenceBy(arr1, arr2, comparator)
Benchmarks
Time(ms) | Elements in array |
---|---|
0.24208301305770874 | 1 |
0.1150830090045929 | 10 |
1.638416975736618 | 100 |
1.484584003686905 | 1000 |
15.348375022411346 | 10000 |
35.60387501120567 | 100000 |
590.6338749825954 | 1000000 |
It’s 200ms slower, but still much faster than using native array methods.
Set (Primitive Values)
Code
const arr2Set = new Set(arr2);
arr1.filter((x) => !arr2Set.has(x));
Benchmark
Time(ms) | Elements in array |
---|---|
0.02225002646446228 | 1 |
0.008125007152557373 | 10 |
0.032958000898361206 | 100 |
0.30558401346206665 | 1000 |
3.6421670019626617 | 10000 |
43.25270900130272 | 100000 |
737.2637079954147 | 1000000 |
Again, this is slower than Lodash but quicker than native array methods. This method is quicker than using native array methods due to how
Set.has
works. A set calculates a hash of a value when storing it, and stores that value under that key. This makes accessing a value take O(1)
time, as opposed to Array.includes
which operates at O(n)
time. Pretty cool right?
Map (Non-Primitive Values)
Code
Now let’s make this work for primitive values.
const arr2Set = new Map(arr2.map((x) => [extractKey(x), x]));
arr1.filter((x) => !arr2Set.has(extractKey(x)));
Benchmark
Time(ms) | Elements in array |
---|---|
0.04791700839996338 | 1 |
0.02158302068710327 | 10 |
0.0885000228881836 | 100 |
0.517208993434906 | 1000 |
4.826333999633789 | 10000 |
88.70929199457169 | 100000 |
1597.0950419902802 | 1000000 |
This is the first optimization that passes the one-second mark. It’s still faster than native methods, but the two-fold speed increase might make it worth it to include Lodash in your project.
Aggregating Two Lists By A Property
This operation will take two lists that have a common property and return a list of objects that hold those matching objects.
Note: For this operation, we are making the following assumptions:
- Both lists are the same length.
- There are entries with duplicate properties in either list.
- Each entry in each list has a corresponding entry in the other list.
Native JavaScript Methods (map and find)
Code
listB.map((b) => ({
b: b,
a: listA.find((a) => a[aProperty] === b[bProperty]),
}));
Benchmarks
Time(ms) | Elements in array |
---|---|
0.021625012159347534 | 1 |
0.011750012636184692 | 10 |
0.13941702246665955 | 100 |
5.005832999944687 | 1000 |
208.6930420100689 | 10000 |
20707.64387497306 | 100000 |
2087215.1352920234 | 1000000 |
Using JavaScript’s array methods is unsurprisingly slow again. Seeing a pattern yet?
Native Javascript Methods (reduce and map)
When doing benchmarks for the map/set version of this operation, I found another more performant way to do this with native array methods.
Code
const listAMapById = listA.reduce((acc, a) => {
return Object.assign(acc, { [a[aProperty]]: a });
}, {});
listB.map((b) => ({
b: b,
a: listAMapById[b[bProperty]],
}));
In this example, we process one of the lists into an object, then index onto that list when finding the object for the other list.
Benchmarks
Time(ms) | Elements in array |
---|---|
0.03525000810623169 | 1 |
0.030667006969451904 | 10 |
0.15033301711082458 | 100 |
1.9047499895095825 | 1000 |
7.687875002622604 | 10000 |
84.34062498807907 | 100000 |
960.1207909882069 | 1000000 |
Whoa! Using the native JavaScript array methods wasn’t incredibly slow for once!
Lodash
Code
_.mergeWith(
_.sortBy(listA, aProperty),
_.sortBy(listB, bProperty),
(a, b) => ({ a, b })
);
I wasn’t able to find a method provided by Lodash that did this out of the box, but I came up with this. This method would not work if any of the above assumptions were not met.
Benchmarks
Time(ms) | Elements in array |
---|---|
0.4717079997062683 | 1 |
0.24620798230171204 | 10 |
0.34333401918411255 | 100 |
2.9508340060710907 | 1000 |
17.965292006731033 | 10000 |
194.1733749806881 | 100000 |
6806.113000005484 | 1000000 |
In a shocking upset, using Lodash doesn’t beat native javascript arrays! This is probably caused by needing to sort both arrays before actually merging them together.
Map
Code
const listAMapByProperty = new Map(listA.map((a) => [a[aProperty], a]));
listB.map((b) => ({
b,
a: listAMapByProperty.get(b[bProperty]),
}));
Benchmark
Time(ms) | Elements in array |
---|---|
0.02512499690055847 | 1 |
0.016208022832870483 | 10 |
0.027875006198883057 | 100 |
0.23816600441932678 | 1000 |
2.2608749866485596 | 10000 |
24.74924999475479 | 100000 |
576.2636669874191 | 1000000 |
Native methods may have beaten Lodash this time, but using a map in this situation seems to be the fastest out of them all.
Takeaways
These are a few things I have taken away from doing these benchmarks.
Using Lodash is the fastest (most of the time).
After I ran these benchmarks, I looked at the source code for the Lodash methods I used. In a lot of cases, it is using sets and maps to get this performance. However, it also has tweaks in place that squeeze out extra performance.
So if performance is important to you and you don’t mind pulling in an npm package, you should probably use Lodash if you’re processing data with a lot of entries. However this isn’t the case all the time, so be sure to research other methods and run benchmarks.
You don’t need Lodash for good performance.
Although Lodash is the fastest, you can get pretty darn close to its speed without it. For more things you can do without Lodash, give this repo a look: You-Dont-Need-Lodash-Underscore.
Maps and sets are awesome!
After running all of these benchmarks, I’m definitely going to start using sets and maps more in my code. Not only are they really fast, but they also are easy to use and provide a good API for operating with them.
JavaScript array methods are fast enough for smaller amounts of data.
If you aren’t operating on arrays with more than 10,000 entries, you probably don’t need to optimize. All of the operations I benchmarked took less than 300ms to execute on data sets of that size
Can’t believe it! So cool!