[PATCH v2 11/11] bloom: enforce a minimum size of 8 bytes

From: Derrick Stolee <dstolee@microsoft.com>

The original design of changed-path Bloom filters included an 8-byte block size for filter lengths. This was changed mid-way through the submission process, and now the length stored in the commit-graph has one-byte granularity.

This can cause some issues for very small filters. The analysis for false positive rates assume large filters, so rounding errors become less important at that scale. When there are only a few paths changed, a filter that has size only a few bytes could have very different behavior. In fact, this is evidenced in the Git repository due to the code organization and careful patch creation that leads to many commits with very small filters. These small filters frequently have false-positive rates in the 8-10% range or higher.

The previous change improved the false-positive rate using multiple Bloom keys when the path has multiple directory components. However, that does not help at all for files at root. It is typical to have several commits that change only the README at root, and those commits would be likely to have these artificially high false-positive rates.

Correct this issue by creating a minimum filters size of 8 bytes. This requires the very small commits (with fewer than six changes, including non-root directories) to have a larger filter. In principle, this violates the bits_per_entry value of struct bloom_filter_settings. However, it does not actually create a functional problem.

As for compatibility, this only affects new versions writing filters for commits that do not yet have a filter. Old version will write the smaller filters and this version will persist and properly read that data. Now, the new files will be generated slightly larger.

               Bytes before   Bytes after  Difference
  --------------------------------------------------
  git             4,021,078    4,275,311   +6.32%
  linux          72,212,101   73,909,286   +2.35%
  tensorflow      7,596,359    7,691,646   +1.25%

This has a measurable improvement in the false-positive rate and the end-to-end run time for these repos. The table below compares the average false-positive rate and runtime of

  git rev-list HEAD -- "$path"

before and after this change for 5000+ randomly* selected paths from each repository:

                    Average false           Average        Average
                    positive rate           runtime        runtime
                  before     after     before     after   difference
  ------------------------------------------------------------------
  git             0.786%     0.227%    0.0387s    0.0289s -25.5%
  linux           0.0296%    0.0174%   0.0766s    0.0706s  -7.8%
  tensorflow      0.6977%    0.0268%   0.0420s    0.0384s  -8.5%

*Path selection was done with the following pipeline:

        git ls-tree -r --name-only HEAD | sort -R | head -n 5000

These relatively-small increases in file size appear to be a fair price to pay for these performance improvements.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 bloom.c | 4 ++++
 1 file changed, 4 insertions(+)