Skip to content

Instantly share code, notes, and snippets.

@derhuerst

derhuerst/1-benchmark.js

Last active March 14, 2022 21:16
Show Gist options
  • Save derhuerst/b254dce635e11eff4da58d15c6ad98a7 to your computer and use it in GitHub Desktop.
Save derhuerst/b254dce635e11eff4da58d15c6ad98a7 to your computer and use it in GitHub Desktop.
Download ZIP
JS bloom filters benchmark
Raw
1-benchmark.js
'use strict'
const {randomBytes} = require('crypto')
const {Suite} = require('benchmark')
const {ok} = require('assert')
const Farmfilter = require('farmfilter')
const XXBloom = require('xxbloom')
const JSBloom = require('jsbloom').filter
const Orlando = require('orlando')
// const Overview = require('overview-js-bloom-filter').BloomFilter
const Bloom = require('bloom-filter-js').BloomFilter
const Bloem = require('bloem').SafeBloem
const {BloomFilter} = require('bloomfilter')
const BloomLite = require('bloom-lite')
const BloomFilter2 = require('bloom-filter')
const MiniBloom = require('@mcrowe/minibloom')
const Asino = require('asino')
const Sai = require('sai-bloom').constructor
const BFilter = require('bfilter').BloomFilter
const Node = require('node_bloom_filter')
const Datalib = require('datalib-sketch').Bloom
const BloomF = require('bloomf')
console.info('generating test data')
const sSetSize = 1000
const sSet = []
for (let i = 0; i < sSetSize; i++) {
sSet[i] = randomBytes(4).toString('hex')
}
const lSetSize = 100000
const lSet = []
for (let i = 0; i < lSetSize; i++) {
lSet[i] = randomBytes(4).toString('hex')
}
console.info('generating 1k index')
const sFarmfilter = Farmfilter.createOptimal(sSetSize, .01)
const sXxbloom = XXBloom.createOptimal(sSetSize, .01)
const sJsbloom = new JSBloom(sSetSize, .01)
const sOrlando = Orlando.create(sSetSize)
// const sOverview = new Overview({m: 10 * sSetSize, k: 7})
const sBloom = new Bloom(10, sSetSize)
const sBloem = new Bloem(sSetSize, .01)
const sBloomFilter = new BloomFilter(10 * sSetSize, 7)
const sBloomLite = new BloomLite()
const sBloomFilter2 = BloomFilter2.create(sSetSize, .01)
const sMiniBloom = MiniBloom.optimalFilter(sSetSize, .01)
const sAsino = Asino({epop: sSetSize, hfn: 7})
const sSai = new Sai({size: sSetSize, rate: .01})
const sBFilter = BFilter.fromRate(sSetSize, .01, -1)
const sNode = new Node({
optimize: true, nElements: sSetSize, falsePositiveRate: .01
})
const sDatalib = Datalib.create(sSetSize, .01)
const sBloomF = new BloomF(10 * sSetSize, 7)
for (let item of sSet) {
sFarmfilter.add(item)
sXxbloom.add(item)
sJsbloom.addEntry(item)
sOrlando.add(item)
// sOverview.add(item)
sBloom.add(item)
sBloem.add(Buffer.from(item))
sBloomFilter.add(item)
sBloomLite.add(item)
sBloomFilter2.insert(Buffer.from(item))
sMiniBloom.add(item)
sAsino.try(Buffer.from(item))
sSai.Add(item)
sBFilter.add(item)
sNode.add(item)
sDatalib.add(item)
sBloomF.insert(item)
}
console.info('making sure the filters work')
const test = (set, size, test) => set.filter(test).length > size * .7
ok(test(sSet, sSetSize, v => sFarmfilter.has(v)), 'farmfilter')
ok(test(sSet, sSetSize, v => sXxbloom.has(v)), 'xxbloom')
ok(test(sSet, sSetSize, v => sJsbloom.checkEntry(v)), 'jsbloom')
ok(test(sSet, sSetSize, v => sOrlando.has(v)), 'orlando')
// ok(test(sSet, sSetSize, v => sBloom.exists(v.split(''))), 'bloom-filter-js')
ok(test(sSet, sSetSize, v => sBloem.has(Buffer.from(v))), 'bloem')
ok(test(sSet, sSetSize, v => sBloomFilter.test(v)), 'bloomfilter')
ok(test(sSet, sSetSize, v => sBloomLite.exist(v)), 'bloom-lite')
ok(test(sSet, sSetSize, v => sBloomFilter2.contains(Buffer.from(v))), 'bloom-filter')
ok(test(sSet, sSetSize, v => sMiniBloom.test(v)), 'minibloom')
ok(test(sSet, sSetSize, v => sAsino.key(Buffer.from(v))), 'asino')
ok(test(sSet, sSetSize, v => sSai.Test(v)), 'sai-bloom')
ok(test(sSet, sSetSize, v => sBFilter.test(v)), 'bfilter')
ok(test(sSet, sSetSize, v => sNode.has(v)), 'node_bloom_filter')
ok(test(sSet, sSetSize, v => sDatalib.query(v)), 'datalib-sketch')
ok(test(sSet, sSetSize, v => sBloomF.test(v)), 'bloomf')
console.info('generating 1m index')
const lFarmfilter = Farmfilter.createOptimal(lSetSize, .01)
const lXxbloom = XXBloom.createOptimal(lSetSize, .01)
const lJsbloom = new JSBloom(lSetSize, .01)
const lOrlando = Orlando.create(lSetSize)
// const lOverview = new Overview({m: 10 * lSetSize, k: 7})
const lBloom = new Bloom(10, lSetSize)
const lBloem = new Bloem(lSetSize, .01)
const lBloomFilter = new BloomFilter(10 * lSetSize, 7)
const lBloomLite = new BloomLite()
const lBloomFilter2 = BloomFilter2.create(lSetSize, .01)
const lMiniBloom = MiniBloom.optimalFilter(lSetSize, .01)
const lAsino = Asino({epop: lSetSize, hfn: 7})
const lSai = new Sai({size: lSetSize, rate: .01})
const lBFilter = BFilter.fromRate(lSetSize, .01, -1)
const lNode = new Node({
optimize: true, nElements: lSetSize, falsePositiveRate: .01
})
const lDatalib = Datalib.create(lSetSize, .01)
const lBloomF = new BloomF(10 * lSetSize, 7)
for (let item of lSet) {
lFarmfilter.add(item)
lXxbloom.add(item)
lJsbloom.addEntry(item)
lOrlando.add(item)
// lOverview.add(item)
lBloom.add(item)
lBloem.add(Buffer.from(item))
lBloomFilter.add(item)
lBloomLite.add(item)
lBloomFilter2.insert(Buffer.from(item))
lMiniBloom.add(item)
lAsino.try(Buffer.from(item))
lSai.Add(item)
lBFilter.add(item)
lNode.add(item)
lDatalib.add(item)
lBloomF.insert(item)
}
console.info('running benchmarks')
new Suite()
.add('1k 1% farmfilter', function () {
for (let i = 0; i < sSetSize; i++) sFarmfilter.has(sSet[i])
})
.add('1k 1% xxbloom', function () {
for (let i = 0; i < sSetSize; i++) sXxbloom.has(sSet[i])
})
.add('1k 1% jsbloom', function () {
for (let i = 0; i < sSetSize; i++) sJsbloom.checkEntry(sSet[i])
})
.add('1k ?% orlando', function () {
for (let i = 0; i < sSetSize; i++) sOrlando.has(sSet[i])
})
// .add('1k ?% overview-js-bloom-filter', function () {
// for (let i = 0; i < sSetSize; i++) sOverview.test(sSet[i])
// })
.add('1k ~1% bloom-filter-js', function () {
for (let i = 0; i < sSetSize; i++) sBloom.exists(sSet[i].split(''))
})
.add('1k 1% bloem', function () {
for (let i = 0; i < sSetSize; i++) sBloem.has(Buffer.from(sSet[i]))
})
.add('1k ~1% bloomfilter', function () {
for (let i = 0; i < sSetSize; i++) sBloomFilter.test(sSet[i])
})
.add('1k ?% bloom-lite', function () {
for (let i = 0; i < sSetSize; i++) sBloomLite.exist(sSet[i])
})
.add('1k 1% bloom-filter', function () {
for (let i = 0; i < sSetSize; i++) sBloomFilter2.contains(Buffer.from(sSet[i]))
})
.add('1k 1% minibloom', function () {
for (let i = 0; i < sSetSize; i++) sMiniBloom.test(sSet[i])
})
.add('1k ?% asino', function () {
for (let i = 0; i < sSetSize; i++) sAsino.key(Buffer.from(sSet[i]))
})
.add('1k 1% sai-bloom', function () {
for (let i = 0; i < sSetSize; i++) sSai.Test(sSet[i])
})
.add('1k 1% bfilter', function () {
for (let i = 0; i < sSetSize; i++) sBFilter.test(sSet[i])
})
.add('1k 1% node_bloom_filter', function () {
for (let i = 0; i < sSetSize; i++) sNode.has(sSet[i])
})
.add('1k 1% datalib-sketch', function () {
for (let i = 0; i < sSetSize; i++) sDatalib.query(sSet[i])
})
.add('1k 1% bloomf', function () {
for (let i = 0; i < sSetSize; i++) sBloomF.test(sSet[i])
})
.add('1k Array.includes', function () {
for (let i = 0; i < sSetSize; i++) sSet.includes(sSet[i])
})
.add('100k 1% farmfilter', function () {
for (let i = 0; i < lSetSize; i++) lFarmfilter.has(lSet[i])
})
.add('100k 1% xxbloom', function () {
for (let i = 0; i < lSetSize; i++) lXxbloom.has(lSet[i])
})
.add('100k 1% jsbloom', function () {
for (let i = 0; i < lSetSize; i++) lJsbloom.checkEntry(lSet[i])
})
.add('100k ?% orlando', function () {
for (let i = 0; i < lSetSize; i++) lOrlando.has(lSet[i])
})
// .add('100k ?% overview-js-bloom-filter', function () {
// for (let i = 0; i < lSetSize; i++) lOverview.test(lSet[i])
// })
.add('100k ~1% bloom-filter-js', function () {
for (let i = 0; i < lSetSize; i++) lBloom.exists(lSet[i].split(''))
})
.add('100k 1% bloem', function () {
for (let i = 0; i < lSetSize; i++) lBloem.has(Buffer.from(lSet[i]))
})
.add('100k ~1% bloomfilter', function () {
for (let i = 0; i < lSetSize; i++) lBloomFilter.test(lSet[i])
})
.add('100k ?% bloom-lite', function () {
for (let i = 0; i < lSetSize; i++) lBloomLite.exist(lSet[i])
})
.add('100k 1% bloom-filter', function () {
for (let i = 0; i < lSetSize; i++) lBloomFilter2.contains(Buffer.from(lSet[i]))
})
.add('100k 1% minibloom', function () {
for (let i = 0; i < lSetSize; i++) lMiniBloom.test(lSet[i])
})
.add('100k ?% asino', function () {
for (let i = 0; i < lSetSize; i++) lAsino.key(Buffer.from(lSet[i]))
})
.add('100k 1% sai-bloom', function () {
for (let i = 0; i < lSetSize; i++) lSai.Test(lSet[i])
})
.add('100k 1% bfilter', function () {
for (let i = 0; i < lSetSize; i++) lBFilter.test(lSet[i])
})
.add('100k 1% node_bloom_filter', function () {
for (let i = 0; i < lSetSize; i++) lNode.has(lSet[i])
})
.add('100k 1% datalib-sketch', function () {
for (let i = 0; i < lSetSize; i++) lDatalib.query(lSet[i])
})
.add('100k 1% bloomf', function () {
for (let i = 0; i < lSetSize; i++) lBloomF.test(lSet[i])
})
.add('100k Array.includes', function () {
for (let i = 0; i < lSetSize; i++) lSet.includes(lSet[i])
})
.on('error', (err) => {
console.error(err)
process.exitCode = 1
})
.on('cycle', (e) => {
console.log(e.target.toString())
})
.run()
Raw
2-package.json
{
"private": true,
"name": "bloom-benchmark",
"version": "1.0.0",
"scripts": {
"benchmark": "node benchmark.js"
},
"author": "Jannis R <mail@jannisr.de>",
"license": "ISC",
"devDependencies": {
"benchmark": "^2.1.4"
},
"dependencies": {
"@mcrowe/minibloom": "^0.2.0",
"asino": "^0.3.3",
"bfilter": "^0.2.0",
"bloem": "^0.2.4",
"bloom-filter": "^0.2.0",
"bloom-filter-js": "0.0.12",
"bloom-lite": "0.0.3",
"bloomf": "^2.1.4",
"bloomfilter": "0.0.18",
"datalib-sketch": "^1.0.2",
"farmfilter": "^1.1.0",
"jsbloom": "^1.1.0",
"node_bloom_filter": "^1.0.4",
"orlando": "^1.0.0",
"overview-js-bloom-filter": "0.0.3",
"sai-bloom": "^1.0.4",
"xxbloom": "^1.0.1"
}
}
Raw
3-output.txt
generating test data
generating 1k index
making sure the filters work
generating 1m index
running benchmarks
1k 1% farmfilter x 85.32 ops/sec ±0.38% (72 runs sampled)
1k 1% xxbloom x 49.91 ops/sec ±2.51% (64 runs sampled)
1k 1% jsbloom x 7,314 ops/sec ±0.33% (97 runs sampled)
1k ?% orlando x 1,257 ops/sec ±0.35% (74 runs sampled)
1k ~1% bloom-filter-js x 535 ops/sec ±0.46% (91 runs sampled)
1k 1% bloem x 927 ops/sec ±0.40% (93 runs sampled)
1k ~1% bloomfilter x 3,962 ops/sec ±0.27% (96 runs sampled)
1k ?% bloom-lite x 255 ops/sec ±13.30% (55 runs sampled)
1k 1% bloom-filter x 2,233 ops/sec ±3.40% (91 runs sampled)
1k 1% minibloom x 5,106 ops/sec ±0.36% (93 runs sampled)
1k ?% asino x 1,425 ops/sec ±0.43% (93 runs sampled)
1k 1% sai-bloom x 5,266 ops/sec ±0.63% (95 runs sampled)
1k 1% bfilter x 796 ops/sec ±0.59% (90 runs sampled)
1k 1% node_bloom_filter x 645 ops/sec ±0.39% (91 runs sampled)
1k 1% datalib-sketch x 5,182 ops/sec ±0.35% (93 runs sampled)
1k 1% bloomf x 33.62 ops/sec ±0.63% (58 runs sampled)
1k Array.includes x 553 ops/sec ±0.49% (91 runs sampled)
100k 1% farmfilter x 0.02 ops/sec ±0.82% (5 runs sampled)
100k 1% xxbloom x 0.02 ops/sec ±0.71% (5 runs sampled)
100k 1% jsbloom x 30.45 ops/sec ±0.44% (54 runs sampled)
100k ?% orlando x 12.18 ops/sec ±0.83% (34 runs sampled)
100k ~1% bloom-filter-js x 6.33 ops/sec ±0.81% (20 runs sampled)
100k 1% bloem x 9.15 ops/sec ±0.99% (27 runs sampled)
100k ~1% bloomfilter x 37.98 ops/sec ±0.39% (65 runs sampled)
100k ?% bloom-lite x 2.83 ops/sec ±7.77% (11 runs sampled)
100k 1% bloom-filter x 19.40 ops/sec ±1.75% (36 runs sampled)
100k 1% minibloom x 48.88 ops/sec ±0.46% (63 runs sampled)
100k ?% asino x 13.49 ops/sec ±2.04% (38 runs sampled)
100k 1% sai-bloom x 52.64 ops/sec ±0.40% (67 runs sampled)
100k 1% bfilter x 7.49 ops/sec ±0.82% (23 runs sampled)
100k 1% node_bloom_filter x 6.26 ops/sec ±1.07% (20 runs sampled)
100k 1% datalib-sketch x 51.34 ops/sec ±0.37% (66 runs sampled)
100k 1% bloomf x 0.33 ops/sec ±0.87% (5 runs sampled)
100k Array.includes x 0.05 ops/sec ±1.93% (5 runs sampled)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment