@hackage / unagi-bloomfilter

A fast, cache-efficient, concurrent bloom filter

Latest0.1.1.2

About

Metadata

  • Last updated , by BrandonSimmons
  • License BSD-3-Clause
  • Categories Concurrency

  • Maintained by: brandon.m.simmons@gmail.com

  • Lottery factor: 0

Links

Installation

Package Flags

Use the -f option with cabal commands to enable flags

    dev (off by default)

    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)

    instrumented (off by default)

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

Readme

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