Git Mailing List Archive on lore.kernel.org
 help / color / Atom feed
From: "SZEDER Gábor" <szeder.dev@gmail.com>
To: git@vger.kernel.org
Cc: "Junio C Hamano" <gitster@pobox.com>,
	"Garima Singh" <garima.singh@microsoft.com>,
	"Derrick Stolee" <stolee@gmail.com>,
	"Jakub Narebski" <jnareb@gmail.com>, "Jeff King" <peff@peff.net>,
	"Taylor Blau" <me@ttaylorr.com>,
	"SZEDER Gábor" <szeder.dev@gmail.com>
Subject: [PATCH 15/34] commit-graph-format.txt: document the modified path Bloom filter chunks
Date: Fri, 29 May 2020 10:50:19 +0200
Message-ID: <20200529085038.26008-16-szeder.dev@gmail.com> (raw)
In-Reply-To: <20200529085038.26008-1-szeder.dev@gmail.com>

During a pathspec-limited revision walk, e.g. 'git log -- dir/file',
Git spends a significant part of its runtime in the tree-diff
machinery, checking whether the given path was modified between
subsequent commits.  By using Bloom filters to store the paths
modified by each commit we can quickly tell that a commit didn't
modify the given path without invoking tree-diff, thus considerably
reduce this diffing overhead, along with the runtime and memory usage.
This patch extends the commit-graph file format with additional chunks
to store those modified path Bloom filters.

The rest of this log message takes a closer look at the problem and
explains why these new chunks look like they do.

In the following the terms "file" and "path" are not used
interchangeably.  If a commit modified 'dir/subdir/foo.c', then it
modified that one file, but it modified three paths (namely 'dir',
'dir/subdir', and 'dir/subdir/foo.c').

Furthermore, unless otherwise noted, "a lot of paths" means 5000
randomly selected paths that have existed at one time or another
during the history of the corresponding repository's default branch
[1], except for git it means all 5089 paths that have ever existed
during the history of v2.25.0, and for homebrew-cask and homebrew-core
all 7307 and 6535 paths, respectively, that have ever existed in the
history of their default branches some time ago.

About pathspec-limited revision walks
-------------------------------------

So, during a pathspec-limited revision walk Git spends a significant
part of its runtime in the tree-diff machinery, checking whether the
given path was modified between subsequent commits.  The table below
shows the average runtime of 'git rev-list HEAD -- $path' for "a lot
of paths" in a couple of repositories, and how much of that runtime is
spent in diff_tree_oid().  It also shows the potential average
speedup, should we be able to reduce the tree-diff overhead to zero
without introducing some other overhead (spoiler alert: we won't be
able to achieve that, of course, but still will achieve even higher
average speedup in several cases).

                 Average    Average            Potential
                 runtime   diff time            speedup
  -------------------------------------------------------
  android-base   0.8780s    0.7320s    83.37%     6.14x
  cmssw          0.3143s    0.2800s    88.95%     9.19x
  cpython        0.7453s    0.6602s    88.58%     8.76x
  elasticsearch  0.1492s    0.1351s    90.55%    10.58x
  gcc            7.1852s    6.9432s    96.63%    29.69x
  gecko-dev      4.6113s    4.0964s    88.83%     8.96x
  git            0.6180s    0.5911s    95.65%    22.97x
  glibc          0.5618s    0.5313s    94.57%    18.42x
  go             0.4913s    0.4469s    90.96%    11.07x
  jdk            0.0482s    0.0431s    89.42%     9.45x
  linux          0.7043s    0.6163s    87.50%     8.00x
  llvm-project   2.6844s    2.2607s    84.22%     6.34x
  rails          0.2784s    0.2372s    85.20%     6.76x
  rust           0.7757s    0.7349s    94.74%    19.01x
  tensorflow     0.6258s    0.5735s    91.64%    11.96x
  webkit         1.9137s    1.6580s    86.64%     7.48x

Notice that the average time spent diffing in the Linux and Git
repositories is quite close (0.6163s vs 0.5911s), although the Linux
repository contains about 15x more commits and 25x more files; more on
this later.

Instrumenting the tree-diff machinery and gathering some stats about
the number of diff calls, tree object comparisons and decoded tree
entries revealed some interesting, perhaps even counterintuitive
things:

  - The number of scanned tree entries can be more important than the
    number of tree comparisons.

    Here are four paths from two repositories, two each in the same
    frequently-modified directory, with one near the beginning and one
    at the end of that directory.  When listing the commits modifying
    these paths, i.e. 'git rev-list HEAD -- $path', the number of tree
    comparisons is (nearly) the same, but the number of scanned tree
    entries differs by over two orders of magnitude.

                                      Average   Nr of scanned   Nr of tree
      Repository          $path      diff time   tree entries  comparisons
      --------------------------------------------------------------------
      git            .clang-format     0.188s          40115       18055
      git            zlib.c            0.729s       10705983       17120
      homebrew-core  Formula/a2ps.rb   8.390s        2122937      326758
      homebrew-core  Formula/zzz.rb   80.495s     1235547836      326758

    This is also noticeable when looking at the average number of
    scanned tree entries and tree comparisons when running 'git
    rev-list HEAD -- $path' for "a lot of paths":

                                Average nr      Average      Average
                     Average    of scanned     nr of tree   nr of diff
                    diff time  tree entries   comparisons      calls
      ----------------------------------------------------------------
      jdk            0.0431s       204466         5520         3702
      elasticsearch  0.1351s       720393        17212        13457
      rails          0.2372s      1299221        43369        33670
      cmssw          0.2800s      1938067        24798        23739
      go             0.4469s      3207155        76432        42346
      glibc          0.5313s      6555231        40442        29208
      tensorflow     0.5735s      3914851        97227        47262
      git            0.5911s      7480371        21789        18168
      linux          0.6163s      4004067        79514        58145
      cpython        0.6602s      4695754        88408        70439
      android-base   0.7320s      4312043       122280        96376
      rust           0.7349s      5084683        68110        29847
      webkit         1.6580s      9395349       303105       218906
      llvm-project   2.2607s     11773792       469801       330250
      gecko-dev      4.0964s     42396246       415843       387162
      gcc            6.9432s     84853083       286904       174218

    Note that although we have a lot less tree comparisons in the git
    than in the linux repository, it has almost double the amount of
    scanned tree entries, because the git repository has some
    frequently modified biggish directories (notably its root dir, 't'
    or 'Documentation').  As a result the average time spent diffing
    in the two repositories is roughly the same, although the linux
    repository is much larger.

    Or that we spend the most time diffing in the gcc repository,
    because it has by far the most scanned tree entries, even though
    it has less tree comparisons than any of the next three slowest
    repositories.

  - The number of path components in the pathspec, i.e. its depth in
    the directory tree seems to be irrelevant.

    When checking whether a path somewhere deep in the directory tree
    has been modified between a commit and its parent the tree-diff
    machinery can short-circuit, and it returns as soon as it finds
    the first leading directory that hasn't been modified.  And more
    often than not it can short-circuit already while comparing the
    root trees, as all the <1.5 values in the "Average tree
    comparisons per diff call" column show.

                     Average   Average tree     Average      Average
                    pathspec    comparisons    nr of diff   nr of tree
                      depth    per diff call      calls    comparisons
      ----------------------------------------------------------------
      android-base    5.78         1.26          96376       122280
      cmssw           4.28         1.04          23739        24798
      cpython         3.72         1.25          70439        88408
      elasticsearch   9.13         1.28          13457        17212
      gcc             5.13         1.64         174218       286904
      gecko-dev       6.25         1.07         387162       415843
      git             2.30         1.19          18168        21789
      glibc           4.17         1.38          29208        40442
      go              4.60         1.80          42346        76432
      jdk             8.45         1.49           3702         5520
      linux           4.49         1.36          58145        79514
      llvm-project    5.45         1.42         330250       469801
      rails           5.43         1.28          33670        43369
      rust            4.70         2.28          29847        68110
      tensorflow      5.56         2.06          47262        97227
      webkit          6.33         1.38         218906       303105

    Note the 2.xy average tree comparisons per diff call in the rust
    and tensorflow repositories.  In the rust repository over 98% of
    the paths are in the 'src' directory and over 93% of commits
    modify a file under that directory, while in the tensorflow
    repository over 92% of paths are in the 'tensorflow' directory and
    over 90% of commits modify a file under that directory.
    Consequently, the tree-diff machinery can only rarely
    short-circuit while comparing the root trees of two subsequent
    commits, but has to dive down and compare the contents of the
    'src' or 'tensorflow' directories most of the time as well.  I
    suspect that we would get a similar ~2 value in the homebrew-core
    repository as well, because over 99.7% of all commits modify the
    'Formula' directory, which contains over 90% of paths in the
    repository.

Bloom filters intro
-------------------

Quoting the (quite good) Wikipedia article, "A Bloom filter is a
space-efficient probabilistic data structure [...] that is used to
test whether an element is a member of a set. False positive matches
are possible, but false negatives are not – in other words, a query
returns either 'possibly in set' or 'definitely not in set'".

A Bloom filter is a bit array, initially all bits set to 0.  To add an
element to a Bloom filter, the element is hashed using 'k' independent
hash functions, the resulting hashes are turned into 'k' array
positions, and the bits at those positions in the filter are set to 1.
To query for an element, the element is hashed using the same 'k' hash
functions, the resulting hashes are turned into 'k' array positions,
and the values of the bits at those positions are checked.  If all
those bits are set, then the element is 'possibly in set'.  If even
one of those bits is unset, then the element is 'definitely not in
set'.

