Set Performance Test

readme.md

A test comparing the performance of Set vs. unordered-set library

Here is the output when run on my computer

Output Node v4.8.7

[10 items]
set.add ................. total: 141.095 μs ......... per-item: 0.0141095 ms
set.delete .............. total: 33.585 μs .......... per-item: 0.0033584999999999995 ms
set.add-del-mix ......... total: 103.953 μs ......... per-item: 0.0103953 ms
array.add ............... total: 9.366 μs ........... per-item: 0.0009365999999999999 ms
array.delete ............ total: 8.771 μs ........... per-item: 0.0008770999999999999 ms
array.add-del-mix ....... total: 17.189 μs .......... per-item: 0.0017189 ms

[100 items]
set.add ................. total: 516.582 μs ......... per-item: 0.00516582 ms
set.delete .............. total: 542.622 μs ......... per-item: 0.005426219999999999 ms
set.add-del-mix ......... total: 600.101 μs ......... per-item: 0.00600101 ms
array.add ............... total: 357.049 μs ......... per-item: 0.00357049 ms
array.delete ............ total: 9.203 μs ........... per-item: 0.00009203 ms
array.add-del-mix ....... total: 27.662 μs .......... per-item: 0.00027662 ms

[1000 items]
set.add ................. total: 1.067958 ms ........ per-item: 0.001067958 ms
set.delete .............. total: 308.255 μs ......... per-item: 0.000308255 ms
set.add-del-mix ......... total: 677.358 μs ......... per-item: 0.000677358 ms
array.add ............... total: 237.894 μs ......... per-item: 0.000237894 ms
array.delete ............ total: 63.038 μs .......... per-item: 0.000063038 ms
array.add-del-mix ....... total: 422.208 μs ......... per-item: 0.000422208 ms

[2000 items]
set.add ................. total: 1.963361 ms ........ per-item: 0.0009816805 ms
set.delete .............. total: 410.77 μs .......... per-item: 0.00020538499999999999 ms
set.add-del-mix ......... total: 1.583801 ms ........ per-item: 0.0007919005 ms
array.add ............... total: 356.276 μs ......... per-item: 0.000178138 ms
array.delete ............ total: 71.306 μs .......... per-item: 0.000035653 ms
array.add-del-mix ....... total: 1.611112 ms ........ per-item: 0.0008055559999999999 ms

[40000 items]
set.add ................. total: 119.475837 ms ...... per-item: 0.002986895925 ms
set.delete .............. total: 9.827622 ms ........ per-item: 0.00024569055 ms
set.add-del-mix ......... total: 30.858546 ms ....... per-item: 0.0007714636499999999 ms
array.add ............... total: 6.806873 ms ........ per-item: 0.00017017182499999998 ms
array.delete ............ total: 2.115046 ms ........ per-item: 0.00005287615 ms
array.add-del-mix ....... total: 4.564949 ms ........ per-item: 0.00011412372499999998 ms

[80000 items]
set.add ................. total: 38.512248 ms ....... per-item: 0.0004814031 ms
set.delete .............. total: 26.502657 ms ....... per-item: 0.0003312832125 ms
set.add-del-mix ......... total: 66.308203 ms ....... per-item: 0.0008288525375 ms
array.add ............... total: 7.071442 ms ........ per-item: 0.00008839302499999999 ms
array.delete ............ total: 900.95 μs .......... per-item: 0.000011261875 ms
array.add-del-mix ....... total: 17.641702 ms ....... per-item: 0.00022052127499999998 ms

[2000000 items]
set.add ................. total: 1.574716167 s ...... per-item: 0.0007873580835 ms
set.delete .............. total: 1.151900023 s ...... per-item: 0.0005759500114999999 ms
set.add-del-mix ......... total: 2.736401193 s ...... per-item: 0.0013682005964999998 ms
array.add ............... total: 952.45378 ms ....... per-item: 0.00047622688999999997 ms
array.delete ............ total: 37.878811 ms ....... per-item: 0.0000189394055 ms
array.add-del-mix ....... total: 1.672826081 s ...... per-item: 0.0008364130405 ms

