remote: make add_missing_tags() linear
authorDerrick Stolee <dstolee@microsoft.com>
Fri, 2 Nov 2018 13:14:49 +0000 (06:14 -0700)
committerJunio C Hamano <gitster@pobox.com>
Fri, 2 Nov 2018 15:12:06 +0000 (00:12 +0900)
The add_missing_tags() method currently has quadratic behavior.
This is due to a linear number (based on number of tags T) of
calls to in_merge_bases_many, which has linear performance (based
on number of commits C in the repository).

Replace this O(T * C) algorithm with an O(T + C) algorithm by
using get_reachable_subset(). We ignore the return list and focus
instead on the reachable_flag assigned to the commits we care
about, because we need to interact with the tag ref and not just
the commit object.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
No differences found