| Message ID | pull.497.v4.git.1586192395.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | Changed Paths Bloom Filters | expand |
On 4/6/2020 12:59 PM, Garima Singh via GitGitGadget wrote: > 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] > > With the changes in this series, git users will be able to choose to write > Bloom filters to the commit-graph using the following command: > > 'git commit-graph write --changed-paths' > > Subsequent 'git log -- path' commands will use these computed Bloom filters > to decided which commits are worth exploring further to produce the history > of the provided path. I noticed Jakub was not CC'd on this email. Jakub: do you plan to re-review the new version? Or are you satisfied with the resolutions to your comments? Is anyone else planning to review this series? I'm just wondering when we should take this series to cook in 'next' and start building things on top of it, such as "git blame" or "git log -L" improvements. While it cooks, any bugs or issues could be resolved with patches on top of this version. That would be my preference, anyway. What do you think, Junio? Thanks, -Stolee
Derrick Stolee <stolee@gmail.com> writes: > I noticed Jakub was not CC'd on this email. Jakub: do you plan to re-review > the new version? Or are you satisfied with the resolutions to your comments? > ... > What do you think, Junio? I was hoping that after Jakub's review, the new round was ready for 'next' to be extended further by building on top as needed. Of course the path-limited revision walk is one of the most important part of the entire system, so I'd welcome reviews from others, too. Thanks.
On Wed, 8 Apr 2020 at 17:51, Derrick Stolee <stolee@gmail.com> wrote: > > On 4/6/2020 12:59 PM, Garima Singh via GitGitGadget wrote: > > 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] > > > > With the changes in this series, git users will be able to choose to write > > Bloom filters to the commit-graph using the following command: > > > > 'git commit-graph write --changed-paths' > > > > Subsequent 'git log -- path' commands will use these computed Bloom filters > > to decided which commits are worth exploring further to produce the history > > of the provided path. > > I noticed Jakub was not CC'd on this email. Jakub: do you plan to re-review > the new version? Or are you satisfied with the resolutions to your comments? I am planning to re-review v4 of this series when I would have time, which means probably after Easter. I think if it handles endianness issues correctly, it should be ready.
Hi Stolee, On Wed, Apr 08, 2020 at 11:51:14AM -0400, Derrick Stolee wrote: > On 4/6/2020 12:59 PM, Garima Singh via GitGitGadget wrote: > > 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] > > > > With the changes in this series, git users will be able to choose to write > > Bloom filters to the commit-graph using the following command: > > > > 'git commit-graph write --changed-paths' > > > > Subsequent 'git log -- path' commands will use these computed Bloom filters > > to decided which commits are worth exploring further to produce the history > > of the provided path. > > I noticed Jakub was not CC'd on this email. Jakub: do you plan to re-review > the new version? Or are you satisfied with the resolutions to your comments? > > Is anyone else planning to review this series? I feel horribly that I've had this patch series sitting in my review backlog for months and haven't gotten to it yet, especially because I have such an interest in these patches and know that much care was taken to prepare them. I read through these patches over some coffee today at a cursory level. The high-level approach makes sense to me, and the implementation looks solid. I think that anything that does come up (see below) can be addressed in 'next' rather than waiting longer on this series. For what it's worth, I'm planning on starting to test this series in some of our testing repositories at GitHub, and I'll report back on our experience with some notes (and patches) should anything come up. > I'm just wondering when we should take this series to cook in 'next' and > start building things on top of it, such as "git blame" or "git log -L" > improvements. While it cooks, any bugs or issues could be resolved with > patches on top of this version. That would be my preference, anyway. That would be my preference, too. I noticed a few small things (mostly a couple of typos and other very minor details). But, I'd much rather build on top of this series once it has landed in 'next' than go to a fifth re-roll since there are many patches involved. I also noticed that you have already sent some patches in a separate series that are based on this one, which would apply cleanly if this series is merged into next. I figure that this will also be helpful as I send some patches about extra 'commit-graph write' options out of GitHub's fork, since they will inevitably create merge conflicts if we both are targeting 'next'. So, I figure that this approach will ease some maintainer burden ;-). > > What do you think, Junio? > > Thanks, > -Stolee Thanks, Taylor
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] With the changes in this series, git users will be able to choose to write Bloom filters to the commit-graph using the following command: 'git commit-graph write --changed-paths' Subsequent 'git log -- path' commands will use these computed Bloom filters to decided which commits are worth exploring further to produce the history of the provided path. Cost of computing and writing Bloom filters =========================================== Computing and writing Bloom filters to the commit graph for the first time implies computing the diffs and the resulting Bloom filters for all the commits in the repository. This adds a non trivial amount of time to run time. Every subsequent run is incremental i.e. we reuse the previously computed Bloom filters. So this is a one time cost. Time taken by 'git commit-graph write' with and w/o --changed-paths, speed up in 'git log -- path' with computed Bloom filters (see a):- ------------------------------------------------------------------------- | Repo | w/o --changed-paths | with --changed-paths | Speed up | ------------------------------------------------------------------------- | git [3] | 0.9 seconds | 7 seconds | 2x to 6x | | linux [4] | 16 seconds | 1 minute 8 seconds | 2x to 6x | | android [5] | 9 seconds | 48 seconds | 2x to 6x | | AzDo(see b) | 1 minute | 5 minutes 2 seconds | 10x to 30x | ------------------------------------------------------------------------- a) We tested the performance of git log -- path with randomly chosen paths of varying depths in each repo. The speed up depends on how deep the files are in the hierarchy and how often a file has been touched in the commit history. b) This internal repository has about 420k commits, 183k files distributed across 34k folders, the size on disk is about 17 GiB. The most massive gains on this repository were for files 6-12 levels deep in the tree. c) These numbers were collected on a Windows machine, except for the linux repo which was tested on a Linux machine. Future Work (not included in the scope of this series) ====================================================== 1. Supporting multiple path based revision walk 2. Adopting it in git blame logic. 3. Interactions with line log git log -L Cheers! Garima Singh [1] https://lore.kernel.org/git/20181009193445.21908-1-szeder.dev@gmail.com/ [2] https://lore.kernel.org/git/61559c5b-546e-d61b-d2e1-68de692f5972@gmail.com/ [3] https://github.com/git/git [4] https://github.com/torvalds/linux [5] https://android.googlesource.com/platform/frameworks/base/ jeffhost@microsoft.com, me@ttaylorr.com, peff@peff.net, garimasigit@gmail.com,jnareb@gmail.com, christian.couder@gmail.com, emilyshaffer@gmail.com,gitster@pobox.com Derrick Stolee (1): diff: halt tree-diff early after max_changes Garima Singh (13): commit-graph: define and use MAX_NUM_CHUNKS bloom.c: add the murmur3 hash implementation bloom.c: introduce core Bloom filter constructs bloom.c: core Bloom filter implementation for changed paths. commit-graph: compute Bloom filters for changed paths commit-graph: examine commits by generation number 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 revision.c: add trace2 stats around Bloom filter usage t4216: add end to end tests for git log with Bloom filters commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Jeff King (1): commit-graph: examine changed-path objects in pack order Documentation/git-commit-graph.txt | 5 + .../technical/commit-graph-format.txt | 30 ++ Makefile | 2 + bloom.c | 275 ++++++++++++++++++ bloom.h | 90 ++++++ builtin/commit-graph.c | 10 +- ci/run-build-and-tests.sh | 1 + commit-graph.c | 213 +++++++++++++- commit-graph.h | 9 +- diff.h | 5 + revision.c | 126 +++++++- revision.h | 11 + t/README | 5 + t/helper/test-bloom.c | 81 ++++++ t/helper/test-read-graph.c | 4 + t/helper/test-tool.c | 1 + t/helper/test-tool.h | 1 + t/t0095-bloom.sh | 117 ++++++++ t/t4216-log-bloom.sh | 155 ++++++++++ t/t5318-commit-graph.sh | 2 + t/t5324-split-commit-graph.sh | 1 + tree-diff.c | 6 + 22 files changed, 1139 insertions(+), 11 deletions(-) create mode 100644 bloom.c create mode 100644 bloom.h create mode 100644 t/helper/test-bloom.c create mode 100755 t/t0095-bloom.sh create mode 100755 t/t4216-log-bloom.sh base-commit: 3bab5d56259722843359702bc27111475437ad2a Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-497%2Fgarimasi514%2FcoreGit-bloomFilters-v4 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-497/garimasi514/coreGit-bloomFilters-v4 Pull-Request: https://github.com/gitgitgadget/git/pull/497 Range-diff vs v3: 1: c3ffd9820d5 = 1: c3ffd9820d5 commit-graph: define and use MAX_NUM_CHUNKS 2: a5aa3415c05 = 2: a5aa3415c05 bloom.c: add the murmur3 hash implementation 3: a7702c1afde = 3: a7702c1afde bloom.c: introduce core Bloom filter constructs 4: 8304c297520 = 4: 8304c297520 bloom.c: core Bloom filter implementation for changed paths. 5: 2d4c0b2da38 = 5: 2d4c0b2da38 diff: halt tree-diff early after max_changes 6: c38b9b386ef = 6: c38b9b386ef commit-graph: compute Bloom filters for changed paths 7: d24c85c54ef = 7: d24c85c54ef commit-graph: examine changed-path objects in pack order 8: 5ed16f35fed = 8: 5ed16f35fed commit-graph: examine commits by generation number 9: 55824cda89c < -: ----------- diff: skip batch object download when possible 10: 1e4663523de = 9: ff6b96aad1e commit-graph: write Bloom filters to commit graph file 11: 68395d4051b ! 10: cc8022bdf82 commit-graph: reuse existing Bloom filters during write @@ bloom.c: struct bloom_filter *get_bloom_filter(struct repository *r, + repo_diff_setup(r, &diffopt); diffopt.flags.recursive = 1; - diffopt.detect_rename = 0; + diffopt.max_changes = max_changes; ## bloom.h ## @@ bloom.h: struct bloom_filter_settings { 12: 7e450e45236 = 11: c8b86c383ab commit-graph: add --changed-paths option to write subcommand 13: b18af58aa3e = 12: 617f549ef25 revision.c: use Bloom filters to speed up path based revision walks 14: b5eb280178f = 13: 6beaede7159 revision.c: add trace2 stats around Bloom filter usage 15: 3019ef72881 = 14: b899df5c98e t4216: add end to end tests for git log with Bloom filters 16: 213abb5d895 = 15: 5656e8590e9 commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag