public inbox for git@vger.kernel.org
 help / color / mirror / Atom feed
* [PATCH v3 0/2] fetch --prune performance problem
@ 2025-07-02  0:58 Phil Hord
  2025-07-02  0:58 ` [PATCH v3 1/2] refs: remove old refs_warn_dangling_symref Phil Hord
                   ` (2 more replies)
  0 siblings, 3 replies; 5+ messages in thread
From: Phil Hord @ 2025-07-02  0:58 UTC (permalink / raw)
  To: gitster; +Cc: peff, git, Jacob Keller, Phil Hord

From: Phil Hord <phil.hord@gmail.com>

`git fetch --prune` runs in O(N^2) time normally. This happens because the code
iterates over each ref to be pruned to display its status. In a repo with
174,000 refs, where I was pruning 15,000 refs, the current code made 2.6 billion
calls to strcmp and consumed 470 seconds of CPU. After this change, the same
operation completes in under 1 second.

The loop looks like this:

    for p in prune_refs { for ref in all_refs { if p == ref { ... }}}

That loop runs only to check for and report newly dangling refs. A workaround to
avoid this slowness is to run with `-q` to bypass this check.

There is similar check/report functionality in `git remote prune`, but it uses a
more efficient method to check for dangling refs. prune_refs is first sorted, so
it can be searched in O(logN), so this loop is O(N*logN).

    for ref in all_refs { if ref in prune_refs { ... }}

We can use that function instead, with some minor cleanup to the output to deal
with the ordering being changed.

This patch version only adds the deleted branch name to the output of the dangling
sym refs since the ordering has changed. This is only a minor cleanup and was
not actually needed since, for example, `git origin prune` already did not
mind losing track of this information in its output. But now it is improved
to be more explicit.

This version (V3) has three changes from V2:
 - Removes a header declaration I forgot to move previously
 - Cleans up the refs_warn_dangling_symrefs API to be more sane
 - Drops the ref shortening that seems ill-advised in retrospect

Phil Hord (2):
  refs: remove old refs_warn_dangling_symref
  clean up interface for refs_warn_dangling_symrefs

 builtin/fetch.c  |  5 +----
 builtin/remote.c |  5 +----
 refs.c           | 34 ++++++++++++----------------------
 refs.h           |  5 ++---
 4 files changed, 16 insertions(+), 33 deletions(-)

-- 
2.50.0.149.g2f19833911.dirty


^ permalink raw reply	[flat|nested] 5+ messages in thread
end of thread, other threads:[~2025-07-02  1:47 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-07-02  0:58 [PATCH v3 0/2] fetch --prune performance problem Phil Hord
2025-07-02  0:58 ` [PATCH v3 1/2] refs: remove old refs_warn_dangling_symref Phil Hord
2025-07-02  0:58 ` [PATCH v3 2/2] clean up interface for refs_warn_dangling_symrefs Phil Hord
2025-07-02  1:42 ` [PATCH v3 0/2] fetch --prune performance problem Junio C Hamano
2025-07-02  1:47   ` Junio C Hamano

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox