From: Derrick Stolee <stolee@gmail.com>
To: "SZEDER Gábor" <szeder.dev@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: Wed, 5 Aug 2020 13:08:52 -0400 [thread overview]
Message-ID: <58ae3044-fa07-8e88-414a-fa9b410957f9@gmail.com> (raw)
In-Reply-To: <cfa4e35e-e227-5862-6978-53e699a4a1d2@gmail.com>
On 8/4/2020 1:31 PM, Derrick Stolee wrote:
> On 8/4/2020 1:00 PM, SZEDER Gábor wrote:
>> 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.
>
> It looks like this part would not be too difficult.
Oh, my hubris! I gave this a shot for some time this morning. This
will definitely take some work to do right. Just changing the callbacks
to return 'int' is a wide-sweeping change, but the place where they are
called already has an 'int' return that means something different.
I'm not saying this is impossible. It just takes more attention and care
than I can currently devote, given my other works in progress right now.
>> - 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.
>
> Thanks for the pointer to that specific patch. You do a good job of
> describing your thought process, including why you used the callback
> approach instead of the diff queue approach. The main reason seemed to
> be memory overhead from populating the entire diff queue before
> checking the limit.
>
> However, if we are using the diff queue as the short-circuit, then
> perhaps that memory overhead isn't as much of a problem?
>
> You admit yourself, that
>
> This patch implements a more efficient, but more complex, approach:
>
> The logic around matching prefixes definitely seems complex and
> hard to test, especially around the file/directory changes with the
> sort order problems that have plagued similar prefix checks recently.
> I'm not doubting your implementation, just saying that the complexity
> is worth considering before jumping to that solution too quickly.
>
> To sum up, I intend to start with a fix that uses the diff queue
> count as a limit, then try the callback approach to see if there are
> measurable improvements in performance.
That fix is now available [1].
[1] https://lore.kernel.org/git/d1c4bbcaa9627068d5d9fbd0e4a2e8c8834a4bd3.1596646576.git.me@ttaylorr.com/
Again, the callback approach seems promising. The complexity is
stopping me from trying to apply it on top of the current
implementation, while I should be focusing on other things. I completely
believe that that approach is faster and more memory-efficient. I would
love to test and review a patch that takes that approach here.
Thanks,
-Stolee
next prev parent reply other threads:[~2020-08-05 17:22 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
2020-08-04 17:31 ` Derrick Stolee
2020-08-05 17:08 ` Derrick Stolee [this message]
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=58ae3044-fa07-8e88-414a-fa9b410957f9@gmail.com \
--to=stolee@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=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).