set equality is slow

[justinabrahms]

We were using isEqual on some set comparisons and found it to be slow.

lodash.isEqual

• ops/sec 83,157
• runs: 87

our implementation:

• ops/sec 2,611,161
• runs: 82

Here's the benchmark:

/* eslint-disable @typescript-eslint/no-var-requires, no-console, no-undef */
'use strict';
const Benchmark = require('benchmark');
const { areSetsEqual } = require(our_module_here);
const _ = require('lodash');

// eslint-disable-next-line new-cap
const suite = Benchmark.Suite({
  onError(...args) {
    console.log('ERROR!', ...args);
  },
});
const sets = [
  new Set(['thing1', 'thing2']),
  new Set(['thing1', 'thing2', 'thing4']),
  new Set(['thing3', 'thing2']),
  new Set(['thing2']),
  new Set(['thing2', 'thing11', 'thing5', 'thing8']),
  new Set(['thing2', 'thing11', 'thing5', 'thing8', 'thing6']),
  new Set(['thing2', 'thing11', 'thing5', 'thing8', 'thing7']),
  new Set(['thing2', 'thing11', 'thing5', 'thing9', 'thing7']),
  new Set(['thing2', 'thing11', 'thing5', 'thing7', 'thing10']),
];

const setToCompare = new Set(['thing2', 'thing3', 'thing5', 'thing7', 'thing8']);

const results = [];

suite
  .add('length and set.has() based implementation', function () {
    sets.forEach((someSet) => areSetsEqual(someSet, setToCompare));
  })
  .add('lodash.isEqual', function () {
    sets.forEach((someSet) => _.isEqual(someSet, setToCompare));
  })
  .on('cycle', function (event) {
    results.push(event.target);
  })
  .on('complete', function () {
    console.log(`### Comparing lodash.isEqual vs plain Set compare
| | ops/sec | # of runs |
| :---------- | ----------: | ----------: |`);

    results.forEach((result) => {
      const {
        name,
        hz,
        stats: { sample },
      } = result;
      const ops = Math.round(hz).toLocaleString('en-US');
      const runs = sample.length;
      console.log(`| ${name} | ${ops} | ${runs} |`);
    });
  })
  .run({ async: true });

And our custom implementation:

export function areSetsEqual<T>(firstSet: Set<T>, secondSet: Set<T>) {
  return (
    firstSet.size === secondSet.size && [...firstSet].every((element) => secondSet.has(element))
  );
}

[rafde]

@justinabrahms you might want to check out https://github.com/epoberezkin/fast-deep-equal#readme