patch, 3 partsSpeed up remove_redundant()

Michael Haggerty pointed out that git merge-base --independent is quite slow when many commits are provided in the input. This boils down to some quadratic behavior in remove_redundant() because it calls paint_down_to_common() in a loop.

This series avoids that by using a single commit walk, pushing a flag that means "this commit is reachable from a parent of a commit in the list." At the end of the walk, the input commits without that flag are independent.

There is an extra performance enhancement using the first-parent history as a heuristic. This helps only when there is a single independent result, as we can short circuit the walk when all other inputs are found to be reachable from the top one.

My tests were on the Linux kernel repository, testing this command:

  git merge-base --independent $(git for-each-ref refs/tags --format="%(refname)")

       Before: 16.4s
After Patch 1:  1.1s
After Patch 2:  0.1s

This does not change the correctness of the function. It is tested carefully in t6600-test-reach.c, among existing merge-base tests.

Thanks, -Stolee

Derrick Stolee (3):
  commit-reach: use one walk in remove_redundant()
  commit-reach: move compare_commits_by_gen
  commit-reach: use heuristic in remove_redundant()

 commit-reach.c | 178 +++++++++++++++++++++++++++++++++----------------
 1 file changed, 120 insertions(+), 58 deletions(-)

base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-852%2Fderrickstolee%2Fmerge-independent-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-852/derrickstolee/merge-independent-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/852

From: Derrick Stolee <dstolee@microsoft.com>

Move this earlier in the file so it can be used by more methods.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

From: Derrick Stolee <dstolee@microsoft.com>

The current implementation of remove_redundant() uses several calls to paint_down_to_common() to determine that commits are independent of each other. This leads to quadratic behavior when many inputs are passed to commands such as 'git merge-base'.

For example, in the Linux kernel repository, I tested the performance by passing all tags:

 git merge-base --independent $(git for-each-ref refs/tags --format="$(refname)")

(Note: I had to delete the tags v2.6.11-tree and v2.6.11 as they do not point to commits.)

Here is the performance improvement introduced by this change:

 Before: 16.4s
  After:  1.1s

The basic approach is to do one commit walk instead of many. First, scan all commits in the list and mark their _parents_ with the STALE flag. This flag will indicate commits that are reachable from one of the inputs, except not including themselves. Then, walk commits until covering all commits up to the minimum generation number pushing the STALE flag throughout.

At the end of the walk, commits in the input list that have the STALE flag are reachable from a _different_ commit in the list. These should be moved to the end of the array while the others are shifted to the front.

This logic is covered by tests in t6600-test-reach.sh, so the behavior does not change.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 108 +++++++++++++++++++++++++++++--------------------
 1 file changed, 65 insertions(+), 43 deletions(-)

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

So, the inner loop makes sure we won't revisit STALE parent, but keep digging parents we haven't seen, and stop when the generation is old enough. What happens when there is no generation number computed yet, I wonder... We'll keep getting infinity and dig all the way down to root?

The "fill stale ones from the end, non-stale ones from the beginning" in the loop looks unnecessarily complex to me. I wonder if we can do only the "fill non-stale ones from the beginning" half, i.e.

	for (i = count_non_stale = 0; i < cnt; i++) {
		if (dup[i] is not stale)
			array[count_non_stale++] = dup[i];
	}

without the "keep the stale one at the end of array[]", and clear marks using what is in dup[] as starting points before discarding dup[]?

Or do the callers still look at the entries beyond count_non_stale?

Other than that, nicely done.

Am 28.01.21 um 21:51 schrieb Junio C Hamano:

Had the same reaction.  Both callers ignore the stale entries.

This loop clears STALE from the parents of both the non-stale and stale entries. OK. Should it also clear it from the stale entries themselves?

On 1/29/2021 12:11 PM, René Scharfe wrote:

Ok, I can update that logic accordingly. I wanted to keep consistent with the comment at the start of the method:

	/*
	 * Some commit in the array may be an ancestor of
	 * another commit.  Move such commit to the end of
	 * the array, and return the number of commits that
	 * are independent from each other.
	 */

but if no caller actually needs that, then I can remove this behavior. Anyone mind if it is a follow-up patch to change this part of the behavior?

clear_commit_marks() walks commits starting from the input commit (parents->item in this case) and clears the STALE bit as long as it is present. This way, the accumulated clear_commit_marks() will walk each commit only once _and_ will visit any of the commits from 'array' that received the STALE bit during the above walk.

Thanks, -Stolee

On 1/28/2021 3:51 PM, Junio C Hamano wrote:

If we are on commits that have no generation number yet, then we will walk until reaching commits in the commit-graph file that have a computed generation (or in the heuristic case, when we have reached all but one of the commits).

In the case of the commit-graph, all commits will have generation number "infinity". In such a case, perhaps the old algorithm _is_ the best we can do, at least for now.

The trade-off is that we might walk more commits in unusual cases with few input commits. That quadratic behavior will take over as the input size grows, no matter if there is a commit-graph or not.

I can do a big more digging into these unusual cases, especially when we cannot rely on commit-graphs being present.

One way to ensure we do not regress from the current behavior would be to condition the new algorithm with

	if (generation_numbers_enabled(the_repository))
		new_algorithm();
	else
		old_algorithm();

much like in repo_is_descendant_of().

Is that a good plan?

Thanks, -Stolee

On 1/30/2021 10:59 PM, Derrick Stolee wrote:

Indeed, the old algorithm is better for cases where generation numbers do not help and there are multiple independent commits.

For example, this command in the Linux kernel repo changes from 0.047s in the old algorithm to 6.6s with the new algorithm:

git -c core.commitGraph=false merge-base --independent 2ecedd756908 d2360a398f0b >/dev/null

I will include this in a v2.

Thanks, -Stolee

Derrick Stolee <stolee@gmail.com> writes:

Hmph, I am afraid that such is life X-<.

It would certainly avoid one particular form of regression, so it is better than nothing.

But at the same time, we'd probably want to encourage people to enable and maintain generation numbers for the majority of commits in their repository, but unless you "gc" twice a day or something, you'd inevitably have a mixture, say, all commits that are more than two weeks old are covered by commit-graph, but more recent ones are not yet enumerated, and you have to traverse at runtime.

And the performance characteristics we would care the most in the longer term is to make sure that we perform well in such a mixed environment for the parts of the history that are not old enough.

Many things can be sped up by precomputing and storing the result in the commit-graph file and that is not all that interesting or surprising part of the story, I would think. Rather, we want to ensure that we do not perform on the youngest part of the history any worse---that way, people will have strong incentive to enable commit-graph, as things will work superbly for older parts of the history, while not doing any worse than the original system for the newest parts of the history.

There was a side thread where somebody wished if they can remove support for all the codepaths that do not use commit-graph, but would this be an example of how such a wish is impractical, I have to wonder?

Thanks.

On 1/31/2021 3:25 PM, Junio C Hamano wrote:

You're right, that in the mixed case of "all of these input commits have infinite generation number" is the worst possible case for this algorithm. However, if even a single commit has a finite generation number, then this new algorithm should out-perform the one using paint_down_to_common() in all cases.

I tested the painful case of

	git merge-base --independent 2ecedd756908 d2360a398f0b

in the Linux kernel repository with different commit-graph files. I found that the new algorithm performed worse than the old algorithm until there were fewer than 2,500 commits reachable from these two but not in the commit-graph file. That's probably too small of a gap to expect of a typical user.

I will modify my check

	if (generation_numbers_enabled(r)) {
		int i;

		/*
		 * If we have a single commit with finite generation
		 * number, then the _with_gen algorithm is preferred.
		 */
		for (i = 0; i < cnt; i++) {
			if (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)
				return remove_redundant_with_gen(r, array, cnt);
		}
	}

	return remove_redundant_no_gen(r, array, cnt);

I'm definitely biased to a case where there is an up-to-date
commit-graph file, since I care most about server-side performance
or users with background maintenance enabled (and computing the
commit-graph frequently). You are right to call out that that is
not always the case.
 

Some cases might allow de-duplication, such as sort_in_topological_order(), that would have roughly the same performance, give or take some overhead. It takes time to check and see if that is the case, however.

Thanks, -Stolee

Am 28.01.21 um 17:24 schrieb Derrick Stolee via GitGitGadget:

You could use CALLOC_ARRAY instead here, which is shorter and uses the correct type automatically. Or -- seeing that the next line overwrites all items anyway -- ALLOC_ARRAY.

René

From: Derrick Stolee <dstolee@microsoft.com>

Reachability algorithms in commit-reach.c frequently benefit from using the first-parent history as a heuristic for satisfying reachability queries. The most obvious example was implemented in 4fbcca4e (commit-reach: make can_all_from_reach... linear, 2018-07-20).

Update the walk in remove_redundant() to use this same heuristic. Here, we are walking starting at the parents of the input commits. Sort those parents and walk from the highest generation to lower. Each time, use the heuristic of searching the first parent history before continuing to expand the walk.

The important piece is to ensure we short-circuit the walk when we find that there is a single non-redundant commit. This happens frequently when looking for merge-bases or comparing several tags with 'git merge-base --independent'. Use a new count 'count_still_independent' and if that hits 1 we can stop walking.

To update 'count_still_independent' properly, we add use of the RESULT flag on the input commits. Then we can detect when we reach one of these commits and decrease the count. We need to remove the RESULT flag at that moment because we might re-visit that commit when popping the stack.

We use the STALE flag to mark parents that have been added to the new walk_start list, but we need to clear that flag before we start walking so those flags don't halt our depth-first-search walk.

On my copy of the Linux kernel repository, the performance of 'git merge-base --independent <all-tags>' goes from 1.1 seconds to 0.11 seconds.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 72 +++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 56 insertions(+), 16 deletions(-)

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

Yay. I've been quite unhappy with the loop ever since I wrote it back in 2012.

Thanks for cleaning it up.

Michael Haggerty pointed out that git merge-base --independent is quite slow when many commits are provided in the input. This boils down to some quadratic behavior in remove_redundant() because it calls paint_down_to_common() in a loop.

This series avoids that by using a single commit walk, pushing a flag that means "this commit is reachable from a parent of a commit in the list." At the end of the walk, the input commits without that flag are independent.

There is an extra performance enhancement using the first-parent history as a heuristic. This helps only when there is a single independent result, as we can short circuit the walk when all other inputs are found to be reachable from the top one. It also gets faster when we discover the commit with lowest generation and can restrict our walk further to the next-lowest generation number.

My tests were on the Linux kernel repository, testing this command:

  git merge-base --independent $(git for-each-ref refs/tags --format="%(refname)")

       Before: 16.4s
After Patch 1:  1.1s
After Patch 2:  0.1s

This does not change the correctness of the function. It is tested carefully in t6600-test-reach.c, among existing merge-base tests. There are also more tests in scripts like t6012-rev-list-simplify.sh that trigger the new logic under GIT_TEST_COMMIT_GRAPH=1.

Updates in V2 =============

 * The old algorithm is not entirely removed. It is still faster than the
   new algorithm if all input commits are not in the commit-graph file
   (unless the commit-graph file is really close to the input commits, but
   that is an unreasonable expectation). Now, the new logic only happens if
   there is an input commit with finite generation number.

 * There was a copy of 'array' being used for the final reorder which is now
   removed. We still need to be careful about the RESULT bit.

 * The final patch is new, adding yet another speedup in the form of
   increasing the min_generation cutoff when we find the input commit of
   smallest generation. This can reduce the time significantly when given
   many inputs. This does require copying the 'array' again, so we can sort
   by generation number while preserving the original order of 'array' which
   is required by some callers.

Thanks, -Stolee

Derrick Stolee (5):
  commit-reach: reduce requirements for remove_redundant()
  commit-reach: use one walk in remove_redundant()
  commit-reach: move compare_commits_by_gen
  commit-reach: use heuristic in remove_redundant()
  commit-reach: stale commits may prune generation further

 commit-reach.c | 188 +++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 166 insertions(+), 22 deletions(-)

base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-852%2Fderrickstolee%2Fmerge-independent-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-852/derrickstolee/merge-independent-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/852

Range-diff vs v1:

 -:  ----------- > 1:  649f6799e6b commit-reach: reduce requirements for remove_redundant()
 1:  3fe74e339fc ! 2:  2f80ae5fcb0 commit-reach: use one walk in remove_redundant()
     @@ Commit message
           Before: 16.4s
            After:  1.1s
      
     +    This performance improvement requires the commit-graph file to be
     +    present. We keep the old algorithm around as remove_redundant_no_gen()
     +    and use it when generation_numbers_enabled() is false. This is similar
     +    to other algorithms within commit-reach.c. The new algorithm is
     +    implemented in remove_redundant_with_gen().
     +
          The basic approach is to do one commit walk instead of many. First, scan
          all commits in the list and mark their _parents_ with the STALE flag.
          This flag will indicate commits that are reachable from one of the
     @@ Commit message
          covering all commits up to the minimum generation number pushing the
          STALE flag throughout.
      
     -    At the end of the walk, commits in the input list that have the STALE
     -    flag are reachable from a _different_ commit in the list. These should
     -    be moved to the end of the array while the others are shifted to the
     -    front.
     +    At the end, we need to clear the STALE bit from all of the commits
     +    we walked. We move the non-stale commits in 'array' to the beginning of
     +    the list, and this might overwrite stale commits. However, we store an
     +    array of commits that started the walk, and use clear_commit_marks() on
     +    each of those starting commits. That method will walk the reachable
     +    commits with the STALE bit and clear them all. This makes the algorithm
     +    safe for re-entry or for other uses of those commits after this walk.
      
          This logic is covered by tests in t6600-test-reach.sh, so the behavior
     -    does not change.
     +    does not change. This is tested both in the case with a commit-graph and
     +    without.
      
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## commit-reach.c ##
     +@@ commit-reach.c: struct commit_list *get_octopus_merge_bases(struct commit_list *in)
     + 	return ret;
     + }
     + 
     +-static int remove_redundant(struct repository *r, struct commit **array, int cnt)
     ++static int remove_redundant_no_gen(struct repository *r,
     ++				   struct commit **array, int cnt)
     + {
     +-	/*
     +-	 * Some commit in the array may be an ancestor of
     +-	 * another commit.  Move the independent commits to the
     +-	 * beginning of 'array' and return their number. Callers
     +-	 * should not rely upon the contents of 'array' after
     +-	 * that number.
     +-	 */
     + 	struct commit **work;
     + 	unsigned char *redundant;
     + 	int *filled_index;
      @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt
     - 	 * the array, and return the number of commits that
     - 	 * are independent from each other.
     - 	 */
     --	struct commit **work;
     --	unsigned char *redundant;
     --	int *filled_index;
     --	int i, j, filled;
     + 	for (i = filled = 0; i < cnt; i++)
     + 		if (!redundant[i])
     + 			array[filled++] = work[i];
     ++	for (j = filled, i = 0; i < cnt; i++)
     ++		if (redundant[i])
     ++			array[j++] = work[i];
     + 	free(work);
     + 	free(redundant);
     + 	free(filled_index);
     + 	return filled;
     + }
     + 
     ++static int remove_redundant_with_gen(struct repository *r,
     ++				     struct commit **array, int cnt)
     ++{
      +	int i, count_non_stale = 0;
      +	timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
     -+	struct commit **dup;
     ++	struct commit **walk_start;
     ++	size_t walk_start_nr = 0, walk_start_alloc = cnt;
      +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
     - 
     --	work = xcalloc(cnt, sizeof(*work));
     --	redundant = xcalloc(cnt, 1);
     --	ALLOC_ARRAY(filled_index, cnt - 1);
     ++
     ++	ALLOC_ARRAY(walk_start, walk_start_alloc);
     ++
      +	/* Mark all parents of the input as STALE */
      +	for (i = 0; i < cnt; i++) {
      +		struct commit_list *parents;
      +		timestamp_t generation;
     - 
     --	for (i = 0; i < cnt; i++)
     - 		repo_parse_commit(r, array[i]);
     --	for (i = 0; i < cnt; i++) {
     --		struct commit_list *common;
     --		timestamp_t min_generation = commit_graph_generation(array[i]);
     ++
     ++		repo_parse_commit(r, array[i]);
      +		parents = array[i]->parents;
      +
      +		while (parents) {
      +			repo_parse_commit(r, parents->item);
      +			if (!(parents->item->object.flags & STALE)) {
      +				parents->item->object.flags |= STALE;
     ++				ALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);
     ++				walk_start[walk_start_nr++] = parents->item;
      +				prio_queue_put(&queue, parents->item);
      +			}
      +			parents = parents->next;
     @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit
      +		struct commit *c = prio_queue_get(&queue);
      +
      +		repo_parse_commit(r, c);
     - 
     --		if (redundant[i])
     ++
      +		if (commit_graph_generation(c) < min_generation)
     - 			continue;
     --		for (j = filled = 0; j < cnt; j++) {
     --			timestamp_t curr_generation;
     --			if (i == j || redundant[j])
     --				continue;
     --			filled_index[filled] = j;
     --			work[filled++] = array[j];
     - 
     --			curr_generation = commit_graph_generation(array[j]);
     --			if (curr_generation < min_generation)
     --				min_generation = curr_generation;
     ++			continue;
     ++
      +		parents = c->parents;
      +		while (parents) {
      +			if (!(parents->item->object.flags & STALE)) {
     @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit
      +	}
      +
      +	/* rearrange array */
     -+	dup = xcalloc(cnt, sizeof(struct commit *));
     -+	COPY_ARRAY(dup, array, cnt);
     -+	for (i = 0; i < cnt; i++) {
     -+		if (dup[i]->object.flags & STALE) {
     -+			int insert = cnt - 1 - (i - count_non_stale);
     -+			array[insert] = dup[i];
     -+		} else {
     -+			array[count_non_stale] = dup[i];
     -+			count_non_stale++;
     -+		}
     ++	for (i = count_non_stale = 0; i < cnt; i++) {
     ++		if (!(array[i]->object.flags & STALE))
     ++			array[count_non_stale++] = array[i];
      +	}
     -+	free(dup);
      +
      +	/* clear marks */
     -+	for (i = 0; i < cnt; i++) {
     -+		struct commit_list *parents;
     -+		parents = array[i]->parents;
     ++	for (i = 0; i < walk_start_nr; i++)
     ++		clear_commit_marks(walk_start[i], STALE);
     ++	free(walk_start);
      +
     -+		while (parents) {
     -+			clear_commit_marks(parents->item, STALE);
     -+			parents = parents->next;
     - 		}
     --		common = paint_down_to_common(r, array[i], filled,
     --					      work, min_generation);
     --		if (array[i]->object.flags & PARENT2)
     --			redundant[i] = 1;
     --		for (j = 0; j < filled; j++)
     --			if (work[j]->object.flags & PARENT1)
     --				redundant[filled_index[j]] = 1;
     --		clear_commit_marks(array[i], all_flags);
     --		clear_commit_marks_many(filled, work, all_flags);
     --		free_commit_list(common);
     - 	}
     - 
     --	/* Now collect the result */
     --	COPY_ARRAY(work, array, cnt);
     --	for (i = filled = 0; i < cnt; i++)
     --		if (!redundant[i])
     --			array[filled++] = work[i];
     --	for (j = filled, i = 0; i < cnt; i++)
     --		if (redundant[i])
     --			array[j++] = work[i];
     --	free(work);
     --	free(redundant);
     --	free(filled_index);
     --	return filled;
      +	return count_non_stale;
     - }
     - 
     ++}
     ++
     ++static int remove_redundant(struct repository *r, struct commit **array, int cnt)
     ++{
     ++	/*
     ++	 * Some commit in the array may be an ancestor of
     ++	 * another commit.  Move the independent commits to the
     ++	 * beginning of 'array' and return their number. Callers
     ++	 * should not rely upon the contents of 'array' after
     ++	 * that number.
     ++	 */
     ++	if (generation_numbers_enabled(r)) {
     ++		int i;
     ++
     ++		/*
     ++		 * If we have a single commit with finite generation
     ++		 * number, then the _with_gen algorithm is preferred.
     ++		 */
     ++		for (i = 0; i < cnt; i++) {
     ++			if (commit_graph_generation(array[i]) < GENERATION_NUMBER_INFINITY)
     ++				return remove_redundant_with_gen(r, array, cnt);
     ++		}
     ++	}
     ++
     ++	return remove_redundant_no_gen(r, array, cnt);
     ++}
     ++
       static struct commit_list *get_merge_bases_many_0(struct repository *r,
     + 						  struct commit *one,
     + 						  int n,
 2:  4c58877a709 = 3:  009f64b53c9 commit-reach: move compare_commits_by_gen
 3:  fbe7bdc1ec2 ! 4:  83feabeebb5 commit-reach: use heuristic in remove_redundant()
     @@ Commit message
          the heuristic of searching the first parent history before continuing to
          expand the walk.
      
     +    The order in which we explore the commits matters, so update
     +    compare_commits_by_gen to break generation number ties with commit date.
     +    This has no effect when the commits are in a commit-graph file with
     +    corrected commit dates computed, but it will assist when the commits are
     +    in the region "above" the commit-graph with "infinite" generation
     +    number. Note that we cannot shift to use
     +    compare_commits_by_gen_then_commit_date as the method prototype is
     +    different. We use compare_commits_by_gen for QSORT() as opposed to as a
     +    priority function.
     +
          The important piece is to ensure we short-circuit the walk when we find
          that there is a single non-redundant commit. This happens frequently
          when looking for merge-bases or comparing several tags with 'git
     @@ Commit message
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## commit-reach.c ##
     -@@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt
     - 	 * the array, and return the number of commits that
     - 	 * are independent from each other.
     - 	 */
     +@@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b)
     + 		return -1;
     + 	if (generation_a > generation_b)
     + 		return 1;
     ++	if (a->date < b->date)
     ++		return -1;
     ++	if (a->date > b->date)
     ++		return 1;
     + 	return 0;
     + }
     + 
     +@@ commit-reach.c: static int remove_redundant_no_gen(struct repository *r,
     + static int remove_redundant_with_gen(struct repository *r,
     + 				     struct commit **array, int cnt)
     + {
      -	int i, count_non_stale = 0;
      +	int i, count_non_stale = 0, count_still_independent = cnt;
       	timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
     - 	struct commit **dup;
     + 	struct commit **walk_start;
     + 	size_t walk_start_nr = 0, walk_start_alloc = cnt;
      -	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
     -+	struct commit **walk_start;
     -+	size_t walk_start_nr = 0, walk_start_alloc = cnt;
     -+
     -+	ALLOC_ARRAY(walk_start, walk_start_alloc);
       
     - 	/* Mark all parents of the input as STALE */
     - 	for (i = 0; i < cnt; i++) {
     -@@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt
     + 	ALLOC_ARRAY(walk_start, walk_start_alloc);
     + 
     +@@ commit-reach.c: static int remove_redundant_with_gen(struct repository *r,
       		timestamp_t generation;
       
       		repo_parse_commit(r, array[i]);
     @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit
       		parents = array[i]->parents;
       
       		while (parents) {
     - 			repo_parse_commit(r, parents->item);
     - 			if (!(parents->item->object.flags & STALE)) {
     +@@ commit-reach.c: static int remove_redundant_with_gen(struct repository *r,
       				parents->item->object.flags |= STALE;
     + 				ALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);
     + 				walk_start[walk_start_nr++] = parents->item;
      -				prio_queue_put(&queue, parents->item);
     -+				ALLOC_GROW(walk_start, walk_start_nr + 1, walk_start_alloc);
     -+				walk_start[walk_start_nr++] = parents->item;
       			}
       			parents = parents->next;
       		}
     -@@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt
     +@@ commit-reach.c: static int remove_redundant_with_gen(struct repository *r,
       			min_generation = generation;
       	}
       
     @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit
       		}
      +		free_commit_list(stack);
       	}
     -+	free(walk_start);
       
     ++	/* clear result */
     ++	for (i = 0; i < cnt; i++)
     ++		array[i]->object.flags &= ~RESULT;
     ++
       	/* rearrange array */
     - 	dup = xcalloc(cnt, sizeof(struct commit *));
     - 	COPY_ARRAY(dup, array, cnt);
     - 	for (i = 0; i < cnt; i++) {
     -+		dup[i]->object.flags &= ~RESULT;
     - 		if (dup[i]->object.flags & STALE) {
     - 			int insert = cnt - 1 - (i - count_non_stale);
     - 			array[insert] = dup[i];
     + 	for (i = count_non_stale = 0; i < cnt; i++) {
     + 		if (!(array[i]->object.flags & STALE))
 -:  ----------- > 5:  14f0974c987 commit-reach: stale commits may prune generation further

From: Derrick Stolee <dstolee@microsoft.com>

Remove a comment at the beggining of remove_redundant() that mentions a reordering of the input array to have the initial segment be the independent commits and the final segment be the redundant commits. While this behavior is followed in remove_redundant(), no callers rely on that behavior.

Remove the final loop that copies this final segment and update the comment to match the new behavior.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

Makes sense, especially since this is a file-local/static helper function, we have reasonably tight control over its callers.

Will queue.  Thanks.

From: Derrick Stolee <dstolee@microsoft.com>

Move this earlier in the file so it can be used by more methods.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

From: Derrick Stolee <dstolee@microsoft.com>

The current implementation of remove_redundant() uses several calls to paint_down_to_common() to determine that commits are independent of each other. This leads to quadratic behavior when many inputs are passed to commands such as 'git merge-base'.

For example, in the Linux kernel repository, I tested the performance by passing all tags:

 git merge-base --independent $(git for-each-ref refs/tags --format="$(refname)")

(Note: I had to delete the tags v2.6.11-tree and v2.6.11 as they do not point to commits.)

Here is the performance improvement introduced by this change:

 Before: 16.4s
  After:  1.1s

This performance improvement requires the commit-graph file to be present. We keep the old algorithm around as remove_redundant_no_gen() and use it when generation_numbers_enabled() is false. This is similar to other algorithms within commit-reach.c. The new algorithm is implemented in remove_redundant_with_gen().

The basic approach is to do one commit walk instead of many. First, scan all commits in the list and mark their _parents_ with the STALE flag. This flag will indicate commits that are reachable from one of the inputs, except not including themselves. Then, walk commits until covering all commits up to the minimum generation number pushing the STALE flag throughout.

At the end, we need to clear the STALE bit from all of the commits we walked. We move the non-stale commits in 'array' to the beginning of the list, and this might overwrite stale commits. However, we store an array of commits that started the walk, and use clear_commit_marks() on each of those starting commits. That method will walk the reachable commits with the STALE bit and clear them all. This makes the algorithm safe for re-entry or for other uses of those commits after this walk.

This logic is covered by tests in t6600-test-reach.sh, so the behavior does not change. This is tested both in the case with a commit-graph and without.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 108 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 100 insertions(+), 8 deletions(-)

Am 01.02.21 um 13:47 schrieb Derrick Stolee via GitGitGadget:

This puts the loop back in that you removed in the previous commit. Intentionally?

Here I would have added another condition, count_non_stale != i, to avoid self-assignment (array[x] = array[x]). The code works without it, though. Not sure if there is a performance benefit to be had -- branch vs. pointer copy. Probably not worth it..

You can replace this loop with a call to clear_commit_marks_many().

On 2/1/2021 11:12 AM, René Scharfe. wrote:

Not intentional. Thanks for noticing.

You are correct, but I'm going to go on the side of not worth it.

Right! Earlier I was using a 'struct commit_list *' which would not work, but this 'struct commit ** walk_start' does work. Thanks.

-Stolee

From: Derrick Stolee <dstolee@microsoft.com>

Reachability algorithms in commit-reach.c frequently benefit from using the first-parent history as a heuristic for satisfying reachability queries. The most obvious example was implemented in 4fbcca4e (commit-reach: make can_all_from_reach... linear, 2018-07-20).

Update the walk in remove_redundant() to use this same heuristic. Here, we are walking starting at the parents of the input commits. Sort those parents and walk from the highest generation to lower. Each time, use the heuristic of searching the first parent history before continuing to expand the walk.

The order in which we explore the commits matters, so update compare_commits_by_gen to break generation number ties with commit date. This has no effect when the commits are in a commit-graph file with corrected commit dates computed, but it will assist when the commits are in the region "above" the commit-graph with "infinite" generation number. Note that we cannot shift to use compare_commits_by_gen_then_commit_date as the method prototype is different. We use compare_commits_by_gen for QSORT() as opposed to as a priority function.

The important piece is to ensure we short-circuit the walk when we find that there is a single non-redundant commit. This happens frequently when looking for merge-bases or comparing several tags with 'git merge-base --independent'. Use a new count 'count_still_independent' and if that hits 1 we can stop walking.

To update 'count_still_independent' properly, we add use of the RESULT flag on the input commits. Then we can detect when we reach one of these commits and decrease the count. We need to remove the RESULT flag at that moment because we might re-visit that commit when popping the stack.

We use the STALE flag to mark parents that have been added to the new walk_start list, but we need to clear that flag before we start walking so those flags don't halt our depth-first-search walk.

On my copy of the Linux kernel repository, the performance of 'git merge-base --independent <all-tags>' goes from 1.1 seconds to 0.11 seconds.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 72 +++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 56 insertions(+), 16 deletions(-)

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

That is because when you are left one single thing, it may be able to reach many other things, but the fact that it by itself won't be reachable by remaining independent things will not change (because, that sole remaining independent thing is itself)?

These two numbers are with commit-graph fully populated with usable generation numbers, I presume, and it is quite impressive.

On 2/1/2021 3:05 PM, Junio C Hamano wrote:

Right. If there is only one non-STALE input commit left, then it will be the only returned result. We will never find that all commits are redundant because the commit graph is acyclic. The performance improvement comes from halting the DFS walk: there might be more commits to walk but they won't change the result.

 
Yes, these numbers are with a full commit-graph.

Thanks, -Stolee

From: Derrick Stolee <dstolee@microsoft.com>

The remove_redundant_with_gen() algorithm performs a depth-first-search to find commits in the 'array' list, starting at the parents of each commit in 'array'. The result is that commits in 'array' are marked STALE when they are reachable from another commit in 'array'.

This depth-first-search is fast when commits lie on or near the first-parent history of the higher commits. The search terminates early if all but one commit becomes marked STALE.

However, it is possible that there are two independent commits with high generation number. In that case, the depth-first-search might languish by searching in lower generations due to the fixed min_generation used throughout the method.

With the expectation that commits with lower generation are expected to become STALE more often, we can optimize further by increasing that min_generation boundary upon discovery of the commit with minimum generation.

We must first sort the commits in 'array' by generation. We cannot sort 'array' itself since it must preserve relative order among the returned results (see revision.c:mark_redundant_parents() for an example).

This simplifies the initialization of min_generation, but it also allows us to increase the new min_generation when we find the commit with smallest generation remaining.

This requires more than two commits in order to test, so I used the Linux kernel repository with a few commits that are slightly off of the first-parent history. I timed the following command:

  git merge-base --independent 2ecedd756908 d2360a398f0b \
	1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e

The first two commits have similar generation and are near the v5.10 tag. Commit 160bab43419e is off of the first-parent history behind v5.5, while the others are scattered somewhere reachable from v5.9. This is designed to demonstrate the optimization, as that commit within v5.5 would normally cause a lot of extra commit walking.

Since remove_redundant_with_alg() is called only when at least one of the input commits has a finite generation number, this algorithm is tested with a commit-graph generated starting at a number of different tags, the earliest being v5.5.

commit-graph at v5.5:

 | Method                | Time  |
 |-----------------------+-------|
 | *_no_gen()            | 864ms |
 | *_with_gen() (before) | 858ms |
 | *_with_gen() (after)  | 810ms |

commit-graph at v5.7:

 | Method                | Time  |
 |-----------------------+-------|
 | *_no_gen()            | 625ms |
 | *_with_gen() (before) | 572ms |
 | *_with_gen() (after)  | 517ms |

commit-graph at v5.9:

 | Method                | Time  |
 |-----------------------+-------|
 | *_no_gen()            | 268ms |
 | *_with_gen() (before) | 224ms |
 | *_with_gen() (after)  | 202ms |

commit-graph at v5.10:

 | Method                | Time  |
 |-----------------------+-------|
 | *_no_gen()            |  72ms |
 | *_with_gen() (before) |  37ms |
 | *_with_gen() (after)  |   9ms |

Note that these are only modest improvements for the case where the two independent commits are not in the commit-graph (not until v5.10). All algorithms get faster as more commits are indexed, which is not a surprise. However, the cost of walking extra commits is more and more prevalent in relative terms as more commits are indexed. Finally, the last case allows us to jump to the minimum generation between the last two commits (that are actually independent) so we greatly reduce the cost in that case.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)

On Mon, Feb 01, 2021 at 12:47:27PM +0000, Derrick Stolee via GitGitGadget wrote:

Very nice. The explanation and implementation makes sense to me.

This line caught my eye, but we return early in commit-reach.c:reduce_heads() before even calling remove_redundant() (which itself calls remove_redundant_with_gen()), so it's always OK to assume that we have at least one element in 'array'.

This patch and the others in v2 all look good to me.

Thanks, Taylor

On 2/1/2021 7:47 AM, Derrick Stolee via GitGitGadget wrote:

During my testing of v2, I discovered how remove_redundant() is being used as part of 'git log --simplify-merges'. So, here are some performance numbers for the Linux kernel repository with a full commit-graph and changed-path Bloom filters running

  git log --oneline -n10 --simplify-merges -- kernel/

Benchmark #1: old
  Time (mean ± σ):      5.770 s ±  0.030 s    [User: 5.551 s, System: 0.219 s]
  Range (min … max):    5.728 s …  5.827 s    10 runs
 
Benchmark #2: new
  Time (mean ± σ):      5.030 s ±  0.017 s    [User: 4.805 s, System: 0.224 s]
  Range (min … max):    4.999 s …  5.054 s    10 runs
 
Summary
  'new' ran
    1.15 ± 0.01 times faster than 'old'

Thanks, -Stolee

Derrick Stolee <stolee@gmail.com> writes:

This topic seems to have been forgotten? Is the only thing missing is an updated 2/5 or is there anything more that is needed?

On 2/18/2021 6:25 PM, Junio C Hamano wrote:

 
I had forgotten about the comments on patch 2/5, sorry. That explains
why it hasn't merged yet...

I'll get right on it.

Thanks, -Stolee

Derrick Stolee <stolee@gmail.com> writes:

Thanks.

Michael Haggerty pointed out that git merge-base --independent is quite slow when many commits are provided in the input. This boils down to some quadratic behavior in remove_redundant() because it calls paint_down_to_common() in a loop.

This series avoids that by using a single commit walk, pushing a flag that means "this commit is reachable from a parent of a commit in the list." At the end of the walk, the input commits without that flag are independent.

There is an extra performance enhancement using the first-parent history as a heuristic. This helps only when there is a single independent result, as we can short circuit the walk when all other inputs are found to be reachable from the top one. It also gets faster when we discover the commit with lowest generation and can restrict our walk further to the next-lowest generation number.

My tests were on the Linux kernel repository, testing this command:

  git merge-base --independent $(git for-each-ref refs/tags --format="%(refname)")

       Before: 16.4s
After Patch 1:  1.1s
After Patch 2:  0.1s

This does not change the correctness of the function. It is tested carefully in t6600-test-reach.c, among existing merge-base tests. There are also more tests in scripts like t6012-rev-list-simplify.sh that trigger the new logic under GIT_TEST_COMMIT_GRAPH=1.

Updates in V3 =============

 * Patch 2 is updated to René's comments. Sorry I dropped the ball on this.
   I had the changes locally, but never pushed them until now.

Updates in V2 =============

 * The old algorithm is not entirely removed. It is still faster than the
   new algorithm if all input commits are not in the commit-graph file
   (unless the commit-graph file is really close to the input commits, but
   that is an unreasonable expectation). Now, the new logic only happens if
   there is an input commit with finite generation number.

 * There was a copy of 'array' being used for the final reorder which is now
   removed. We still need to be careful about the RESULT bit.

 * The final patch is new, adding yet another speedup in the form of
   increasing the min_generation cutoff when we find the input commit of
   smallest generation. This can reduce the time significantly when given
   many inputs. This does require copying the 'array' again, so we can sort
   by generation number while preserving the original order of 'array' which
   is required by some callers.

Thanks, -Stolee

Derrick Stolee (5):
  commit-reach: reduce requirements for remove_redundant()
  commit-reach: use one walk in remove_redundant()
  commit-reach: move compare_commits_by_gen
  commit-reach: use heuristic in remove_redundant()
  commit-reach: stale commits may prune generation further

 commit-reach.c | 190 ++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 165 insertions(+), 25 deletions(-)

base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-852%2Fderrickstolee%2Fmerge-independent-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-852/derrickstolee/merge-independent-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/852

Range-diff vs v2:

 1:  649f6799e6bf = 1:  649f6799e6bf commit-reach: reduce requirements for remove_redundant()
 2:  2f80ae5fcb00 ! 2:  c2c08989ce60 commit-reach: use one walk in remove_redundant()
     @@ commit-reach.c: struct commit_list *get_octopus_merge_bases(struct commit_list *
       	unsigned char *redundant;
       	int *filled_index;
      @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit **array, int cnt
     - 	for (i = filled = 0; i < cnt; i++)
     - 		if (!redundant[i])
     - 			array[filled++] = work[i];
     -+	for (j = filled, i = 0; i < cnt; i++)
     -+		if (redundant[i])
     -+			array[j++] = work[i];
     - 	free(work);
     - 	free(redundant);
     - 	free(filled_index);
       	return filled;
       }
       
     @@ commit-reach.c: static int remove_redundant(struct repository *r, struct commit
      +	}
      +
      +	/* clear marks */
     -+	for (i = 0; i < walk_start_nr; i++)
     -+		clear_commit_marks(walk_start[i], STALE);
     ++	clear_commit_marks_many(walk_start_nr, walk_start, STALE);
      +	free(walk_start);
      +
      +	return count_non_stale;
 3:  009f64b53c95 = 3:  1d3c5ebbb632 commit-reach: move compare_commits_by_gen
 4:  83feabeebb5f = 4:  c1fc174d42aa commit-reach: use heuristic in remove_redundant()
 5:  14f0974c9872 = 5:  539db83bd735 commit-reach: stale commits may prune generation further

From: Derrick Stolee <dstolee@microsoft.com>

Remove a comment at the beggining of remove_redundant() that mentions a reordering of the input array to have the initial segment be the independent commits and the final segment be the redundant commits. While this behavior is followed in remove_redundant(), no callers rely on that behavior.

Remove the final loop that copies this final segment and update the comment to match the new behavior.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

From: Derrick Stolee <dstolee@microsoft.com>

The remove_redundant_with_gen() algorithm performs a depth-first-search to find commits in the 'array' list, starting at the parents of each commit in 'array'. The result is that commits in 'array' are marked STALE when they are reachable from another commit in 'array'.

This depth-first-search is fast when commits lie on or near the first-parent history of the higher commits. The search terminates early if all but one commit becomes marked STALE.

However, it is possible that there are two independent commits with high generation number. In that case, the depth-first-search might languish by searching in lower generations due to the fixed min_generation used throughout the method.

With the expectation that commits with lower generation are expected to become STALE more often, we can optimize further by increasing that min_generation boundary upon discovery of the commit with minimum generation.

We must first sort the commits in 'array' by generation. We cannot sort 'array' itself since it must preserve relative order among the returned results (see revision.c:mark_redundant_parents() for an example).

This simplifies the initialization of min_generation, but it also allows us to increase the new min_generation when we find the commit with smallest generation remaining.

This requires more than two commits in order to test, so I used the Linux kernel repository with a few commits that are slightly off of the first-parent history. I timed the following command:

  git merge-base --independent 2ecedd756908 d2360a398f0b \
	1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e

The first two commits have similar generation and are near the v5.10 tag. Commit 160bab43419e is off of the first-parent history behind v5.5, while the others are scattered somewhere reachable from v5.9. This is designed to demonstrate the optimization, as that commit within v5.5 would normally cause a lot of extra commit walking.

Since remove_redundant_with_alg() is called only when at least one of the input commits has a finite generation number, this algorithm is tested with a commit-graph generated starting at a number of different tags, the earliest being v5.5.

commit-graph at v5.5:

 | Method                | Time  |
 |-----------------------+-------|
 | *_no_gen()            | 864ms |
 | *_with_gen() (before) | 858ms |
 | *_with_gen() (after)  | 810ms |

commit-graph at v5.7:

 | Method                | Time  |
 |-----------------------+-------|
 | *_no_gen()            | 625ms |
 | *_with_gen() (before) | 572ms |
 | *_with_gen() (after)  | 517ms |

commit-graph at v5.9:

 | Method                | Time  |
 |-----------------------+-------|
 | *_no_gen()            | 268ms |
 | *_with_gen() (before) | 224ms |
 | *_with_gen() (after)  | 202ms |

commit-graph at v5.10:

 | Method                | Time  |
 |-----------------------+-------|
 | *_no_gen()            |  72ms |
 | *_with_gen() (before) |  37ms |
 | *_with_gen() (after)  |   9ms |

Note that these are only modest improvements for the case where the two independent commits are not in the commit-graph (not until v5.10). All algorithms get faster as more commits are indexed, which is not a surprise. However, the cost of walking extra commits is more and more prevalent in relative terms as more commits are indexed. Finally, the last case allows us to jump to the minimum generation between the last two commits (that are actually independent) so we greatly reduce the cost in that case.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)

From: Derrick Stolee <dstolee@microsoft.com>

Reachability algorithms in commit-reach.c frequently benefit from using the first-parent history as a heuristic for satisfying reachability queries. The most obvious example was implemented in 4fbcca4e (commit-reach: make can_all_from_reach... linear, 2018-07-20).

Update the walk in remove_redundant() to use this same heuristic. Here, we are walking starting at the parents of the input commits. Sort those parents and walk from the highest generation to lower. Each time, use the heuristic of searching the first parent history before continuing to expand the walk.

The order in which we explore the commits matters, so update compare_commits_by_gen to break generation number ties with commit date. This has no effect when the commits are in a commit-graph file with corrected commit dates computed, but it will assist when the commits are in the region "above" the commit-graph with "infinite" generation number. Note that we cannot shift to use compare_commits_by_gen_then_commit_date as the method prototype is different. We use compare_commits_by_gen for QSORT() as opposed to as a priority function.

The important piece is to ensure we short-circuit the walk when we find that there is a single non-redundant commit. This happens frequently when looking for merge-bases or comparing several tags with 'git merge-base --independent'. Use a new count 'count_still_independent' and if that hits 1 we can stop walking.

To update 'count_still_independent' properly, we add use of the RESULT flag on the input commits. Then we can detect when we reach one of these commits and decrease the count. We need to remove the RESULT flag at that moment because we might re-visit that commit when popping the stack.

We use the STALE flag to mark parents that have been added to the new walk_start list, but we need to clear that flag before we start walking so those flags don't halt our depth-first-search walk.

On my copy of the Linux kernel repository, the performance of 'git merge-base --independent <all-tags>' goes from 1.1 seconds to 0.11 seconds.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 72 +++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 56 insertions(+), 16 deletions(-)

From: Derrick Stolee <dstolee@microsoft.com>

Move this earlier in the file so it can be used by more methods.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

From: Derrick Stolee <dstolee@microsoft.com>

The current implementation of remove_redundant() uses several calls to paint_down_to_common() to determine that commits are independent of each other. This leads to quadratic behavior when many inputs are passed to commands such as 'git merge-base'.

For example, in the Linux kernel repository, I tested the performance by passing all tags:

 git merge-base --independent $(git for-each-ref refs/tags --format="$(refname)")

(Note: I had to delete the tags v2.6.11-tree and v2.6.11 as they do not point to commits.)

Here is the performance improvement introduced by this change:

 Before: 16.4s
  After:  1.1s

This performance improvement requires the commit-graph file to be present. We keep the old algorithm around as remove_redundant_no_gen() and use it when generation_numbers_enabled() is false. This is similar to other algorithms within commit-reach.c. The new algorithm is implemented in remove_redundant_with_gen().

The basic approach is to do one commit walk instead of many. First, scan all commits in the list and mark their _parents_ with the STALE flag. This flag will indicate commits that are reachable from one of the inputs, except not including themselves. Then, walk commits until covering all commits up to the minimum generation number pushing the STALE flag throughout.

At the end, we need to clear the STALE bit from all of the commits we walked. We move the non-stale commits in 'array' to the beginning of the list, and this might overwrite stale commits. However, we store an array of commits that started the walk, and use clear_commit_marks() on each of those starting commits. That method will walk the reachable commits with the STALE bit and clear them all. This makes the algorithm safe for re-entry or for other uses of those commits after this walk.

This logic is covered by tests in t6600-test-reach.sh, so the behavior does not change. This is tested both in the case with a commit-graph and without.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 104 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 96 insertions(+), 8 deletions(-)