unagi-bloomfilter: A fast, cache-efficient, concurrent bloom filter

[ bsd3, concurrency, library ] [ Propose Tags ]

This library implements a fast concurrent bloom filter, based on bloom-1 from "Fast Bloom Filters and Their Generalization" by Y Qiao, et al.

A bloom filter is a probabilistic, constant-space, set-like data structure supporting insertion and membership queries. This implementation is backed by SipHash so can safely consume untrusted inputs.

The implementation here compares favorably with traditional set implementations in a single-threaded context:

Unfortunately writes in particular don't seem to scale currently; i.e. distributing writes across multiple threads may be slower than in a single-threaded context, because of memory effects. We plan to export functionality that would support using the filter here in a concurrent context with better memory behavior (e.g. a server that shards to a thread-pool which handles only a portion of the bloom array).

Versions 0.1.0.0, 0.1.1.0, 0.1.1.1, 0.1.1.2
Dependencies atomic-primops (>=0.8), base (>=4.7 && <5), bytestring, hashabler (>=1.3.0), primitive [details]
License BSD-3-Clause
Author Brandon Simmons
Maintainer brandon.m.simmons@gmail.com
Category Concurrency
Home page http://github.com/jberryman/unagi-bloomfilter
Source repo head: git clone https://github.com/jberryman/unagi-bloomfilter.git
Uploaded by BrandonSimmons at Tue Aug 23 17:40:45 UTC 2016
Distributions NixOS:0.1.1.2
Executables dev-example
Downloads 528 total (13 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2016-11-20 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Flags

NameDescriptionDefaultType
dev

To build tests, executables and benchmarks do `configure -fdev --enable-tests` and run the built executables by hand (i.e. not with `cabal test` etc.; we put all our different executables in test-suite sections in order to hide their dependencies from hackage)

DisabledManual
instrumented

Enables assertions in library code. When --enable-library-profiling and --enable-executable-profiling is turned on, you can get stacktraces as well

DisabledManual

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

For package maintainers and hackage trustees