Some of the for us relevant properties of Bloom filters are:

  - A Bloom filter doesn't store the elements themselves, it only sets
    a couple of bits based on the elements' hashes.  Consequently, a
    Bloom filter can't tell which elements it contains; it can't even
    tell the number of elements in there.

  - A bit in the Bloom filter's bit array might be set by more than
    one element.  This is where the probabilistic nature and the
    possibility of false positives come from: it is possible that some
    elements in the set happen to have set all 'k' bits that would
    indicate the presence of a particular element, even though that
    element itself is not part of the set.

  - Elements can't be removed from a Bloom filter: the 'k' bits
    indicating the presence of an element can't simply be unset,
    because that might unset bits that were set by other elements as
    well.
    There are enhanced Bloom filter variants that allow removal of
    elements, like a counting Bloom filter, but they come with
    additional complexity and require considerably more space.

  - Bloom filters can't be resized, because turning the hashes into
    positions in the bit array critically depends on the size of the
    bit array (usually pos[i] = hash[i] % bit_array_size).

  - Bloom filters of the same size can be bitwise OR-ed to create the
    union of the sets of elements in the filters.

  - When playing long enough with probabilities and making some
    reasonable assumptions and approximations it can be shown (see the
    Wikipedia article) that for a desired false positive probability
    'p' there is an optimal number of 'k' hash functions:

      k = -log₂(p)    (that's a base 2 logarithm there)

    For 1% false positive probability k = 6.64, but of course there
    can only be an integral number of hash functions, so 7 it is.

    Note that this value is independent both from the size of the
    Bloom filter and from the number of elements in there.

    Inversely, when using a properly sized bit array, then the false
    positive probability falls exponentially as 'k' increases.

  - To store 'n' elements in a Bloom filter with a desired false
    positive probability using the optimal number of 'k' bits/hash
    functions, we need a bit array with approximate size 'm':

      m ≈ n * k / ln(2) ≈ n * k * 10 / 7

    When using 7 hash functions to aim for < 1% false positive
    probability this simplifies down to:

      m ≈ n * 7 * 10 / 7 = 10 * n

    i.e. approx. 10 bits per element.

  - In general the more elements, IOW the more set bits there are in a
    Bloom filter of certain size, the higher the probability of false
    positives.  Similarly, the larger the size of a Bloom filter's bit
    array for a certain number of elements, the lower the probability
    of false positives.

  - A Bloom filter with all bits set appears to contain "everything",
    because all queries will return 'possibly in set'.

Modified Path Bloom Filters
---------------------------

We'll use Bloom filters to store modified paths and will store them in
the Modified Path Bloom Filters chunk.  Yes, plural: we'll use a lot
of small Bloom filters, each one storing all paths modified by one
commit compared to one of its parents (see the Alternatives section
near the end for reasons for not using one big Bloom filter).  Then as
the pathspec-limited revision walk iterates over all commits it will
query each modified path Bloom filter to see whether the given
pathspec is in there, and if it is 'definitely not in set', then we
can spare a tree-diff call and skip the commit right away, but if it's
'possibly in set', then we must do the tree-diff to make sure.

Each modified path Bloom filter consists of:

  - 4 bytes specifying the number of bits in the Bloom filter's bit
    array.

    For practical purposes 32 bit is more than sufficient to store the
    number of bits in the Bloom filter's array.  When using k = 7
    hashes, i.e. 10 bits per path, then we could store over 400
    million paths in a single Bloom filter; with k = 32 hashes we'd
    use 46 bit per path, which is still over 93 million paths.

  - The actual bit array.  See the next and the Hashing scheme
    sections for details about how this bit array is used.

All modified path Bloom filters will use the same k number of hashes
per path, so we won't have to store that in each Bloom filter.  I
suspect that having modified path Bloom filters with different k
number of hashes wouldn't bring enough benefit to justify storing that
value in each and every filter.

The order of modified path Bloom filters in this chunk is unspecified
on purpose, so implementations can experiment with writing them in
history or topological order, which may bring performance benefits
through better locality.

[Somewhere in the middle of this section the length of this commit
message surpassed the length of 72441af7c4 (tree-diff: rework
diff_tree() to generate diffs for multiparent cases as well,
2014-04-07), the mother of all commit messages from the great Kirill
Smelkov, yay! :)]

Modified Path Bloom Filter Index
--------------------------------

Since modified path Bloom filters vary in size, we can't have an array
of modified path Bloom filters indexed by the position of the commit
OID in the OID Lookup chunk, but we'll need a level of indirection
between the commit OID position and the position of the associated
modified path Bloom filter.

So the Modified Path Bloom Filter Index chunk will contain an array of
offsets to quickly map commit OID positions to offsets in the Modified
Path Bloom Filters chunk, i.e. its Nth entry contains the offset for
the commit whose OID is Nth in the OID Lookup chunk.

Since the commit-graph file can store information about 2^31-1
commits, a merely 4 byte offset per commit is clearly insufficient.
However, surely noone want to have lots of gigabyte-sized modified
path Bloom filters, so a standard 8 byte file offset will be
underutilized.  This allows us to use a few bits from those 8 bytes
for special purposes.  For now we'll have two special purpose bits:

  - The most significant bit indicates that the entry is not an offset
    into the Modified Path Bloom Filters chunk, but an "embedded"
    modified path Bloom filter containing all paths modified by the
    commit compared to its first parent; see the next section.

  - The second most significant bit indicates that modified path Bloom
    filters are stored not only for the first parent of a merge
    commit, but for all its parents, and the entry is neither an
    offset nor an "embedded" modified path Bloom filter, but an array
    index into the Modified Path Bloom Filter Merge Index chunk; see
    the "Merges" section below.

  - [TODO: perhaps we might want to reserve one or two more bits for
    special purposes?]

Make these offsets relative to the start of the Modified Path Bloom
Filters chunk, so they will depend neither on the number of chunks nor
on the combined size of any other chunks that are written before the
Modified Path Bloom Filters chunk, thus allowing implementations to
calculate all these offsets without knowing anything about those other
chunks.  Furthermore, if the offsets were relative to the beginning of
the file, then some huge chunks could make the offsets grow too large,
and would mess up those special purpose bits (though, arguably, an
exabyte sized commit-graph file is just too unlikely to be worried
about...).

An "all bits set" index entry can be used to indicate that there is no
modified path Bloom filter stored for the corresponding commit.  A
reader implementation can either special-case such an entry, or
interpret it as an embedded modified path Bloom filter that replies
'possibly in set' to all queries, the result is the same: it has to
resort to running tree-diff for that commit.

These embedded modified path Bloom filters have implications on the
low-level Bloom filter format in the Modified Path Bloom Filters chunk
as well, namely:

  - Their array contains only 63 bits, not 64, i.e. not 8 full bytes.
    Therefore, for simplicity, we'll store the size of the bit array
    as the number of bits, not bytes.

  - Assigning special purpose to the most significant bits of the
    index entries is convenient when the entry is an offset into the
    Modified Path Bloom Filters chunk.  OTOH, it makes indexing into
    the Bloom filter's array awkward if we try to treat it like an
    ordinary array, i.e. whose 0th element comes first, because we'd
    have to account for the special purpose bits.  Therefore, we'll
    store the bit array kind of in big endian byte order, i.e. the
    most significant byte first and the 0th byte last.

In addition, this chunk will start with a small header storing a bit
of metadata that applies to all modified path Bloom filters in all
related chunks.  The reason for storing this header in the Modified
Path Bloom Filter Index chunk is that only this chunk is essential to
use modified path Bloom filters (if all commits modify so few files
that their modified path Bloom filters can all be embedded into the
index chunk, then the Modified Path Bloom Filters chunk will contain
nothing and thus can be omitted; e.g. the two homebrew repositories
come quite close to this, as shown below).

This header contains:

  - One byte storing the number of 'k' hashes per path.

    Using a single byte is more than sufficient: as 'k' increases the
    false positive probability falls exponentially, and quickly
    becomes unnecessarily low (i.e. with k = 31 even a full
    commit-graph containing 2^31-1 commits is expected to have only a
    single false positive).

  - [TODO: What else?  We might want to have a version byte, though if
    a format change becomes necessary, then we could simply rename the
    chunks just as well...]

Embedded Modified Path Bloom Filters
------------------------------------

The ideal size of a Bloom filter to store a set of 6 or 7 elements
with 7 hash functions is approximately 60 or 70 bits, respectively.
So in the space of a 8 byte Modified Path Bloom Filter Index entry we
could comfortably store 6 entries by using one bit to indicate that
the entry is not a file offset but an "embedded" modified path Bloom
filter and the remaining 63 bits as the Bloom filter's bit array.

As the table below shows, a significant portion or even the vast
majority of commits modify no more than 6 paths, so we can embed a lot
of modified path Bloom filters into the Modified Path Bloom Filter
Index chunk.  (Also note the unusually large percentage of empty diffs
in the android-base and cpython repositories.)

        Percentage of commits modifying <=N (or =N) paths compared to their first parents
                   0      <=1      <=2      <=3      <=4      <=5      <=6      <=7      <=8
                          (=1)     (=2)     (=3)     (=4)     (=5)     (=6)     (=7)     (=8)
  --------------------------------------------------------------------------------------------
  elasticsearch  0.70%   4.00%    5.67%    8.50%   13.17%   16.55%   18.32%   21.18%   27.47%
                        (3.30%)  (1.67%)  (2.83%)  (4.67%)  (3.37%)  (1.77%)  (2.86%)  (6.29%)
  jdk            0.26%   3.47%   10.60%   13.99%   15.62%   19.02%   26.62%   34.30%   40.57%
                        (3.20%)  (7.14%)  (3.39%)  (1.63%)  (3.40%)  (7.60%)  (7.68%)  (6.27%)
  webkit         0.05%   0.07%    0.77%    2.14%    9.15%   26.66%   38.42%   47.34%   52.83%
                        (0.02%)  (0.71%)  (1.37%)  (7.01%) (17.51%) (11.76%)  (8.92%)  (5.49%)
  android-base  13.20%  13.62%   14.23%   18.55%   20.91%   35.18%   42.32%   50.82%   62.05%
                        (0.42%)  (0.62%)  (4.32%)  (2.36%) (14.28%)  (7.14%)  (8.49%) (11.23%)
  llvm-project   0.12%   0.12%    0.94%    6.45%   25.24%   46.68%   53.60%   60.97%   67.33%
                        (0.00%)  (0.81%)  (5.51%) (18.79%) (21.44%)  (6.92%)  (7.37%)  (6.36%)
  gecko-dev      0.14%   0.96%    1.88%   15.44%   32.42%   46.12%   54.54%   61.37%   66.65%
                        (0.82%)  (0.92%) (13.56%) (16.98%) (13.70%)  (8.42%)  (6.82%)  (5.28%)
  tensorflow     0.09%   1.26%    2.72%    5.00%   26.30%   42.36%   55.17%   63.11%   69.70%
                        (1.17%)  (1.46%)  (2.28%) (21.27%) (16.07%) (12.81%)  (7.94%)  (6.59%)
  rails          0.10%   2.09%    5.79%   16.03%   35.57%   51.47%   58.71%   65.15%   72.96%
                        (1.99%)  (3.70%) (10.23%) (19.54%) (15.90%)  (7.24%)  (6.44%)  (7.82%)
  rust           0.07%   2.20%    5.11%   22.81%   42.35%   52.50%   59.29%   65.33%   70.02%
                        (2.13%)  (2.91%) (17.70%) (19.54%) (10.15%)  (6.79%)  (6.04%)  (4.69%)
  glibc          0.02%   7.33%   14.03%   30.86%   42.22%   52.53%   61.59%   68.50%   73.68%
                        (7.31%)  (6.70%) (16.83%) (11.36%) (10.32%)  (9.06%)  (6.91%)  (5.19%)
  gcc            0.00%   0.24%   10.92%   26.61%   39.85%   54.97%   63.80%   69.37%   76.52%
                        (0.24%) (10.68%) (15.69%) (13.24%) (15.13%)  (8.82%)  (5.57%)  (7.14%)
  go             0.00%   0.96%    9.09%   19.35%   39.97%   53.16%   65.31%   72.10%   77.36%
                        (0.95%)  (8.13%) (10.26%) (20.63%) (13.19%) (12.15%)  (6.79%)  (5.26%)
  cmssw          0.15%   0.19%    0.20%    2.43%   45.35%   56.49%   67.58%   73.17%   77.99%
                        (0.03%)  (0.01%)  (2.23%) (42.92%) (11.15%) (11.08%)  (5.59%)  (4.83%)
  linux          0.01%   0.66%    3.97%   23.49%   46.15%   62.97%   72.79%   79.16%   83.57%
                        (0.65%)  (3.30%) (19.52%) (22.66%) (16.82%)  (9.82%)  (6.37%)  (4.41%)
  cpython        3.07%   4.97%   27.73%   59.54%   70.34%   77.48%   81.91%   86.76%   89.34%
                        (1.91%) (22.75%) (31.82%) (10.80%)  (7.13%)  (4.43%)  (4.85%)  (2.59%)
  git            0.11%  27.54%   55.92%   73.79%   81.90%   87.05%   90.28%   92.29%   93.82%
                       (27.43%) (28.38%) (17.87%)  (8.11%)  (5.15%)  (3.23%)  (2.01%)  (1.53%)
  homebrew-cask  0.40%   0.94%   95.41%   97.42%   98.11%   98.40%   98.61%   98.79%   98.93%
                        (0.54%) (94.46%)  (2.01%)  (0.70%)  (0.29%)  (0.21%)  (0.18%)  (0.14%)
  homebrew-core  0.01%   0.07%   98.81%   99.35%   99.56%   99.75%   99.81%   99.84%   99.86%
                        (0.07%) (98.74%)  (0.53%)  (0.22%)  (0.19%)  (0.06%)  (0.03%)  (0.02%)

This saves space, because the Modified Path Bloom Filters chunk will
contain a lot less Bloom filters (albeit those would be rather small
filters).

It reduces the probability of false positives, because all commits
modifying 1-6 paths will have larger than strictly necessary modified
path Bloom filters.

Finally, it makes the Bloom filter query ever so slightly faster,
partly because there is no redirection into the Modified Path Bloom
Filters chunk, and partly because we can check all bit positions in a
63 bit modified path Bloom filter using a 64 bit mask at once, instead
of checking those bit positions one by one, and we can use the same
mask to check all embedded Bloom filters.

The number of paths that can be stored in a 63 bit Bloom filter
depending on the number of hashes per path:

  k     |  3   |  4   |  5  |  6  |  7  |  8  | 9 - 11 | 12 - 14 | 15 - 22 | 23 - 44
  ------+------+------+-----+-----+-----+-----+--------+---------+---------+--------
  paths | <=14 | <=11 | <=8 | <=7 | <=6 | <=5 |  <=4   |   <=3   |   <=2   |   <=1

Hashing scheme
--------------

We need to map each modified path to 'k' independent bit positions in
the Bloom filters bit array.  We want the hash function and hashing
scheme that results in the lowest false positive rate and has the
lowest probability of "colliding" paths (see below), but it should
still be fast to compute, and should be widely available for
alternative Git implementations.

At this point we don't care about the runtime of pathspec-limited
revision walks here.  Lower false positive rate inherently leads to
lower runtime, though we are reaching diminishing returns on common
setups as the false positive rate gets lower and lower... and e.g. in
the webkit repository we'll reach an average false positive rate of
~0.001% with only k = 7 hashes per path.  However, on unusual
setups/configurations accessing tree objects might be considerably
more expensive than accessing commit objects, especially when using
only commit info stored in the commit-graph.  E.g. consider a future
where we can distribute commit-graphs with modified path Bloom filters
to partial clones containing only commit objects for most of the
history: any tree-diff will be really expensive, because the tree
objects must be fetched from the promisor.  In such a setup every
avoidable tree-diff call counts, and low false positive rate is
king.

For now I went with 32 bit MurmurHash3 used in enhanced double hashing
scheme with 32 bit unsigned integer arithmetic, though as I will show
below it seems that this is not the best option.

So, to map each modified path to 'k' bit positions in the Bloom
filter's array we first need 'k' independent hashes.  In general,
hashing a path 'k' times with the same hash function but using 'k'
different seeds produces hashes that are independent enough.  In
practice, to reduce the overhead of hashing, especially for larger 'k'
values, some variant of double hashing is often used to generate the
'k' independent-ish hashes from the results of only two hash function
calls with different seeds.  In general:

  h1 = h(seed1, path)
  h2 = h(seed2, path)
  for (i = 0; i < k; i++)
      pos[i] = (h1 + i * h2 + f(i)) % nr_bits

Depending on how the f(i) term is defined there are a few named
variants:

  - Double hashing: f(1) = 0:

      pos[i] = (h1 + i * h2) % nr_bits

  - Improved double hashing: f(i) adds a simple quadratic term:

      pos[i] = (h1 + i * h2 + i^2) % nr_bits

  - Enhanced double hashing: f(i) adds a not-so-simple cubic term:

      pos[i] = (h1 + i * h2 + (i^3 - i) / 6) % nr_bits

    This cubic term is equal to the following sequence of numbers,
    starting from i = 0:

      0, 0, 1, 4, 10, 20, 35, 56, 84, 120, etc.

    These are almost the same as tetrahedral numbers, except that the
    mathematical definition starts with 1, 4, 10..., while the OEIS
    A000292 sequence starts with 0, 1, 4, 10...

    I'm puzzled by this term being 0 not only for i = 0, but for i = 1
    as well, because this means that if (h2 % nr_bits == 0) (see
    below), then both pos[0] = h1 and pos[1] = h1, IOW in that case
    the path has one less bit set.  We'll take a look at whether
    starting the sequence with a single 0 makes a difference (it does)
    and how that affects the false positive rate (slightly increases
    it overall), and this will be labeled "enhanced double hashing
    variant #1" below.

    This sequence is supposed to be just as good as a simple i^3 term,
    but this can easily be calculated incrementally without
    multiplication, using only addition.  We'll take a look at how a
    simple cubic term affects the false positive rate (it increases
    it), and this will be labeled "enhanced double hashing variant
    #2" below.

These hashing schemes usually work fairly well in practice, but in
practice Bloom filters are primarily used to check whether an element
is part of _one_ _big_ set, and, consequently, most of the wisdom and
experience out there applies to big Bloom filters.

We, however, will repeatedly check whether a particular element (i.e.
path) is part of a large number of mostly very small sets, and our use
case does challenge those best practices.

In our use case it is important when two paths "collide", i.e. when
one path in itself sets all the bit positions that (falsely) indicate
the presence of another path in a modified path Bloom filter, so let's
have a look at that.  And let's hope against hope that I don't mess up
the math...

So, if we have k truly independent hashes for each path, then:

  (1) The probability of two paths mapping to the same k separate bit
      positions in a Bloom filter of size nr_bits is nr_bits! /
      ((nr_bits - k)! * k!).

  (2) The probability of a path setting only a single bit position is
      1 / nr_bits^(k-1), and the probability of a path setting one
      particular bit position is k / nr_bits (assuming that it does
      set k separate bits), so the probability of a path setting a bit
      position that happens to be the only bit position set by an
      other path is k / nr_bits^k.

In case of our 63 bit embedded modified path Bloom filters and k = 7
the probabilities of these two cases are about 1.81 * 10^(-9) and
1.77 * 10^(-12), respectively.  I think that these are low enough not
to worry about.

However, the hashes in the various double hashing schemes are far from
being independent.  When starting out with unsigned 32 bit hashes
(like we'll do) and using 64 bit arithmetic, then there is no integer
overflow, because neither i nor f(i) are large enough for that.  Then,
due to the distributivity of the modulo operation (and because i <
nr_bits), all double hashing schemes are equivalent to:

  pos[i] = (h1 % nr_bits + i * (h2 % nr_bits) + f(i) % nr_bits) % nr_bits

For the above mentioned two colliding cases this means:

  (1) if (h(seed1, "foo") % nr_bits == h(seed1, "bar") % nr_bits &&
          h(seed2, "foo") % nr_bits == h(seed2, "bar") % nr_bits)

      then all double hashing variants will work as if both paths were
      hashed to the same h1 and h2 values, and, consequently, both
      paths will be mapped to the same bit positions.  This has the
      probability of 1 / nr_bits^2.

  (2) if (h2 % nr_bits == 0)

      then the i * h2 term will basically amount to nothing and this
      term can be simplified away, and all bit positions will depend
      only on h1; this has the probability of 1 / nr_bits.

      In case of double hashing the f(i) term is 0 as well, meaning
      that the path maps to a single bit position.  The probability of
      a path setting a bit position that happens to be the only bit
      position set by an other path is k / nr_bits^2.

      The quadratic or cubic f(i) terms in improved or enhanced double
      hashing ensure that a path is mapped to multiple bit positions
      even in this case, though those bit positions are not nearly as
      random as one would like.

In case of 63 bit Bloom filters and k = 7, the probabilities of these
two cases are 1 / 3969 and 1 / 567, respectively.

When using 32 bit unsigned integer arithmetic, then an integer
overflow is definitely possible, so the double hashing formula
becomes:

  pos[i] = (h1 + i * h2 + f(i)) % 2^32 % nr_bits

If nr_bits is a power of two, then the "% 2^32" term can be simplified
away, and we end up with the same formula as with 64 bit arithmetic,
and the probabilities of cases (1) and (2) above remain the same.

If nr_bits is not a power of two, then...  well, I don't offhand know
how to approach that formally :)  Anyway:

  (1) This type of collision seems to occur if that two-liner
      condition above is true and for both paths there is an overflow
      for the same values of i, which has the approximate probability
      of 1 / ((k - 1) * nr_bits^2).

  (2) This type of collision seems to occur if (h2 % nr_bits == 0) and
      there is either no integer overflow for any values of i or if
      there is an overflow for all values of i, which has the
      approximate probability of k / ((k - 1) * nr_bits^2).

In case of 63 bit Bloom filters and k = 7 the probabilities of these
two cases are 1 / 23814 and 1 / 3402, respectively.

There are several other colliding cases, e.g. with double hashing
variants its more probable that a path maps only to 2, 3, etc. bit
positions instead of 'k' than with 'k' truly independent hashes,
though I haven't looked into how the probabilities work out.

Anyway, all the above already shows that:

  - These colliding cases are several orders of magnitude more likely
    with any double hashing variant than with k truly independent hash
    functions.

  - When using some sort of double hashing, then these colliding cases
    can happen with a high enough probability that we can't just
    ignore them.

  - These colliding cases can happen much more frequently with double
    hashing than with improved or enhanced double hashing.

  - Using 64 vs 32 bit arithmetic while calculating various double
    hashing schemes makes a difference, and suggests that 32 bit
    arithmetic has lower false positives probability.

  - Bloom filters whose size is a power of two might have higher false
    positive probability.

All this is important, because there are repositories out there that
modify the same path in the majority of commits, e.g.:

  - homebrew-core: contains 6535 paths, and over 99.5% of commits
    modify the 'Formula' directory and have an embedded modified path
    Bloom filter.

  - homebrew-cask: contains 7307 paths, and over 95.5% of commits
    modify the 'Casks' directory and have an embedded modified path
    Bloom filter.

  - rust: contains 58k+ paths, and almost 93% of commits modify the
    'src' directory, though only over 54% of commits modify that
    directory and have an embedded modified path Bloom filter.

  - tensorflow: contains 47k+ paths, and almost 91% of commits modify
    the 'tensorflow' directory, though only about 51% of commits
    modify that directory and have an embedded modified path Bloom
    filter.

  - go: contains 22k+ paths, and almost 84% of commits modify the
    'src' directory, though only over 50% of commits modify that
    directory and have an embedded modified path Bloom filter.

So e.g. if we were to look for commits modifying a path in the
homebrew-core repository, which happens to map to the same bit
positions in a 63 bit Bloom filter as the 'Formula' directory, then
Boom! we would get over 99.5% false positive rate, effectively
rendering modified path Bloom filters useless for that particular
path.

The table below shows the number of paths that happen to collide with
the repository's frequently modified directory in embedded modified
path Bloom filters using different hash functions and hashing schemes
with 32 bit unsigned integer arithmetic and 64 bit arithmetic (the
latter in parentheses):

                |    Double hashing   |      Enhanced     |      7 seeds
                |                     |   double hashing  |
                |  Murmur3 |  xxHash  | Murmur3 |  xxHash | Murmur3 | xxHash
  --------------+----------+----------+---------+---------+---------+--------
  homebrew-core |  4  (15) |  5  (17) |  0  (0) |  0  (2) |    0    |    0
  homebrew-cask |  2  (21) |  6  (14) |  0  (2) |  1  (1) |    0    |    0
  rust          | 18 (143) | 38 (144) |  1 (15) |  6 (24) |    0    |    0
  tensorflow    | 20 (110) | 18 (105) |  4 (15) |  0 (12) |    0    |    0
  go            |  9  (66) | 12  (62) |  0  (1) |  3  (8) |    0    |    0
  --------------+----------+----------+---------+---------+---------+--------
  all           | 53 (355) | 79 (342) |  5 (33) | 10 (47) |    0         0

The effect of embedded modified path Bloom filters on these colliding
cases can be both beneficial and harmful:

  - We use a larger than necessary Bloom filter to hold 1-6 paths,
    which lowers the probability of these cases considerably.

    This is especially important for the homebrew repositories.  E.g.
    in homebrew-core over 98.6% of commits modify a single file in the
    'Formula' directory, i.e. two paths in total.  To store 2 paths
    using 7 hashes per path we would need a Bloom filter with a 20 bit
    array, which we would round up to 24 bits to use full bytes, i.e.
    those 98.6% of commits would have merely 24 bit Bloom filters.
    This makes those colliding cases all the more probable: 1 / 3456
    for case (1) and 1 / 493.7 for case (2) with 32 bit arithmetic).

  - We use Bloom filters of the same size to hold 1-6 paths, so if a
    path were to run into these cases, then more Bloom filter queries
    would return false positives than when using appropriately sized
    Bloom filters.

Now, there is a simple trick that can, to some extent, alleviate these
collision issues: check all leading directories of the pathspecs, i.e.
while looking for commits modifying 'dir/subdir/file', then query the
modified path Bloom filters not only for the full path, but for all
its leading directories 'dir/subdir' and 'dir' as well.  This way we
would only get a false positive if all bit positions of all leading
directories were set as well, which can significantly reduce the
probability of a pathspec running afoul of these colliding cases, and,
in general, can reduce the false positive rate by an order of
magnitude or three as well (see later in this patch series).

Checking all leading directories is not a silver bullet, though,
because it can only help if the pathspec does actually have leading
directories, and the deeper the pathspec in the directory tree, i.e.
the more leading directories it has, the lower the false positive
rate becomes.

  - So this doesn't help pathspecs in the root tree, because they
    obviously don't have any leading directories.

  - Furthermore, this doesn't help pathspecs that are immediately
    below such a frequently modified directory, because their only
    leading directory is modified in the majority of commits.

    This means that it can't help in the homebrew repositories,
    because 85% or 90% of their paths are directly under their
    frequently modified directories.

The only thing that can help even in these cases is hashing the paths
k times using k different seeds.

Phew.  Let's see some actual benchmarks, shall we?

The following tables in this section show the average false positive
rate of various hash functions and hashing schemes while listing the
histories of "a lot of paths", i.e. 'git rev-list HEAD -- $path'.  A
'*' denotes the lowest value in each row.  All cases use k = 7 hashes
per path, use the same basically random seeds of immense historical
significance, store 6 path in embedded modified path Bloom filters,
and check all leading directories of the given pathspec.

The table below compares the average false positive rate of 64 bit and
32 bit unsigned integer arithmetic using double hashing and enhanced
double hashing with the MurmurHash3 hash function:

                    Double hashing     | Enhanced double hashing
                   32 bit     64 bit   |    32 bit     64 bit
  -------------------------------------+------------------------
  android-base   0.008539%  0.015709%  | *0.004155%  0.004961%
  cmssw          0.006022%  0.013334%  | *0.003953%  0.004109%
  cpython        0.036840%  0.079816%  | *0.016607%  0.019330%
  elasticsearch  0.004069%  0.005297%  |  0.003249% *0.003101%
  gcc            0.016982%  0.034096%  | *0.008919%  0.011152%
  gecko-dev      0.001058%  0.002691%  | *0.000725%  0.000829%
  git            0.144256%  0.331346%  | *0.069921%  0.079405%
  glibc          0.026480%  0.053838%  | *0.016389%  0.017902%
  go             0.021930%  0.050348%  | *0.012616%  0.014178%
  homebrew-cask  0.097523%  0.508175%  | *0.009096%  0.042034%
  homebrew-core  0.120860%  0.556014%  | *0.005360%  0.026810%
  jdk            0.006085%  0.007526%  |  0.006431% *0.005911%
  linux          0.010908%  0.019081%  | *0.007494%  0.007896%
  llvm-project   0.006417%  0.009327%  | *0.003913%  0.004050%
  rails          0.024997%  0.046829%  |  0.013134% *0.012361%
  rust           0.038579%  0.056852%  | *0.025509%  0.027068%
  tensorflow     0.013732%  0.023307%  | *0.008243%  0.008848%
  webkit         0.002212%  0.002950%  | *0.001007%  0.001065%
  -------------------------------------+------------------------
  all            0.028395%  0.110075%  | *0.006085%  0.006675%
  w/o homebrew   0.010940%  0.021286%  | *0.005968%  0.011023%

The 64 bit unsigned arithmetic does indeed fare worse in almost every
case, and significantly worse in the two homebrew repositories.

So it seems that if using some form of double hashing, then 32 bit
unsigned integer arithmetic is the way to go, even though several
programming languages lack support for unsigned types (though thanks
to the distributivity of the modulo operation, they can simply and
cheaply implement it using 64 bit arithmetic and a '& (2^32-1)' mask).

The table below compares the average false positive rate of various
hashing schemes using 32 bit unsigned integer arithmetic and the
MurmurHash3 hash function:

                              Enhanced   Enhanced   Enhanced
                               double     double     double    Improved
                               hashing    hashing    hashing    double     Double
                   7 seeds   (original)  variant 1  variant 2   hashing    hashing
  ---------------------------------------------------------------------------------
  android-base    0.004214%  *0.004155%  0.004853%  0.005193%  0.008252%  0.008539%
  cmssw          *0.003344%   0.003953%  0.003546%  0.004732%  0.004226%  0.006022%
  cpython         0.016120%   0.016607% *0.015896%  0.020259%  0.020311%  0.036840%
  elasticsearch  *0.003167%   0.003249% *0.003164%  0.003531%  0.003553%  0.004069%
  gcc             0.010281%  *0.008919%  0.010359%  0.010642%  0.012166%  0.016982%
  gecko-dev       0.000804%   0.000725% *0.000646% *0.000648%  0.000822%  0.001058%
  git            *0.063025%   0.069921%  0.067643%  0.080744%  0.091423%  0.144256%
  glibc          *0.016278%   0.016389%  0.018660%  0.021094%  0.025596%  0.026480%
  go              0.013009%  *0.012616%  0.013301%  0.014316%  0.016345%  0.021930%
  homebrew-cask  *0.007199%   0.009096%  0.009070%  0.010722%  0.016617%  0.097523%
  homebrew-core  *0.003041%   0.005360%  0.005277%  0.005148%  0.016150%  0.120860%
  jdk             0.005873%   0.006431% *0.005326%  0.005955%  0.006984%  0.006085%
  linux           0.007764%  *0.007494%  0.007714%  0.008709%  0.009429%  0.010908%
  llvm-project   *0.003367%   0.003913%  0.003730%  0.004064%  0.004809%  0.006417%
  rails          *0.012708%   0.013134%  0.013929%  0.016316%  0.014358%  0.024997%
  rust           *0.024245%   0.025509%  0.025045%  0.028204%  0.032491%  0.038579%
  tensorflow     *0.007907%   0.008243%  0.008670%  0.009913%  0.010115%  0.013732%
  webkit         *0.000999%  *0.001007%  0.001142%  0.001113%  0.001274%  0.002212%
  ---------------------------------------------------------------------------------
  all            *0.005646%   0.006085%  0.006226%  0.006928%  0.009264%  0.028395%
  w/o homebrew   *0.005888%   0.005968%  0.006152%  0.006899%  0.007807%  0.010940%

Double hashing and improved double hashing have higher average false
positive rates than enhanced double hashing; note in particular the
significantly higher false positive rate with double hashing in the
two homebrew repositories.  Enhanced double hashing is only slightly
worse than 7 different seeds, at least in this particular case (i.e.
MurmurHash3 and these specific seeds).

Comparing these hashing schemes using a different hash function
(xxHash or FNV1a) shows a similar trend; for brevity I won't include
those tables here.

The table below compares the average false positive rate of different
32 bit hash functions when used in enhanced double hashing scheme with
k = 7 and 32 bit unsigned int arithmetic, or with 7 different seeds:

                     Enhanced double hashing     |             7 seeds             |  7 uint32
                  Murmur3     xxHash     FNV1a   |  Murmur3     xxHash     FNV1a   |   SHA256
  -----------------------------------------------+---------------------------------+-----------
  android-base   0.004155%  0.005556%  0.006113% | 0.004214% *0.004101%  0.005918% | 0.004168%
  cmssw          0.003953%  0.003775%  0.005087% | 0.003344%  0.003677%  0.004353% |*0.003322%
  cpython        0.016607%  0.015919%  0.021957% | 0.016120% *0.015238%  0.023649% | 0.017632%
  elasticsearch  0.003249%  0.003589%  0.004616% | 0.003167%  0.003360%  0.003586% |*0.003027%
  gcc           *0.008919%  0.009376%  0.010555% | 0.010281%  0.009157%  0.011882% | 0.010338%
  gecko-dev      0.000725%  0.000721%  0.000932% | 0.000804% *0.000611%  0.000911% | 0.000737%
  git            0.069921%  0.063449%  0.083097% |*0.063025%  0.069137%  0.087132% | 0.063763%
  glibc          0.016389%  0.017477%  0.024321% | 0.016278% *0.016062%  0.022641% | 0.017241%
  go             0.012616%  0.012449%  0.016728% | 0.013009% *0.011692%  0.017214% | 0.012489%
  homebrew-cask  0.009096%  0.025104%  0.011073% | 0.007199%  0.007343%  0.009037% |*0.007050%
  homebrew-core  0.005360%  0.007940%  0.005450% |*0.003041%  0.003832%  0.004888% | 0.003884%
  jdk            0.006431% *0.005451%  0.007428% | 0.005873%  0.005738%  0.006654% | 0.005749%
  linux         *0.007494%  0.008266%  0.009917% | 0.007764%  0.007723%  0.009256% | 0.007939%
  llvm-project   0.003913%  0.003727%  0.004584% | 0.003367% *0.003247%  0.005115% | 0.003664%
  rails          0.013134%  0.011277%  0.014103% | 0.012708% *0.010389%  0.015928% | 0.012506%
  rust           0.025509%  0.024596%  0.032983% |*0.024245%  0.025697%  0.031593% | 0.024794%
  tensorflow     0.008243%  0.008743%  0.011499% |*0.007907%  0.008089%  0.011922% | 0.008033%
  webkit         0.001007%  0.001155%  0.001401% | 0.000999% *0.000962%  0.001291% | 0.001054%
  -----------------------------------------------+---------------------------------+----------
  all            0.006085%  0.007327%  0.007518% | 0.005646% *0.005554%  0.007591% | 0.005857%
  w/o homebrew   0.005968%  0.005979%  0.007545% | 0.005888% *0.005660%  0.007855% | 0.006039%

MurmurHash3 and xxHash are neck and neck, be it enhanced double
hashing or 7 different seeds, at least when we ignore the unusually
high false positive rate of enhanced double hashing with xxHash in the
homebrew-cask repository (it stumbles upon one of those colliding
cases discussed above).

FNV1a has a decidedly higher average false positive rate than any of
the others.

I was curious to see whether using 7 unsigned integers from SHA256
offers any benefits (being a cryptographic hash function, it should
provide some high quality hash values), but apparently it doesn't fare
any better than MurmurHash3 and xxHash.  This leads me to believe that
both MurmurHash3 and xxHash are as good as it gets, and I would not
expect that any other hash function could achieve notably lower false
positive rates.

Now let's see how these hash functions and hashing schemes fare when
writing commit-graph files with '--reachable' and with modified path
Bloom filters from scratch at the end of this patch series.  Hash
functions tend to praise themselves about how fast they can process
huge chunks of data, but we'll use them to hash many tiny strings...

                         Total runtime of writing a commit-graph file
                         with modified path Bloom filters from scratch
                                    (Time spent hashing)

                     Enhanced double hashing     |             7 seeds             |  7 uint32
                  Murmur3     xxHash     FNV1a   |  Murmur3     xxHash     FNV1a   |   SHA256
  -----------------------------------------------+---------------------------------+----------
  android-base    40.880s    40.368s    40.569s  |  41.375s    40.557s    41.843s  |  42.706s
                  (0.627s)   (0.484s)   (0.777s) |  (1.467s)   (0.886s)   (2.138s) |  (3.682s)
  cmssw           25.691s    25.224s    25.645s  |  26.715s    25.998s    27.762s  |  29.527s
                  (0.894s)   (0.650s)   (1.179s) |  (2.083s)   (1.235s)   (3.259s) |  (5.077s)
  cpython          8.951s     8.929s     9.067s  |   9.072s     9.015s     9.008s  |   9.275s
                  (0.057s)   (0.042s)   (0.045s) |  (0.112s)   (0.067s)   (0.102s) |  (0.324s)
  elasticsearch   14.470s    14.320s    14.703s  |  14.983s    14.588s    15.948s  |  16.720s
                  (0.407s)   (0.300s)   (0.622s) |  (0.991s)   (0.594s)   (1.760s) |  (2.332s)
  gcc             36.917s    36.724s    37.251s  |  37.971s    37.449s    38.178s  |  38.332s
                  (0.313s)   (0.230s)   (0.346s) |  (0.694s)   (0.418s)   (0.919s) |  (1.796s)
  gecko-dev       97.729s    96.791s    97.233s  |  99.215s    97.158s   101.403s  | 105.332s
                  (1.730s)   (1.267s)   (2.099s) |  (3.902s)   (2.344s)   (5.773s) |  (9.553s)
  git              5.245s     5.401s     5.412s  |   5.518s     5.457s     5.474s  |   5.494s
                  (0.022s)   (0.017s)   (0.018s) |  (0.045s)   (0.027s)   (0.040s) |  (0.124s)
  glibc            4.146s     4.156s     4.187s  |   4.267s     4.201s     4.278s  |   4.495s
                  (0.060s)   (0.045s)   (0.057s) |  (0.128s)   (0.079s)   (0.144s) |  (0.331s)
  go               3.565s     3.563s     3.564s  |   3.631s     3.582s     3.607s  |   3.727s
                  (0.040s)   (0.030s)   (0.035s) |  (0.084s)   (0.051s)   (0.084s) |  (0.221s)
  homebrew-cask   29.818s    29.936s    30.279s  |  30.316s    30.435s    29.942s  |  29.939s
                  (0.025s)   (0.020s)   (0.019s) |  (0.049s)   (0.032s)   (0.038s) |  (0.153s)
  homebrew-core   55.478s    55.534s    56.248s  |  56.551s    56.100s    56.445s  |  55.641s
                  (0.031s)   (0.024s)   (0.023s) |  (0.062s)   (0.038s)   (0.047s) |  (0.195s)
  jdk             19.418s    19.151s    20.246s  |  21.270s    20.037s    24.073s  |  25.916s
                  (1.260s)   (0.878s)   (2.105s) |  (3.154s)   (1.833s)   (6.133s) |  (7.732s)
  linux          100.837s   100.130s   101.244s  | 103.775s   101.645s   103.856s  | 109.365s
                  (2.027s)   (1.498s)   (2.030s) |  (4.319s)   (2.682s)   (5.316s) | (11.075s)
  llvm-project    31.188s    31.392s    31.442s  |  31.895s    31.479s    31.984s  |  32.863s
                  (0.334s)   (0.251s)   (0.345s) |  (0.724s)   (0.437s)   (0.895s) |  (1.794s)
  rails            5.607s     5.639s     5.694s  |   5.742s     5.720s     5.865s  |   6.087s
                  (0.084s)   (0.063s)   (0.095s) |  (0.189s)   (0.116s)   (0.252s) |  (0.467s)
  rust            13.250s    13.206s    13.422s  |  13.701s    13.426s    13.680s  |  13.949s
                  (0.163s)   (0.122s)   (0.169s) |  (0.359s)   (0.217s)   (0.440s) |  (0.880s)
  tensorflow      11.808s    11.608s    11.915s  |  12.379s    11.966s    12.860s  |  13.588s
                  (0.368s)   (0.267s)   (0.497s) |  (0.860s)   (0.517s)   (1.369s) |  (2.081s)
  webkit          30.469s    30.735s    30.945s  |  32.005s    31.004s    32.401s  |  33.303s
                  (0.501s)   (0.376s)   (0.733s) |  (1.212s)   (0.725s)   (2.084s) |  (3.044s)

So xxHash is indeed the fastest, even in our use case, and MurmurHash3
comes in second.  The time spent hashing with 7 seeds tends to be
around twice as much as with enhanced double hashing when using the
same hash function.  However, the time spent hashing is only a
fraction of the total runtime, and while its effect on total runtime
is measurable both in best-of-five and average, it tends to be smaller
than run-to-run noise.

