Subject: Re: [PATCH v3 12/14] commit-graph: add large-filters bitmap chunk

From: SZEDER Gábor <[email-masked]>
Date: Wed, 19 Aug 2020 15:35:26 +0200

On Tue, Aug 11, 2020 at 04:52:07PM -0400, Taylor Blau wrote:
> When a commit has more than a certain number of changed paths (commonly
> 512), the commit-graph machinery represents it as a zero-length filter.
> This is done since having many entries in the Bloom filter has
> undesirable effects on the false positivity rate.

This is not the case, the false positive probability depends on the
ratio of the Bloom filter's size and the number of elements it
contains, and we size the filters proportional to the number of
elements they contain, so the number of elements shouldn't affect the 
false positive rate.

On the contrary, it's the small filters, up to around 30-35 bytes, 
that tend to have larger than expected false positive rate when using
double hashing.