* [PATCH] subtree: fix split processing with multiple subtrees present
@ 2023-09-18 20:05 Zach FettersMoore via GitGitGadget
2023-09-18 23:31 ` Junio C Hamano
2023-09-19 1:04 ` Junio C Hamano
0 siblings, 2 replies; 3+ messages in thread
From: Zach FettersMoore via GitGitGadget @ 2023-09-18 20:05 UTC (permalink / raw)
To: git; +Cc: Zach FettersMoore, Zach FettersMoore
From: Zach FettersMoore <zach.fetters@apollographql.com>
When there are multiple subtrees present in a repository and they are
all using 'git subtree split', the 'split' command can take a
significant (and constantly growing) amount of time to run even when
using the '--rejoin' flag. This is due to the fact that when processing
commits to determine the last known split to start from when looking
for changes, if there has been a split/merge done from another subtree
there will be 2 split commits, one mainline and one subtree, for the
second subtree that are part of the processing. The non-mainline
subtree split commit will cause the processing to always need to search
the entire history of the given subtree as part of its processing even
though those commits are totally irrelevant to the current subtree
split being run.
In the diagram below, 'M' represents the mainline repo branch, 'A'
represents one subtree, and 'B' represents another. M3 and B1 represent
a split commit for subtree B that was created from commit M4. M2 and A1
represent a split commit made from subtree A that was also created
based on changes back to and including M4. M1 represents new changes to
the repo, in this scenario if you try to run a 'git subtree split
--rejoin' for subtree B, commits M1, M2, and A1, will be included in
the processing of changes for the new split commit since the last
split/rejoin for subtree B was at M3. The issue is that by having A1
included in this processing the command ends up needing to processing
every commit down tree A even though none of that is needed or relevant
to the current command and result.
M1
| \ \
M2 | |
| A1 |
M3 | |
| | B1
M4 | |
So this commit makes a change to the processing of commits for the split
command in order to ignore non-mainline commits from other subtrees such
as A1 in the diagram by adding a new function
'should_ignore_subtree_commit' which is called during
'process_split_commit'. This allows the split/rejoin processing to still
function as expected but removes all of the unnecessary processing that
takes place currently which greatly inflates the processing time.
Signed-off-by: Zach FettersMoore <zach.fetters@apollographql.com>
---
subtree: fix split processing with multiple subtrees present
When there are multiple subtrees in a repo and git subtree split
--rejoin is being used for the subtrees, the processing of commits for a
new split can take a significant (and constantly growing) amount of time
because the split commits from other subtrees cause the processing to
have to scan the entire history of the other subtree(s). This patch
filters out the other subtree split commits that are unnecessary for the
split commit processing.
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1587%2FBobaFetters%2Fzf%2Fmulti-subtree-processing-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1587/BobaFetters/zf/multi-subtree-processing-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1587
contrib/subtree/git-subtree.sh | 17 +++++++++++++++++
1 file changed, 17 insertions(+)
diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
index e0c5d3b0de6..e9250dfb019 100755
--- a/contrib/subtree/git-subtree.sh
+++ b/contrib/subtree/git-subtree.sh
@@ -778,12 +778,29 @@ ensure_valid_ref_format () {
die "fatal: '$1' does not look like a ref"
}
+# Usage: check if a commit from another subtree should be ignored from processing for splits
+should_ignore_subtree_commit () {
+ if [ "$(git log -1 --grep="git-subtree-dir:" $1)" ]
+ then
+ if [[ -z "$(git log -1 --grep="git-subtree-mainline:" $1)" && -z "$(git log -1 --grep="git-subtree-dir: $dir$" $1)" ]]
+ then
+ return 0
+ fi
+ fi
+ return 1
+}
+
# Usage: process_split_commit REV PARENTS
process_split_commit () {
assert test $# = 2
local rev="$1"
local parents="$2"
+ if should_ignore_subtree_commit $rev
+ then
+ return
+ fi
+
if test $indent -eq 0
then
revcount=$(($revcount + 1))
base-commit: bda494f4043963b9ec9a1ecd4b19b7d1cd9a0518
--
gitgitgadget
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH] subtree: fix split processing with multiple subtrees present
2023-09-18 20:05 [PATCH] subtree: fix split processing with multiple subtrees present Zach FettersMoore via GitGitGadget
@ 2023-09-18 23:31 ` Junio C Hamano
2023-09-19 1:04 ` Junio C Hamano
1 sibling, 0 replies; 3+ messages in thread
From: Junio C Hamano @ 2023-09-18 23:31 UTC (permalink / raw)
To: Zach FettersMoore via GitGitGadget; +Cc: git, Zach FettersMoore
"Zach FettersMoore via GitGitGadget" <gitgitgadget@gmail.com>
writes:
> contrib/subtree/git-subtree.sh | 17 +++++++++++++++++
> 1 file changed, 17 insertions(+)
>
> diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
> index e0c5d3b0de6..e9250dfb019 100755
> --- a/contrib/subtree/git-subtree.sh
> +++ b/contrib/subtree/git-subtree.sh
> @@ -778,12 +778,29 @@ ensure_valid_ref_format () {
> die "fatal: '$1' does not look like a ref"
> }
>
> +# Usage: check if a commit from another subtree should be ignored from processing for splits
> +should_ignore_subtree_commit () {
> + if [ "$(git log -1 --grep="git-subtree-dir:" $1)" ]
> + then
> + if [[ -z "$(git log -1 --grep="git-subtree-mainline:" $1)" && -z "$(git log -1 --grep="git-subtree-dir: $dir$" $1)" ]]
> + then
> + return 0
> + fi
> + fi
> + return 1
> +}
>
> # Usage: process_split_commit REV PARENTS
> process_split_commit () {
> assert test $# = 2
> local rev="$1"
> local parents="$2"
>
> + if should_ignore_subtree_commit $rev
> + then
> + return
> + fi
> +
Please do not violate Documentation/CodingGuidelines for our shell
scripted Porcelain, even if it is a script in contrib/ and also
please avoid bash-isms.
Also doesn't "subtree" have its own test? If this change is a fix
for some problem(s), can we have a test or two that demonstrate how
the current code without the patch is broken?
Thanks.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] subtree: fix split processing with multiple subtrees present
2023-09-18 20:05 [PATCH] subtree: fix split processing with multiple subtrees present Zach FettersMoore via GitGitGadget
2023-09-18 23:31 ` Junio C Hamano
@ 2023-09-19 1:04 ` Junio C Hamano
1 sibling, 0 replies; 3+ messages in thread
From: Junio C Hamano @ 2023-09-19 1:04 UTC (permalink / raw)
To: Zach FettersMoore via GitGitGadget; +Cc: git, Zach FettersMoore
"Zach FettersMoore via GitGitGadget" <gitgitgadget@gmail.com>
writes:
> In the diagram below, 'M' represents the mainline repo branch, 'A'
> represents one subtree, and 'B' represents another. M3 and B1 represent
> a split commit for subtree B that was created from commit M4. M2 and A1
> represent a split commit made from subtree A that was also created
> based on changes back to and including M4. M1 represents new changes to
> the repo, in this scenario if you try to run a 'git subtree split
> --rejoin' for subtree B, commits M1, M2, and A1, will be included in
> the processing of changes for the new split commit since the last
> split/rejoin for subtree B was at M3. The issue is that by having A1
> included in this processing the command ends up needing to processing
> every commit down tree A even though none of that is needed or relevant
> to the current command and result.
>
> M1
> | \ \
> M2 | |
> | A1 |
> M3 | |
> | | B1
> M4 | |
The above paragraph explains which different things you drew in the
diagram are representing, but it is not clear how they relate to
each other. Do they for example depict parent-child commit
relationship? What are the wide gaps between these three tracks and
what are the short angled lines leaning to the left near the tip?
Is the time/topology flowing from bottom to top?
> diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
> index e0c5d3b0de6..e9250dfb019 100755
> --- a/contrib/subtree/git-subtree.sh
> +++ b/contrib/subtree/git-subtree.sh
> @@ -778,12 +778,29 @@ ensure_valid_ref_format () {
> die "fatal: '$1' does not look like a ref"
> }
>
> +# Usage: check if a commit from another subtree should be ignored from processing for splits
Way overlong line. Please split them accordingly. I won't comment
on what CodingGuidelines tells us already, in this review, but have
a few comments here:
> +should_ignore_subtree_commit () {
> + if [ "$(git log -1 --grep="git-subtree-dir:" $1)" ]
> + then
> + if [[ -z "$(git log -1 --grep="git-subtree-mainline:" $1)" && -z "$(git log -1 --grep="git-subtree-dir: $dir$" $1)" ]]
Here $dir is a free variable that comes from outside. The caller
does not supply it as a parameter to this function (and the caller
does not receive it as its parameter from its caller). Yet the file
as a whole seems to liberally make assignments to it ("git grep dir="
on the file counts 7 assignments). Are we sure we are looking for
the right $dir in this particular grep?
Side note: I am not familiar with this part of the code at
all, so do not take it as "here is a bug", but more as "this
smells error prone."
Also can $dir have regular expressions special characters? "The
existing code and new code alike, git-subtree is not prepared to
handle directory names with RE special characters well at all, so
do not use them if you do not want your history broken" is an
acceptable answer.
The caller of this function process_split_commit is cmd_split and
process_split_commit (hence this function) is called repeatedly
inside a loop. This function makes a traversal over the entire
history for each and every iteration in "good" cases where there is
no 'mainline' or 'subtree-dir' commits for the given $dir.
I wonder if it is more efficient to enumerate all commits that hits
these grep criteria in the cmd_split before it starts to call
process_split_commit repeatedly. If it knows which commit can be
ignored beforehand, it can skip and not call process_split_commit,
no?
> + then
> + return 0
> + fi
> + fi
> + return 1
> +}
> +
> # Usage: process_split_commit REV PARENTS
> process_split_commit () {
> assert test $# = 2
> local rev="$1"
> local parents="$2"
These seem to assume that $1 and $2 can have $IFS in them, so
shouldn't ...
> + if should_ignore_subtree_commit $rev
... this call too enclose $rev inside a pair of double-quotes for
consistency? We know the loop in the cmd_split that calls this
function is reading from "rev-list --parents" and $rev is a 40-hex
commit object name (and $parents can have more than one 40-hex
commit object names separated with SP), so it is safe to leave $rev
unquoted, but it pays to be consistent to help make the code more
readable.
> + then
> + return
> + fi
> +
> if test $indent -eq 0
> then
> revcount=$(($revcount + 1))
>
> base-commit: bda494f4043963b9ec9a1ecd4b19b7d1cd9a0518
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-09-19 1:04 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-09-18 20:05 [PATCH] subtree: fix split processing with multiple subtrees present Zach FettersMoore via GitGitGadget
2023-09-18 23:31 ` Junio C Hamano
2023-09-19 1:04 ` Junio C Hamano
Code repositories for project(s) associated with this public inbox
https://80x24.org/pub/scm/git/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).