Re: [PATCH v2 00/11] Changed Paths Bloom Filters

From: Garima Singh <garimasigit@gmail.com>
Date: Feb 21, 2020, 17:41 UTC
Message-ID: <fdcbd793-57c2-f5ea-ccb9-cf34e911b669@gmail.com>
In-Reply-To: <86a75swuie.fsf@gmail.com>

On 2/8/2020 6:04 PM, Jakub Narebski wrote:

Show 27 quoted lines

> "Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> Hey! 
>>
>> The commit graph feature brought in a lot of performance improvements across
>> multiple commands. However, file based history continues to be a performance
>> pain point, especially in large repositories. 
>>
>> Adopting changed path Bloom filters has been discussed on the list before,
>> and a prototype version was worked on by SZEDER Gábor, Jonathan Tan and Dr.
>> Derrick Stolee [1]. This series is based on Dr. Stolee's proof of
>> concept in [2].
> 
> Sidenote: I wondered why it did use MurmurHash3 (64-bit version), which
> requires adding its implementation, instead of reusing FNV-1 hash
> (Fowler–Noll–Vo hash function) used by Git hashmap implementation, see
> https://github.com/git/git/blob/228f53135a4a41a37b6be8e4d6e2b6153db4a8ed/hashmap.h#L109
> Beside the fact that everyone is using MurmurHash for Bloom filters ;-)
> 
> It turns out that in various benchmark MurmurHash is faster and also
> slightly better as a hash than FNV-1 or FNV-1b.
> 
> 
> I wonder then if it would be a good idea (in the future) to make it easy
> to use hashmap with MurmurHash3 instead of FNV-1, or maybe to even make
> it the default for hashing strings.
>

Making Murmur3 hash the default for hashing strings is definitely outside the scope of this series. Also, if the method signatures for the murmur3 hash matched the existing hash method signatures in hashmap.c, then it would be appropriate to place them adjacently, even if no hashmap consumer uses it for hashmaps. However, we need the option to start at a custom seed to do our double hashing. A change in the future that involves adopting murmur3 in the hashmap code would involve a simple code move before creating the new methods that avoid a custom seed. So for now, it makes sense that these methods leave in bloom.c where they are being used for a very specific purpose.

Show 14 quoted lines

>>
>> Performance Gains: We tested the performance of git log -- path on the git
>> repo, the linux repo and some internal large repos, with a variety of paths
>> of varying depths.
> 
> As I wrote in reply to previous version of this series, a good public
> repository (and thus being able to use by anyone) to test the Bloom
> filter performance improvements could be AOSP (Android) base:
> 
>   https://android.googlesource.com/platform/frameworks/base/
> 
> which is a large repository with long path depths (due to Java file
> naming conventions).
>

Thank you! I will incorporate these results into the commit messages as appropriate in v3.

Show 12 quoted lines

>>
>> On the git and linux repos: We observed a 2x to 5x speed up.
>>
>> On a large internal repo with files seated 6-10 levels deep in the tree: We
>> observed 10x to 20x speed ups, with some paths going up to 28 times faster.
> 
> Very nice! Good work!
> 
> What is the cost of this feature, that is how long it takes to generate
> Bloom filters, and how much larger commit-graph file gets?  It would be
> nice to know.
>

The cost of writing is much better now with Peff and Dr. Stolee's improvements. I will include these numbers as well in the commit messages as appropriate in v3.

Show 10 quoted lines

>>
>> Future Work (not included in the scope of this series):
>>
>>  1. Supporting multiple path based revision walk
> 
> Shouldn't then tests that were added in v2 mark use of Bloom filters
> with multiple paths revision walking as _not working *yet*_
> (test_expect_failure), and not expected to not work (test_expect_success
> with test_bloom_filters_not_used)?
>

My intent is to ensure that bloom filters are not being used in any of the unsupported code paths. I don't have a strong preference about the test semantics as long as I get that coverage :) So I will look into switching it to test_expect_failure as you have suggested.

