JavaScript Set vs. Array performance

Question

It may be because Set is relatively new to JavaScript but I haven't been able to find an article, on Stack Overflow 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.

Answer 1

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.")

Answer 2

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

Answer 3

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)
}

Array

• for loop
• for loop (reversed)
• array.includes(target)

Set

• set.has(target)

Object

• obj.hasOwnProperty(target)
• target in obj <- 1.29% slower
• obj[target] <- fastest

Map

• map.has(target) <- 2.94% slower

Results from January 2021, Chrome 87

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.

Answer 4

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. Another interesting point is that Objects do not have officially guaranteed order, whereas Set in JavaScript is implemented as an OrderedSet and does maintain the order of insertion.

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. At this period of time (when this test ran): Chrome's V8 clearly only optimized for Objects: The following is a snapshot for Chrome v86 in November 2020.

1. For loop: 104167.14 ops/s ‡ 0.22% Slowest
2. Array.includes: 111524.8 ops/s ‡ 0.24% 1.07x more ops/s than for loop (9k iterations for both)
3. For loop reversed: 218074.48 ops/s ‡ 0.59% 1.96x more ops/s than non-reversed Array.includes (9k iterations)
4. Set.has: 154744804.61 ops/s ‡ 1.88% 709.6x more ops/s than for loop reverse (only 1k iterations since target is on right side)
5. hasOwnProperty: 161399953.02 ops/s ‡ 1.81% 1.043x more ops/s than Set.has
6. key in myObject: 883055194.54 ops/s ‡ 2.08% ... 5x more ops/sec than myObject.hasOwnProperty.

---

Update: 11/10/2022: I re-ran (2 years after my original image) the same tests on Safari and Chrome today and had some interesting results: TLDR Set is equally fast if not faster than using key in Object and way faster than using Object.hasOwnProperty for both browsers. Chrome also has somehow dramatically optimized Array.includes to the extent that it is in the same realm of speed as Object/Set look up time (whereas for loops take 1000+x longer to complete).

For Safari Set is significantly faster than key in Object and Object.hasOwnProperty is barely in the same realm of speed. All array variants (for loops/includes) are as expected dramatically slower than set/object look ups.

Snapshot 11/10/2022: Tested On Safari v16.1 Operations per second (higher = faster):

• mySet.has(key): 1,550,924,292.31
• key in myObject: 942,192,599.63 (39.25% slower aka using Set you can perform around 1.6x more operations per second
• myObject.hasOwnProperty(key): 21,363,224.51 (98.62% slower) aka you can perform about 72.6x more Set.has operations as hasOwnProperty checks in 1 second.
• Reverse For loop 619,876.17 ops/s (target is 9,000 out of 10,000-so reverse for loop means iterating only 1,000 times vs 9,000) meaning you can do 2502x more Set look ups than for loop checks even when you know the item's position is advantageous.
• for loop: 137,434 ops/s: as expected is even slower but surprisingly not much slower: Reverse for loop which involves 1/9th the loop iterations is only about 4.5x faster than for loop.
• Array.includes(target) 111,076 ops/s is a bit slower still than the for loop manually checking for target you can perform 1.23x checks manually for each check of includes.

On Chrome v107.0.5304.87 11/10/2022: It is no longer true that Set significantly underperforms Object in operation: they now nearly tie. (Though the expected behavior is that set would outperform Object in due to the smaller possible of options with a set vs an object and how this is the behavior in Safari.) Notably impressive Array.includes has apparently been significantly optimized in Chrome (v8) for at least this type of test:

• Object in finished 792894327.81 ops/s ‡ 2.51% Fastest

• Set.prototype.has finished 790523864.11 ops/s ‡ 2.22% Fastest

• Array.prototype.includes finished 679373215.29 ops/s ‡ 1.82% 14.32% slower

• Object.hasOwnProperty finished 154217006.71 ops/s ‡ 1.31% 80.55% slower

• for loop finished 103015.26 ops/s + 0.98% 99.99% slower

---

Answer 5

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

Answer 6

Let's consider the case where you want to maintain a set of unique values. You can emulate nearly all the Set operations using an array: add, delete, has, clear, and size.

We can implement iteration as well, but note that it will not behave quite the same as Set. A Set you can safely modify during iteration without skipping elements, but the same is not true of an array. So the comparison there is not quite fair for all use cases.

/** Set implemented using an array internally */
class ArraySet{
    constructor(){
        this._arr = [];
    }
    add(value){
        if (this._arr.indexOf(value) === -1)
            this._arr.push(value);
        return this;
    }
    delete(value){
        const idx = this._arr.indexOf(value);
        if (idx !== -1){
            this._arr.splice(idx,1);
            return true;
        }
        return false;
    }
    has(value){
        return this._arr.indexOf(value) !== -1;
    }
    clear(){
        this._arr.length = 0;
    }
    // Note: iterating is not safe from modifications
    values(){   
        return this._arr.values();
    }
    [Symbol.iterator](){
        return this._arr[Symbol.iterator]();
    }
}

While Set has better algorithmic complexity (O(1) vs ArraySet's O(n) operations), it likely has a bit more overhead in maintaining its internal tree/hash. At what size does the overhead of the Set become worth it? Here is the data I gathered from benchmarking NodeJS v18.12 for an average use case (see benchmarking code):

As expected, we see the O(n) algorithmic advantage for Set for many elements. As for overhead:

• size: equal speed
• add: An interesting pattern emerges, where a Set's performance oscillates depending on its size. In general an array will be faster for < 33 elements, and a Set always faster for > 52 elements.
• delete: Array is faster for < 10 elements
• has: Array is faster for < 20 elements
• values: Set is always faster
• iterator (e.g. for-of loop): Set is always faster

In practice, you likely are not going to create your own ArraySet class, and instead will just inline the particular operation you're interested in. Assuming the array operations are inlined, how does the performance change?

The results are nearly identical, except now the iterating performance has improved for Array. An inlined for-of loop (not going through the ArraySet wrapper class) is now always faster than a Set. The values iterator is roughly equal speed.

Answer 7

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