Output Node v10.13.0

[10 items]
set.add ................. total: 292.49 μs .......... per-item: 0.029248999999999997 ms
set.delete .............. total: 52.785 μs .......... per-item: 0.0052785 ms
set.add-del-mix ......... total: 28.893 μs .......... per-item: 0.0028893 ms
array.add ............... total: 12.532 μs .......... per-item: 0.0012531999999999999 ms
array.delete ............ total: 17.895 μs .......... per-item: 0.0017894999999999999 ms
array.add-del-mix ....... total: 14.205 μs .......... per-item: 0.0014204999999999999 ms

[100 items]
set.add ................. total: 34.024 μs .......... per-item: 0.00034024 ms
set.delete .............. total: 23.056 μs .......... per-item: 0.00023056 ms
set.add-del-mix ......... total: 31.094 μs .......... per-item: 0.00031094 ms
array.add ............... total: 47.908 μs .......... per-item: 0.00047908 ms
array.delete ............ total: 50.375 μs .......... per-item: 0.00050375 ms
array.add-del-mix ....... total: 61.495 μs .......... per-item: 0.00061495 ms

[1000 items]
set.add ................. total: 216.979 μs ......... per-item: 0.00021697899999999998 ms
set.delete .............. total: 194.638 μs ......... per-item: 0.000194638 ms
set.add-del-mix ......... total: 297.723 μs ......... per-item: 0.00029772299999999995 ms
array.add ............... total: 545.472 μs ......... per-item: 0.000545472 ms
array.delete ............ total: 526.302 μs ......... per-item: 0.000526302 ms
array.add-del-mix ....... total: 792.795 μs ......... per-item: 0.0007927949999999999 ms

[2000 items]
set.add ................. total: 490.499 μs ......... per-item: 0.00024524949999999996 ms
set.delete .............. total: 460.857 μs ......... per-item: 0.00023042849999999998 ms
set.add-del-mix ......... total: 649.261 μs ......... per-item: 0.00032463049999999997 ms
array.add ............... total: 1.431934 ms ........ per-item: 0.000715967 ms
array.delete ............ total: 1.008677 ms ........ per-item: 0.0005043385000000001 ms
array.add-del-mix ....... total: 590.624 μs ......... per-item: 0.00029531199999999994 ms

[40000 items]
set.add ................. total: 8.586607 ms ........ per-item: 0.00021466517499999998 ms
set.delete .............. total: 9.754222 ms ........ per-item: 0.00024385555000000001 ms
set.add-del-mix ......... total: 17.771929 ms ....... per-item: 0.000444298225 ms
array.add ............... total: 18.581872 ms ....... per-item: 0.00046454680000000004 ms
array.delete ............ total: 6.59152 ms ......... per-item: 0.000164788 ms
array.add-del-mix ....... total: 14.012335 ms ....... per-item: 0.000350308375 ms

[80000 items]
set.add ................. total: 16.753804 ms ....... per-item: 0.00020942254999999999 ms
set.delete .............. total: 13.401603 ms ....... per-item: 0.0001675200375 ms
set.add-del-mix ......... total: 44.499277 ms ....... per-item: 0.0005562409625 ms
array.add ............... total: 22.30177 ms ........ per-item: 0.000278772125 ms
array.delete ............ total: 1.734762 ms ........ per-item: 0.000021684525 ms
array.add-del-mix ....... total: 38.630494 ms ....... per-item: 0.000482881175 ms

[2000000 items]
set.add ................. total: 308.939032 ms ...... per-item: 0.00015446951599999999 ms
set.delete .............. total: 695.484363 ms ...... per-item: 0.0003477421815 ms
set.add-del-mix ......... total: 1.522512054 s ...... per-item: 0.0007612560269999999 ms
array.add ............... total: 2.4766789510000002 s  per-item: 0.0012383394755 ms
array.delete ............ total: 35.982425 ms ....... per-item: 0.0000179912125 ms
array.add-del-mix ....... total: 1.24411647 s ....... per-item: 0.0006220582349999999 ms

