unagi-bloomfilter: A fast, cache-efficient, concurrent bloom filter
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, e.g. here are 10 inserts or lookups compared across some sets of different sizes:
With the llvm backend benchmarks take around 75-85% of the runtime of the native code gen.
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).
Modules
- Control
- Concurrent
- Control.Concurrent.BloomFilter
- Control.Concurrent.BloomFilter.Internal
- Control.Concurrent.BloomFilter
- Concurrent
Flags
Manual Flags
Name | Description | Default |
---|---|---|
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) | Disabled |
instrumented | Enables assertions in library code. When --enable-library-profiling and --enable-executable-profiling is turned on, you can get stacktraces as well | Disabled |
Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info
Downloads
- unagi-bloomfilter-0.1.1.2.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
Versions [RSS] | 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 2018-04-11T02:58:54Z |
Distributions | |
Reverse Dependencies | 1 direct, 0 indirect [details] |
Executables | dev-example |
Downloads | 2468 total (7 in the last 30 days) |
Rating | (no votes yet) [estimated by Bayesian average] |
Your Rating | |
Status | Docs not available [build log] All reported builds failed as of 2021-06-02 [all 2 reports] |