From cc7dc407fe4c153195e5ce38d0109f3c2c35ceaf Mon Sep 17 00:00:00 2001 From: Phil Hord Date: Tue, 1 Jul 2025 18:12:13 -0700 Subject: [PATCH] fetch-prune: optimize dangling-ref reporting When pruning during `git fetch` we check each pruned ref against the ref_store one at a time to decide whether to report it as dangling. This causes every local ref to be scanned for each ref being pruned. If there are N refs in the repo and M refs being pruned, this code is O(M*N). However, `git remote prune` uses a very similar function that is only O(N*log(M)). Remove the wasteful ref scanning for each pruned ref and use the faster version already available in refs_warn_dangling_symrefs. Change the message to include the original refname since the message is no longer printed immediately after the line that did just print the refname. In a repo with 126,000 refs, where I was pruning 28,000 refs, this code made about 3.6 billion calls to strcmp and consumed 410 seconds of CPU. (Invariably in that time, my remote would timeout and the fetch would fail anyway.) After this change, the same operation completes in under a second. Signed-off-by: Phil Hord Reviewed-by: Jacob Keller Signed-off-by: Junio C Hamano --- builtin/fetch.c | 20 ++++++++++---------- builtin/remote.c | 4 ++-- refs.c | 2 +- 3 files changed, 13 insertions(+), 13 deletions(-) diff --git a/builtin/fetch.c b/builtin/fetch.c index fe2b26c74a..f05530b62e 100644 --- a/builtin/fetch.c +++ b/builtin/fetch.c @@ -1384,9 +1384,13 @@ static int prune_refs(struct display_state *display_state, int result = 0; struct ref *ref, *stale_refs = get_stale_heads(rs, ref_map); struct strbuf err = STRBUF_INIT; + struct string_list refnames = STRING_LIST_INIT_NODUP; const char *dangling_msg = dry_run - ? _(" (%s will become dangling)") - : _(" (%s has become dangling)"); + ? _(" %s will become dangling after %s is deleted") + : _(" %s has become dangling after %s was deleted"); + + for (ref = stale_refs; ref; ref = ref->next) + string_list_append(&refnames, ref->name); if (!dry_run) { if (transaction) { @@ -1397,15 +1401,9 @@ static int prune_refs(struct display_state *display_state, goto cleanup; } } else { - struct string_list refnames = STRING_LIST_INIT_NODUP; - - for (ref = stale_refs; ref; ref = ref->next) - string_list_append(&refnames, ref->name); - result = refs_delete_refs(get_main_ref_store(the_repository), "fetch: prune", &refnames, 0); - string_list_clear(&refnames, 0); } } @@ -1417,12 +1415,14 @@ static int prune_refs(struct display_state *display_state, _("(none)"), ref->name, &ref->new_oid, &ref->old_oid, summary_width); - refs_warn_dangling_symref(get_main_ref_store(the_repository), - stderr, dangling_msg, ref->name); } + string_list_sort(&refnames); + refs_warn_dangling_symrefs(get_main_ref_store(the_repository), + stderr, dangling_msg, &refnames); } cleanup: + string_list_clear(&refnames, 0); strbuf_release(&err); free_refs(stale_refs); return result; diff --git a/builtin/remote.c b/builtin/remote.c index 0435963286..30cf4100d4 100644 --- a/builtin/remote.c +++ b/builtin/remote.c @@ -1516,8 +1516,8 @@ static int prune_remote(const char *remote, int dry_run) struct string_list refs_to_prune = STRING_LIST_INIT_NODUP; struct string_list_item *item; const char *dangling_msg = dry_run - ? _(" %s will become dangling!") - : _(" %s has become dangling!"); + ? _(" %s will become dangling after %s is deleted!") + : _(" %s has become dangling after %s was deleted!"); get_remote_ref_states(remote, &states, GET_REF_STATES); diff --git a/refs.c b/refs.c index 0f41b2fd4a..def147b685 100644 --- a/refs.c +++ b/refs.c @@ -461,7 +461,7 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU return 0; } - fprintf(d->fp, d->msg_fmt, refname); + fprintf(d->fp, d->msg_fmt, refname, resolves_to); fputc('\n', d->fp); return 0; } -- 2.47.3