[v2,0/3] Make add_missing_tags() linear

Message

Kazuhiro Kato via GitGitGadget Nov. 2, 2018, 1:14 p.m. UTC

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

Thanks, -Stolee

[1] 
https://public-inbox.org/git/[e-mail]/

Derrick Stolee (3):
  commit-reach: implement get_reachable_subset
  test-reach: test get_reachable_subset
  remote: make add_missing_tags() linear

 commit-reach.c        | 70 +++++++++++++++++++++++++++++++++++++++++++
 commit-reach.h        | 13 ++++++++
 remote.c              | 34 ++++++++++++++++++++-
 t/helper/test-reach.c | 34 ++++++++++++++++++---
 t/t6600-test-reach.sh | 52 ++++++++++++++++++++++++++++++++
 5 files changed, 198 insertions(+), 5 deletions(-)


base-commit: c670b1f876521c9f7cd40184bf7ed05aad843433
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-60%2Fderrickstolee%2Fadd-missing-tags-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-60/derrickstolee/add-missing-tags-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/60

Range-diff vs v1:

 1:  4c0c5c9143 ! 1:  9e570603bd commit-reach: implement get_reachable_subset
     @@ -49,7 +49,7 @@
      +
      +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
      +					 struct commit **to, int nr_to,
     -+					 int reachable_flag)
     ++					 unsigned int reachable_flag)
      +{
      +	struct commit **item;
      +	struct commit *current;
     @@ -129,9 +129,12 @@
      + * 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.
     ++ *
     ++ * This method uses the PARENT1 and PARENT2 flags during its operation,
     ++ * so be sure these flags are not set before calling the method.
      + */
      +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
      +					 struct commit **to, int nr_to,
     -+					 int reachable_flag);
     ++					 unsigned int reachable_flag);
      +
       #endif
 2:  382f4f4a5b = 2:  52e847b928 test-reach: test get_reachable_subset
 3:  ecbed3de5c = 3:  dfaceb162f remote: make add_missing_tags() linear