From cc7dc407fe4c153195e5ce38d0109f3c2c35ceaf Mon Sep 17 00:00:00 2001 From: Phil Hord Date: Tue, 1 Jul 2025 18:12:13 -0700 Subject: 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 --- refs.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'refs.c') 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; } -- cgit v1.3