Skip to content

fetch --prune performance problem

Phil Hord git 4 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest3 patches 4 repliesIn review
  2. v32 patches 2 repliesSuperseded
  3. v22 patches 1 replySuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v1 RFC2 patches11 repliesSuperseded

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/3fetch-prune: optimize dangling-ref reportingbuiltin/fetch.c builtin/remote.c refs.c+13 -130 replies
2/3refs: remove old refs_warn_dangling_symrefrefs.c refs.h+1 -180 replies
3/3clean up interface for refs_warn_dangling_symrefsbuiltin/fetch.c builtin/remote.c refs.c +1 more+15 -151 reply

Reviews trailers per patch

1 of 3 patches has a Reviewed-by or Acked-by.

PatchJacob Keller
1/3R-b
2/3
3/3

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v4 thread

Cover letter [PATCH v4 0/3] fetch --prune performance problem

From: Phil Hord <[email protected]>

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.

V3 forgot to include the first commit in the series (I forgot it grew). So here's V4.

Phil Hord (3):
fetch-prune: optimize dangling-ref reporting
refs: remove old refs_warn_dangling_symref clean up interface for refs_warn_dangling_symrefs

 builtin/fetch.c  | 19 ++++++++-----------
 builtin/remote.c |  5 +----
 refs.c           | 34 ++++++++++++----------------------
 refs.h           |  5 ++---
 4 files changed, 23 insertions(+), 40 deletions(-)
Signature · 1 line
2.50.0.149.g1bab277d62