array.js

'use strict'
const setOp = require('unordered-set')
module.exports = {
  add: (count, objs) => {
    const set = []
    for (var i = 0; i < count; i++) {
      setOp.add(set, objs[i])
      setOp.add(set, objs[i])
    }
    return set
  },
  delete: (count, objs, set) => {
    for (var i = 0; i < count; i++) {
      setOp.remove(set, objs[i])
      setOp.remove(set, objs[i])
    }
  },
  addDelMix: (count, objs, deleteObjs) => {
    const set = []
    for (let i = 0; i < count; i++) {
      setOp.add(set, objs[i]) 
    }
    for (let i = 0; i < count; i++) {
      setOp.remove(set, deleteObjs[i])
    }
    return set
  }
}

index.js

'use strict'
const assert = require('assert')
const perf = require('execution-time')()
const shuffle = require('lodash.shuffle')
const padRight = require('pad-right')
const prettyHrtime = require('pretty-hrtime')

const counts = [10, 100, 1000, 2000, 40000, 80000, 2000000]
const max = Math.max.apply(Math, counts)
const objs = []
const testNames = ['set', 'array']
const tests = testNames.map(testName => {
  const test = require('./' + testName + '.js')
  test.name = testName
  return test
})
for (let i=0; i<max; i++) {
  objs[i] = { nr: i }
}

function warmUp() {
  tests.forEach(test => {
    test.delete(100, objs, test.add(100, objs))
    test.addDelMix(100, objs, objs)
  })
}
function len (item) {
  if (typeof item.size === 'number') {
    return item.size
  }
  return item.length
}

function runtest () {
  counts.forEach(count => {
    console.log('\n[' + count + ' items]')
    const shuffled = shuffle(objs.slice(0, count))

    function log (name) {
      const time = perf.stop()
      console.log(padRight(name + ' ', 25, '.') + ' total: ' + padRight(time.preciseWords + ' ', 20, '.') + ' per-item: ' + padRight(time.time / count) + ' ms')
    }
    tests.forEach(test => {
      let set
      perf.start()
      set = test.add(count, objs)
      log(test.name + '.add')
      assert.equal(len(set), count)
  
      perf.start()
      test.delete(count, objs, set)
      log(test.name + '.delete')
      assert.equal(len(set), 0)
  
      perf.start()
      set = test.addDelMix(count, objs, shuffled)
      log(test.name + '.add-del-mix')
      assert.equal(len(set), 0)
    })
  })
}

warmUp()
setTimeout(runtest, 1000)

package.json

{
  "name": "set-perf-test",
  "version": "1.0.0",
  "description": "Testing the performance of set",
  "main": "index.js",
  "private": true,
  "scripts": {
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "author": "Martin Heidegger",
  "license": "ISC",
  "dependencies": {
    "execution-time": "^1.3.0",
    "lodash.shuffle": "^4.2.0",
    "pad-right": "^0.2.2",
    "pretty-hrtime": "^1.0.3",
    "unordered-set": "^2.0.1"
  }
}

set.js

'use strict'
module.exports = {
  add: (count, objs) => {
    const set = new Set()
    for (var i = 0; i < count; i++) {
      set.add(objs[i])
      set.add(objs[i])
    }
    return set
  },
  delete: (count, objs, set) => {
    for (var i = 0; i < count; i++) {
      set.delete(objs[i])
      set.delete(objs[i])
    }
  },
  addDelMix: (count, objs, deleteObjs) => {
    const set = new Set()
    for (let i = 0; i < count; i++) {
      set.add(objs[i]) 
    }
    for (let i = 0; i < count; i++) {
      set.delete(deleteObjs[i])
    }
    return set
  }
}