Skip to content

Releases: dmatth1/quickbloom

Release list

v0.2.0 — aarch64 (NEON) backend

v0.2.0 — aarch64 (NEON) backend Latest
Latest

Choose a tag to compare

View all tags
@dmatth1 dmatth1 released this 23 May 00:19
v0.2.0
82b4e7e

quickbloom 0.2.0 adds a native aarch64 / NEON backend alongside the existing AVX2 backend. The SBBF bitset is bit-identical across architectures and bit-identical to the Apache Parquet spec.

Highlights

  • New aarch64 / NEON backend. Apple Silicon, AWS Graviton 1–4, Ampere Altra, Azure Cobalt, any ARMv8-A core. Selected automatically at build time by uname -m. Hand-tuned NEON shim (vmulq + vshrq + vshlq + vbicq + vmaxvq) — measured ~1.2–2.2× faster than a simde-based portable wrapper on the same probe.
  • Cross-arch bit-compat is verified on every CI run on both ubuntu-latest (x86_64) and ubuntu-24.04-arm (aarch64) by test/test_compat_arrow_rs.py, which feeds the same XXH64 hash to quickbloom and arrow-rs's Sbbf and asserts every probe answer agrees on 100k queries.
  • CI matrix extended for build+test, ASan/UBSan, and the arrow-rs cross-validation to Linux aarch64 — gcc and clang both green.
  • Tooling fixes for Linux aarch64 / macOS dev loops: Makefile picks Linux .so vs Darwin .dylib naming and the right soname/install_name flags; harness.py cpu_info has a sysctl-backed macOS fallback; tools/bench_all.py skips x86-only kernels cleanly on aarch64 hosts.
  • posix_memalign → C11 aligned_alloc. Removes the strict-C11 implicit-declaration issue on Linux aarch64 clang.
  • Comparison kernels audited against their upstream sources. No measured numbers changed; pinned Rust shims (fastbloom, parquet) to exact versions; documented one PRNG swap in bloom_krassovsky.c's mask-table init.

What's unchanged

  • ABI in quickbloom.h — qb_* signatures, struct layout, on-disk serialized bitset format.
  • AVX2 codegen — byte-identical to 0.1.0.
  • SOVERSION stays 0.

Supported build targets

Arch Required Compilers
x86_64 AVX2 + BMI2 gcc, clang
aarch64 ARMv8-A NEON (baseline) gcc, clang

Quick start

make           # builds libquickbloom.{a,so|dylib}
sudo make install
#include <quickbloom.h>
void* f = qb_new(qb_estimate_bits(100000, 0.01));
qb_insert(f, "hello", 5);
if (qb_contains(f, "hello", 5)) { /* probably present */ }
qb_free(f);

Rejected alternatives (documented in README)

  • simde portable shim: 1.2–2.2× slower than the hand-NEON kernel.
  • AVX-512 single-key and 8-way: slower than AVX2 on Sapphire Rapids (frequency throttle exceeds the width gain).
  • Scalar fallback for RISC-V / WASM: deferred until there's a customer.
Assets 2
Loading

v0.1.0

v0.1.0

Choose a tag to compare

View all tags
@dmatth1 dmatth1 released this 21 May 08:36
v0.1.0
8ce7907
This commit was signed with the committer’s verified signature.
claude Claude
SSH Key Fingerprint: 32dP45eSMmVSt/G/CGvcxl/P+MO3Nwj9xeTh/GSA2wc
Verified
Learn about vigilant mode.

Fast Split Block Bloom Filter for x86_64. wyhash-style hash + AVX2 mask compute, one cache line per probe.

Performance

Min ns/op on Intel Xeon @ 2.8 GHz (Cascade Lake-class, 1 MB L2 per core, 33 MB L3), clang -O3, make bench-qb:

Size hash+bloom prehash
S (128 KB) 2.29 1.37
M (2 MB) 5.73 2.70
L (32 MB) 18.61 11.66

The fastest single-key SBBF probe kernel we've measured. Versus the same kernel in other Parquet SBBF implementations, prehash at M:

Implementation K prehash M (ns)
quickbloom 8 2.70
krassovsky (batched only) 5 7.11
xorfuse 3 8.49
impala 8 11.11
classic 8 12.74
fastbloom (Rust) 8 17.30

Per-key hash cost on the same host: wymum16 1.67 ns, XXH64 3.50 ns, SipHash-1-3 3.38 ns.

What's in the box

  • C ABI (quickbloom.h): single-key and bulk insert/contains, prehash variants (pass a 64-bit hash directly), serialize/deserialize. The on-disk format is the raw Parquet SBBF bitset — bit-identical to arrow-rs, arrow-cpp, Velox, DuckDB, and Impala for the same hash inputs (verified against arrow-rs on every CI run).
  • Algorithm: 256-bit blocks, K=8, Parquet-spec salts and fastrange block index. AVX2 SIMD mask compute (vpmullo + vpsrli + vpsllv + vptest). wyhash-style 128-bit multiply + xor-fold on the 16-byte fast path; fasthash64 for variable-length keys.
  • Build: gcc or clang, -O3 -mavx2 -mbmi2 -mfma -maes. Runs on any x86_64 with AVX2 + BMI2 (Intel Haswell 2013+ or AMD Excavator 2015+ / Zen 1+). No AArch64.
  • Verified: native + Python correctness suites, structured-input regression tests, libFuzzer harnesses, ASan/UBSan on gcc and clang, bit-identical cross-validation against arrow-rs parquet::bloom_filter::Sbbf on every CI run.

Quick start

git clone <https://github.com/dmatth1/quickbloom>
cd quickbloom
make && sudo make install
Loading