Skip to content

Instantly share code, notes, and snippets.

@martinheidegger
Last active January 31, 2019 15:06
Show Gist options
  • Save martinheidegger/4ba55728c3e049f03a7536d4b64b1949 to your computer and use it in GitHub Desktop.
Save martinheidegger/4ba55728c3e049f03a7536d4b64b1949 to your computer and use it in GitHub Desktop.
Set Performance Test

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
'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
}
}
'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)
{
"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"
}
}
'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
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment