[v2,2/5] commit-reach: use one walk in remove_redundant()

Commit Message

Derrick Stolee Feb. 1, 2021, 12:47 p.m. UTC

From: Derrick Stolee <[e-mail]>

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 <[e-mail]>
---
 commit-reach.c | 108 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 100 insertions(+), 8 deletions(-)

Comments

René Scharfe Feb. 1, 2021, 4:12 p.m. UTC | #1

Am 01.02.21 um 13:47 schrieb Derrick Stolee via GitGitGadget:
> @@ -210,12 +204,110 @@ 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];

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

>  	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 **walk_start;
> +	size_t walk_start_nr = 0, walk_start_alloc = cnt;
> +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
> +
> +	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;
> +
> +		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;
> +		}
> +
> +		generation = commit_graph_generation(array[i]);
> +
> +		if (generation < min_generation)
> +			min_generation = generation;
> +	}
> +
> +	/* push the STALE bits up to min generation */
> +	while (queue.nr) {
> +		struct commit_list *parents;
> +		struct commit *c = prio_queue_get(&queue);
> +
> +		repo_parse_commit(r, c);
> +
> +		if (commit_graph_generation(c) < min_generation)
> +			continue;
> +
> +		parents = c->parents;
> +		while (parents) {
> +			if (!(parents->item->object.flags & STALE)) {
> +				parents->item->object.flags |= STALE;
> +				prio_queue_put(&queue, parents->item);
> +			}
> +			parents = parents->next;
> +		}
> +	}
> +
> +	/* rearrange array */
> +	for (i = count_non_stale = 0; i < cnt; i++) {
> +		if (!(array[i]->object.flags & STALE))

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

> +			array[count_non_stale++] = array[i];
> +	}
> +
> +	/* clear marks */
> +	for (i = 0; i < walk_start_nr; i++)
> +		clear_commit_marks(walk_start[i], STALE);

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

> +	free(walk_start);
> +
> +	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,
>

Derrick Stolee Feb. 1, 2021, 4:31 p.m. UTC | #2

On 2/1/2021 11:12 AM, René Scharfe. wrote:
> Am 01.02.21 um 13:47 schrieb Derrick Stolee via GitGitGadget:
>> @@ -210,12 +204,110 @@ 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];
> 
> This puts the loop back in that you removed in the previous commit.
> Intentionally?

Not intentional. Thanks for noticing.

>> +	/* rearrange array */
>> +	for (i = count_non_stale = 0; i < cnt; i++) {
>> +		if (!(array[i]->object.flags & STALE))
> 
> 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 are correct, but I'm going to go on the side of not worth it.

>> +			array[count_non_stale++] = array[i];
>> +	}
>> +
>> +	/* clear marks */
>> +	for (i = 0; i < walk_start_nr; i++)
>> +		clear_commit_marks(walk_start[i], STALE);
> 
> You can replace this loop with a call to clear_commit_marks_many().

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

-Stolee

Patch

diff --git a/commit-reach.c b/commit-reach.c
index 9af51fe7e07..053676e51d0 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -156,15 +156,9 @@  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;
@@ -210,12 +204,110 @@  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;
 }
 
+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 **walk_start;
+	size_t walk_start_nr = 0, walk_start_alloc = cnt;
+	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+
+	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;
+
+		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;
+		}
+
+		generation = commit_graph_generation(array[i]);
+
+		if (generation < min_generation)
+			min_generation = generation;
+	}
+
+	/* push the STALE bits up to min generation */
+	while (queue.nr) {
+		struct commit_list *parents;
+		struct commit *c = prio_queue_get(&queue);
+
+		repo_parse_commit(r, c);
+
+		if (commit_graph_generation(c) < min_generation)
+			continue;
+
+		parents = c->parents;
+		while (parents) {
+			if (!(parents->item->object.flags & STALE)) {
+				parents->item->object.flags |= STALE;
+				prio_queue_put(&queue, parents->item);
+			}
+			parents = parents->next;
+		}
+	}
+
+	/* rearrange array */
+	for (i = count_non_stale = 0; i < cnt; i++) {
+		if (!(array[i]->object.flags & STALE))
+			array[count_non_stale++] = array[i];
+	}
+
+	/* clear marks */
+	for (i = 0; i < walk_start_nr; i++)
+		clear_commit_marks(walk_start[i], STALE);
+	free(walk_start);
+
+	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,