It maybe because Sets are relatively new to Javascript but I haven't been able to find an article, on StackO or anywhere else, that talks about the performance difference between the two in Javascript. So, what is the difference, in terms of performance, between the two? Specifically, when it comes to removing, adding and iterating.
6 Answers
Ok, I have tested adding, iterating and removing elements from both an array and a set. I ran a "small" test, using 10 000 elements and a "big" test, using 100 000 elements. Here are the results.
Adding elements to a collection
It would seem that the .push
array method is about 4 times faster than the .add
set method, no matter the number of elements being added.
Iterating over and modifying elements in a collection
For this part of the test I used a for
loop to iterate over the array and a for of
loop to iterate over the set. Again, iterating over the array was faster. This time it would seem that it is exponentially so as it took twice as long during the "small" tests and almost four times longer during the "big" tests.
Removing elements from a collection
Now this is where it gets interesting. I used a combination of a for
loop and .splice
to remove some elements from the array and I used for of
and .delete
to remove some elements from the set. For the "small" tests, it was about three times faster to remove items from the set (2.6 ms vs 7.1 ms) but things changed drastically for the "big" test where it took 1955.1 ms to remove items from the array while it only took 83.6 ms to remove them from the set, 23 times faster.
Conclusions
At 10k elements, both tests ran comparable times (array: 16.6 ms, set: 20.7 ms) but when dealing with 100k elements, the set was the clear winner (array: 1974.8 ms, set: 83.6 ms) but only because of the removing operation. Otherwise the array was faster. I couldn't say exactly why that is.
I played around with some hybrid scenarios where an array was created and populated and then converted into a set where some elements would be removed, the set would then be reconverted into an array. Although doing this will give much better performance than removing elements in the array, the additional processing time needed to transfer to and from a set outweighs the gains of populating an array instead of a set. In the end, it is faster to only deal with a set. Still, it is an interesting idea, that if one chooses to use an array as a data collection for some big data that doesn't have duplicates, it could be advantageous performance wise, if there is ever a need to remove many elements in one operation, to convert the array to a set, perform the removal operation, and convert the set back to an array.
Array code:
var timer = function(name) {
var start = new Date();
return {
stop: function() {
var end = new Date();
var time = end.getTime() - start.getTime();
console.log('Timer:', name, 'finished in', time, 'ms');
}
}
};
var getRandom = function(min, max) {
return Math.random() * (max - min) + min;
};
var lastNames = ['SMITH', 'JOHNSON', 'WILLIAMS', 'JONES', 'BROWN', 'DAVIS', 'MILLER', 'WILSON', 'MOORE', 'TAYLOR', 'ANDERSON', 'THOMAS'];
var genLastName = function() {
var index = Math.round(getRandom(0, lastNames.length - 1));
return lastNames[index];
};
var sex = ["Male", "Female"];
var genSex = function() {
var index = Math.round(getRandom(0, sex.length - 1));
return sex[index];
};
var Person = function() {
this.name = genLastName();
this.age = Math.round(getRandom(0, 100))
this.sex = "Male"
};
var genPersons = function() {
for (var i = 0; i < 100000; i++)
personArray.push(new Person());
};
var changeSex = function() {
for (var i = 0; i < personArray.length; i++) {
personArray[i].sex = genSex();
}
};
var deleteMale = function() {
for (var i = 0; i < personArray.length; i++) {
if (personArray[i].sex === "Male") {
personArray.splice(i, 1)
i--
}
}
};
var t = timer("Array");
var personArray = [];
genPersons();
changeSex();
deleteMale();
t.stop();
console.log("Done! There are " + personArray.length + " persons.")
Set code:
var timer = function(name) {
var start = new Date();
return {
stop: function() {
var end = new Date();
var time = end.getTime() - start.getTime();
console.log('Timer:', name, 'finished in', time, 'ms');
}
}
};
var getRandom = function (min, max) {
return Math.random() * (max - min) + min;
};
var lastNames = ['SMITH','JOHNSON','WILLIAMS','JONES','BROWN','DAVIS','MILLER','WILSON','MOORE','TAYLOR','ANDERSON','THOMAS'];
var genLastName = function() {
var index = Math.round(getRandom(0, lastNames.length - 1));
return lastNames[index];
};
var sex = ["Male", "Female"];
var genSex = function() {
var index = Math.round(getRandom(0, sex.length - 1));
return sex[index];
};
var Person = function() {
this.name = genLastName();
this.age = Math.round(getRandom(0,100))
this.sex = "Male"
};
var genPersons = function() {
for (var i = 0; i < 100000; i++)
personSet.add(new Person());
};
var changeSex = function() {
for (var key of personSet) {
key.sex = genSex();
}
};
var deleteMale = function() {
for (var key of personSet) {
if (key.sex === "Male") {
personSet.delete(key)
}
}
};
var t = timer("Set");
var personSet = new Set();
genPersons();
changeSex();
deleteMale();
t.stop();
console.log("Done! There are " + personSet.size + " persons.")
-
1Keep in mind, the values of a set are unique by default. So, where as
[1,1,1,1,1,1]
for an array would have length 6, a set would have size 1. Looks like your code could actually be generating sets of wildly differing sizes than 100,000 items in size on each run because of this trait of Sets. You probably never noticed because you aren't showing the size of the set until after the entire script is run. Oct 24, 2016 at 20:21 -
6@KyleFarris Unless I am mistaken, this would be true if there were duplicates in the set, like in your example
[1, 1, 1, 1, 1]
, but since each item in the set is actually an object with various properties including a first name and last name randomly generated from a list of hundreds of possible names, a randomly generated age, a randomly generated sex and other randomly generated attributes... the odds of having two identical objects in the sets are slim to none. Nov 1, 2016 at 15:59 -
3Actually, you're right in this case because it seems Sets don't actually differentiate from objects in the set. So, indeed you could even have the same exact object
{foo: 'bar'}
10,000x in the set and it would have a size of 10,000. Same goes for arrays. It seems it's only unique with scalar values (strings, numbers, booleans, etc..). Jan 11, 2017 at 21:15 -
17You could have the same exact content of an object
{foo: 'bar'}
many times in the Set, but not the exact same object (reference). Worth pointing out the subtle difference IMO Sep 9, 2017 at 9:32 -
37You forgot the measure the most important reason to use a Set, the 0(1) lookup.
has
vsIndexOf
.– MagnusAug 29, 2018 at 6:32
OBSERVATIONS:
- Set operations can be understood as snapshots within the execution stream.
- We are not before a definitive substitute.
- The elements of a Set class have no accessible indexes.
- Set class is an Array class complement, useful in those scenarios where we need to store a collection on which to apply basic addition, Deletion, checking and iteration operations.
I share some test of performance. Try to open your console and copypaste the code below.
Creating an array (125000)
var n = 125000;
var arr = Array.apply( null, Array( n ) ).map( ( x, i ) => i );
console.info( arr.length ); // 125000
1. Locating an Index
We compared the has method of Set with Array indexOf:
Array/indexOf (0.281ms) | Set/has (0.053ms)
// Helpers
var checkArr = ( arr, item ) => arr.indexOf( item ) !== -1;
var checkSet = ( set, item ) => set.has( item );
// Vars
var set, result;
console.time( 'timeTest' );
result = checkArr( arr, 123123 );
console.timeEnd( 'timeTest' );
set = new Set( arr );
console.time( 'timeTest' );
checkSet( set, 123123 );
console.timeEnd( 'timeTest' );
2. Adding a new element
We compare the add and push methods of the Set and Array objects respectively:
Array/push (1.612ms) | Set/add (0.006ms)
console.time( 'timeTest' );
arr.push( n + 1 );
console.timeEnd( 'timeTest' );
set = new Set( arr );
console.time( 'timeTest' );
set.add( n + 1 );
console.timeEnd( 'timeTest' );
console.info( arr.length ); // 125001
console.info( set.size ); // 125001
3. Deleting an element
When deleting elements, we have to keep in mind that Array and Set do not start under equal conditions. Array does not have a native method, so an external function is necessary.
Array/deleteFromArr (0.356ms) | Set/remove (0.019ms)
var deleteFromArr = ( arr, item ) => {
var i = arr.indexOf( item );
i !== -1 && arr.splice( i, 1 );
};
console.time( 'timeTest' );
deleteFromArr( arr, 123123 );
console.timeEnd( 'timeTest' );
set = new Set( arr );
console.time( 'timeTest' );
set.delete( 123123 );
console.timeEnd( 'timeTest' );
Read the full article here
-
4Array.indexOf should be Array.includes for them to be equivalent. I'm getting very different numbers on Firefox. Jul 10, 2019 at 19:16
-
3I would be interested in the Object.includes vs. Set.has comparison... Jan 16, 2020 at 9:17
-
2@LeopoldKristjansson I didn't write a comparison test, but we did timings in a production site with arrays with 24k items and switching from Array.includes to Set.has was a tremendous performance boost!– sedotOct 27, 2020 at 16:51
Just the Property Lookup, little or zero writes
If property lookup is your main concern, here are some numbers.
JSBench tests https://jsbench.me/3pkjlwzhbr/1
// https://jsbench.me/3pkjlwzhbr/1
// https://docs.google.com/spreadsheets/d/1WucECh5uHlKGCCGYvEKn6ORrQ_9RS6BubO208nXkozk/edit?usp=sharing
// JSBench forked from https://jsbench.me/irkhdxnoqa/2
var theArr = Array.from({ length: 10000 }, (_, el) => el)
var theSet = new Set(theArr)
var theObject = Object.assign({}, ...theArr.map(num => ({ [num]: true })))
var theMap = new Map(theArr.map(num => [num, true]))
var theTarget = 9000
// Array
function isTargetThereFor(arr, target) {
const len = arr.length
for (let i = 0; i < len; i++) {
if (arr[i] === target) {
return true
}
}
return false
}
function isTargetThereForReverse(arr, target) {
const len = arr.length
for (let i = len; i > 0; i--) {
if (arr[i] === target) {
return true
}
}
return false
}
function isTargetThereIncludes(arr, target) {
return arr.includes(target)
}
// Set
function isTargetThereSet(numberSet, target) {
return numberSet.has(target)
}
// Object
function isTargetThereHasOwnProperty(obj, target) {
return obj.hasOwnProperty(target)
}
function isTargetThereIn(obj, target) {
return target in obj
}
function isTargetThereSelectKey(obj, target) {
return obj[target]
}
// Map
function isTargetThereMap(numberMap, target) {
return numberMap.has(target)
}
for
loopfor
loop (reversed)array.includes(target)
set.has(target)
obj.hasOwnProperty(target)
target in obj
<- 1.29% slowerobj[target]
<- fastest
map.has(target)
<- 2.94% slower
Results from other browsers are most welcome, please update this answer.
You can use this spreadsheet to make a nice screenshot.
JSBench test forked from Zargold's answer.
-
-
1@EdmundoDelGusto Yes, the higher Average the better. Also "Perf" stands for performance, the best one is rated at 100%. You can also run the tests (the jsbench link above) and see for yourself.– QwertyFeb 22 at 14:50
My observation is that a Set is always better with two pitfalls for large arrays in mind :
a) The creation of Sets from Arrays must be done in a for
loop with a precached length.
slow (e.g. 18ms) new Set(largeArray)
fast (e.g. 6ms)
const SET = new Set();
const L = largeArray.length;
for(var i = 0; i<L; i++) { SET.add(largeArray[i]) }
b) Iterating could be done in the same way because it is also faster than a for of
loop ...
See https://jsfiddle.net/0j2gkae7/5/
for a real life comparison to
difference()
, intersection()
, union()
and uniq()
( + their iteratee companions etc.) with 40.000 elements
For the iteration part of your question, I recently ran this test and found that Set much outperformed an Array of 10,000 items (around 10x the operations could happen in the same timeframe). And depending on the browser either beat or lost to Object.hasOwnProperty in a like for like test.
Both Set and Object have their "has" method performing in what seems to be amortized to O(1), but depending on the browser's implementation a single operation could take longer or faster. It seems that most browsers implement key in Object faster than Set.has(). Even Object.hasOwnProperty which includes an additional check on the key is about 5% faster than Set.has() at least for me on Chrome v86.
https://jsperf.com/set-has-vs-object-hasownproperty-vs-array-includes/1
Update: 11/11/2020: https://jsbench.me/irkhdxnoqa/2
In case you want to run your own tests with different browsers/environments.
Similarly I'll add a benchmark for adding items to an array vs set and removing.
-
4Please don't use links in your answers (unless linked to an official libraries) since these links could be broken - as happened in your case. You link is 404. Feb 17, 2019 at 9:48
-
I used a link but also copied the output when it was available. It's unfortunate that they changed their linking strategy so quickly.– ZargoldFeb 19, 2019 at 4:59
-
Updated the post now with a screenshot and a new JS performance website: jsbench.me– ZargoldNov 11, 2020 at 22:21
-
I wrote why Set.has() is slower in here: stackoverflow.com/a/69338420/1474113 TL;DR: Because V8 does not optimize Set.has() much.– yprestoSep 26, 2021 at 20:03
console.time("set")
var s = new Set()
for(var i = 0; i < 10000; i++)
s.add(Math.random())
s.forEach(function(e){
s.delete(e)
})
console.timeEnd("set")
console.time("array")
var s = new Array()
for(var i = 0; i < 10000; i++)
s.push(Math.random())
s.forEach(function(e,i){
s.splice(i)
})
console.timeEnd("array")
Those three operations on 10K items gave me:
set: 7.787ms
array: 2.388ms
-
-
1@zerkms: Define "work" :-) Yes, the array will be empty after the
forEach
, but probably not in the way you expected. If one wants comparable behaviour, it should bes.forEach(function(e) { s.clear(); })
as well.– BergiAug 17, 2016 at 23:43 -
1Well, it does something, just not what is intended: it deletes all elements between index i and the end. That does not compare to what the
delete
does on the Set.– trincotAug 17, 2016 at 23:43 -
-
4
Set
and[]
or{}
?