Phil Hord <phil.hord@xxxxxxxxx> writes: > From: Phil Hord <phil.hord@xxxxxxxxx> > > 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. > > 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 4 seconds. Nice.
