diff mbox series

[v4] subtree: fix split processing with multiple subtrees present

Message ID pull.1587.v4.git.1698347871200.gitgitgadget@gmail.com (mailing list archive)
State New, archived
Headers show
Series [v4] subtree: fix split processing with multiple subtrees present | expand

Commit Message

Zach FettersMoore Oct. 26, 2023, 7:17 p.m. UTC
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.

Added a test to validate that the proposed fix
solves the issue.

The test accomplishes this by checking the output
of the split command to ensure the output from
the progress of 'process_split_commit' function
that represents the 'extracount' of commits
processed does not increment.

This was tested against the original functionality
to show the test failed, and then with this fix
to show the test passes.

This illustrated that when using multiple subtrees,
A and B, when doing a split on subtree B, the
processing does not traverse the entire history
of subtree A which is unnecessary and would cause
the 'extracount' of processed commits to climb
based on the number of commits in the history of
subtree A.

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-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1587/BobaFetters/zf/multi-subtree-processing-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/1587

Range-diff vs v3:

 1:  43175154a82 < -:  ----------- subtree: fix split processing with multiple subtrees present
 2:  d6811daf7cf < -:  ----------- subtree: changing location of commit ignore processing
 3:  eff8bfcc042 ! 1:  353152910eb subtree: adding test to validate fix
     @@ Metadata
      Author: Zach FettersMoore <zach.fetters@apollographql.com>
      
       ## Commit message ##
     -    subtree: adding test to validate fix
     +    subtree: fix split processing with multiple subtrees present
      
     -    Adding a test to validate that the proposed fix
     +    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.
     +
     +    Added a test to validate that the proposed fix
          solves the issue.
      
          The test accomplishes this by checking the output
     @@ Commit message
      
          Signed-off-by: Zach FettersMoore <zach.fetters@apollographql.com>
      
     + ## contrib/subtree/git-subtree.sh ##
     +@@ contrib/subtree/git-subtree.sh: 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_split_commit () {
     ++  if test -n "$(git log -1 --grep="git-subtree-dir:" $1)"
     ++  then
     ++    if test -z "$(git log -1 --grep="git-subtree-mainline:" $1)" &&
     ++			test -z "$(git log -1 --grep="git-subtree-dir: $arg_prefix$" $1)"
     ++    then
     ++      return 0
     ++    fi
     ++  fi
     ++  return 1
     ++}
     ++
     + # Usage: process_split_commit REV PARENTS
     + process_split_commit () {
     + 	assert test $# = 2
     +@@ contrib/subtree/git-subtree.sh: cmd_split () {
     + 	eval "$grl" |
     + 	while read rev parents
     + 	do
     +-		process_split_commit "$rev" "$parents"
     ++		if should_ignore_subtree_split_commit "$rev"
     ++		then
     ++			continue
     ++		fi
     ++		parsedParents=''
     ++		for parent in $parents
     ++		do
     ++			should_ignore_subtree_split_commit "$parent"
     ++			if test $? -eq 1
     ++			then
     ++				parsedParents+="$parent "
     ++			fi
     ++		done
     ++		process_split_commit "$rev" "$parsedParents"
     + 	done || exit $?
     + 
     + 	latest_new=$(cache_get latest_new) || exit $?
     +
       ## contrib/subtree/t/t7900-subtree.sh ##
      @@ contrib/subtree/t/t7900-subtree.sh: test_expect_success 'split sub dir/ with --rejoin' '
       	)
     @@ contrib/subtree/t/t7900-subtree.sh: test_expect_success 'split sub dir/ with --r
      +	) &&
      +	(
      +		cd "$test_count" &&
     -+		test "$(git subtree split --prefix=subBDir --squash --rejoin -d -m "Sub B Split 1" 2>&1 | grep -w "\[1\]")" = ""
     ++		test "$(git subtree split --prefix=subBDir --squash --rejoin \
     ++		 -d -m "Sub B Split 1" 2>&1 | grep -w "\[1\]")" = ""
      +	)
      +'
      +


 contrib/subtree/git-subtree.sh     | 29 ++++++++++++++++++++-
 contrib/subtree/t/t7900-subtree.sh | 42 ++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+), 1 deletion(-)


