diff options
author | Derrick Stolee <dstolee@microsoft.com> | 2018-11-02 06:14:49 -0700 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2018-11-03 00:12:06 +0900 |
commit | 85daa01f6b80cb6eb14c5f484a6da9f0b1247143 (patch) | |
tree | 93a59bf1f2dba5246c12610c4fac0678e4b0ccd7 /builtin/grep.c | |
parent | test-reach: test get_reachable_subset (diff) | |
download | tgif-85daa01f6b80cb6eb14c5f484a6da9f0b1247143.tar.xz |
remote: make add_missing_tags() linear
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>
Diffstat (limited to 'builtin/grep.c')
0 files changed, 0 insertions, 0 deletions