Subject: Re: [PATCH 0/9] [RFC] Changed Paths Bloom Filters

From: Emily Shaffer <[email-masked]>
Date: Tue, 21 Jan 2020 15:40:55 -0800

Hi,

On Fri, Dec 20, 2019 at 10:05:11PM +0000, Garima Singh via GitGitGadget wrote:
> This series is intended to start the conversation and many of the commit
> messages include specific call outs for suggestions and thoughts. 

Since it's mostly in RFC stage, I'm holding off on line by line comments
for now. I read the series (thanks for your patience) and I'll try to
leave some review thoughts in the diffspec here.

> Garima Singh (9):
>   [1/9] commit-graph: add --changed-paths option to write
I wonder if this can be combined with 2; without 2 actually the
documentation is wrong for this one, right? Although I suppose you also
mentioned 2 perhaps being too long :)

>   [2/9] commit-graph: write changed paths bloom filters
As I understand it, this one always regenerates the bloom filter pieces,
and doesn't write it down in the commit-graph file. How much longer does
that take now than before? I don't have a great feel for how often 'git
commit-graph' is run, or whether I need to be invoking it manually.

>   [3/9] commit-graph: use MAX_NUM_CHUNKS
>   [4/9] commit-graph: document bloom filter format
I suppose I might like to see this commit squashed with 5, but it's a
nit. I'm thinking it'd be handy to say "git blame commit-graph" and see
some nice doc about the format expected in the commit-graph file.

>   [5/9] commit-graph: write changed path bloom filters to commit-graph file.
Ah, so here we finally write down the result from 2 to disk in the
commit-graph file. And without 7, this gets recalculated every time we
call 'git commit-graph' still.

As for a technical doc around here, I'd really appreciate one. But I'm
speaking selfishly - I'd also be happy if I could watch a talk about
this design to make sure I understand it right :)

>   [6/9] commit-graph: test commit-graph write --changed-paths
>   [7/9] commit-graph: reuse existing bloom filters during write.
I saw an option to give up if there wasn't an existing bloom filter, but
I didn't see an option here to force recalculating. Is there a scenario
when that would be useful? What's the mitigation path if:
 - I have a commit-graph with v0 of the bloom index piece, but update to
   Git which uses v1?
 - My commit-graph file is corrupted in a way that the bloom filter
   results are incorrect and I am missing a blob change (and therefore
   not finding it during the walk)?
I think I understand that without this commit, 8 is not much speedup
because we will be recalculating the filter for each commit, rather than
using the written-down commit-graph file.

>   [8/9] revision.c: use bloom filters to speed up path based revision walks
>   [9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag

Speaking of making sure I understand the change right, I will also
summarize my own understanding in the hopes that I can be corrected and
others can learn too ;)

 - The general idea is that we can write down a hint at the tree level
   saying "something I own did change this commit"; when we look for an
   object later, we can skip the commit where it looks like that path
   didn't change.
 - The change is in two pieces: first, to generate the hints per tree
   (which happens during commit-graph); second, to use those hints to
   optimize a rev walk (which happens in revision.c patch 8)
 - When we calculate the hints during commit-graph, we check the diff of
   each tree compared to its recent ancestor to see if there was a
   change; if so we calculate a hash for each path and use that as a key
   for a map from hash to path. After we look through everything changed
   in the diff, we can add it to a cumulative bloom filter list (one
   filter per commit) so we have a handy in-memory idea of which paths
   changed in each commit.
 - When it's time to do the rev walk, we ask for the bloom filter for
   each commit and check if that commit's map contains the path to the
   object we're worried about; if so, then it's OK to unpack the tree
   and check if the path we are interested in actually did get changed
   during that commit.

Thanks.
 - Emily

> 
>  Documentation/git-commit-graph.txt            |   5 +
>  .../technical/commit-graph-format.txt         |  17 ++
>  Makefile                                      |   1 +
>  bloom.c                                       | 257 +++++++++++++++++
>  bloom.h                                       |  51 ++++
>  builtin/commit-graph.c                        |   9 +-
>  ci/run-build-and-tests.sh                     |   1 +
>  commit-graph.c                                | 116 +++++++-
>  commit-graph.h                                |   9 +-
>  revision.c                                    |  67 ++++-
>  revision.h                                    |   5 +
>  t/README                                      |   3 +
>  t/helper/test-read-graph.c                    |   4 +
>  t/t4216-log-bloom.sh                          |  77 ++++++
>  t/t5318-commit-graph.sh                       |   2 +
>  t/t5324-split-commit-graph.sh                 |   1 +
>  t/t5325-commit-graph-bloom.sh                 | 258 ++++++++++++++++++
>  17 files changed, 875 insertions(+), 8 deletions(-)
>  create mode 100644 bloom.c
>  create mode 100644 bloom.h
>  create mode 100755 t/t4216-log-bloom.sh
>  create mode 100755 t/t5325-commit-graph-bloom.sh
> 
> 
> base-commit: b02fd2accad4d48078671adf38fe5b5976d77304
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-497%2Fgarimasi514%2FcoreGit-bloomFilters-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-497/garimasi514/coreGit-bloomFilters-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/497
> -- 
> gitgitgadget