base-commit: bda494f4043963b9ec9a1ecd4b19b7d1cd9a0518

Comments

Christian Couder Nov. 18, 2023, 11:28 a.m. UTC | #1
On Thu, Oct 26, 2023 at 9:18 PM Zach FettersMoore via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> 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.

Thanks for your continued work on this!

I am not familiar with git subtree so I might miss obvious things. On
the other hand, my comments might help increase a bit the number of
people who could review this patch.

> 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         |       |

About the above, Junio already commented the following:

-> 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?

and it doesn't look like you have addressed that comment.

When you say "M3 and B1 represent a split commit for subtree B that
was created from commit M4." I am not sure what it means exactly.
Could you give example commands that could have created the M3 and B1
commits?

> 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.

Could you tell a bit more what kind of processing time reduction is or
would be possible on what kind of repo? Have you benchmark-ed or just
timed this somehow on one of your repos or better on an open source
repo (so that we could reproduce if we wanted)?

> Added a test to validate that the proposed fix
> solves the issue.
>
> The test accomplishes this by checking the output
> of the split command to ensure the output from
> the progress of 'process_split_commit' function
> that represents the 'extracount' of commits
> processed does not increment.

Does not increment compared to what?

> This was tested against the original functionality
> to show the test failed, and then with this fix
> to show the test passes.
>
> This illustrated that when using multiple subtrees,
> A and B, when doing a split on subtree B, the
> processing does not traverse the entire history
> of subtree A which is unnecessary and would cause
> the 'extracount' of processed commits to climb
> based on the number of commits in the history of
> subtree A.

Does this mean that the test checks that the extracount is the same
when subtree A exists as when it doesn't exist?

[...]

>  contrib/subtree/git-subtree.sh     | 29 ++++++++++++++++++++-
>  contrib/subtree/t/t7900-subtree.sh | 42 ++++++++++++++++++++++++++++++
>  2 files changed, 70 insertions(+), 1 deletion(-)
>
> diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
> index e0c5d3b0de6..e69991a9d80 100755
> --- a/contrib/subtree/git-subtree.sh
> +++ b/contrib/subtree/git-subtree.sh
> @@ -778,6 +778,20 @@ 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_split_commit () {

Maybe adding:

    assert test $# = 1
    local rev="$1"

here, and using $rev instead of $1 in this function could make things
a bit clearer and similar to what is done in other functions.

> +  if test -n "$(git log -1 --grep="git-subtree-dir:" $1)"
> +  then
> +    if test -z "$(git log -1 --grep="git-subtree-mainline:" $1)" &&
> +                       test -z "$(git log -1 --grep="git-subtree-dir: $arg_prefix$" $1)"
> +    then
> +      return 0
> +    fi
> +  fi
> +  return 1
> +}

The above doesn't seem to be properly indented. We use tabs not spaces.

