From: Taylor Blau <me@ttaylorr.com>
To: Derrick Stolee <stolee@gmail.com>
Cc: "SZEDER Gábor" <szeder.dev@gmail.com>,
"Taylor Blau" <me@ttaylorr.com>,
git@vger.kernel.org, peff@peff.net, dstolee@microsoft.com,
gitster@pobox.com
Subject: Re: [PATCH v3 01/14] commit-graph: introduce 'get_bloom_filter_settings()'
Date: Fri, 14 Aug 2020 16:17:32 -0400 [thread overview]
Message-ID: <20200814201732.GD30103@syl.lan> (raw)
In-Reply-To: <d525c35e-12fb-1918-c02b-d0323ee9b664@gmail.com>
On Wed, Aug 12, 2020 at 07:48:55AM -0400, Derrick Stolee wrote:
> On 8/11/2020 7:55 PM, SZEDER Gábor wrote:
> > On Tue, Aug 11, 2020 at 05:34:11PM -0400, Taylor Blau wrote:
> >> On Tue, Aug 11, 2020 at 11:27:16PM +0200, SZEDER Gábor wrote:
> >>> On Tue, Aug 11, 2020 at 05:21:18PM -0400, Taylor Blau wrote:
> >>>> On Tue, Aug 11, 2020 at 11:18:30PM +0200, SZEDER Gábor wrote:
> >>>>> On Tue, Aug 11, 2020 at 04:51:19PM -0400, Taylor Blau wrote:
> >>>>>> Many places in the code often need a pointer to the commit-graph's
> >>>>>> 'struct bloom_filter_settings', in which case they often take the value
> >>>>>> from the top-most commit-graph.
> >>>>>>
> >>>>>> In the non-split case, this works as expected. In the split case,
> >>>>>> however, things get a little tricky. Not all layers in a chain of
> >>>>>> incremental commit-graphs are required to themselves have Bloom data,
> >>>>>> and so whether or not some part of the code uses Bloom filters depends
> >>>>>> entirely on whether or not the top-most level of the commit-graph chain
> >>>>>> has Bloom filters.
> >>>>>>
> >>>>>> This has been the behavior since Bloom filters were introduced, and has
> >>>>>> been codified into the tests since a759bfa9ee (t4216: add end to end
> >>>>>> tests for git log with Bloom filters, 2020-04-06). In fact, t4216.130
> >>>>>> requires that Bloom filters are not used in exactly the case described
> >>>>>> earlier.
> >>>>>>
> >>>>>> There is no reason that this needs to be the case, since it is perfectly
> >>>>>> valid for commits in an earlier layer to have Bloom filters when commits
> >>>>>> in a newer layer do not.
> >>>>>>
> >>>>>> Since Bloom settings are guaranteed to be the same for any layer in a
> >>>>>> chain that has Bloom data,
> >>>>>
> >>>>> Is it? Where is that guaranteed?
>
> Perhaps instead of "guaranteed" we could say "Git never writes
> a commit-graph chain with different settings between layers."
>
> >>>> There is no mechanism whatsoever to customize these settings that is
> >>>> exposed to the user (except for the undocumented 'GIT_TEST' environment
> >>>> variables).
> >>>
> >>> Let me rephrase it, then: where is it written in the commit-graph
> >>> format specification that these must be the same in all layers?
> >>>
> >>> Nowhere.
> >>
> >> OK. We can certainly document that this is the case.
> >
> > IMO we absolutely must document this first; ideally it should have
> > been carefully considered and documented right from the start.
>
> You're right. One of the major difficulties in bringing a Bloom
> filter implementation to the commit-graph feature when we did was
> that the split commit-graph was introduced between our initial
> prototypes and when it was finally prepared for a full submission.
>
> There certainly are gaps in the implementation and documentation.
> I think Taylor is doing a great job by addressing one of those gaps
> in a focused, thoughtful way.
>
> > Some thougths about this:
> >
> > https://public-inbox.org/git/20200619140230.GB22200@szeder.dev/
>
> I appreciate your attention to detail. Your comments on the existing
> implementation do point out some of its shortcomings, and that is a
> valuable contribution.
>
> Actually converting those thoughts into patches is a lot of work.
>
> >> For this purpose,
> >> all we really care about is that the graph _has_ Bloom filters anywhere.
> >> If you wanted to return the exact matching settings, you could also
> >> provide a commit and return the settings belonging to the graph that
> >> contains that commit.
> >>
> >> In the case where we don't have a commit, we could use the default
> >> settings instead.
> >>
> >> I think that we are a little bit dealing with a problem that doesn't
> >> exist, since we do not document the sole method by which you would
> >> change these settings. So, maybe we can think more about this, but my
> >> preference would be to leave this patch alone.
> >
> > Other implementations can write split commit-graphs with modified path
> > Bloom filters as well, and at the moment there is nothing in the specs
> > that tells them not to use different Bloom filter settings in
> > different layers.
>
> You are 100% correct that there is a gap in documentation. That should
> be corrected at some point. (I don't consider it a blocker for this
> series.)
>
> But also: Git itself is the true test of a "correct" third-party
> implementation. libgit2 and JGit try to match Git, "warts and all".
> If another implementation wrote data that results in incorrect
> behavior by Git, then that implementation is wrong.
>
> Improving documentation can make those errors less likely.
I agree with this reasoning. Would anybody object to moving forward with
this series without a change in documentation today (but rather down the
road)?
> We also must design with "future Git" in mind, presenting it with
> enough flexibility to improve formats. The custom Bloom filter
> settings do allow that flexibility, but the requirement that all
> layers have identical settings exists for a reason (despite not
> being documented). It is important that any commit walk that intends
> to use the changed-path Bloom filters can compute the bloom keys
> for the test paths only once.
>
> Thanks,
> -Stolee
Thanks,
Taylor
next prev parent reply other threads:[~2020-08-14 20:17 UTC|newest]
Thread overview: 117+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-08-03 18:57 [PATCH 00/10] more miscellaneous Bloom filter improvements Taylor Blau
2020-08-03 18:57 ` [PATCH 01/10] commit-graph: introduce 'get_bloom_filter_settings()' Taylor Blau
2020-08-04 7:24 ` Jeff King
2020-08-04 20:08 ` Taylor Blau
2020-08-03 18:57 ` [PATCH 02/10] commit-graph: pass a 'struct repository *' in more places Taylor Blau
2020-08-03 18:57 ` [PATCH 03/10] t4216: use an '&&'-chain Taylor Blau
2020-08-03 18:57 ` [PATCH 04/10] t/helper/test-read-graph.c: prepare repo settings Taylor Blau
2020-08-03 18:57 ` [PATCH 05/10] commit-graph: respect 'commitgraph.readChangedPaths' Taylor Blau
2020-08-03 18:57 ` [PATCH 06/10] commit-graph.c: sort index into commits list Taylor Blau
2020-08-04 12:31 ` Derrick Stolee
2020-08-04 20:10 ` Taylor Blau
2020-08-03 18:57 ` [PATCH 07/10] commit-graph: add large-filters bitmap chunk Taylor Blau
2020-08-03 18:59 ` Taylor Blau
2020-08-04 12:57 ` Derrick Stolee
2020-08-03 18:57 ` [PATCH 08/10] bloom: split 'get_bloom_filter()' in two Taylor Blau
2020-08-04 13:00 ` Derrick Stolee
2020-08-04 20:12 ` Taylor Blau
2020-08-03 18:57 ` [PATCH 09/10] commit-graph: rename 'split_commit_graph_opts' Taylor Blau
2020-08-03 18:57 ` [PATCH 10/10] builtin/commit-graph.c: introduce '--max-new-filters=<n>' Taylor Blau
2020-08-04 13:03 ` Derrick Stolee
2020-08-04 20:14 ` Taylor Blau
2020-08-05 17:01 ` [PATCH v2 00/14] more miscellaneous Bloom filter improvements Taylor Blau
2020-08-05 17:01 ` [PATCH v2 01/14] commit-graph: introduce 'get_bloom_filter_settings()' Taylor Blau
2020-08-05 17:02 ` [PATCH v2 02/14] t4216: use an '&&'-chain Taylor Blau
2020-08-05 17:02 ` [PATCH v2 03/14] commit-graph: pass a 'struct repository *' in more places Taylor Blau
2020-08-05 17:02 ` [PATCH v2 04/14] t/helper/test-read-graph.c: prepare repo settings Taylor Blau
2020-08-05 17:02 ` [PATCH v2 05/14] commit-graph: respect 'commitGraph.readChangedPaths' Taylor Blau
2020-08-05 17:02 ` [PATCH v2 06/14] commit-graph.c: store maximum changed paths Taylor Blau
2020-08-05 17:02 ` [PATCH v2 07/14] bloom: split 'get_bloom_filter()' in two Taylor Blau
2020-08-05 17:02 ` [PATCH v2 08/14] bloom: use provided 'struct bloom_filter_settings' Taylor Blau
2020-08-05 17:02 ` [PATCH v2 09/14] bloom/diff: properly short-circuit on max_changes Taylor Blau
2020-08-05 17:02 ` [PATCH v2 10/14] commit-graph.c: sort index into commits list Taylor Blau
2020-08-05 17:02 ` [PATCH v2 11/14] csum-file.h: introduce 'hashwrite_be64()' Taylor Blau
2020-08-05 17:02 ` [PATCH v2 12/14] commit-graph: add large-filters bitmap chunk Taylor Blau
2020-08-05 21:01 ` Junio C Hamano
2020-08-05 21:17 ` Taylor Blau
2020-08-05 22:21 ` Junio C Hamano
2020-08-05 22:25 ` Taylor Blau
2020-08-11 13:48 ` Taylor Blau
2020-08-11 18:59 ` Junio C Hamano
2020-08-05 17:03 ` [PATCH v2 13/14] commit-graph: rename 'split_commit_graph_opts' Taylor Blau
2020-08-05 17:03 ` [PATCH v2 14/14] builtin/commit-graph.c: introduce '--max-new-filters=<n>' Taylor Blau
2020-08-11 20:51 ` [PATCH v3 00/14] more miscellaneous Bloom filter improvements Taylor Blau
2020-08-11 20:51 ` [PATCH v3 01/14] commit-graph: introduce 'get_bloom_filter_settings()' Taylor Blau
2020-08-11 21:18 ` SZEDER Gábor
2020-08-11 21:21 ` Taylor Blau
2020-08-11 21:27 ` SZEDER Gábor
2020-08-11 21:34 ` Taylor Blau
2020-08-11 23:55 ` SZEDER Gábor
2020-08-12 11:48 ` Derrick Stolee
2020-08-14 20:17 ` Taylor Blau [this message]
2020-08-11 20:51 ` [PATCH v3 02/14] t4216: use an '&&'-chain Taylor Blau
2020-08-11 20:51 ` [PATCH v3 03/14] commit-graph: pass a 'struct repository *' in more places Taylor Blau
2020-08-11 20:51 ` [PATCH v3 04/14] t/helper/test-read-graph.c: prepare repo settings Taylor Blau
2020-08-11 20:51 ` [PATCH v3 05/14] commit-graph: respect 'commitGraph.readChangedPaths' Taylor Blau
2020-08-11 20:51 ` [PATCH v3 06/14] commit-graph.c: store maximum changed paths Taylor Blau
2020-08-11 20:51 ` [PATCH v3 07/14] bloom: split 'get_bloom_filter()' in two Taylor Blau
2020-08-11 20:51 ` [PATCH v3 11/14] csum-file.h: introduce 'hashwrite_be64()' Taylor Blau
2020-08-11 20:51 ` [PATCH v3 08/14] bloom: use provided 'struct bloom_filter_settings' Taylor Blau
2020-08-11 20:51 ` [PATCH v3 09/14] bloom/diff: properly short-circuit on max_changes Taylor Blau
2020-08-11 20:52 ` [PATCH v3 10/14] commit-graph.c: sort index into commits list Taylor Blau
2020-08-11 20:52 ` [PATCH v3 12/14] commit-graph: add large-filters bitmap chunk Taylor Blau
2020-08-11 21:11 ` Derrick Stolee
2020-08-11 21:18 ` Taylor Blau
2020-08-11 22:05 ` Taylor Blau
2020-08-19 13:35 ` SZEDER Gábor
2020-09-02 20:23 ` Taylor Blau
2020-09-01 14:35 ` SZEDER Gábor
2020-09-02 20:40 ` Taylor Blau
2020-08-11 20:52 ` [PATCH v3 13/14] commit-graph: rename 'split_commit_graph_opts' Taylor Blau
2020-08-19 9:56 ` SZEDER Gábor
2020-09-02 21:02 ` Taylor Blau
2020-08-11 20:52 ` [PATCH v3 14/14] builtin/commit-graph.c: introduce '--max-new-filters=<n>' Taylor Blau
2020-08-12 11:49 ` SZEDER Gábor
2020-08-14 20:20 ` Taylor Blau
2020-08-17 22:50 ` SZEDER Gábor
2020-09-02 21:03 ` Taylor Blau
2020-08-12 12:29 ` Derrick Stolee
2020-08-14 20:10 ` Taylor Blau
2020-08-18 22:23 ` SZEDER Gábor
2020-09-03 16:35 ` Taylor Blau
2020-08-19 8:20 ` SZEDER Gábor
2020-09-03 16:42 ` Taylor Blau
2020-09-04 8:50 ` SZEDER Gábor
2020-09-01 14:36 ` SZEDER Gábor
2020-09-03 18:49 ` Taylor Blau
2020-09-03 21:45 ` [PATCH v3 00/14] more miscellaneous Bloom filter improvements Junio C Hamano
2020-09-03 22:33 ` Taylor Blau
2020-09-03 22:45 ` [PATCH v4 " Taylor Blau
2020-09-03 22:46 ` [PATCH v4 01/14] commit-graph: introduce 'get_bloom_filter_settings()' Taylor Blau
2020-09-03 22:46 ` [PATCH v4 02/14] t4216: use an '&&'-chain Taylor Blau
2020-09-03 22:46 ` [PATCH v4 03/14] commit-graph: pass a 'struct repository *' in more places Taylor Blau
2020-09-03 22:46 ` [PATCH v4 04/14] t/helper/test-read-graph.c: prepare repo settings Taylor Blau
2020-09-03 22:46 ` [PATCH v4 05/14] commit-graph: respect 'commitGraph.readChangedPaths' Taylor Blau
2020-09-03 22:46 ` [PATCH v4 06/14] commit-graph.c: store maximum changed paths Taylor Blau
2020-09-03 22:46 ` [PATCH v4 07/14] bloom: split 'get_bloom_filter()' in two Taylor Blau
2020-09-05 17:22 ` Jakub Narębski
2020-09-05 17:38 ` Taylor Blau
2020-09-05 17:50 ` Jakub Narębski
2020-09-05 18:01 ` Taylor Blau
2020-09-05 18:18 ` Jakub Narębski
2020-09-05 18:38 ` Taylor Blau
2020-09-05 18:55 ` Taylor Blau
2020-09-05 19:04 ` SZEDER Gábor
2020-09-05 19:49 ` Taylor Blau
2020-09-06 21:52 ` Junio C Hamano
2020-09-03 22:46 ` [PATCH v4 08/14] bloom: use provided 'struct bloom_filter_settings' Taylor Blau
2020-09-03 22:46 ` [PATCH v4 09/14] bloom/diff: properly short-circuit on max_changes Taylor Blau
2020-09-03 22:46 ` [PATCH v4 10/14] commit-graph.c: sort index into commits list Taylor Blau
2020-09-03 22:46 ` [PATCH v4 11/14] csum-file.h: introduce 'hashwrite_be64()' Taylor Blau
2020-09-04 20:18 ` René Scharfe
2020-09-04 20:22 ` Taylor Blau
2020-09-03 22:46 ` [PATCH v4 12/14] commit-graph: add large-filters bitmap chunk Taylor Blau
2020-09-03 22:46 ` [PATCH v4 13/14] commit-graph: rename 'split_commit_graph_opts' Taylor Blau
2020-09-04 15:20 ` Taylor Blau
2020-09-03 22:47 ` [PATCH v4 14/14] builtin/commit-graph.c: introduce '--max-new-filters=<n>' Taylor Blau
2020-09-04 14:39 ` [PATCH v4 00/14] more miscellaneous Bloom filter improvements Derrick Stolee
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=20200814201732.GD30103@syl.lan \
--to=me@ttaylorr.com \
--cc=dstolee@microsoft.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=peff@peff.net \
--cc=stolee@gmail.com \
--cc=szeder.dev@gmail.com \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public 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).