Make add_missing_tags() linear

Add a new method in commit-reach.c called get_reachable_subset() which does a many-to-many reachability test. Starting at the 'from' commits, walk until the generation is below the smallest generation in the 'to' commits, or all 'to' commits have been discovered. This performs only one commit walk for the entire add_missing_tags() method, giving linear performance in the worst case.

commit-reach.c +23 -0

+{
+	struct commit **item;
+	struct commit *current;
+	struct commit_list *found_commits = NULL;
+	struct commit **to_last = to + nr_to;
+	struct commit **from_last = from + nr_from;
+	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
+	int num_to_find = 0;
+
+	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+
+	for (item = to; item < to_last; item++) {
+		struct commit *c = *item;
+		
+		parse_commit(c);
+		if (c->generation < min_generation)
+			min_generation = c->generation;
+
+		if (!(c->object.flags & PARENT1)) {
+			c->object.flags |= PARENT1;
+			num_to_find++;
+		}
+	}

commit-reach.h +10 -0

index 7d313e297..43bd50a70 100644
@@ -74,4 +74,14 @@ int can_all_from_reach_with_flag(struct object_array *from,
 int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 		       int commit_date_cutoff);
 
+
+/*
+ * Return a list of commits containing the commits in the 'to' array
+ * that are reachable from at least one commit in the 'from' array.
+ * Also add the given 'flag' to each of the commits in the returned list.
+ */
+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
+					 struct commit **to, int nr_to,
+					 int reachable_flag);
+
 #endif

As reported earlier [1], the add_missing_tags() method in remote.c has quadratic performance. Some of that performance is curbed due to the generation-number cutoff in in_merge_bases_many(). However, that fix doesn't help users without a commit-graph, and it can still be painful if that cutoff is sufficiently low compared to the tags we are using for reachability testing.

Add a new method in commit-reach.c called get_reachable_subset() which does a many-to-many reachability test. Starting at the 'from' commits, walk until the generation is below the smallest generation in the 'to' commits, or all 'to' commits have been discovered. This performs only one commit walk for the entire add_missing_tags() method, giving linear performance in the worst case.

Tests are added in t6600-test-reach.sh to ensure get_reachable_subset() works independently of its application in add_missing_tags().

commit-reach.c +11 -0

@@ -688,3 +688,73 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
        object_array_clear(&from_objs);
        return result;
 }
+
+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
+                                        struct commit **to, int nr_to,
+                                        int reachable_flag)
+{
+       struct commit **item;
+       struct commit *current;
+       struct commit_list *found_commits = NULL;
+       struct commit **to_last = to + nr_to;
+       struct commit **from_last = from + nr_from;
+       uint32_t min_generation = GENERATION_NUMBER_INFINITY;

commit-reach.c +49 -0

+
+               if (!(c->object.flags & PARENT1)) {
+                       c->object.flags |= PARENT1;
+                       num_to_find++;
+               }
+       }
+
+       for (item = from; item < from_last; item++) {
+               struct commit *c = *item;
+               if (!(c->object.flags & PARENT2)) {
+                       c->object.flags |= PARENT2;
+                       parse_commit(c);
+
+                       prio_queue_put(&queue, *item);
+               }
+       }
+
+       while (num_to_find && (current = prio_queue_get(&queue)) != NULL) {
+               struct commit_list *parents;
+
+               if (current->object.flags & PARENT1) {
+                       current->object.flags &= ~PARENT1;
+                       current->object.flags |= reachable_flag;
+                       commit_list_insert(current, &found_commits);
+                       num_to_find--;
+               }
+
+               for (parents = current->parents; parents; parents = parents->next) {
+                       struct commit *p = parents->item;
+
+                       parse_commit(p);
+
+                       if (p->generation < min_generation)
+                               continue;
+
+                       if (p->object.flags & PARENT2)
+                               continue;
+
+                       p->object.flags |= PARENT2;
+                       prio_queue_put(&queue, p);
+               }
+       }
+
+       clear_commit_marks_many(nr_to, to, PARENT1);
+       clear_commit_marks_many(nr_from, from, PARENT2);
+
+       return found_commits;
+}
+

commit-reach.h +10 -1

index 7d313e297..43bd50a70 100644
@@ -74,4 +74,14 @@ int can_all_from_reach_with_flag(struct object_array *from,
 int can_all_from_reach(struct commit_list *from, struct commit_list *to,
                       int commit_date_cutoff);
 
+
+/*
+ * Return a list of commits containing the commits in the 'to' array
+ * that are reachable from at least one commit in the 'from' array.
+ * Also add the given 'flag' to each of the commits in the returned list.
+ */
+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
+                                        struct commit **to, int nr_to,
+                                        int reachable_flag);
+
 #endif
--

gitgitgadget

Quoted 23 lines · Derrick Stolee via GitGitGadget

commit-reach.c +17 -0

@@ -688,3 +688,73 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
         object_array_clear(&from_objs);
         return result;
  }
+
+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
+                                        struct commit **to, int nr_to,
+                                        int reachable_flag)
+{
+       struct commit **item;
+       struct commit *current;
+       struct commit_list *found_commits = NULL;
+       struct commit **to_last = to + nr_to;
+       struct commit **from_last = from + nr_from;
+       uint32_t min_generation = GENERATION_NUMBER_INFINITY;
+       int num_to_find = 0;
+
+       struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+
+       for (item = to; item < to_last; item++) {
+               struct commit *c = *item;

commit-reach.c int can_all_from_reach(struct commit_list *from, struct commit_list *to, · line 711

Quoted 4 lines

commit-reach.c +4 -0

+
+               parse_commit(c);
+               if (c->generation < min_generation)
+                       min_generation = c->generation;

So, when we don't have a commit-graph, is c->generation just going to be 0, making min_generation also be 0? (meaning we get no possible speed benefit from the commit-graph, since we just don't have that information available)?

commit-reach.c int can_all_from_reach(struct commit_list *from, struct commit_list *to, · line 694

Quoted 3 lines · Derrick Stolee via GitGitGadget

commit-reach.c +3 -0

+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
+					 struct commit **to, int nr_to,
+					 int reachable_flag)

This is OR'ed into object.flags, and I somoehow expected to see it as 'unsigned int', not a signed one.

Quoted 24 lines

commit-reach.c +23 -0

+{
+	struct commit **item;
+	struct commit *current;
+	struct commit_list *found_commits = NULL;
+	struct commit **to_last = to + nr_to;
+	struct commit **from_last = from + nr_from;
+	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
+	int num_to_find = 0;
+
+	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+
+	for (item = to; item < to_last; item++) {
+		struct commit *c = *item;
+		
+		parse_commit(c);
+		if (c->generation < min_generation)
+			min_generation = c->generation;
+
+		if (!(c->object.flags & PARENT1)) {
+			c->object.flags |= PARENT1;
+			num_to_find++;
+		}
+	}

commit-reach.c int can_all_from_reach(struct commit_list *from, struct commit_list *to, · line 727

Quoted 10 lines

commit-reach.c +10 -0

+
+	for (item = from; item < from_last; item++) {
+		struct commit *c = *item;
+		if (!(c->object.flags & PARENT2)) {
+			c->object.flags |= PARENT2;
+			parse_commit(c);
+
+			prio_queue_put(&queue, *item);
+		}
+	}

OK, we marked "to" with PARENT1 and counted them in num_to_find without dups. We also marked "from" with PARENT2 and threw them in the "queue" without dups.

Mental note: the caller must guarantee that everybody reachable from "to" and "from" have PARENT1 and PARENT2 clear. This might deserve to be in the comment before the function.

OK, this all makes sense. Unlike merge-base traversals, this does not have to traverse from the "to" side at all, which makes it quite simpler and straight-forward.

I do wonder if we can now reimplement in_merge_bases_many() in terms of this helper, and if that gives us a better performance. It asks "is 'commit', i.e. a single 'to', an ancestor of, i.e. reachable from, one of the 'references', i.e. 'from'"?

Quoted 15 lines · Derrick Stolee via GitGitGadget

As reported earlier [1], the add_missing_tags() method in remote.c has quadratic performance. Some of that performance is curbed due to the generation-number cutoff in in_merge_bases_many(). However, that fix doesn't help users without a commit-graph, and it can still be painful if that cutoff is sufficiently low compared to the tags we are using for reachability testing.

Add a new method in commit-reach.c called get_reachable_subset() which does a many-to-many reachability test. Starting at the 'from' commits, walk until the generation is below the smallest generation in the 'to' commits, or all 'to' commits have been discovered. This performs only one commit walk for the entire add_missing_tags() method, giving linear performance in the worst case.

Quoted 2 lines

Tests are added in t6600-test-reach.sh to ensure get_reachable_subset() works independently of its application in add_missing_tags().

On the original repo where the topic was brought up, with commit-graph NOT turned on and using origin/master, I see:

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
To /home/newren/repo-mirror
 * [new branch]       test5 -> test5

real 1m20.081s
user 1m19.688s
sys 0m0.292s

Merging this series in, I now get:

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
To /home/newren/repo-mirror
 * [new branch]       test5 -> test5

real 0m2.857s
user 0m2.580s
sys 0m0.328s

which provides a very nice speedup.

Oddly enough, if I _also_ do the following:

$ git config core.commitgraph true
$ git config gc.writecommitgraph true
$ git gc

then my timing actually slows down just slightly:

$ time git push --follow-tags --dry-run /home/newren/repo-mirror
To /home/newren/repo-mirror
 * [new branch]          test5 -> test5

real 0m3.027s
user 0m2.696s
sys 0m0.400s

(run-to-run variation seems pretty consistent, < .1s variation, so this difference is just enough to notice.) I wouldn't be that surprised if that means there's some really old tags with very small generation numbers, meaning it's not gaining anything in this special case from the commit-graph, but it does pay the cost of loading the commit-graph.

Quoted 48 lines · Elijah Newren

Quoted 15 lines · Derrick Stolee via GitGitGadget

As reported earlier [1], the add_missing_tags() method in remote.c has quadratic performance. Some of that performance is curbed due to the generation-number cutoff in in_merge_bases_many(). However, that fix doesn't help users without a commit-graph, and it can still be painful if that cutoff is sufficiently low compared to the tags we are using for reachability testing.

Add a new method in commit-reach.c called get_reachable_subset() which does a many-to-many reachability test. Starting at the 'from' commits, walk until the generation is below the smallest generation in the 'to' commits, or all 'to' commits have been discovered. This performs only one commit walk for the entire add_missing_tags() method, giving linear performance in the worst case.

Quoted 2 lines

Tests are added in t6600-test-reach.sh to ensure get_reachable_subset() works independently of its application in add_missing_tags().

On the original repo where the topic was brought up, with commit-graph NOT turned on and using origin/master, I see:

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
To /home/newren/repo-mirror
 * [new branch]       test5 -> test5

real 1m20.081s
user 1m19.688s
sys 0m0.292s

Merging this series in, I now get:

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
To /home/newren/repo-mirror
 * [new branch]       test5 -> test5

real 0m2.857s
user 0m2.580s
sys 0m0.328s

which provides a very nice speedup.

Oddly enough, if I _also_ do the following:

$ git config core.commitgraph true
$ git config gc.writecommitgraph true
$ git gc

Quoted 8 lines

then my timing actually slows down just slightly:

$ time git push --follow-tags --dry-run /home/newren/repo-mirror
To /home/newren/repo-mirror
 * [new branch]          test5 -> test5

real 0m3.027s
user 0m2.696s
sys 0m0.400s

So you say that the commit-graph is off in the 2.8s case, but not here in the 3.1s case? I would expect _at minimum_ that the cost of parsing commits would have a speedup in the commit-graph case. There may be something else going on here, since you are timing a push event that is doing more than the current walk.

Quoted 6 lines

(run-to-run variation seems pretty consistent, < .1s variation, so this difference is just enough to notice.) I wouldn't be that surprised if that means there's some really old tags with very small generation numbers, meaning it's not gaining anything in this special case from the commit-graph, but it does pay the cost of loading the commit-graph.

While you have this test environment, do you mind applying the diff below and re-running the tests? It will output a count for how many commits are walked by the algorithm. This should help us determine if this is another case where generation numbers are worse than commit-date, or if there is something else going on. Thanks!

Quoted 50 lines · Derrick Stolee

Quoted 29 lines · Elijah Newren

On the original repo where the topic was brought up, with commit-graph NOT turned on and using origin/master, I see:

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
To /home/newren/repo-mirror
  * [new branch]       test5 -> test5

real 1m20.081s
user 1m19.688s
sys 0m0.292s

Merging this series in, I now get:

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
To /home/newren/repo-mirror
  * [new branch]       test5 -> test5

real 0m2.857s
user 0m2.580s
sys 0m0.328s

which provides a very nice speedup.

Oddly enough, if I _also_ do the following:

$ git config core.commitgraph true
$ git config gc.writecommitgraph true
$ git gc

Quoted 8 lines

then my timing actually slows down just slightly:

$ time git push --follow-tags --dry-run /home/newren/repo-mirror
To /home/newren/repo-mirror
  * [new branch]          test5 -> test5

real 0m3.027s
user 0m2.696s
sys 0m0.400s

So you say that the commit-graph is off in the 2.8s case, but not here in the 3.1s case? I would expect _at minimum_ that the cost of parsing commits would have a speedup in the commit-graph case. There may be something else going on here, since you are timing a push event that is doing more than the current walk.

Quoted 6 lines

(run-to-run variation seems pretty consistent, < .1s variation, so this difference is just enough to notice.) I wouldn't be that surprised if that means there's some really old tags with very small generation numbers, meaning it's not gaining anything in this special case from the commit-graph, but it does pay the cost of loading the commit-graph.

Quoted 5 lines

While you have this test environment, do you mind applying the diff below and re-running the tests? It will output a count for how many commits are walked by the algorithm. This should help us determine if this is another case where generation numbers are worse than commit-date, or if there is something else going on. Thanks!

I can do that, but wouldn't you want a similar patch for the old get_merge_bases_many() in order to compare? Does an absolute number help by itself?
It's going to have to be tomorrow, though; not enough time tonight.

Quoted 56 lines · Elijah Newren

Quoted 50 lines · Derrick Stolee

Quoted 29 lines · Elijah Newren

On the original repo where the topic was brought up, with commit-graph NOT turned on and using origin/master, I see:

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
To /home/newren/repo-mirror
  * [new branch]       test5 -> test5

real 1m20.081s
user 1m19.688s
sys 0m0.292s

Merging this series in, I now get:

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
To /home/newren/repo-mirror
  * [new branch]       test5 -> test5

real 0m2.857s
user 0m2.580s
sys 0m0.328s

which provides a very nice speedup.

Oddly enough, if I _also_ do the following:

$ git config core.commitgraph true
$ git config gc.writecommitgraph true
$ git gc

Quoted 8 lines

then my timing actually slows down just slightly:

$ time git push --follow-tags --dry-run /home/newren/repo-mirror
To /home/newren/repo-mirror
  * [new branch]          test5 -> test5

real 0m3.027s
user 0m2.696s
sys 0m0.400s

So you say that the commit-graph is off in the 2.8s case, but not here in the 3.1s case? I would expect _at minimum_ that the cost of parsing commits would have a speedup in the commit-graph case. There may be something else going on here, since you are timing a push event that is doing more than the current walk.

Quoted 6 lines

(run-to-run variation seems pretty consistent, < .1s variation, so this difference is just enough to notice.) I wouldn't be that surprised if that means there's some really old tags with very small generation numbers, meaning it's not gaining anything in this special case from the commit-graph, but it does pay the cost of loading the commit-graph.

Quoted 5 lines

While you have this test environment, do you mind applying the diff below and re-running the tests? It will output a count for how many commits are walked by the algorithm. This should help us determine if this is another case where generation numbers are worse than commit-date, or if there is something else going on. Thanks!

Quoted 4 lines

I can do that, but wouldn't you want a similar patch for the old get_merge_bases_many() in order to compare? Does an absolute number help by itself?
It's going to have to be tomorrow, though; not enough time tonight.

No rush. I'd just like to understand how removing the commit-graph file can make the new algorithm faster. Putting a similar count in the old algorithm would involve giving a count for every call to in_merge_bases_many(), which would be very noisy.

Quoted 4 lines · Derrick Stolee

No rush. I'd just like to understand how removing the commit-graph file can make the new algorithm faster. Putting a similar count in the old algorithm would involve giving a count for every call to in_merge_bases_many(), which would be very noisy.

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
count: 92912
To /home/newren/repo-mirror
  * [new branch]              test5 -> test5

real 0m3.024s
user 0m2.752s
sys 0m0.320s

We could do this, but it does come with a performance hit when the following are all true:

1. 'to' is not reachable from any 'from' commits.

2. The 'to' and 'from' commits are close in commit-date.

3. Generation numbers are not available, or the topology is skewed to have commits with high commit date and low generation number.

Since in_merge_bases_many() calls paint_down_to_common(), it has the same issues with the current generation numbers. This can be fixed when we have the next version of generation numbers available.

I'll make a note to have in_merge_bases_many() call get_reachable_subset() conditionally (like the generation_numbers_available() trick in the --topo-order
series) after the generation numbers are settled and implemented.

Quoted 10 lines · Elijah Newren

Quoted 4 lines · Derrick Stolee

No rush. I'd just like to understand how removing the commit-graph file can make the new algorithm faster. Putting a similar count in the old algorithm would involve giving a count for every call to in_merge_bases_many(), which would be very noisy.

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
count: 92912
To /home/newren/repo-mirror
  * [new branch]              test5 -> test5

Quoted 3 lines

real 0m3.024s
user 0m2.752s
sys 0m0.320s

Is the above test with or without the commit-graph file? Can you run it in the other mode, too? I'd like to see if the "count" value changes when the only difference is the presence of a commit-graph file.

Quoted 11 lines · Derrick Stolee

Quoted 10 lines · Elijah Newren

Quoted 4 lines · Derrick Stolee

No rush. I'd just like to understand how removing the commit-graph file can make the new algorithm faster. Putting a similar count in the old algorithm would involve giving a count for every call to in_merge_bases_many(), which would be very noisy.

$ time git push --dry-run --follow-tags /home/newren/repo-mirror
count: 92912
To /home/newren/repo-mirror
   * [new branch]              test5 -> test5

Quoted 6 lines

Quoted 3 lines

real 0m3.024s
user 0m2.752s
sys 0m0.320s

Is the above test with or without the commit-graph file? Can you run it in the other mode, too? I'd like to see if the "count" value changes when the only difference is the presence of a commit-graph file.

I apologize for providing misleading information earlier; this was an apples to oranges comparison. Here's what I did:

<build a version of git with your fixes>
git clone coworker.bundle coworker-repo
cd coworker-repo
time git push --dry-run --follow-tags /home/newren/repo-mirror git config core.commitgraph true
git config gc.writecommitgraph true
git gc
time git push --dry-run --follow-tags /home/newren/nucleus-mirror

I figured I had just done a fresh clone, so surely the gc wouldn't do anything other than write the .git/objects/info/commit-graph file. However, the original bundle contained many references outside of refs/heads/ and refs/tags/:

$ git bundle list-heads ../coworker.bundle | grep -v -e refs/heads/ -e
refs/tags/ -e HEAD | wc -l
2396

These other refs apparently referred to objects not otherwise referenced in refs/heads/ and refs/tags/, and caused the gc to explode lots of loose objects:

$ git count-objects -v
count: 147604
size: 856416
in-pack: 1180692
packs: 1
size-pack: 796143
prune-packable: 0
garbage: 0
size-garbage: 0

The slowdown with commit-graph was entirely due to there being lots of loose objects (147K of them). If I add a git-prune before doing the timing with commit-graph, then the timing with commit-graph is faster than the run without a commit-graph.

Sorry for the wild goose chase.

And thanks for the fixes; get_reachable_subset() makes things much faster even without a commit-graph, and the commit-graph just improves it more. :-)