Show 21 quoted lines

>> Derrick Stolee (2):
>>   diff: halt tree-diff early after max_changes
>>   commit-graph: examine commits by generation number
>>
>> Garima Singh (8):
>>   commit-graph: use MAX_NUM_CHUNKS
>>   bloom: core Bloom filter implementation for changed paths
>>   commit-graph: compute Bloom filters for changed paths
>>   commit-graph: write Bloom filters to commit graph file
>>   commit-graph: reuse existing Bloom filters during write.
>>   commit-graph: add --changed-paths option to write subcommand
>>   revision.c: use Bloom filters to speed up path based revision walks
>>   commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag
>>
>> Jeff King (1):
>>   commit-graph: examine changed-path objects in pack order
> 
> The shortlog summary is a fine tool to show contributors to the patch
> series, but is not as useful to show patch series as a whole: splitting
> of patches and their ordering.
>

This is a GitGitGadget specific thing, and it is probably by design. I have 
opened an issue in that repo for any follow up discussions:
  https://github.com/gitgitgadget/gitgitgadget/issues/203

Show 5 quoted lines

> - [PATCH v2 02/11] bloom: core Bloom filter implementation for changed paths
> 
>   In my opinion this patch could be split into three individual pieces,
>   though one might think it is not worth it.
>

I have gone back and forth on doing this. I like most of the core Bloom filter computations being isolated in one patch/commit. But based on the rest of your review, it seems like you are leaning heavily on having this split out. So, I will take a proper stab at doing it for v3.

Show 13 quoted lines

> - [PATCH v2 07/11] commit-graph: write Bloom filters to commit graph file
> 
>   This commit includes the documentation of the two new chunks of
>   commit-graph file format.
> 
>   I wonder if the 9th patch in this series, namely
>   commit-graph: add --changed-paths option to write subcommand
>   should not precede this commit.  Otherwise we have this new code but
>   no way of testing it.  On the other hand it makes it easier to
>   review.  On the gripping hand, you can't really test that writing
>   works without the ability to parse Bloom filter data out of
>   commit-graph file... which is the next commit.
>

Getting complete test coverage within a single patch would require 2 or 3 of 
these patches to be combined. This would lead to a large patch that would be 
much more difficult to review.
 
My tests in the patches following this one run git commands. Hence the tests 
get introduced when the command line is ready to use all the new code.

The current ordering of patches works better than adding the --changed-paths option before the logic that computes and writes. Otherwise the option will not be doing what it is supposed to do in the patch it was introduced in.

Show 6 quoted lines

> - [PATCH v2 08/11] commit-graph: reuse existing Bloom filters during write
> 
>   This implements reading Bloom filters data from commit-graph file.
>   Is it a good split?  I think it makes it easier to review the single
>   patch, but itt also makes them less standalone.
>

All the logic upto this point works just fine without the ability to read and parse precomputed bloom filters. This patch is an enhancement and it also separates out the reading and writing logic. Reusing existing bloom filters during write is the simplest interatcion that involves reading from the commit graph file, and builds the foundation to make the `git log` improvements. Hence, it warrants its own patch and review.

Show 13 quoted lines

> - [PATCH v2 10/11] revision.c: use Bloom filters to speed up path based revision walks
> 
>   This is quite a big and involved patch, which in my opinion could be
>   split in two or three parts:
> 
>   a. Add a bare bones implementation, like in v2
> 
>   This limits amount of testing we can do; the only thing we can really
>   test is that we get the same results with and without Bloom filters.
> 
>   b.1. Add trace2 Bloom filter statistics
>   b.2. Use said trace2 statistics to test use of Bloom filters
>

Sure. I will look into doing this split as well for v3.

> 
> Feel free to disagree with those ideas.
> 
> Best,

Thanks for taking the time for reviewing this series so thoroughly! It is greatly appreciated!

Cheers, Garima Singh