On Tue, Oct 30, 2018 at 7:16 AM Derrick Stolee via GitGitGadget <gitgitgadget@xxxxxxxxx> wrote: > > 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(). 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. Anyway, looks good in my testing. Thanks much for working on this!
