{"thread":{"id":"60225","subject":"[RFC PATCH] Not computing changed path filter for root commits","startedAt":"2023-09-12T02:50:58Z","lastAt":"2023-10-10T19:47:29Z","messageCount":10,"participants":["Jonathan Tan","Junio C Hamano","SZEDER Gábor","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"481735","messageId":"20230911223157.446269-1-jonathantanmy@google.com","threadId":"60225","inReplyTo":null,"subject":"[RFC PATCH] Not computing changed path filter for root commits","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-09-11T22:31:56Z","receivedAt":"2023-09-12T02:50:58Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This is following the discussion about adding a new changed path filter\nversion due to the current implementation of murmur3 not matching the\nalgorithm. [1]\n\nSZEDER Gábor suggested [2] that we change the revision walk to read\nchanged path filters also for root commits, but I don't think that's\npossible - we have to tie reading changed path filters to when we read\ntrees, and right now, we don't seem to read trees when evaluating root\ncommits (rev_compare_tree() in revision.c is in the only code path that\nuses changed path filters, and it itself is only called per-parent and\nthus not called for root commits). The alternative is to not generate\nchanged path filters for root commits (or what I did in this patch,\nwhich is to generate an all-1 filter), which seems reasonable to me.\n\nIs this a good idea? If yes, there is the follow-up question of how to\nreport it in traces. I don't know off-hand if it's better to reuse the\n\"large\" statistic, since what we output is the same (all 1s), or if we\nshould make a new one. Presumably what we need to weigh is the clarity\nversus the migration costs, but I don't know how to weigh it.\n\nIf people are generally in agreement, I can send an updated patch that\ndoes not goto into an \"else\" block :) and also with updated tests (t0095\nneeds to check a non-root commit, and t4216 needs to be updated with\nwhatever statistics we decide to use).\n\n[1] https://lore.kernel.org/git/20230826150610.GA1928@szeder.dev/\n[2] https://lore.kernel.org/git/20230830200218.GA5147@szeder.dev/\n---\n bloom.c              |  3 ++-\n t/t0095-bloom.sh     |  2 +-\n t/t4216-log-bloom.sh | 12 +++---------\n 3 files changed, 6 insertions(+), 11 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex aef6b5fea2..b21130b236 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -226,7 +226,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \tif (c->parents)\n \t\tdiff_tree_oid(&c->parents->item->object.oid, &c->object.oid, \"\", &diffopt);\n \telse\n-\t\tdiff_tree_oid(NULL, &c->object.oid, \"\", &diffopt);\n+\t\tgoto large;\n \tdiffcore_std(&diffopt);\n \n \tif (diff_queued_diff.nr <= settings->max_changed_paths) {\n@@ -292,6 +292,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t} else {\n \t\tfor (i = 0; i < diff_queued_diff.nr; i++)\n \t\t\tdiff_free_filepair(diff_queued_diff.queue[i]);\n+large:\n \t\tinit_truncated_large_filter(filter);\n \n \t\tif (computed)\ndiff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\nindex b567383eb8..02a0b41026 100755\n--- a/t/t0095-bloom.sh\n+++ b/t/t0095-bloom.sh\n@@ -74,7 +74,7 @@ test_expect_success !SANITIZE_LEAK 'get bloom filters for commit with no changes\n \tgit commit --allow-empty -m \"c0\" &&\n \tcat >expect <<-\\EOF &&\n \tFilter_Length:1\n-\tFilter_Data:00|\n+\tFilter_Data:ff|\n \tEOF\n \ttest-tool bloom get_filter_for_commit \"$(git rev-parse HEAD)\" >actual &&\n \ttest_cmp expect actual\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex fa9d32facf..d14fe93fb1 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -283,7 +283,6 @@ test_expect_success 'correctly report changes over limit' '\n \t\t\tgit commit-graph write --reachable --changed-paths &&\n \t\ttest_max_changed_paths 11 trace-update &&\n \t\ttest_filter_computed 2 trace-update &&\n-\t\ttest_filter_trunc_large 0 trace-update &&\n \n \t\tfor path in $(git ls-tree -r --name-only HEAD)\n \t\tdo\n@@ -306,9 +305,7 @@ test_expect_success 'correctly report commits with no changed paths' '\n \t\tGIT_TRACE2_EVENT=\"$(pwd)/trace.event\" \\\n \t\t\tgit commit-graph write --reachable --changed-paths &&\n \t\ttest_filter_computed 1 trace.event &&\n-\t\ttest_filter_not_computed 0 trace.event &&\n-\t\ttest_filter_trunc_empty 1 trace.event &&\n-\t\ttest_filter_trunc_large 0 trace.event\n+\t\ttest_filter_not_computed 0 trace.event\n \t)\n '\n \n@@ -363,8 +360,7 @@ test_expect_success '--max-new-filters overrides configuration' '\n \t\t\t\t--max-new-filters=1 &&\n \t\ttest_filter_computed 1 trace.event &&\n \t\ttest_filter_not_computed 1 trace.event &&\n-\t\ttest_filter_trunc_empty 0 trace.event &&\n-\t\ttest_filter_trunc_large 0 trace.event\n+\t\ttest_filter_trunc_empty 0 trace.event\n \t)\n '\n \n@@ -386,9 +382,7 @@ test_expect_success 'Bloom generation backfills empty commits' '\n \t\t\t\tgit commit-graph write --reachable \\\n \t\t\t\t\t--changed-paths --max-new-filters=2 &&\n \t\t\ttest_filter_computed 2 trace.event &&\n-\t\t\ttest_filter_not_computed 4 trace.event &&\n-\t\t\ttest_filter_trunc_empty 2 trace.event &&\n-\t\t\ttest_filter_trunc_large 0 trace.event || return 1\n+\t\t\ttest_filter_not_computed 4 trace.event || return 1\n \t\tdone &&\n \n \t\t# Finally, make sure that once all commits have filters, that\n-- \n2.42.0.283.g2d96d420d3-goog\n\n"},{"id":"481886","messageId":"xmqqled7e1kq.fsf@gitster.g","threadId":"60225","inReplyTo":"20230911223157.446269-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-09-15T18:25:09Z","receivedAt":"2023-09-15T18:25:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> This is following the discussion about adding a new changed path filter\n> version due to the current implementation of murmur3 not matching the\n> algorithm. [1]\n>\n> SZEDER Gábor suggested [2] that we change the revision walk to read\n> changed path filters also for root commits, but I don't think that's\n> possible - we have to tie reading changed path filters to when we read\n> trees, and right now, we don't seem to read trees when evaluating root\n> commits (rev_compare_tree() in revision.c is in the only code path that\n> uses changed path filters, and it itself is only called per-parent and\n> thus not called for root commits). The alternative is to not generate\n> changed path filters for root commits (or what I did in this patch,\n> which is to generate an all-1 filter), which seems reasonable to me.\n\nI know this is a very silly question, but if the filter is not read\nfor root commits at runtime, does it matter if a filter is created\nfor them beforehand (or not)?  They will not be read whether if they\nexist or not, no?  One observation in the thread [2] appears in was:\n\n    In several of the above test cases test_bloom_filters_used is invoked\n    in a repository with only a root commit, so they don't check that\n    the output is the same with and without Bloom filters.\n\ni.e. the check would be ineffective with the current system that we\nknow does not use the filter for a root commit even if it existed.\nBut would it be an improvement to add a filter to a root commit and\ntest with the filter enabled and disabled to compare the results, if\nwe know the filter is not used anyway?\n"},{"id":"481895","messageId":"20230915202912.GA8705@szeder.dev","threadId":"60225","inReplyTo":"20230911223157.446269-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2023-09-15T20:29:12Z","receivedAt":"2023-09-15T20:30:04Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Mon, Sep 11, 2023 at 03:31:56PM -0700, Jonathan Tan wrote:\n> SZEDER Gábor suggested [2] that we change the revision walk to read\n> changed path filters also for root commits, but I don't think that's\n> possible - we have to tie reading changed path filters to when we read\n> trees, and right now, we don't seem to read trees when evaluating root\n> commits (rev_compare_tree() in revision.c is in the only code path that\n> uses changed path filters, and it itself is only called per-parent and\n> thus not called for root commits).\n\nWhen encountering a root commit during a pathspec-limited revision\nwalk we call rev_same_tree_as_empty() instead of rev_compare_tree().\nAll that's missing there is checking the Bloom filter and accounting\nfor false positives.\n\n"},{"id":"482024","messageId":"ZQnmTXUO94/Qy8mq@nand.local","threadId":"60225","inReplyTo":"20230915202912.GA8705@szeder.dev","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-09-19T18:19:57Z","receivedAt":"2023-09-19T18:20:04Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Sep 15, 2023 at 10:29:12PM +0200, SZEDER Gábor wrote:\n> On Mon, Sep 11, 2023 at 03:31:56PM -0700, Jonathan Tan wrote:\n> > SZEDER Gábor suggested [2] that we change the revision walk to read\n> > changed path filters also for root commits, but I don't think that's\n> > possible - we have to tie reading changed path filters to when we read\n> > trees, and right now, we don't seem to read trees when evaluating root\n> > commits (rev_compare_tree() in revision.c is in the only code path that\n> > uses changed path filters, and it itself is only called per-parent and\n> > thus not called for root commits).\n>\n> When encountering a root commit during a pathspec-limited revision\n> walk we call rev_same_tree_as_empty() instead of rev_compare_tree().\n> All that's missing there is checking the Bloom filter and accounting\n> for false positives.\n\nI think that we'd want something like this, though I would definitely\nappreciate a second set of eyes since I am not 100% confident in my\nset of changes here:\n\n--- 8< ---\ndiff --git a/revision.c b/revision.c\nindex 2f4c53ea20..1d36df49e2 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -837,14 +837,24 @@ static int rev_compare_tree(struct rev_info *revs,\n static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n {\n \tstruct tree *t1 = repo_get_commit_tree(the_repository, commit);\n+\tint bloom_ret = 1;\n\n \tif (!t1)\n \t\treturn 0;\n\n+\tif (revs->bloom_keys_nr) {\n+\t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n+\t\tif (!bloom_ret)\n+\t\t\treturn 1;\n+\t}\n+\n \ttree_difference = REV_TREE_SAME;\n \trevs->pruning.flags.has_changes = 0;\n \tdiff_tree_oid(NULL, &t1->object.oid, \"\", &revs->pruning);\n\n+\tif (bloom_ret == 1 && tree_difference == REV_TREE_SAME)\n+\t\tcount_bloom_filter_false_positive++;\n+\n \treturn tree_difference == REV_TREE_SAME;\n }\n\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex fa9d32facf..3a45cb997b 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -162,7 +162,7 @@ test_expect_success 'setup - add commit-graph to the chain with Bloom filters' '\n\n test_bloom_filters_used_when_some_filters_are_missing () {\n \tlog_args=$1\n-\tbloom_trace_prefix=\"statistics:{\\\"filter_not_present\\\":3,\\\"maybe\\\":6,\\\"definitely_not\\\":9\"\n+\tbloom_trace_prefix=\"statistics:{\\\"filter_not_present\\\":3,\\\"maybe\\\":6,\\\"definitely_not\\\":10\"\n \tsetup \"$log_args\" &&\n \tgrep -q \"$bloom_trace_prefix\" \"$TRASH_DIRECTORY/trace.perf\" &&\n \ttest_cmp log_wo_bloom log_w_bloom\n--- >8 ---\n\nThanks,\nTaylor\n"},{"id":"482025","messageId":"ZQnmwID4PNlB5ME0@nand.local","threadId":"60225","inReplyTo":"20230911223157.446269-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-09-19T18:21:52Z","receivedAt":"2023-09-19T18:21:57Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Sep 11, 2023 at 03:31:56PM -0700, Jonathan Tan wrote:\n> SZEDER Gábor suggested [2] that we change the revision walk to read\n> changed path filters also for root commits, but I don't think that's\n> possible - we have to tie reading changed path filters to when we read\n> trees, and right now, we don't seem to read trees when evaluating root\n> commits (rev_compare_tree() in revision.c is in the only code path that\n> uses changed path filters, and it itself is only called per-parent and\n> thus not called for root commits). The alternative is to not generate\n> changed path filters for root commits (or what I did in this patch,\n> which is to generate an all-1 filter), which seems reasonable to me.\n\nI think between the two, the all-1's filter is the more sensible choice,\nsince not computing a filter is typically reserved for blowing past the\n`commitGraph.maxNewFilters` setting.\n\nBut, I agree with Gábor down-thread that we could instead teach\n`rev_same_tree_as_empty()` to be aware of Bloom filters, which I think\nwould accomplish our goal of reading Bloom filters at the root commit\nwhile not having to tweak their generation.\n\nThanks,\nTaylor\n"},{"id":"482546","messageId":"20231002225546.409837-1-jonathantanmy@google.com","threadId":"60225","inReplyTo":"ZQnmTXUO94/Qy8mq@nand.local","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-10-02T22:55:46Z","receivedAt":"2023-10-02T22:55:52Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> diff --git a/revision.c b/revision.c\n> index 2f4c53ea20..1d36df49e2 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -837,14 +837,24 @@ static int rev_compare_tree(struct rev_info *revs,\n>  static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n>  {\n>  \tstruct tree *t1 = repo_get_commit_tree(the_repository, commit);\n> +\tint bloom_ret = 1;\n> \n>  \tif (!t1)\n>  \t\treturn 0;\n> \n> +\tif (revs->bloom_keys_nr) {\n> +\t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n> +\t\tif (!bloom_ret)\n> +\t\t\treturn 1;\n> +\t}\n> +\n>  \ttree_difference = REV_TREE_SAME;\n>  \trevs->pruning.flags.has_changes = 0;\n>  \tdiff_tree_oid(NULL, &t1->object.oid, \"\", &revs->pruning);\n> \n> +\tif (bloom_ret == 1 && tree_difference == REV_TREE_SAME)\n> +\t\tcount_bloom_filter_false_positive++;\n> +\n>  \treturn tree_difference == REV_TREE_SAME;\n>  }\n\nI'll concentrate on getting this patch in, and will look at (and\ndiscuss) the other Bloom filter-related emails later.\n\nThis looks good, possibly except a code path in try_to_simplify_commit()\nthat calls this rev_same_tree_as_empty() function when\nrev_compare_tree() between a commit and its parent returns REV_TREE_NEW.\nSo there are 2 issues: How can rev_compare_tree() ever return\nREV_TREE_NEW? And it doesn't seem right to check Bloom filters in this\ncode path, since rev_same_tree_as_empty() was invoked here while we are\nenumerating through a commit's parents, which necessarily implies that\nthe commit has parents, but here we're using the Bloom filter as if the\ncommit is known to have no parents.\n\nAs for the first issue, rev_compare_tree() returns REV_TREE_NEW when the\nparent's tree is NULL. I'm not sure how this can happen - the tree can\nbe NULL if the parent commit is not parsed, but at this point I think\nthat it has been parsed. And I think every commit has a tree. This goes\nback all the way to 3a5e860815 (revision: make tree comparison functions\ntake commits rather than trees, 2008-11-03) and even beyond that (I\ndidn't dig further).\n\nAs for the second issue, we can probably solve this by being defensive\nin rev_same_tree_as_empty() by only using the Bloom filter when the\ncommit has no parents. Not sure if this is being overly defensive,\nthough.\n\nThere is also the issue that count_bloom_filter_false_positive is\nincremented even when no Bloom filters are present, but I think this is\nfine (it matches the behavior of rev_compare_tree()).\n\n"},{"id":"482878","messageId":"ZSQ2XwbTM4DDLfJq@nand.local","threadId":"60225","inReplyTo":"20231002225546.409837-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-10-09T17:20:31Z","receivedAt":"2023-10-09T17:20:38Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Oct 02, 2023 at 03:55:46PM -0700, Jonathan Tan wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n> > diff --git a/revision.c b/revision.c\n> > index 2f4c53ea20..1d36df49e2 100644\n> > --- a/revision.c\n> > +++ b/revision.c\n> > @@ -837,14 +837,24 @@ static int rev_compare_tree(struct rev_info *revs,\n> >  static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n> >  {\n> >  \tstruct tree *t1 = repo_get_commit_tree(the_repository, commit);\n> > +\tint bloom_ret = 1;\n> >\n> >  \tif (!t1)\n> >  \t\treturn 0;\n> >\n> > +\tif (revs->bloom_keys_nr) {\n> > +\t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n> > +\t\tif (!bloom_ret)\n> > +\t\t\treturn 1;\n> > +\t}\n> > +\n> >  \ttree_difference = REV_TREE_SAME;\n> >  \trevs->pruning.flags.has_changes = 0;\n> >  \tdiff_tree_oid(NULL, &t1->object.oid, \"\", &revs->pruning);\n> >\n> > +\tif (bloom_ret == 1 && tree_difference == REV_TREE_SAME)\n> > +\t\tcount_bloom_filter_false_positive++;\n> > +\n> >  \treturn tree_difference == REV_TREE_SAME;\n> >  }\n>\n> I'll concentrate on getting this patch in, and will look at (and\n> discuss) the other Bloom filter-related emails later.\n\nSounds good. I know that I have some pending mail from SZEDER as well,\nso I'll try and apply any feedback from both of you before sending a\nreroll so that we can get this all done in one shot.\n\n> This looks good, possibly except a code path in try_to_simplify_commit()\n> that calls this rev_same_tree_as_empty() function when\n> rev_compare_tree() between a commit and its parent returns REV_TREE_NEW.\n> So there are 2 issues: How can rev_compare_tree() ever return\n> REV_TREE_NEW? And it doesn't seem right to check Bloom filters in this\n> code path, since rev_same_tree_as_empty() was invoked here while we are\n> enumerating through a commit's parents, which necessarily implies that\n> the commit has parents, but here we're using the Bloom filter as if the\n> commit is known to have no parents.\n\n> As for the first issue, rev_compare_tree() returns REV_TREE_NEW when the\n> parent's tree is NULL. I'm not sure how this can happen - the tree can\n> be NULL if the parent commit is not parsed, but at this point I think\n> that it has been parsed. And I think every commit has a tree. This goes\n> back all the way to 3a5e860815 (revision: make tree comparison functions\n> take commits rather than trees, 2008-11-03) and even beyond that (I\n> didn't dig further).\n\nThe more I think about this, the more confused I become ;-). I was able\nto track this all the way back to Linus's 461cf59f89 (rev-list: stop\nwhen the file disappears, 2006-01-18), but am convinced that both of\nthese cases (we have an analogous one for when t2 is NULL and we return\nREV_TREE_OLD) are dead code.\n\nI replaced the \"if (!t1) return REV_TREE_NEW;\" with \"if (!t1)\nBUG(\"oops\")\", and was able to get the whole test suite to pass. So... I\nam pretty sure that this is dead code, but not sure enough to remove it\nmyself ;-).\n\nTo your point about seeing the tree as NULL before parsing the parent, I\ndon't think that is the case here, since we parse the parent immediately\nbefore calling rev_compare_tree() (and indeed Git will refuse to read\ncommit objects which do not list a tree).\n\n> As for the second issue, we can probably solve this by being defensive\n> in rev_same_tree_as_empty() by only using the Bloom filter when the\n> commit has no parents. Not sure if this is being overly defensive,\n> though.\n\nI am also unsure whether we are being overly defensive here or not. But\nI agree that it does feel safer to apply something like:\n\n--- 8< ---\ndiff --git a/revision.c b/revision.c\nindex 3d78ea6a9a..21b3085465 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -834,7 +834,8 @@ static int rev_compare_tree(struct rev_info *revs,\n \treturn tree_difference;\n }\n\n-static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n+static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,\n+\t\t\t\t  int use_bloom_filter)\n {\n \tstruct tree *t1 = repo_get_commit_tree(the_repository, commit);\n \tint bloom_ret = 1;\n@@ -842,7 +843,7 @@ static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n \tif (!t1)\n \t\treturn 0;\n\n-\tif (revs->bloom_keys_nr) {\n+\tif (use_bloom_filter && revs->bloom_keys_nr) {\n \t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n \t\tif (!bloom_ret)\n \t\t\treturn 1;\n@@ -892,7 +893,7 @@ static int compact_treesame(struct rev_info *revs, struct commit *commit, unsign\n \t\tif (nth_parent != 0)\n \t\t\tdie(\"compact_treesame %u\", nth_parent);\n \t\told_same = !!(commit->object.flags & TREESAME);\n-\t\tif (rev_same_tree_as_empty(revs, commit))\n+\t\tif (rev_same_tree_as_empty(revs, commit, 1))\n \t\t\tcommit->object.flags |= TREESAME;\n \t\telse\n \t\t\tcommit->object.flags &= ~TREESAME;\n@@ -988,7 +989,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\treturn;\n\n \tif (!commit->parents) {\n-\t\tif (rev_same_tree_as_empty(revs, commit))\n+\t\tif (rev_same_tree_as_empty(revs, commit, 1))\n \t\t\tcommit->object.flags |= TREESAME;\n \t\treturn;\n \t}\n@@ -1069,7 +1070,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n\n \t\tcase REV_TREE_NEW:\n \t\t\tif (revs->remove_empty_trees &&\n-\t\t\t    rev_same_tree_as_empty(revs, p)) {\n+\t\t\t    rev_same_tree_as_empty(revs, p, 0)) {\n \t\t\t\t/* We are adding all the specified\n \t\t\t\t * paths from this parent, so the\n \t\t\t\t * history beyond this parent is not\n--- >8 ---\n\non top.\n\n> There is also the issue that count_bloom_filter_false_positive is\n> incremented even when no Bloom filters are present, but I think this is\n> fine (it matches the behavior of rev_compare_tree()).\n\nYep, agreed.\n\nThanks,\nTaylor\n"},{"id":"482881","messageId":"ZSQ3s3ZiRcvQIKOa@nand.local","threadId":"60225","inReplyTo":"ZSQ2XwbTM4DDLfJq@nand.local","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-10-09T17:26:11Z","receivedAt":"2023-10-09T17:26:22Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Oct 09, 2023 at 01:20:31PM -0400, Taylor Blau wrote:\n> On Mon, Oct 02, 2023 at 03:55:46PM -0700, Jonathan Tan wrote:\n> > As for the second issue, we can probably solve this by being defensive\n> > in rev_same_tree_as_empty() by only using the Bloom filter when the\n> > commit has no parents. Not sure if this is being overly defensive,\n> > though.\n>\n> I am also unsure whether we are being overly defensive here or not. But\n> I agree that it does feel safer to apply something like:\n\nNever mind, we are being overly defensive there. The goal here is to\navoid using a commit's Bloom filter in cases where we are acting as if a\ncommit is at the root of history, but in fact has parents.\n\nThis only happens when we return REV_TREE_NEW from a call to\n`rev_compare_tree(revs, p, commit, nth_parent)`. But we'll only get\nREV_TREE_NEW back if\n\n    repo_get_commit_tree(the_repository, p);\n\nreturns NULL. But when we call rev_same_tree_as_empty(revs, p) in the\nREV_TREE_NEW case, we return early as follows:\n\n    struct tree *t1 = repo_get_commit_tree(revs, p);\n    if (!t1)\n      return 0;\n\nSo we won't even consult the Bloom filter in that case, since t1 is NULL\nfor the same reason as what caused rev_compare_tree() to return\nREV_TREE_NEW in the first place.\n\nI am still dumbfounded by how we would ever get REV_TREE_NEW in the\nfirst place, but if we did, I think we would be OK here.\n\nThanks,\nTaylor\n"},{"id":"482907","messageId":"20231009205925.1915096-1-jonathantanmy@google.com","threadId":"60225","inReplyTo":"ZSQ3s3ZiRcvQIKOa@nand.local","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-10-09T20:59:25Z","receivedAt":"2023-10-09T20:59:32Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> This only happens when we return REV_TREE_NEW from a call to\n> `rev_compare_tree(revs, p, commit, nth_parent)`. But we'll only get\n> REV_TREE_NEW back if\n> \n>     repo_get_commit_tree(the_repository, p);\n> \n> returns NULL. But when we call rev_same_tree_as_empty(revs, p) in the\n> REV_TREE_NEW case, we return early as follows:\n> \n>     struct tree *t1 = repo_get_commit_tree(revs, p);\n>     if (!t1)\n>       return 0;\n> \n> So we won't even consult the Bloom filter in that case, since t1 is NULL\n> for the same reason as what caused rev_compare_tree() to return\n> REV_TREE_NEW in the first place.\n> \n> I am still dumbfounded by how we would ever get REV_TREE_NEW in the\n> first place, but if we did, I think we would be OK here.\n> \n> Thanks,\n> Taylor\n\nAh, good point. Your patch in\nhttps://lore.kernel.org/git/ZQnmTXUO94%2FQy8mq@nand.local/ looks good to\nme, then.\n"},{"id":"482999","messageId":"ZSWqStEpsFU0SmEm@nand.local","threadId":"60225","inReplyTo":"20231009205925.1915096-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] Not computing changed path filter for root commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-10-10T19:47:22Z","receivedAt":"2023-10-10T19:47:29Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Oct 09, 2023 at 01:59:25PM -0700, Jonathan Tan wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n> > This only happens when we return REV_TREE_NEW from a call to\n> > `rev_compare_tree(revs, p, commit, nth_parent)`. But we'll only get\n> > REV_TREE_NEW back if\n> >\n> >     repo_get_commit_tree(the_repository, p);\n> >\n> > returns NULL. But when we call rev_same_tree_as_empty(revs, p) in the\n> > REV_TREE_NEW case, we return early as follows:\n> >\n> >     struct tree *t1 = repo_get_commit_tree(revs, p);\n> >     if (!t1)\n> >       return 0;\n> >\n> > So we won't even consult the Bloom filter in that case, since t1 is NULL\n> > for the same reason as what caused rev_compare_tree() to return\n> > REV_TREE_NEW in the first place.\n> >\n> > I am still dumbfounded by how we would ever get REV_TREE_NEW in the\n> > first place, but if we did, I think we would be OK here.\n> >\n> > Thanks,\n> > Taylor\n>\n> Ah, good point. Your patch in\n> https://lore.kernel.org/git/ZQnmTXUO94%2FQy8mq@nand.local/ looks good to\n> me, then.\n\nOops, I made a mistake in the quoted portion, which is that we could get\nREV_TREE_NEW if the tree-diff itself only adds files. This is the\nnon-trivial case that we get when t1 is non-NULL, and we end up calling\n`diff_tree_oid()` which sets the static `tree_difference` variable.\n\nSo I think adding an nth_parent field (like you originally\nsuggested[^1]) makes sense.\n\nThanks,\nTaylor\n\n[^1]: Thanks for being patient with me ;-).\n"}]}