As for availability of hash functions:

  - MurmurHash3 is widely available; both the reference implementation
    and a streaming-capable ANSI C implementation is in the public
    domain.

  - xxHash is allegedly available in a variety of programming
    languages, as shown on www.xxhash.com (supposedly, but I haven't
    been able to load that page since months... some cloudflare host
    error persists)

  - SHA256 is widely available, and it must be part of every Git
    implementation in the near future anyway, but it's slower than the
    others, and, more importantly, it doesn't scale for k > 8.

  - FNV1a is so simple that anyone can implement a variant that
    incrementally computes two hashes up to the next directory
    separator in one go in about 20 lines of code (though note that
    the above benchmarks didn't use such an implementation).  Alas,
    because of its higher false positive rate it's out anyway.

Conclusion: we should seriously consider using MurmurHash3 (or xxHash)
and hashing each path k times with k different seeds instead of any
double hashing scheme.

Merges
------

It's not clear whether it's worth computing, storing and using
modified path Bloom filters for all parents of merge commits.

  - The number of paths modified between a merge commit and its
    second..nth parents is in general considerably larger than between
    any commit and its first parent.  E.g. a lot of files are modified
    in Git's master branch while a topic cooks for a few weeks, and
    much more in Linux when a branch started from the previous release
    is merged near the end of the next merge window.

                                 Average number of
                                   modified paths
                    Percentage      compared to:
                     of merge     first    second
                      commits     parent   parent
      --------------------------------------------
      android-base     73.6%       14.1    1553.6
      cmssw            11.0%       16.1     977.4
      cpython          11.7%        5.1     933.7
      elasticsearch     8.4%       40.1     246.5
      gecko-dev         3.5%       23.5     602.0
      git              25.3%        4.0     394.8
      homebrew-cask     9.6%        2.7      42.8
      jdk              25.0%      184.1     408.2
      linux             7.4%       26.1    2268.0
      rails            22.2%        9.6     101.0
      rust             27.0%       15.7     397.3
      tensorflow        9.1%       39.2    1057.4

    Consequently:

      - The tree-diff machinery has to work that much more to gather
        modified paths for all parents of merge commits, significantly
        increasing the runtime of writing the commit-graph file.

      - Storing modified path Bloom filters for all parents of merge
        commits significantly increases the size of the Modified Path
        Bloom Filters chunk, though depending on the percentage of
        merge commits and on the size of the other chunks the relative
        size increase of the whole commit-graph file might not be all
        that much.

      - [TODO: A few old test results suggest that pathspec-limited
        revision walks with default history simplification using a
        commit-graph file storing modified path Bloom filters for all
        merge parents are a few percents slower than when storing
        Bloom filters only for first parents.  Even fewer old test
        results suggest that writing all Bloom filters for first
        parents first, and then all for second..nth parents might
        eliminate much of that runtime difference.
        Definitely need more benchmarking.]

  - During a pathspec-limited revision walk Git's default history
    simplification only checks whether the given path was modified
    between a merge commit and its second..nth parents when the path
    was modified between that merge commit and its first parent.  This
    usually happens rarely, though these second..nth parent diffs tend
    to be more expensive than first parent diffs (because of the
    considerably more modified paths the tree-diff machinery can't
    short-circuit that early).  Anyway, the potential speedup is low.

  - However, with '--full-history', i.e. without any history
    simplification, all merge commits are compared to all their
    parents, and typical additional speedups are in the range of
    2x-3x, while in some cases over 7x or 11x can be achieved by using
    modified path Bloom filters for all parents of merge commits.

Does it worth it?  For me personally it doesn't, but I don't know how
often others use '--full-history' and what trade-offs they might be
willing to make.

So the file format described here adds _optional_ support for storing
modified path Bloom filters for all parents of merge commits, and the
users can make this decision themselves.

[TODO: describe it!]

Deduplication
-------------

Some commits have identical modified path Bloom filters, because they
modify the same set of paths (or because they modify different set of
paths but happen to end up setting the same bit positions in the Bloom
filter).  By omitting duplicates from the Modified Path Bloom Filters
chunk its size can be reduced typically by around 5-20%, and in case
of the android-base repository by over 69%.

Explicitly allow that multiple entries of the Modified Path Bloom
Filter Index chunk can refer to the same offset in the Modified Path
Bloom Filters chunk.  This is important, because even if an
implementation doesn't perform this deduplication while writing the
commit-graph file, it must be prepared for multiple index entries
referring to the same offset in commit-graph file written by a
different implementation.

Modified Path Bloom Filter Excludes
-----------------------------------

Some repositories contain leading directories that are modified in the
great majority of commits, e.g. the homebrew-core repository's
'Formula' directory is modified in over 99.7% of commits, while
homebrew-cask's 'Casks' and rust's 'src' are modified in over 93% of
commits.  And there is 'src/main/java/com/company/division/project' in
convention-following Java projects...

Modified path Bloom filters can't speed up revision walks when the
pathspec is such a frequently modified leading directory, because
because of potential false positives we'll have to run tree-diff for
the majority of commits anyway.  And it doesn't really make sense to
query the history of such a leading directory in practice, because it
will list the majority of commits, so one might as well look straight
at the output of a pathspec-less 'git log'.

However, adding those frequently modified leading directories to the
modified path Bloom filters requires more space and increases the
probability of false positives.

So the file format described here adds support for excluding specific
paths from modified path Bloom filters by listing them in the Modified
Path Bloom Filter Excludes chunk.

[TODO: Figure out the details!]

Limitations
-----------

Because of the possibility of false positives, if a modified path
Bloom filter query returns 'possibly in set', then we have to invoke
tree-diff to make sure that the path in question was indeed modified
by the given commit.  Consequently, Bloom filters can't improve
performance that much when looking for the history of a frequently
modified path, because a lot of tree-diff invocations can't be
eliminated.  In the extreme case when looking for the history of a
path modified in every commit, then using Bloom filters will only add
extra overhead.

A modified path Bloom filter doesn't store the names of modified
paths, it only sets a couple of bits based on those paths' hashes.
Consequently, it can only be used when looking for the history of a
concrete path, and:

  - It can't be used with a pathspec containing wildcards like 'git
    log -- "*.h"'.

    However, it could still be used when the pathspec contains leading
    directories without wildcards, e.g. 'git log --
    "arch/x86/include/*.h", by limiting tree-diff only to commits
    modifying the 'arch/x86/include/' directory.

  - It can't tell which paths were modified by a given commit; for
    that we would still have to run tree-diff for the full tree.

Submodules [TODO]
-----------------

No modified path Bloom filters should be stored for commits modifying
submodules.

This is questionable, but is necessary to produce the same output with
and without modified path Bloom filters.  If 'dir/submod' is a gitlink
file, then currently 'git rev-list HEAD -- dir/submod/whatever' lists
all commits touching 'dir/submod', even when that 'whatever' has never
existed.  And that 'whatever' can be basically anything, so we will
not find them in any of our modified path Bloom filters, therefore in
a Bloom-filter-assisted revision walk we won't list any commits.

The only way around this is to not not write any modified path Bloom
filters for commits modifying submodules.

Note, however, that once upon a time that command wouldn't list
anything, either, but the behavior changed with commit 74b4f7f277
(tree-walk.c: ignore trailing slash on submodule in
tree_entry_interesting(), 2014-01-23) to what we have now.  As
74b4f7f277's log message only talks about handling 'dir/submod/' and
'dir/submod' (i.e. with and without trailing slash) consistently, I
suspect that this behavior change with 'dir/submod/anything' is an
unintended and undesired side effect.  However, as it involves
submodules I would rather not have an opinion :)

In any case, someone with more clues about submodules should take a
closer look and decide whether this is a bug or not, before this
modified path Bloom filter thing goes much further.  If it is a bug
indeed, then it should be fixed and the remark about submodules should
be removed from the modified path Bloom filter specs.  If the current
behavior is desired, then the remark about submodules should be
updated to use proper English (IMO it must be part of the spec,
because this is a subtle issue that developers of other
implementations (JGit, libgit2, etc.) might easily overlook).

Threats to validity
-------------------

  - Random paths are... random.  Picking random paths can
    over-represent rarely modified files.  Since modified path Bloom
    filters bring more benefits to rarely modified paths, the reported
    speedups later in the series might be higher than what the users
    will usually see.  (I suppose that users more often check the logs
    of frequently modified files than of rarely modified ones.)

    Though some of these random paths made me stumble upon the issue
    with submodules discussed above, so...

  - Bugs :)  It's not that hard to make subtle bugs that don't affect
    correctness, because the probabilistic nature of Bloom filters
    cover them up.  However, bugs like incorrectly calculating the
    size of a Bloom filter or having an off-by-one error in the
    filter's array handling affect the false positive rate and in turn
    the runtime of pathspec-limited revision walks.

Alternatives considered
-----------------------

Here are some alternatives that I've considered but discarded and
ideas that I haven't (yet) followed through:

  - One Bloom filter to rule them all?  No.

    While the first proof of concept implementation [2] demonstrated
    that by combining hashes of modified pathnames with commit and
    parent object ids it is possible to use a single big Bloom filter
    and achieve notable speedups, that approach has several drawbacks:

      - Poor locality: The bit positions that are set for any element
        are supposed to be random, so we need to access random parts
        of the big Bloom filter array for each checked commit and
        path, which is bad for the caches.  Furthermore, we would
        likely need to read the whole big Bloom filter array even when
        looking for only a handful of commits, e.g. for 'git log -3 --
        dir/file'.

      - Need to grow: As the repository grows, more and more paths
        will be added to the modified path Bloom filter, thus lowering
        its false positive rate.  Eventually we'll reach a point where
        we would need to increase the size of the Bloom filter, but a
        Bloom filter can't be resized, so we'll have to create a
        larger Bloom filter and re-fill it from scratch.  This is a
        considerably more expensive operation than creating a
        modified-path-Bloom-filter-less commit-graph from scratch.

      - Expired commits: Unreachable commits are eventually pruned by
        'git gc', but elements can't be removed from a Bloom filter.
        Consequently, all the bits set for paths modified by expired
        commits will remain set, slightly increasing the probability
        of false positives until the Bloom filter is eventually
        resized/rewritten.  There are enhanced Bloom filter variants
        that allow removal of elements, like a counting Bloom filter,
        but they come with additional complexity and require
        considerably more space.

      - Excluded commits: Sometimes we can't or just don't want to
        record the paths modified by a particular commit, so we need a
        way to record which commits don't have entries in the big
        Bloom filter.

      - There are plans for split commit-graph files, because
        rewriting the whole commit-graph file in big repositories to
        add only relatively few new commits seems to impose
        considerable overhead.  We would need a big modified path
        Bloom filter in each of the split commit-graph files that
        we'll combine together when the split commit-graph files are
        combined.  Bloom filters of the same size can be quickly
        combined by bitwise OR-ing their arrays, but this implies that
        the split commit-graph files holding only a few commits would
        have to contain as large a Bloom filter as is used in the
        shared commit-graph file holding most of the commits in the
        repository, wasting valuable storage space.  (Though the false
        positive rate for commits stored in the split commit-graph
        should be spectacularly low).

    Using a small Bloom filter for each commit avoids these issues,
    though, as discussed earlier, not without introducing issues of
    its own.

  - Xor filters "are a faster and more concise alternative to Bloom
    filters", but they turned out to be too large in our use case.

    Each Xor filter consists of a header and an array: the header
    contains a 64 bit seed and a 64 bit blocklength, while the array
    contains 3 * blocklength bytes.  Consequently, the space advantage
    of Xor filters compared to Bloom filters is only true for large
    filters, where the header's size is negligible compared to the
    array's size.  We, however, have a lot of very small filters, and
    all those extra headers cause an unacceptable size increase
    (partly because the Xor filter's header is 4 times the size of the
    header of our modified path Bloom filters, and partly because
    their headers make Xor filters too large to be embedded in the
    index chunk).

                     MPBF chunk      Total
                        size       Xor Filter
                     (no dedup)       size
      ------------------------------------------------
      android-base     8620198      28840220     +334%
      cmssw           10347018      21538283     +208%
      cpython           526381       6393731    +1214%
      elasticsearch    4733274       9101088     +192%
      gcc              3724544      14637474     +393%
      gecko-dev       20591010      56887518     +276%
      git               160718       3115827    +1938%
      glibc             759132       3162898     +416%
      go                458375       2676306     +584%
      homebrew-cask      94383       5272317    +5586%
      homebrew-core      27823       8051585   +28938%
      jdk             13213208      15574498     +117%
      linux           26575278      69577374     +261%
      llvm-project     3988133      20235803     +507%
      rails             958691       5172643     +539%
      rust             1985782       7082949     +356%
      tensorflow       4173570       8333062     +200%
      webkit           5891751      15927504     +270%

    https://github.com/FastFilter/xor_singleheader

  - fastrange is "a fast alternative to the modulo reduction", but it
    turned out to significantly increase the average false positive
    rate when using (enhanced) double hashing.

    The traditional way to fairly map an integer value to the range
    [0,m) is the modulo reduction, i.e. 'h % m'.  Alas, integer
    division is a costly instruction, and we have to do it a lot while
    checking modified path Bloom filters for every commit.  Fastrange
    proposes to use the combination of an integer multiplication and a
    shift as: '((uint64_t)h * (uint64_t)m) >> 32', as it is supposed
    to be faster while being just as fair.

    In my benchmarks fastrange did indeed reduce the time spent
    checking modified path Bloom filters by up to ~10% (no table about
    this), though that's usually only a fraction of the total runtime
    of a pathspec-limited revision walk.  Unfortunately, as the table
    below shows, it also increased the average false positive rate by
    about 5x when using enhanced double hashing.  I haven't yet
    investigated why this happens.  However, fastrange is a viable
    option when using the same hash function with 'k' different seeds,
    as in that case it's on par with the good old % operator, and in
    fact its false positive rate happens to be slightly lower.

                           Enhanced        |
                        double hashing     |        7 seeds
                                           |
                    % operator  fastrange  | % operator  fastrange
      -------------------------------------+----------------------
      android-base  *0.004155%  0.013987%  |  0.004214%  0.004873%
      cmssw          0.003953%  0.006129%  | *0.003344%  0.005513%
      cpython        0.016607%  0.033979%  | *0.016120%  0.018069%
      elasticsearch  0.003249% *0.003149%  |  0.003167%  0.003333%
      gcc            0.008919%  0.013098%  |  0.010281% *0.007324%
      gecko-dev      0.000725%  0.000923%  |  0.000804% *0.000631%
      git            0.069921%  0.106424%  | *0.063025%  0.065347%
      glibc          0.016389%  0.025323%  | *0.016278%  0.016796%
      go            *0.012616%  0.020914%  |  0.013009%  0.012915%
      homebrew-cask  0.009096%  0.182016%  |  0.007199% *0.006937%
      homebrew-core  0.005360%  0.092957%  | *0.003041%  0.004251%
      jdk            0.006431%  0.005732%  |  0.005873% *0.005673%
      linux          0.007494%  0.013862%  |  0.007764% *0.007127%
      llvm-project   0.003913%  0.004829%  |  0.003367% *0.002943%
      rails          0.013134%  0.019524%  | *0.012708%  0.012979%
      rust           0.025509%  0.029824%  | *0.024245%  0.025174%
      tensorflow     0.008243%  0.012485%  | *0.007907%  0.008120%
      webkit        *0.001007%  0.001044%  | *0.000999%  0.001220%
      -------------------------------------+----------------------
      all            0.006085%  0.029034%  |  0.005646% *0.005579%
      w/o homebrew   0.005968%  0.009478%  |  0.005888% *0.005662%

    https://github.com/lemire/fastrange

  - fastmod "is a header file for fast 32-bit division remainders on
    64-bit hardware", promising faster computation when the same
    divisor is (re)used for multiple remainder calculations.  This is
    exactly what we are doing when checking a modified path Bloom
    filter, as we have to map a bunch of unsigned 32 bit hash values
    to bit positions with pos = hash % nr_bits, using the same nr_bits
    for all hash values.

    However, benchmarking has not shown conclusive improvements: while
    fastmod slightly reduces the time spent checking modified path
    Bloom filters in some repositories, it slightly increases in
    others, and any effect on the runtime of the whole
    pathspec-limited revision walk is below the noise.  Perhaps we
    have too many "embedded" modified path Bloom filters that we can
    check with a mask.  Or perhaps my CPU is too old and its integer
    multiplication instruction is not that much faster compared to
    integer division.

    https://github.com/lemire/fastmod

  - Varints.  Using 4 bytes for the size of each Bloom filter in the
    Modified Path Bloom Filters chunk is a lot more than necessary.
    How much space can be saved by using varints?  How much is the
    runtime overhead of decoding those varints?  How can we ensure
    that varint decoding doesn't read past the end of the mmapped
    memory region?

  - Path-depth-dependent number of hash functions.
    As shown later in this patch series, we can drastically reduce the
    average false positive rate by checking the presence of the
    pathspec's leading directories as well.  With that change the
    false positive rate will depend on the depth of the path in the
    directory tree as well: the deeper the path (i.e. the more leading
    directories can be checked), the lower the false positive rate,
    sometimes maybe even unnecessarily low (0% is not an
    approximation, but there was not a single false positive, though
    the number of checked paths at those depths is quite low):

                     linux.git                  webkit.git

               Number of                    Number of
      Path      checked   Average false      checked   Average false
      depth    paths at   positive rate     paths at   positive rate
      depth   that depth  at that depth    that depth  at that depth
      --------------------------------------------------------------
        1           2      0.31974050%          0       n/a
        2          97      0.06539501%         16       0.04927891%
        3        1052      0.01782569%        176       0.00472128%
        4        1674      0.00396338%        586       0.00399830%
        5        1315      0.00350913%        775       0.00089653%
        6         548      0.00149110%       1396       0.00025000%
        7         113      0.00057555%       1004       0.00004777%
        8         124      0.00085726%        397       0.00001380%
        9          34      0.00025182%        311       0.00001468%
       10          14      0%                 250       0.00000182%
       11           8      0%                  45       0%
       12          19      0%                  39       0%
       13           0      n/a                  3       0%
       14           0      n/a                  1       0%
       15           0      n/a                  1       0%
      --------------------------------------------------------------
      all        5000      0.007607%         5000       0.001012%

    So we could use fewer hashes when adding deep paths to modified
    path Bloom filters, saving same space while still achieving quite
    low false positive rate.  Or when aiming for consistently lower
    false positive rate, then we could use more hashes only for
    shallower paths.

[1] The repositories used in the above benchmarks are:

    android-base:
      https://android.googlesource.com/platform/frameworks/base
    cmssw:
      https://github.com/cms-sw/cmssw
    cpython:
      https://github.com/python/cpython
    elasticsearch:
      https://github.com/elastic/elasticsearch
    gcc:
      git://gcc.gnu.org/git/gcc.git
    gecko-dev:
      https://github.com/mozilla/gecko-dev
    git:
      https://git.kernel.org/pub/scm/git/git.git
    glibc:
      git://sourceware.org/git/glibc.git
    go:
      https://github.com/golang/go
    homebrew-cask:
      https://github.com/homebrew/homebrew-cask
    homebrew-core:
      https://github.com/homebrew/homebrew-core
    jdk:
      https://github.com/openjdk/jdk
    linux:
      https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
    llvm-project:
      https://github.com/llvm/llvm-project.git
    rails:
      https://github.com/rails/rails
    rust:
      https://github.com/rust-lang/rust
    tensorflow:
      https://github.com/tensorflow/tensorflow
    webkit:
      git://git.webkit.org/WebKit.git

[2] First PoC Bloom filter experiment:
    https://public-inbox.org/git/20181009193445.21908-1-szeder.dev@gmail.com/

Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
 .../technical/commit-graph-format.txt         | 125 ++++++++++++++++++
 1 file changed, 125 insertions(+)

diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt
index efd0f99d8b..6b041f94ee 100644
--- a/Documentation/technical/commit-graph-format.txt
+++ b/Documentation/technical/commit-graph-format.txt
@@ -99,6 +99,131 @@ CHUNK DATA:
       file's OID Lookup chunk is equal to i plus the number of commits in all
       base graphs.  If B is non-zero, this chunk must exist.
 
