False-positive rate against bits per element, k = 4, n = 4,000

False-positive rate against bits per element, k = 4, n = 4,000

Filled circles are measured: 60,000 queries for keys that were never inserted, counted. The solid line is (1 − e^(−kn/m))^k, the formula every sizing guide prints. The dashed line is the same expression computed from the bits the filter actually has set. At 4 bits per element the measured rate is 16.2% and at 12 it is 0.620%. Not one inserted key tested absent at any size: the errors a filter makes are all in one direction. The keys are drawn at random, which is what the analysis assumes; the two lines then agree with the points to within 2.8%.

Drawn at 690 × 400, wide on the page. Everything above is what bloom-rate returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

12 essays call bloom-rate. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.