JS bloom filters benchmark

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()

2-package.json

{
  "private": true,
  "name": "bloom-benchmark",
  "version": "1.0.0",
  "scripts": {
    "benchmark": "node benchmark.js"
  },
  "author": "Jannis R <[email protected]>",
  "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"
  }
}

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)