Set lookup time slower than Object?

Question

Out of curiousity, I decided to confirm my belief that the Set implementation is faster than Object (running in google chrome) in terms of insertion/addition and lookup. My results were slightly confusing.

x = {};
y = new Set();

console.time('Insert into Object');
for (var i = 0; i < 1000000; i++) {
    x[i] = 0;
}
console.timeEnd('Insert into Object');

console.time('Insert into Set');
for (i = 0; i < 1000000; i++) {
    y.add(i);
}
console.timeEnd('Insert into Set');

var t = 0;

console.time('Retrieve from Object');
for (i = 0; i < 1000000; i++) {
    t = x[i];
}
console.timeEnd('Retrieve from Object');

console.time('Retrieve from Set');
for (i = 0; i < 1000000; i++) {
    t = y.has(i);
}
console.timeEnd('Retrieve from Set');

VM19742:9  Insert into Object: 1341.777ms
VM19742:15 Insert into Set: 1473.025ms
VM19742:23 Retrieve from Object: 1469.717ms
VM19742:29 Retrieve from Set: 1666.430ms

As you can see, the set performed slightly worse than the Object. This confuses me because I thought the underlying implementation would just be the same as the object without the extra overhead of storing the values. Does anyone have any extra insight as to why this is?

Answer 1

To counter your question, why do you believe that storing a value is likely to be slower than checking the existing values to see if you need to store it?

Just to be complete, I modified your code to include Arrays, too.

x = {};
y = new Set();
z = [];

console.time('Insert into Object');
for (var i = 0; i < 1000000; i++) {
    x[i] = 0;
}
console.timeEnd('Insert into Object');

console.time('Insert into Set');
for (i = 0; i < 1000000; i++) {
    y.add(i);
}
console.timeEnd('Insert into Set');

console.time('Insert into Array');
for (i = 0; i < 1000000; i++) {
    z[i] = 0;
}
console.timeEnd('Insert into Array');

var t = 0;

console.time('Retrieve from Object');
for (i = 0; i < 1000000; i++) {
    t = x[i];
}
console.timeEnd('Retrieve from Object');

console.time('Retrieve from Set');
for (i = 0; i < 1000000; i++) {
    t = y.has(i);
}
console.timeEnd('Retrieve from Set');

console.time('Retrieve from Array');
for (i = 0; i < 1000000; i++) {
    t = z[i];
}
console.timeEnd('Retrieve from Array');

console.log(t);

Ordinarily, one would expect that storing into an object is O(1) time complexity while checking the existing values in a set should be no more than O(n) (where n is the number of items in the set), so we should expect that the set may become slower as it becomes larger. This performance may even be implementation-dependent, i.e. different javascript runtimes may behave differently.

And in fact, that's exactly what we see: (Running on my machine)

(your code)

Insert into Object: 67.558ms
Insert into Set: 259.841ms
Insert into Array: 64.297ms
Retrieve from Object: 19.337ms
Retrieve from Set: 149.968ms
Retrieve from Array: 3.981ms

But if we change your insertion tests to continually re-add the same values...

We see this:

Insert into Object: 19.103ms
Insert into Set: 40.645ms
Insert into Array: 16.384ms
Retrieve from Object: 40.116ms
Retrieve from Set: 30.672ms
Retrieve from Array: 70.050ms

Which tells us a couple of things. First, different types are differently sensitive to the size of the collection. Secondly, retrieving non-existent keys from either an array or an object is slower than checking a set for the same value (at least on this particular implementation).

As a final note

I think it's important to note here that we're discussing the relative performance of things that take well under a second for a million iterations (or about a second-and-a-half on your test). That's pretty fast already. For those reading this in the future, remember to choose the data structure that's semantically the one you want. Any of these three is a perfectly good choice from a performance perspective. Choose the one that makes your program the most understandable.