>  # Usage: process_split_commit REV PARENTS
>  process_split_commit () {
>         assert test $# = 2
> @@ -963,7 +977,20 @@ cmd_split () {
>         eval "$grl" |
>         while read rev parents
>         do
> -               process_split_commit "$rev" "$parents"
> +               if should_ignore_subtree_split_commit "$rev"
> +               then
> +                       continue
> +               fi
> +               parsedParents=''

It seems to me that we name variables "parsed_parents" (or sometimes
"parsedparents") rather than "parsedParents".

> +               for parent in $parents
> +               do
> +                       should_ignore_subtree_split_commit "$parent"
> +                       if test $? -eq 1

I think the 2 lines above could be replaced by:

+                       if ! should_ignore_subtree_split_commit "$parent"

> +                       then
> +                               parsedParents+="$parent "

It doesn't seem to me that we use "+=" much in our shell scripts.
https://www.shellcheck.net/ emits the following:

(warning): In POSIX sh, += is undefined.

so I guess we don't use it because it's not available in some usual shells.

(I haven't checked the script with https://www.shellcheck.net/ before
and after your patch, but it might help avoid bash-isms and such
issues.)

> +                       fi
> +               done
> +               process_split_commit "$rev" "$parsedParents"
>         done || exit $?

It looks like we use "exit $?" a lot in git-subtree.sh while we use
just "exit" most often elsewhere. Not sure why.

>         latest_new=$(cache_get latest_new) || exit $?
> diff --git a/contrib/subtree/t/t7900-subtree.sh b/contrib/subtree/t/t7900-subtree.sh
> index 49a21dd7c9c..87d59afd761 100755
> --- a/contrib/subtree/t/t7900-subtree.sh
> +++ b/contrib/subtree/t/t7900-subtree.sh
> @@ -385,6 +385,48 @@ test_expect_success 'split sub dir/ with --rejoin' '
>         )
>  '
>
> +test_expect_success 'split with multiple subtrees' '
> +       subtree_test_create_repo "$test_count" &&
> +       subtree_test_create_repo "$test_count/subA" &&
> +       subtree_test_create_repo "$test_count/subB" &&
> +       test_create_commit "$test_count" main1 &&
> +       test_create_commit "$test_count/subA" subA1 &&
> +       test_create_commit "$test_count/subA" subA2 &&
> +       test_create_commit "$test_count/subA" subA3 &&
> +       test_create_commit "$test_count/subB" subB1 &&
> +       (
> +               cd "$test_count" &&
> +               git fetch ./subA HEAD &&
> +               git subtree add --prefix=subADir FETCH_HEAD
> +       ) &&
> +       (
> +               cd "$test_count" &&
> +               git fetch ./subB HEAD &&
> +               git subtree add --prefix=subBDir FETCH_HEAD
> +       ) &&
> +       test_create_commit "$test_count" subADir/main-subA1 &&
> +       test_create_commit "$test_count" subBDir/main-subB1 &&
> +       (
> +               cd "$test_count" &&
> +               git subtree split --prefix=subADir --squash --rejoin -m "Sub A Split 1"
> +       ) &&

Not sure why there are so many sub-shells used, and why the -C option
is not used instead to tell Git to work in a subdirectory. I guess you
copied what most existing (old) tests in this test script do.

For example perhaps the 4 line above could be replaced by just:

+               git -C "$test_count" subtree split --prefix=subADir
--squash --rejoin -m "Sub A Split 1" &&

> +       (
> +               cd "$test_count" &&
> +               git subtree split --prefix=subBDir --squash --rejoin -m "Sub B Split 1"
> +       ) &&
> +       test_create_commit "$test_count" subADir/main-subA2 &&
> +       test_create_commit "$test_count" subBDir/main-subB2 &&
> +       (
> +               cd "$test_count" &&
> +               git subtree split --prefix=subADir --squash --rejoin -m "Sub A Split 2"
> +       ) &&
> +       (
> +               cd "$test_count" &&
> +               test "$(git subtree split --prefix=subBDir --squash --rejoin \
> +                -d -m "Sub B Split 1" 2>&1 | grep -w "\[1\]")" = ""
> +       )
> +'

It's not clear to me what the test is doing. Maybe you could split it
into 2 tests. Perhaps one setting up a repo with multiple subtrees and
one checking that a new split ignores other subtree split commits.
Perhaps adding a few comments would help too.

Best,
Christian.
Zach FettersMoore Nov. 28, 2023, 9:04 p.m. UTC | #2
>> 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         |       |

> About the above, Junio already commented the following:
>
> -> 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?
>
> and it doesn't look like you have addressed that comment.
>
> When you say "M3 and B1 represent a split commit for subtree B that
> was created from commit M4." I am not sure what it means exactly.
> Could you give example commands that could have created the M3 and B1
> commits?

I removed the diagram from the commit message since it seems a little
unclear, and in its place I added an example of an open source repo
(which I am currently using the fix in) and the commands to replicate
the issue. Hopefully that better illustrates how I came across the issue
and what it is.

>> 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.

> Could you tell a bit more what kind of processing time reduction is or
> would be possible on what kind of repo? Have you benchmark-ed or just
> timed this somehow on one of your repos or better on an open source
> repo (so that we could reproduce if we wanted)?

I added some extra info for this to the commit message as well, but to
answer your question yes I discovered and benchmarked this issue in a
repo I help maintain. I was seeing splits take upwards of 12 minutes
before the fix, and after they were taking only seconds. Also provided
infor on the repo and how to reproduce in the updated commit message.

>> Added a test to validate that the proposed fix
>> solves the issue.
>>
>> The test accomplishes this by checking the output
>> of the split command to ensure the output from
>> the progress of 'process_split_commit' function
>> that represents the 'extracount' of commits
>> processed does not increment.

> Does not increment compared to what?

I reworded this to say the 'extracount' remains at 0 since
there should be no extra processed commits from the second subtree
in the test.

>> This was tested against the original functionality
>> to show the test failed, and then with this fix
>> to show the test passes.
>>
>> This illustrated that when using multiple subtrees,
>> A and B, when doing a split on subtree B, the
>> processing does not traverse the entire history
>> of subtree A which is unnecessary and would cause
>> the 'extracount' of processed commits to climb
>> based on the number of commits in the history of
>> subtree A.

> Does this mean that the test checks that the extracount is the same
> when subtree A exists as when it doesn't exist?

This means the test is checking that the 'extracount' remains at
0, because anything above 0 would mean commits from subtree A were
being processed, which is where the issue stems from.

>>  contrib/subtree/git-subtree.sh     | 29 ++++++++++++++++++++-
>>  contrib/subtree/t/t7900-subtree.sh | 42 ++++++++++++++++++++++++++++++
>>  2 files changed, 70 insertions(+), 1 deletion(-)
>>
>> diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree=
>.sh
>> index e0c5d3b0de6..e69991a9d80 100755
>> --- a/contrib/subtree/git-subtree.sh
>> +++ b/contrib/subtree/git-subtree.sh
>> @@ -778,6 +778,20 @@ 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_split_commit () {

> Maybe adding:
>
>     assert test $# =3D 1
>     local rev=3D"$1"
>
> here, and using $rev instead of $1 in this function could make things
> a bit clearer and similar to what is done in other functions.

Updated.

>> +  if test -n "$(git log -1 --grep=3D"git-subtree-dir:" $1)"
>> +  then
>> +    if test -z "$(git log -1 --grep=3D"git-subtree-mainline:" $1)" &&
>> +                       test -z "$(git log -1 --grep=3D"git-subtree-dir: =
>>  $arg_prefix$" $1)"
>> +    then
>> +      return 0
>> +    fi
>> +  fi
>> +  return 1
>> +}

> The above doesn't seem to be properly indented. We use tabs not spaces.

Fixed.

>>  # Usage: process_split_commit REV PARENTS
>>  process_split_commit () {
>>         assert test $# =3D 2
>> @@ -963,7 +977,20 @@ cmd_split () {
>>         eval "$grl" |
>>         while read rev parents
>>         do
>> -               process_split_commit "$rev" "$parents"
>> +               if should_ignore_subtree_split_commit "$rev"
>> +               then
>> +                       continue
>> +               fi
>> +               parsedParents=3D''

> It seems to me that we name variables "parsed_parents" (or sometimes
> "parsedparents") rather than "parsedParents".

Fixed.

>> +               for parent in $parents
>> +               do
>> +                       should_ignore_subtree_split_commit "$parent"
>> +                       if test $? -eq 1

> I think the 2 lines above could be replaced by:
>
> +                       if ! should_ignore_subtree_split_commit "$parent"

Updated.

>> +                       then
>> +                               parsedParents+=3D"$parent "

> It doesn't seem to me that we use "+=3D" much in our shell scripts.
> https://www.shellcheck.net/ emits the following:
>
> (warning): In POSIX sh, +=3D is undefined.
>
> so I guess we don't use it because it's not available in some usual shells.
>
> (I haven't checked the script with https://www.shellcheck.net/ before
> and after your patch, but it might help avoid bash-isms and such
> issues.)

Updated this to remove the '+=' usage.

>> +                       fi
>> +               done
>> +               process_split_commit "$rev" "$parsedParents"
>>         done || exit $?

> It looks like we use "exit $?" a lot in git-subtree.sh while we use
> just "exit" most often elsewhere. Not sure why.

Yea I am unsure of the reasoning of that, I was just trying to follow the
what the existing script was already doing.

>>         latest_new=3D$(cache_get latest_new) || exit $?
>> diff --git a/contrib/subtree/t/t7900-subtree.sh b/contrib/subtree/t/t7900=
>> -subtree.sh
>> index 49a21dd7c9c..87d59afd761 100755
>> --- a/contrib/subtree/t/t7900-subtree.sh
>> +++ b/contrib/subtree/t/t7900-subtree.sh
>> @@ -385,6 +385,48 @@ test_expect_success 'split sub dir/ with --rejoin' '
>>         )
>>  '
>>
>> +test_expect_success 'split with multiple subtrees' '
>> +       subtree_test_create_repo "$test_count" &&
>> +       subtree_test_create_repo "$test_count/subA" &&
>> +       subtree_test_create_repo "$test_count/subB" &&
>> +       test_create_commit "$test_count" main1 &&
>> +       test_create_commit "$test_count/subA" subA1 &&
>> +       test_create_commit "$test_count/subA" subA2 &&
>> +       test_create_commit "$test_count/subA" subA3 &&
>> +       test_create_commit "$test_count/subB" subB1 &&
>> +       (
>> +               cd "$test_count" &&
>> +               git fetch ./subA HEAD &&
>> +               git subtree add --prefix=3DsubADir FETCH_HEAD
>> +       ) &&
>> +       (
>> +               cd "$test_count" &&
>> +               git fetch ./subB HEAD &&
>> +               git subtree add --prefix=3DsubBDir FETCH_HEAD
>> +       ) &&
>> +       test_create_commit "$test_count" subADir/main-subA1 &&
>> +       test_create_commit "$test_count" subBDir/main-subB1 &&
>> +       (
>> +               cd "$test_count" &&
>> +               git subtree split --prefix=3DsubADir --squash --rejoin -m=
>> "Sub A Split 1"
>> +       ) &&

> Not sure why there are so many sub-shells used, and why the -C option
> is not used instead to tell Git to work in a subdirectory. I guess you
> copied what most existing (old) tests in this test script do.
>
> For example perhaps the 4 line above could be replaced by just:
>
> +               git -C "$test_count" subtree split --prefix=3DsubADir
> --squash --rejoin -m "Sub A Split 1" &&

Yea I was following what was being done in other existing tests, although
this seems like a better way to do this so I updated the test to remove
the extra sub-shells.

>> +       (
>> +               cd "$test_count" &&
>> +               git subtree split --prefix=3DsubBDir --squash --rejoin -m=
>> "Sub B Split 1"
>> +       ) &&
>> +       test_create_commit "$test_count" subADir/main-subA2 &&
>> +       test_create_commit "$test_count" subBDir/main-subB2 &&
>> +       (
>> +               cd "$test_count" &&
>> +               git subtree split --prefix=3DsubADir --squash --rejoin -m=
>> "Sub A Split 2"
>> +       ) &&
>> +       (
>> +               cd "$test_count" &&
>> +               test "$(git subtree split --prefix=3DsubBDir --squash --r=
>> ejoin \
>> +                -d -m "Sub B Split 1" 2>&1 | grep -w "\[1\]")" =3D ""
>> +       )
>> +'

> It's not clear to me what the test is doing. Maybe you could split it
> into 2 tests. Perhaps one setting up a repo with multiple subtrees and
> one checking that a new split ignores other subtree split commits.
> Perhaps adding a few comments would help too.

Added some comments before the test to describe the steps the test is taking in
order to verify the desired behavior.


On Sat, Nov 18, 2023 at 6:28 AM Christian Couder
<christian.couder@gmail.com> wrote:
>
> On Thu, Oct 26, 2023 at 9:18 PM Zach FettersMoore via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
> >
> > 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.
>
> Thanks for your continued work on this!
>
> I am not familiar with git subtree so I might miss obvious things. On
> the other hand, my comments might help increase a bit the number of
> people who could review this patch.
>
> > 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         |       |
>
> About the above, Junio already commented the following:
>
> -> 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?
>
> and it doesn't look like you have addressed that comment.
>
> When you say "M3 and B1 represent a split commit for subtree B that
> was created from commit M4." I am not sure what it means exactly.
> Could you give example commands that could have created the M3 and B1
> commits?
>
> > 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.
>
> Could you tell a bit more what kind of processing time reduction is or
> would be possible on what kind of repo? Have you benchmark-ed or just
> timed this somehow on one of your repos or better on an open source
> repo (so that we could reproduce if we wanted)?
>
> > Added a test to validate that the proposed fix
> > solves the issue.
> >
> > The test accomplishes this by checking the output
> > of the split command to ensure the output from
> > the progress of 'process_split_commit' function
> > that represents the 'extracount' of commits
> > processed does not increment.
>
> Does not increment compared to what?
>
> > This was tested against the original functionality
> > to show the test failed, and then with this fix
> > to show the test passes.
> >
> > This illustrated that when using multiple subtrees,
> > A and B, when doing a split on subtree B, the
> > processing does not traverse the entire history
> > of subtree A which is unnecessary and would cause
> > the 'extracount' of processed commits to climb
> > based on the number of commits in the history of
> > subtree A.
>
> Does this mean that the test checks that the extracount is the same
> when subtree A exists as when it doesn't exist?
>
> [...]
>
> >  contrib/subtree/git-subtree.sh     | 29 ++++++++++++++++++++-
> >  contrib/subtree/t/t7900-subtree.sh | 42 ++++++++++++++++++++++++++++++
> >  2 files changed, 70 insertions(+), 1 deletion(-)
> >
> > diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
> > index e0c5d3b0de6..e69991a9d80 100755
> > --- a/contrib/subtree/git-subtree.sh
> > +++ b/contrib/subtree/git-subtree.sh
> > @@ -778,6 +778,20 @@ 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_split_commit () {
>
> Maybe adding:
>
>     assert test $# = 1
>     local rev="$1"
>
> here, and using $rev instead of $1 in this function could make things
> a bit clearer and similar to what is done in other functions.
>
> > +  if test -n "$(git log -1 --grep="git-subtree-dir:" $1)"
> > +  then
> > +    if test -z "$(git log -1 --grep="git-subtree-mainline:" $1)" &&
> > +                       test -z "$(git log -1 --grep="git-subtree-dir: $arg_prefix$" $1)"
> > +    then
> > +      return 0
> > +    fi
> > +  fi
> > +  return 1
> > +}
>
> The above doesn't seem to be properly indented. We use tabs not spaces.
>
> >  # Usage: process_split_commit REV PARENTS
> >  process_split_commit () {
> >         assert test $# = 2
> > @@ -963,7 +977,20 @@ cmd_split () {
> >         eval "$grl" |
> >         while read rev parents
> >         do
> > -               process_split_commit "$rev" "$parents"
> > +               if should_ignore_subtree_split_commit "$rev"
> > +               then
> > +                       continue
> > +               fi
> > +               parsedParents=''
>
> It seems to me that we name variables "parsed_parents" (or sometimes
> "parsedparents") rather than "parsedParents".
>
> > +               for parent in $parents
> > +               do
> > +                       should_ignore_subtree_split_commit "$parent"
> > +                       if test $? -eq 1
>
> I think the 2 lines above could be replaced by:
>
> +                       if ! should_ignore_subtree_split_commit "$parent"
>
> > +                       then
> > +                               parsedParents+="$parent "
>
> It doesn't seem to me that we use "+=" much in our shell scripts.
> https://www.shellcheck.net/ emits the following:
>
> (warning): In POSIX sh, += is undefined.
>
> so I guess we don't use it because it's not available in some usual shells.
>
> (I haven't checked the script with https://www.shellcheck.net/ before
> and after your patch, but it might help avoid bash-isms and such
> issues.)
>
> > +                       fi
> > +               done
> > +               process_split_commit "$rev" "$parsedParents"
> >         done || exit $?
>
> It looks like we use "exit $?" a lot in git-subtree.sh while we use
> just "exit" most often elsewhere. Not sure why.
>
> >         latest_new=$(cache_get latest_new) || exit $?
> > diff --git a/contrib/subtree/t/t7900-subtree.sh b/contrib/subtree/t/t7900-subtree.sh
> > index 49a21dd7c9c..87d59afd761 100755
> > --- a/contrib/subtree/t/t7900-subtree.sh
> > +++ b/contrib/subtree/t/t7900-subtree.sh
> > @@ -385,6 +385,48 @@ test_expect_success 'split sub dir/ with --rejoin' '
> >         )
> >  '
> >
> > +test_expect_success 'split with multiple subtrees' '
> > +       subtree_test_create_repo "$test_count" &&
> > +       subtree_test_create_repo "$test_count/subA" &&
> > +       subtree_test_create_repo "$test_count/subB" &&
> > +       test_create_commit "$test_count" main1 &&
> > +       test_create_commit "$test_count/subA" subA1 &&
> > +       test_create_commit "$test_count/subA" subA2 &&
> > +       test_create_commit "$test_count/subA" subA3 &&
> > +       test_create_commit "$test_count/subB" subB1 &&
> > +       (
> > +               cd "$test_count" &&
> > +               git fetch ./subA HEAD &&
> > +               git subtree add --prefix=subADir FETCH_HEAD
> > +       ) &&
> > +       (
> > +               cd "$test_count" &&
> > +               git fetch ./subB HEAD &&
> > +               git subtree add --prefix=subBDir FETCH_HEAD
> > +       ) &&
> > +       test_create_commit "$test_count" subADir/main-subA1 &&
> > +       test_create_commit "$test_count" subBDir/main-subB1 &&
> > +       (
> > +               cd "$test_count" &&
> > +               git subtree split --prefix=subADir --squash --rejoin -m "Sub A Split 1"
> > +       ) &&
>
> Not sure why there are so many sub-shells used, and why the -C option
> is not used instead to tell Git to work in a subdirectory. I guess you
> copied what most existing (old) tests in this test script do.
>
> For example perhaps the 4 line above could be replaced by just:
>
> +               git -C "$test_count" subtree split --prefix=subADir
> --squash --rejoin -m "Sub A Split 1" &&
>
> > +       (
> > +               cd "$test_count" &&
> > +               git subtree split --prefix=subBDir --squash --rejoin -m "Sub B Split 1"
> > +       ) &&
> > +       test_create_commit "$test_count" subADir/main-subA2 &&
> > +       test_create_commit "$test_count" subBDir/main-subB2 &&
> > +       (
> > +               cd "$test_count" &&
> > +               git subtree split --prefix=subADir --squash --rejoin -m "Sub A Split 2"
> > +       ) &&
> > +       (
> > +               cd "$test_count" &&
> > +               test "$(git subtree split --prefix=subBDir --squash --rejoin \
> > +                -d -m "Sub B Split 1" 2>&1 | grep -w "\[1\]")" = ""
> > +       )
> > +'
>
> It's not clear to me what the test is doing. Maybe you could split it
> into 2 tests. Perhaps one setting up a repo with multiple subtrees and
> one checking that a new split ignores other subtree split commits.
> Perhaps adding a few comments would help too.
>
> Best,
> Christian.
diff mbox series

Patch

diff --git a/contrib/subtree/git-subtree.sh b/contrib/subtree/git-subtree.sh
index e0c5d3b0de6..e69991a9d80 100755
--- a/contrib/subtree/git-subtree.sh
+++ b/contrib/subtree/git-subtree.sh
@@ -778,6 +778,20 @@  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_split_commit () {
+  if test -n "$(git log -1 --grep="git-subtree-dir:" $1)"
+  then
+    if test -z "$(git log -1 --grep="git-subtree-mainline:" $1)" &&
+			test -z "$(git log -1 --grep="git-subtree-dir: $arg_prefix$" $1)"
+    then
+      return 0
+    fi
+  fi
+  return 1
+}
+
 # Usage: process_split_commit REV PARENTS
 process_split_commit () {
 	assert test $# = 2
@@ -963,7 +977,20 @@  cmd_split () {
 	eval "$grl" |
 	while read rev parents
 	do
-		process_split_commit "$rev" "$parents"
+		if should_ignore_subtree_split_commit "$rev"
+		then
+			continue
+		fi
+		parsedParents=''
+		for parent in $parents
+		do
+			should_ignore_subtree_split_commit "$parent"
+			if test $? -eq 1
+			then
+				parsedParents+="$parent "
+			fi
+		done
+		process_split_commit "$rev" "$parsedParents"
 	done || exit $?
 
 	latest_new=$(cache_get latest_new) || exit $?
diff --git a/contrib/subtree/t/t7900-subtree.sh b/contrib/subtree/t/t7900-subtree.sh
index 49a21dd7c9c..87d59afd761 100755
--- a/contrib/subtree/t/t7900-subtree.sh
+++ b/contrib/subtree/t/t7900-subtree.sh
@@ -385,6 +385,48 @@  test_expect_success 'split sub dir/ with --rejoin' '
 	)
 '
 
+test_expect_success 'split with multiple subtrees' '
+	subtree_test_create_repo "$test_count" &&
+	subtree_test_create_repo "$test_count/subA" &&
+	subtree_test_create_repo "$test_count/subB" &&
+	test_create_commit "$test_count" main1 &&
+	test_create_commit "$test_count/subA" subA1 &&
+	test_create_commit "$test_count/subA" subA2 &&
+	test_create_commit "$test_count/subA" subA3 &&
+	test_create_commit "$test_count/subB" subB1 &&
+	(
+		cd "$test_count" &&
+		git fetch ./subA HEAD &&
+		git subtree add --prefix=subADir FETCH_HEAD
+	) &&
+	(
+		cd "$test_count" &&
+		git fetch ./subB HEAD &&
+		git subtree add --prefix=subBDir FETCH_HEAD
+	) &&
+	test_create_commit "$test_count" subADir/main-subA1 &&
+	test_create_commit "$test_count" subBDir/main-subB1 &&
+	(
+		cd "$test_count" &&
+		git subtree split --prefix=subADir --squash --rejoin -m "Sub A Split 1"
+	) &&
+	(
+		cd "$test_count" &&
+		git subtree split --prefix=subBDir --squash --rejoin -m "Sub B Split 1"
+	) &&
+	test_create_commit "$test_count" subADir/main-subA2 &&
+	test_create_commit "$test_count" subBDir/main-subB2 &&
+	(
+		cd "$test_count" &&
+		git subtree split --prefix=subADir --squash --rejoin -m "Sub A Split 2"
+	) &&
+	(
+		cd "$test_count" &&
+		test "$(git subtree split --prefix=subBDir --squash --rejoin \
+		 -d -m "Sub B Split 1" 2>&1 | grep -w "\[1\]")" = ""
+	)
+'
+
 test_expect_success 'split sub dir/ with --rejoin from scratch' '
 	subtree_test_create_repo "$test_count" &&
 	test_create_commit "$test_count" main1 &&