Benchmarks

Every number below came from a real run, timed with Python's own timeit, on the machine described here. Where a figure goes beyond what was actually measured (capacity planning past what fits on one laptop) it is marked as calculated or extrapolated, not measured.

Complexity, in Big O

Every measurement further down is a real-world reading of the same underlying complexity. Here it is in the form you can reason about without a stopwatch.

Reading the notation: k and m are fixed per filter, so O(k) and O(m) are a flat cost, not one that grows with n. Nothing here is logarithmic or quadratic, staying flat is the whole point.

BloomFilter.add

O(k)

k hash rounds per insert. Independent of capacity n and of how many members are already in.

might_contain

O(k)

Worst case checks all k bits. Best case exits on the first cleared bit, often round 0.

Construction

O(m)

Zeroing the bit array, m bits sized from capacity and error rate at construction time.

serialize / save

O(m)

Proportional to bit array size in bytes (m / 8), not to how many members were inserted.

ShardedBloomFilter.checkpoint

O(d · m/s)

d dirty shards out of s total, each of size m/s. Untouched shards cost nothing.

Space, overall

O(n)

m is derived from n and the target error rate p, and scales linearly with n for fixed p.

Throughput

Every figure below is at 100,000 items and a 0.1% target error rate, unless noted otherwise. Hover a bar for the exact number.

Core operations

in memory, no disk involved

Persistence

serialization and checkpoint I/O

The gap between the two charts is the entire reason ManagedBloomFilter and ShardedBloomFilter exist. In-memory operations run in low single-digit microseconds. Writing a checkpoint means serializing and fsyncing real bytes to disk, three orders of magnitude slower, which is exactly why you control how often it happens rather than doing it on every insert.

Scaling with capacity

Bit array size grows linearly with expected item count. Past a few hundred million items, these numbers move from measured to calculated, the formula in core.py does not change with scale.

Memory footprint

at a 0.1% target error rate, log scale

Hash rounds vs. target error rate

at 1,000,000 items capacity

Why sharding pays for itself

A ShardedBloomFilter tracks which shards changed and rewrites only those on checkpoint. A plain ManagedBloomFilter has no such concept, every checkpoint rewrites everything, every time. Same 100,000 item filter, 16 shards, checkpointing at different dirty fractions.

Checkpoint cost as dirty shards grow

100,000 item capacity, 16 shards

Observed vs. requested false positive rate

50,000 lookups against a filter sized for 100,000 items

Capacity	Target	False positives	Observed	Theoretical

Concurrency, honestly

Not thread-safe

BloomFilter must not be shared across threads without a lock

self._bits[byte_index] |= 1 << bit_offset

That line compiles to separate load, or, and store bytecodes. A GIL handoff between the read and the write, on the same byte, from two threads, is a genuine lost-update hazard: one thread's bit can be silently overwritten by another's stale copy of the same byte.

A stress test of 16 threads doing 500 inserts each into a shared 2-byte array, forced to collide, produced 0 bit differences against a single-threaded reference across every trial run. That result does not prove safety, it only means this specific run did not happen to trigger the race. Put a lock around writes if more than one thread touches the same filter.

Capacity planner

Pick an expected item count and a target error rate. These numbers come straight from optimal_size and optimal_hash_count, the same functions the library calls internally.

Expected items

Target error rate

Checkpoint and load figures assume a single file with the OS page cache warm. A cold-cache disk read will be slower than what is shown here.

Full capacity table

All 98 rows behind the planner above, every combination of the 7 capacities and 14 error rates the suite covers.

Click a header to sort. Click any cell to select its row and column, Excel-style, useful for lining up a number with its label while scrolling.

Full operation log

All 194 timed records from the run. Search by operation, scenario, or note, or filter to one operation at a time.

MEASURED figures were timed directly. CALCULATED figures come from exact formulas. EXTRAPOLATED figures project past what was actually run, see the notes column for the caveat.