+  Modified Path Bloom Filter Index (ID: {'M', 'P', 'B', 'I'}) [Optional]
+    2 + (N * 8) bytes
+
+    * 1-byte number (K) of hashes per path
+
+    * An array of 8 byte entries, one for each N commits stored in the
+      commit-graph, with the ith entry associated to the ith commit in the
+      OID Lookup chunk.
+      Each entry should be interpreted as follows:
+
+      - If all bits in the 8 bytes are set, then there is no modified path
+	Bloom filter stored for this commit.
+
+	Thou shalt not store a modified path Bloom filter for a commit that
+	modifies a submodule (gitlink file)!
+
+      - If the most significant bit of the first byte is set, then the
+	remaining 63 bits represent the bit array of an "embedded" Bloom
+	filter containing the set of paths that were modified between the
+	associated commit and its first parent, or in case of a root commit
+	between the associated commit and the empty tree.  All embedded
+	modified path Bloom filters use the same hashing scheme that is
+	used in the Modified Path Bloom Filters chunk, see below.
+
+      - If the second most significant bit of the first byte is set, then
+	the last four bytes form an array position into the Modified Path
+	Bloom Filter Merge Index chunk.  The remaining bits in the first
+	four bytes should be set to 0.  This can optionally be used to
+	store Bloom filters for all parents of merge commits.
+	[TODO: Only the last four bytes?  Shouldn't that be last 62 bits?!]
+
+      - If the two most significant bits of the first byte are unset, then
+	the entry represents an 8 byte offset pointing to a Bloom filter
+	in the Modified Path Bloom Filters chunk, which contains the set
+	of paths that were modified between the associated commit and its
+	first parent, or in case of a root commit between the associated
+	commit and the empty tree.  This offset is relative to the start
+	of the Modified Path Bloom Filters chunk.  Multiple entries can
+	point to the same offset.
+
+  Modified Path Bloom Filter Merge Index (ID: {'M', 'P', 'B', 'M'}) [Optional]
+      An array of 8 byte entries.
+      If a merge commit's entry in the Modified Path Bloom Filter Index
+      chunk stores an array position into this chunk, then the entry at
+      that position is associated with that merge commit and its first
+      parent, the next entry with that merge commit and its second parent,
+      etc. for all parents of that merge commit.
+
+      Each entry should be interpreted as follows, similar to the entries
+      in the Modified Path Bloom Filter Index chunk:
+
+      - If all bits in the 8 bytes are set, then there is no modified path
+	Bloom filter stored for the associated merge commit and its
+	corresponding parent.
+
+      - If the MSB of the first byte is set, then the remaining 63 bits
+	represent the bit array of an "embedded" Bloom filter containing
+	the set of paths that were modified between the associated merge
+	commit and its corresponding parent.  All embedded modified path
+	Bloom filters use the same hashing scheme that is used in the
+	Modified Path Bloom Filters chunk, see below.
+
+      - If the most significant bit of the first byte is unset, then the
+	entry represents an 8 byte offset pointing to a Bloom filter in
+	the Modified Path Bloom Filters chunk, which contains the set of
+	paths that were modified between the associated merge commit and
+	its corresponding parent.  This offset is relative to the start of
+	the Modified Path Bloom Filters chunk.  Multiple entries can point
+	to the same offset.
+
+      This chunk should not exist if the commit-graph file doesn't contain
+      a Modified Path Bloom Filter Index chunk.  This chunk can be omitted
+      if the Modified Path Bloom Filter Index doesn't contain any array
+      indexes pointing into it.  This chunk can be omitted even when the
+      commit-graph contains merge commits.
+
+  Modified Path Bloom Filters (ID: {'M', 'P', 'B', 'F'}) [Optional]
+      A number of consecuive modified path Bloom filters of varying sizes.
+      Each Bloom filter consists of 4 + M bytes:
+
+      - The first 4 bytes specify the number of m bits in the Bloom
+	filter's bit array.
+
+      - The next M bytes hold the Bloom filter's bit array of m bits.
+
+      The bits in the array are indexed in network byte order, i.e. the
+      array's 0th bit is the least significant bit of the last byte, and
+      the (m-1)th bit is in the first byte.  If m is not a multiple of 8,
+      then the unused leading bits should be set to 0.
+
+      For each path (including leading directories) modified between a
+      commit and its parent K bit positions should be set using the
+      following hashing scheme:
+
+	for i in [0, K)
+	  bit_pos[i] = (hash1 + i * hash2 + (i * i * i - i) / 6) % m
+
+      where hash1 and hash2 are the 32 bit MurmurHash3 hashes of the path
+      with seeds 0xe83c5163 and 0x3b376b0c, respectively.  These bit
+      positions should be calculated using 32 bit unsigned integer
+      arithmetic.  The directory separator is a single '/'.  Directories
+      should be added without a trailing '/'.
+
+      The order of Bloom filters in this chunk is unspecified.  Multiple
+      entries in the Modified Path Bloom Filter Index or Modified Path
+      Bloom Filter Merge Index chunks can point to the same Bloom filter
+      in this chunk.
+
+      This chunk should not exist if the commit-graph doesn't contain a
+      Modified Path Bloom Filter Index chunk.  This chunk can be omitted
+      if neither the Modified Path Bloom Filter Index nor the Modified
+      Path Bloom Filter Merge Index chunks contain any offsets pointing
+      into it.
+
+  Modified Path Bloom Filter Excludes (ID: {'M', 'P', 'B', 'X'}) [Optional]
+      A number of consecutive null terminated strings in memcmp() order.
+      Paths in these strings should not be added to any modified path
+      Bloom filters.
+      [TODO: Clarify!  Only literal matches, or should we support
+      globbing/patterns as well?  Only full match, or leading directories
+      as well?]
+
+      This chunk should not exist if the commit-graph doesn't contain a
+      Modified Path Bloom Filter Index chunk.
+
 TRAILER:
 
 	H-byte HASH-checksum of all of the above.
-- 
2.27.0.rc1.431.g5c813f95dc


  parent reply index

Thread overview: 43+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-05-29  8:50 [PoC PATCH 00/34] An alternative modified path Bloom filters implementation SZEDER Gábor
2020-05-28 22:09 ` Johannes Schindelin
2020-05-29  8:50 ` [PATCH 01/34] tree-walk.c: don't match submodule entries for 'submod/anything' SZEDER Gábor
2020-05-29  8:50 ` [PATCH 02/34] commit-graph: fix parsing the Chunk Lookup table SZEDER Gábor
2020-05-29  8:50 ` [PATCH 03/34] commit-graph-format.txt: all multi-byte numbers are in network byte order SZEDER Gábor
2020-05-29  8:50 ` [PATCH 04/34] commit-slab: add a function to deep free entries on the slab SZEDER Gábor
2020-06-04 16:43   ` Derrick Stolee
2020-06-27 15:56     ` SZEDER Gábor
2020-06-29 11:30       ` Derrick Stolee
2020-05-29  8:50 ` [PATCH 05/34] diff.h: drop diff_tree_oid() & friends' return value SZEDER Gábor
2020-05-29  8:50 ` [PATCH 06/34] commit-graph: clean up #includes SZEDER Gábor
2020-05-29  8:50 ` [PATCH 07/34] commit-graph: simplify parse_commit_graph() #1 SZEDER Gábor
2020-05-29  8:50 ` [PATCH 08/34] commit-graph: simplify parse_commit_graph() #2 SZEDER Gábor
2020-05-29  8:50 ` [PATCH 09/34] commit-graph: simplify write_commit_graph_file() #1 SZEDER Gábor
2020-05-29  8:50 ` [PATCH 10/34] commit-graph: simplify write_commit_graph_file() #2 SZEDER Gábor
2020-05-29  8:50 ` [PATCH 11/34] commit-graph: allocate the 'struct chunk_info' array dinamically SZEDER Gábor
2020-05-29  8:50 ` [PATCH 12/34] commit-graph: unify the signatures of all write_graph_chunk_*() functions SZEDER Gábor
2020-05-29  8:50 ` [PATCH 13/34] commit-graph: simplify write_commit_graph_file() #3 SZEDER Gábor
2020-05-29  8:50 ` [PATCH 14/34] commit-graph: check chunk sizes after writing SZEDER Gábor
2020-05-29  8:50 ` SZEDER Gábor [this message]
2020-06-02 17:59   ` [PATCH 15/34] commit-graph-format.txt: document the modified path Bloom filter chunks SZEDER Gábor
2020-05-29  8:50 ` [PATCH 16/34] Add a generic and minimal Bloom filter implementation SZEDER Gábor
2020-05-29  8:50 ` [PATCH 17/34] Import a streaming-capable Murmur3 hash function implementation SZEDER Gábor
2020-05-29  8:50 ` [PATCH 18/34] commit-graph: write "empty" Modified Path Bloom Filter Index chunk SZEDER Gábor
2020-05-29  8:50 ` [PATCH 19/34] commit-graph: add commit slab for modified path Bloom filters SZEDER Gábor
2020-05-29  8:50 ` [PATCH 20/34] commit-graph: fill the Modified Path Bloom Filter Index chunk SZEDER Gábor
2020-05-29  8:50 ` [PATCH 21/34] commit-graph: load and use " SZEDER Gábor
2020-05-29  8:50 ` [PATCH 22/34] commit-graph: write the Modified Path Bloom Filters chunk SZEDER Gábor
2020-05-29  8:50 ` [PATCH 23/34] commit-graph: load and use " SZEDER Gábor
2020-05-29  8:50 ` [PATCH 24/34] commit-graph: check all leading directories in modified path Bloom filters SZEDER Gábor
2020-05-29  8:50 ` [PATCH 25/34] commit-graph: check embedded modified path Bloom filters with a mask SZEDER Gábor
2020-05-29  8:50 ` [PATCH 26/34] commit-graph: deduplicate modified path Bloom filters SZEDER Gábor
2020-05-29  8:50 ` [PATCH 27/34] commit-graph: load modified path Bloom filters for merge commits SZEDER Gábor
2020-05-29  8:50 ` [PATCH 28/34] commit-graph: write Modified Path Bloom Filter Merge Index chunk SZEDER Gábor
2020-05-29  8:50 ` [PATCH 29/34] commit-graph: extract init and free write_commit_graph_context SZEDER Gábor
2020-05-29  8:50 ` [PATCH 30/34] commit-graph: move write_commit_graph_reachable below write_commit_graph SZEDER Gábor
2020-05-29  8:50 ` [PATCH 31/34] t7007-show: make the first test compatible with the next patch SZEDER Gábor
2020-05-29  8:50 ` [PATCH 32/34] PoC commit-graph: use revision walk machinery for '--reachable' SZEDER Gábor
2020-05-29  8:50 ` [PATCH 33/34] commit-graph: write modified path Bloom filters in "history order" SZEDER Gábor
2020-05-29  8:50 ` [PATCH 34/34] commit-graph: use modified path Bloom filters with wildcards, if possible SZEDER Gábor
2020-05-29 13:59 ` [PoC PATCH 00/34] An alternative modified path Bloom filters implementation Derrick Stolee
2020-06-01 23:25 ` Taylor Blau
2020-06-02 17:08   ` Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200529085038.26008-16-szeder.dev@gmail.com \
    --to=szeder.dev@gmail.com \
    --cc=garima.singh@microsoft.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=jnareb@gmail.com \
    --cc=me@ttaylorr.com \
    --cc=peff@peff.net \
    --cc=stolee@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Git Mailing List Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/git/0 git/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 git git/ https://lore.kernel.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.git


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git