From: "SZEDER Gábor" <szeder.dev@gmail.com> To: Derrick Stolee <stolee@gmail.com> Cc: Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com>, git@vger.kernel.org, jonathantanmy@google.com, Garima Singh <garima.singh@microsoft.com>, Derrick Stolee <dstolee@microsoft.com>, Taylor Blau <me@ttaylorr.com> Subject: Re: [PATCH v4 05/15] diff: halt tree-diff early after max_changes Date: Tue, 4 Aug 2020 19:00:40 +0200 [thread overview] Message-ID: <20200804170040.GB25052@szeder.dev> (raw) In-Reply-To: <a08c26bb-54ec-13af-e503-fccd68727cf3@gmail.com> On Tue, Aug 04, 2020 at 12:25:45PM -0400, Derrick Stolee wrote: > On 8/4/2020 10:47 AM, SZEDER Gábor wrote: > > On Mon, Apr 06, 2020 at 04:59:45PM +0000, Derrick Stolee via GitGitGadget wrote: > > This counter is basically broken, its value is wrong for over 98% of > > commits, and, worse, its value remains 0 for over 85% of commits in > > the repositories I usually use to test modified path Bloom filters. > > Consequently, a relatively large number of commits modifying more than > > 512 paths get Bloom filters. > > Thanks for finding this! The counter is only really tested in one > place, and that test only considers _file adds_, which is a problem. > > If I understand this correctly, the bug is a performance-only bug > (since this is a performance-only feature), but it is an important > one to fix. Or a performance-only feature in a performance-only feature, because those additional modified path Bloom filters can improve the runtime of pathspec-limited revision walks (assuming that the false positive rate is low enough). > There is certainly some dark magic happening in this tree-diff logic, > so instead of trying to get an accurate count we should just use the > magic global diff_queued_diff to track the current list of file changes. > > Note: diff_queued_diff does not track the directory changes, so it > is an under-count for the total changes to track in the Bloom filter. > This is later corrected by the block that adds these leading directory > changes. > > > The makeshift tests in the patch below demonstrate these issues as > > most of them fail, most notably those two tests that demonstrate that > > modifying existing paths are not counted at all. > > I adapted your diff along with ripping out 'num_changes' in favor > of diff_queued_diff.nr. This required modifying some of your expected > values in the test script (losing the leading directories in the > count). > > I'll work with Taylor to create a fix, and include proper testing > of the logic here. We'll stick it in the v2 of his max-changed-paths > series [1]. He already has some helpful logging that can help create > tests that ensure this logic is performing as expected. Don't forget to include a check of the hashmap's size, to make sure. FWIW, the patch below does result in the correct count (read: the same as in my implemenation) for all but 4 commits in those repositories I use for testing, without adding any memory allocations and extra strcmp() calls. --- >8 --- diff --git a/cache.h b/cache.h index 0f0485ecfe..3fc7e1b427 100644 --- a/cache.h +++ b/cache.h @@ -1574,6 +1574,7 @@ int repo_interpret_branch_name(struct repository *r, int validate_headref(const char *ref); int base_name_compare(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2); +int base_name_compare_df(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2, int *df); int df_name_compare(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2); int name_compare(const char *name1, size_t len1, const char *name2, size_t len2); int cache_name_stage_compare(const char *name1, int len1, int stage1, const char *name2, int len2, int stage2); diff --git a/read-cache.c b/read-cache.c index aa427c5c17..041af19e60 100644 --- a/read-cache.c +++ b/read-cache.c @@ -460,13 +460,16 @@ int ie_modified(struct index_state *istate, return 0; } -int base_name_compare(const char *name1, int len1, int mode1, - const char *name2, int len2, int mode2) +int base_name_compare_df(const char *name1, int len1, int mode1, + const char *name2, int len2, int mode2, + int *df) { unsigned char c1, c2; int len = len1 < len2 ? len1 : len2; int cmp; + *df = 0; + cmp = memcmp(name1, name2, len); if (cmp) return cmp; @@ -476,7 +479,21 @@ int base_name_compare(const char *name1, int len1, int mode1, c1 = '/'; if (!c2 && S_ISDIR(mode2)) c2 = '/'; - return (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0; + if (c1 == c2) + return 0; /* TODO: is this even possible? */ + if ((c1 == '/' && !c2) || + (!c1 && c2 == '/')) + *df = 1; + return (c1 < c2) ? -1 : 1; +} + +int base_name_compare(const char *name1, int len1, int mode1, + const char *name2, int len2, int mode2) +{ + int unused; + return base_name_compare_df(name1, len1, mode1, + name2, len2, mode2, + &unused); } /* diff --git a/t/t9999-test.sh b/t/t9999-test.sh index 8d2bd9f03f..4f08590b45 100755 --- a/t/t9999-test.sh +++ b/t/t9999-test.sh @@ -125,7 +125,7 @@ test_expect_success 'replace file with dir' ' test_cmp expect actual ' -test_expect_success 'replace dir with file' ' +test_expect_failure 'replace dir with file' ' git diff --name-status $dir_to_file^ $dir_to_file && echo "$dir_to_file 2" >expect && grep "$dir_to_file" out >actual && diff --git a/tree-diff.c b/tree-diff.c index f3d303c6e5..e27f9c805e 100644 --- a/tree-diff.c +++ b/tree-diff.c @@ -46,11 +46,14 @@ static int ll_diff_tree_oid(const struct object_id *old_oid, * Due to this convention, if trees are scanned in sorted order, all * non-empty descriptors will be processed first. */ -static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2) +static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2, + int *df) { struct name_entry *e1, *e2; int cmp; + *df = 0; + /* empty descriptors sort after valid tree entries */ if (!t1->size) return t2->size ? 1 : 0; @@ -59,8 +62,9 @@ static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2) e1 = &t1->entry; e2 = &t2->entry; - cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode, - e2->path, tree_entry_len(e2), e2->mode); + cmp = base_name_compare_df(e1->path, tree_entry_len(e1), e1->mode, + e2->path, tree_entry_len(e2), e2->mode, + df); return cmp; } @@ -410,7 +414,7 @@ static struct combine_diff_path *ll_diff_tree_paths( { struct tree_desc t, *tp; void *ttree, **tptree; - int i; + int i, df; FAST_ARRAY_ALLOC(tp, nparent); FAST_ARRAY_ALLOC(tptree, nparent); @@ -463,7 +467,7 @@ static struct combine_diff_path *ll_diff_tree_paths( tp[0].entry.mode &= ~S_IFXMIN_NEQ; for (i = 1; i < nparent; ++i) { - cmp = tree_entry_pathcmp(&tp[i], &tp[imin]); + cmp = tree_entry_pathcmp(&tp[i], &tp[imin], &df); if (cmp < 0) { imin = i; tp[i].entry.mode &= ~S_IFXMIN_NEQ; @@ -483,10 +487,12 @@ static struct combine_diff_path *ll_diff_tree_paths( /* compare t vs p[imin] */ - cmp = tree_entry_pathcmp(&t, &tp[imin]); + cmp = tree_entry_pathcmp(&t, &tp[imin], &df); /* t = p[imin] */ if (cmp == 0) { + int prev_num_changes = opt->num_changes; + /* are either pi > p[imin] or diff(t,pi) != ø ? */ if (!opt->flags.find_copies_harder) { for (i = 0; i < nparent; ++i) { @@ -506,6 +512,9 @@ static struct combine_diff_path *ll_diff_tree_paths( /* D += {δ(t,pi) if pi=p[imin]; "+a" if pi > p[imin]} */ p = emit_path(p, base, opt, nparent, &t, tp, imin); + if (!(opt->num_changes == prev_num_changes && + S_ISDIR(t.entry.mode))) + opt->num_changes++; skip_emit_t_tp: /* t↓, ∀ pi=p[imin] pi↓ */ @@ -518,10 +527,11 @@ static struct combine_diff_path *ll_diff_tree_paths( /* D += "+t" */ p = emit_path(p, base, opt, nparent, &t, /*tp=*/NULL, -1); + if (!df) + opt->num_changes++; /* t↓ */ update_tree_entry(&t); - opt->num_changes++; } /* t > p[imin] */ @@ -535,11 +545,12 @@ static struct combine_diff_path *ll_diff_tree_paths( p = emit_path(p, base, opt, nparent, /*t=*/NULL, tp, imin); + if (!df) + opt->num_changes++; skip_emit_tp: /* ∀ pi=p[imin] pi↓ */ update_tp_entries(tp, nparent); - opt->num_changes++; } } --- >8 --- Having said that, the best (i.e faster and accurate) solution to this issue is probably: - Update the callchain between diff_tree_oid() and the diff callback functions to allow the callbacks to break diffing with a non-zero error code. - Fill Bloom filters using the approach presented in: https://public-inbox.org/git/20200529085038.26008-21-szeder.dev@gmail.com/ but modify the callbacks to return non-zero when too many paths have been processed. - Drop this counter entirely, as there are no other users. > We plan to have that fix available by later today or early tomorrow. > Will you be available to help validate it? > > [1] https://lore.kernel.org/git/cover.1596480582.git.me@ttaylorr.com/ > > Thanks, > -Stolee > > --- >8 --- > > diff --git a/bloom.c b/bloom.c > index 1a573226e7..b8d6cb9240 100644 > --- a/bloom.c > +++ b/bloom.c > @@ -218,8 +218,9 @@ struct bloom_filter *get_bloom_filter(struct repository *r, > else > diff_tree_oid(NULL, &c->object.oid, "", &diffopt); > diffcore_std(&diffopt); > + printf("%s %d\n", oid_to_hex(&c->object.oid), diff_queued_diff.nr); > > - if (diffopt.num_changes <= max_changes) { > + if (diff_queued_diff.nr <= max_changes) { > struct hashmap pathmap; > struct pathmap_hash_entry *e; > struct hashmap_iter iter; > diff --git a/diff.h b/diff.h > index e0c0af6286b..1d32b718857 100644 > --- a/diff.h > +++ b/diff.h > @@ -287,8 +287,6 @@ struct diff_options { > > /* If non-zero, then stop computing after this many changes. */ > int max_changes; > - /* For internal use only. */ > - int num_changes; > > int ita_invisible_in_index; > /* white-space error highlighting */ > diff --git a/t/t9999-test.sh b/t/t9999-test.sh > new file mode 100755 > index 00000000000..1f35aa8e2c5 > --- /dev/null > +++ b/t/t9999-test.sh > @@ -0,0 +1,142 @@ > +#!/bin/sh > + > +test_description='test' > + > +. ./test-lib.sh > + > +test_expect_success 'setup' ' > + test_tick && > + > + echo 1 >file && > + mkdir -p dir/subdir && > + echo 1 >dir/subdir/file1 && > + echo 1 >dir/subdir/file2 && > + git add file dir && > + git commit -m setup && > + > + echo 2 >file && > + git commit -a -m "modify one path in root" && > + mod_one_path=$(git rev-parse HEAD) && > + > + echo 2 >dir/subdir/file1 && > + echo 2 >dir/subdir/file2 && > + git commit -a -m "modify two file two dirs deep" && > + mod_four_paths=$(git rev-parse HEAD) && > + > + >new-file && > + git add new-file && > + git commit -m "add new file in root" && > + new_file_in_root=$(git rev-parse HEAD) && > + > + git rm new-file && > + git commit -m "delete file in root" && > + delete_file_in_root=$(git rev-parse HEAD) && > + > + >dir/new-file && > + git add dir/new-file && > + git commit -m "add new file in dir" && > + new_file_in_dir=$(git rev-parse HEAD) && > + > + git rm dir/new-file && > + git commit -m "delete file in dir" && > + delete_file_in_dir=$(git rev-parse HEAD) && > + > + echo 1 >d-f && > + git add d-f && > + git commit -m foo && > + git rm d-f && > + mkdir d-f && > + echo 2 >d-f/file && > + git add d-f && > + git commit -m "replace file with dir" && > + file_to_dir=$(git rev-parse HEAD) && > + > + >d-f.c && > + git add d-f.c && > + git commit -m "add a file that sorts between d-f and d-f/" && > + git rm -r d-f && > + echo 3 >d-f && > + git add d-f && > + git commit -m "replace dir with file" && > + dir_to_file=$(git rev-parse HEAD) && > + > + bin_sha1=$(git rev-parse HEAD:dir/subdir | hex2oct) && > + # leading zero in mode: the content of the tree remains the same, > + # but its oid does change! > + printf "040000 subdir\0$bin_sha1" >rawtree && > + tree1=$(git hash-object -t tree -w rawtree) && > + git cat-file -p HEAD^{tree} >out && > + tree2=$(sed -e "s/$(git rev-parse HEAD:dir/)/$tree1/" out |git mktree) && > + different_but_same_tree=$(git commit-tree \ > + -m "leading zeros in mode" \ > + -p $(git rev-parse HEAD) $tree2) && > + git update-ref HEAD $different_but_same_tree && > + > + git commit-graph write --reachable --changed-paths >out && > + cat out # debug > +' > + > +test_expect_success 'modify one path in root' ' > + git diff --name-status $mod_one_path^ $mod_one_path && > + echo "$mod_one_path 1" >expect && > + grep "$mod_one_path" out >actual && > + test_cmp expect actual > +' > + > +test_expect_success 'modify two file two dirs deep' ' > + git diff --name-status $mod_four_paths^ $mod_four_paths && > + echo "$mod_four_paths 2" >expect && > + grep "$mod_four_paths" out >actual && > + test_cmp expect actual > +' > + > +test_expect_success 'add new file in root' ' > + git diff --name-status $new_file_in_root^ $new_file_in_root && > + echo "$new_file_in_root 1" >expect && > + grep "$new_file_in_root" out >actual && > + test_cmp expect actual > +' > + > +test_expect_success 'delete file in root' ' > + git diff --name-status $delete_file_in_root^ $delete_file_in_root && > + echo "$delete_file_in_root 1" >expect && > + grep "$delete_file_in_root" out >actual && > + test_cmp expect actual > +' > + > +test_expect_success 'add new file in dir' ' > + git diff --name-status $new_file_in_dir^ $new_file_in_dir && > + echo "$new_file_in_dir 1" >expect && > + grep "$new_file_in_dir" out >actual && > + test_cmp expect actual > +' > + > +test_expect_success 'delete file in dir' ' > + git diff --name-status $delete_file_in_dir^ $delete_file_in_dir && > + echo "$delete_file_in_dir 1" >expect && > + grep "$delete_file_in_dir" out >actual && > + test_cmp expect actual > +' > + > +test_expect_success 'replace file with dir' ' > + git diff --name-status $file_to_dir^ $file_to_dir && > + echo "$file_to_dir 2" >expect && > + grep "$file_to_dir" out >actual && > + test_cmp expect actual > +' > + > +test_expect_success 'replace dir with file' ' > + git diff --name-status $dir_to_file^ $dir_to_file && > + echo "$dir_to_file 2" >expect && > + grep "$dir_to_file" out >actual && > + test_cmp expect actual > +' > + > +test_expect_success 'leading zeros in mode' ' > + git diff --name-status $different_but_same_tree^ $different_but_same_tree && > + echo "$different_but_same_tree 0" >expect && > + grep "$different_but_same_tree" out >actual && > + test_cmp expect actual > +' > + > +test_done > diff --git a/tree-diff.c b/tree-diff.c > index 6ebad1a46f3..7cebbb327e2 100644 > --- a/tree-diff.c > +++ b/tree-diff.c > @@ -434,7 +434,7 @@ static struct combine_diff_path *ll_diff_tree_paths( > if (diff_can_quit_early(opt)) > break; > > - if (opt->max_changes && opt->num_changes > opt->max_changes) > + if (opt->max_changes && diff_queued_diff.nr > opt->max_changes) > break; > > if (opt->pathspec.nr) { > @@ -521,7 +521,6 @@ static struct combine_diff_path *ll_diff_tree_paths( > > /* t↓ */ > update_tree_entry(&t); > - opt->num_changes++; > } > > /* t > p[imin] */ > @@ -539,7 +538,6 @@ static struct combine_diff_path *ll_diff_tree_paths( > skip_emit_tp: > /* ∀ pi=p[imin] pi↓ */ > update_tp_entries(tp, nparent); > - opt->num_changes++; > } > } > > @@ -557,7 +555,6 @@ struct combine_diff_path *diff_tree_paths( > const struct object_id **parents_oid, int nparent, > struct strbuf *base, struct diff_options *opt) > { > - opt->num_changes = 0; > p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt); > > /*
next prev parent reply other threads:[~2020-08-04 17:03 UTC|newest] Thread overview: 159+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-12-20 22:05 [PATCH 0/9] [RFC] Changed Paths Bloom Filters Garima Singh via GitGitGadget 2019-12-20 22:05 ` [PATCH 1/9] commit-graph: add --changed-paths option to write Garima Singh via GitGitGadget 2020-01-01 20:20 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 2/9] commit-graph: write changed paths bloom filters Garima Singh via GitGitGadget 2019-12-21 16:48 ` Philip Oakley 2020-01-06 18:44 ` Jakub Narebski 2020-01-13 19:48 ` Garima Singh 2019-12-20 22:05 ` [PATCH 3/9] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget 2020-01-07 12:19 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 4/9] commit-graph: document bloom filter format Garima Singh via GitGitGadget 2020-01-07 14:46 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 5/9] commit-graph: write changed path bloom filters to commit-graph file Garima Singh via GitGitGadget 2020-01-07 16:01 ` Jakub Narebski 2020-01-14 15:14 ` Garima Singh 2019-12-20 22:05 ` [PATCH 6/9] commit-graph: test commit-graph write --changed-paths Garima Singh via GitGitGadget 2020-01-08 0:32 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 7/9] commit-graph: reuse existing bloom filters during write Garima Singh via GitGitGadget 2020-01-09 19:12 ` Jakub Narebski 2019-12-20 22:05 ` [PATCH 8/9] revision.c: use bloom filters to speed up path based revision walks Garima Singh via GitGitGadget 2020-01-11 0:27 ` Jakub Narebski 2020-01-15 0:08 ` Garima Singh 2019-12-20 22:05 ` [PATCH 9/9] commit-graph: add GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS test flag Garima Singh via GitGitGadget 2020-01-11 19:56 ` Jakub Narebski 2020-01-15 0:55 ` Garima Singh 2019-12-20 22:14 ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Junio C Hamano 2019-12-22 9:26 ` Christian Couder 2019-12-22 9:38 ` Jeff King 2020-01-01 12:04 ` Jakub Narebski 2019-12-22 9:30 ` Jeff King 2019-12-22 9:32 ` [PATCH 1/3] commit-graph: examine changed-path objects in pack order Jeff King 2019-12-27 14:51 ` Derrick Stolee 2019-12-29 6:12 ` Jeff King 2019-12-29 6:28 ` Jeff King 2019-12-30 14:37 ` Derrick Stolee 2019-12-30 14:51 ` Derrick Stolee 2019-12-22 9:32 ` [PATCH 2/3] commit-graph: free large diffs, too Jeff King 2019-12-27 14:52 ` Derrick Stolee 2019-12-22 9:32 ` [PATCH 3/3] commit-graph: stop using full rev_info for diffs Jeff King 2019-12-27 14:53 ` Derrick Stolee 2019-12-26 14:21 ` [PATCH 0/9] [RFC] Changed Paths Bloom Filters Derrick Stolee 2019-12-29 6:03 ` Jeff King 2019-12-27 16:11 ` Derrick Stolee 2019-12-29 6:24 ` Jeff King 2019-12-30 16:04 ` Derrick Stolee 2019-12-30 17:02 ` Junio C Hamano 2019-12-31 16:45 ` Jakub Narebski 2020-01-13 16:54 ` Garima Singh 2020-01-20 13:48 ` Jakub Narebski 2020-01-21 16:14 ` Garima Singh 2020-02-02 18:43 ` Jakub Narebski 2020-01-21 23:40 ` Emily Shaffer 2020-01-27 18:24 ` Garima Singh 2020-02-01 23:32 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 00/11] " Garima Singh via GitGitGadget 2020-02-05 22:56 ` [PATCH v2 01/11] commit-graph: use MAX_NUM_CHUNKS Garima Singh via GitGitGadget 2020-02-09 12:39 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 02/11] bloom: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget 2020-02-15 17:17 ` Jakub Narebski 2020-02-16 16:49 ` Jakub Narebski 2020-02-22 0:32 ` Garima Singh 2020-02-23 13:38 ` Jakub Narebski 2020-02-24 17:34 ` Garima Singh 2020-02-24 18:20 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 03/11] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget 2020-02-17 0:00 ` Jakub Narebski 2020-02-22 0:37 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 04/11] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget 2020-02-17 21:56 ` Jakub Narebski 2020-02-22 0:55 ` Garima Singh 2020-02-23 17:34 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 05/11] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget 2020-02-18 17:59 ` Jakub Narebski 2020-02-24 18:29 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 06/11] commit-graph: examine commits by generation number Derrick Stolee via GitGitGadget 2020-02-19 0:32 ` Jakub Narebski 2020-02-24 20:45 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 07/11] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget 2020-02-19 15:13 ` Jakub Narebski 2020-02-24 21:14 ` Garima Singh 2020-02-25 11:40 ` Jakub Narebski 2020-02-25 15:58 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 08/11] commit-graph: reuse existing Bloom filters during write Garima Singh via GitGitGadget 2020-02-20 18:48 ` Jakub Narebski 2020-02-24 21:45 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 09/11] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget 2020-02-20 20:28 ` Jakub Narebski 2020-02-24 21:51 ` Garima Singh 2020-02-25 12:10 ` Jakub Narebski 2020-02-20 22:10 ` Bryan Turner 2020-02-22 1:44 ` Garima Singh 2020-02-05 22:56 ` [PATCH v2 10/11] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget 2020-02-21 17:31 ` Jakub Narebski 2020-02-21 22:45 ` Jakub Narebski 2020-02-05 22:56 ` [PATCH v2 11/11] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget 2020-02-22 0:11 ` Jakub Narebski 2020-02-07 13:52 ` [PATCH v2 00/11] Changed Paths Bloom Filters SZEDER Gábor 2020-02-07 15:09 ` Garima Singh 2020-02-07 15:36 ` Derrick Stolee 2020-02-07 16:15 ` SZEDER Gábor 2020-02-07 16:33 ` Derrick Stolee 2020-02-11 19:08 ` Garima Singh 2020-02-08 23:04 ` Jakub Narebski 2020-02-21 17:41 ` Garima Singh 2020-03-29 18:36 ` Junio C Hamano 2020-03-30 0:31 ` [PATCH v3 00/16] " Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 01/16] commit-graph: define and use MAX_NUM_CHUNKS Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 02/16] bloom.c: add the murmur3 hash implementation Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 03/16] bloom.c: introduce core Bloom filter constructs Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 04/16] bloom.c: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 05/16] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 06/16] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 07/16] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 08/16] commit-graph: examine commits by generation number Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 09/16] diff: skip batch object download when possible Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 10/16] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 11/16] commit-graph: reuse existing Bloom filters during write Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 12/16] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 13/16] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 14/16] revision.c: add trace2 stats around Bloom filter usage Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 15/16] t4216: add end to end tests for git log with Bloom filters Garima Singh via GitGitGadget 2020-03-30 0:31 ` [PATCH v3 16/16] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 00/15] Changed Paths Bloom Filters Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 01/15] commit-graph: define and use MAX_NUM_CHUNKS Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 02/15] bloom.c: add the murmur3 hash implementation Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 03/15] bloom.c: introduce core Bloom filter constructs Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 04/15] bloom.c: core Bloom filter implementation for changed paths Garima Singh via GitGitGadget 2020-06-27 15:53 ` SZEDER Gábor 2020-04-06 16:59 ` [PATCH v4 05/15] diff: halt tree-diff early after max_changes Derrick Stolee via GitGitGadget 2020-08-04 14:47 ` SZEDER Gábor 2020-08-04 16:25 ` Derrick Stolee 2020-08-04 17:00 ` SZEDER Gábor [this message] 2020-08-04 17:31 ` Derrick Stolee 2020-08-05 17:08 ` Derrick Stolee 2020-04-06 16:59 ` [PATCH v4 06/15] commit-graph: compute Bloom filters for changed paths Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 07/15] commit-graph: examine changed-path objects in pack order Jeff King via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 08/15] commit-graph: examine commits by generation number Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 09/15] commit-graph: write Bloom filters to commit graph file Garima Singh via GitGitGadget 2020-05-29 8:57 ` SZEDER Gábor 2020-05-29 13:35 ` Derrick Stolee 2020-05-31 17:23 ` SZEDER Gábor 2020-07-09 17:00 ` [PATCH] commit-graph: fix "Writing out commit graph" progress counter SZEDER Gábor 2020-07-09 18:01 ` Derrick Stolee 2020-07-09 18:20 ` Derrick Stolee 2020-04-06 16:59 ` [PATCH v4 10/15] commit-graph: reuse existing Bloom filters during write Garima Singh via GitGitGadget 2020-06-19 14:02 ` SZEDER Gábor 2020-06-19 19:28 ` Junio C Hamano 2020-07-27 21:33 ` SZEDER Gábor 2020-04-06 16:59 ` [PATCH v4 11/15] commit-graph: add --changed-paths option to write subcommand Garima Singh via GitGitGadget 2020-06-07 22:21 ` SZEDER Gábor 2020-04-06 16:59 ` [PATCH v4 12/15] revision.c: use Bloom filters to speed up path based revision walks Garima Singh via GitGitGadget 2020-06-26 6:34 ` SZEDER Gábor 2020-04-06 16:59 ` [PATCH v4 13/15] revision.c: add trace2 stats around Bloom filter usage Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 14/15] t4216: add end to end tests for git log with Bloom filters Garima Singh via GitGitGadget 2020-04-06 16:59 ` [PATCH v4 15/15] commit-graph: add GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS test flag Garima Singh via GitGitGadget 2020-04-08 15:51 ` [PATCH v4 00/15] Changed Paths Bloom Filters Derrick Stolee 2020-04-08 19:21 ` Junio C Hamano 2020-04-08 20:05 ` Jakub Narębski 2020-04-12 20:34 ` Taylor Blau 2020-03-05 19:49 ` [PATCH 0/9] [RFC] " Garima Singh
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 List information: http://vger.kernel.org/majordomo-info.html * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20200804170040.GB25052@szeder.dev \ --to=szeder.dev@gmail.com \ --cc=dstolee@microsoft.com \ --cc=garima.singh@microsoft.com \ --cc=git@vger.kernel.org \ --cc=gitgitgadget@gmail.com \ --cc=jonathantanmy@google.com \ --cc=me@ttaylorr.com \ --cc=stolee@gmail.com \ --subject='Re: [PATCH v4 05/15] diff: halt tree-diff early after max_changes' \ /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
Code repositories for project(s) associated with this inbox: https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).