{"thread":{"id":"63685","subject":"[PATCH v2 0/2] fetch --prune performance problem","startedAt":"2025-06-23T23:43:57Z","lastAt":"2025-06-24T10:49:06Z","messageCount":4,"participants":["Phil Hord","Jeff King"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"520616","messageId":"20250623234327.335490-1-phil.hord@gmail.com","threadId":"63685","inReplyTo":null,"subject":"[PATCH v2 0/2] fetch --prune performance problem","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2025-06-23T23:43:25Z","receivedAt":"2025-06-23T23:43:57Z","isPatch":true,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"From: Phil Hord <phil.hord@gmail.com>\n\n`git fetch --prune` runs in O(N^2) time normally. This happens because the code\niterates over each ref to be pruned to display its status. In a repo with\n174,000 refs, where I was pruning 15,000 refs, the current code made 2.6 billion\ncalls to strcmp and consumed 470 seconds of CPU. After this change, the same\noperation completes in under 1 second.\n\nThe loop looks like this:\n\n    for p in prune_refs { for ref in all_refs { if p == ref { ... }}}\n\nThat loop runs only to check for and report newly dangling refs. A workaround to\navoid this slowness is to run with `-q` to bypass this check.\n\nThere is similar check/report functionality in `git remote prune`, but it uses a\nmore efficient method to check for dangling refs. prune_refs is first sorted, so\nit can be searched in O(logN), so this loop is O(N*logN).\n\n    for ref in all_refs { if ref in prune_refs { ... }}\n\nWe can use that function instead, with some minor cleanup to the output to deal\nwith the ordering being changed.\n\nThis patch version only adds the deleted branch name to the output of the dangling\nsym refs since the ordering has changed. This is only a minor cleanup and was\nnot actually needed since, for example, `git origin prune` already did not\nmind losing track of this information in its output. But now it is improved\nto be more explicit.\n\nPhil Hord (2):\n  fetch-prune: optimize dangling-ref reporting\n  refs: remove old refs_warn_dangling_symref\n\n builtin/fetch.c  | 20 ++++++++++----------\n builtin/remote.c |  4 ++--\n refs.c           | 21 ++++-----------------\n 3 files changed, 16 insertions(+), 29 deletions(-)\n\n-- \n2.50.0.84.g5d85fe910b.dirty\n\n"},{"id":"520617","messageId":"20250623234327.335490-2-phil.hord@gmail.com","threadId":"63685","inReplyTo":"20250623234327.335490-1-phil.hord@gmail.com","subject":"[PATCH v2 1/2] fetch-prune: optimize dangling-ref reporting","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2025-06-23T23:43:26Z","receivedAt":"2025-06-23T23:44:09Z","isPatch":true,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"From: Phil Hord <phil.hord@gmail.com>\n\nWhen pruning during `git fetch` we check each pruned ref against the\nref_store one at a time to decide whether to report it as dangling.\nThis causes every local ref to be scanned for each ref being pruned.\n\nIf there are N refs in the repo and M refs being pruned, this code is\nO(M*N). However, `git remote prune` uses a very similar function that\nis only O(N*log(M)).\n\nRemove the wasteful ref scanning for each pruned ref and use the faster\nversion already available in refs_warn_dangling_symrefs.\n\nIn a repo with 126,000 refs, where I was pruning 28,000 refs, this\ncode made about 3.6 billion calls to strcmp and consumed 410 seconds\nof CPU. (Invariably in that time, my remote would timeout and the\nfetch would fail anyway.)\n\nAfter this change, the same operation completes in under a second.\n\nSigned-off-by: Phil Hord <phil.hord@gmail.com>\nReviewed-by: Jacob Keller <jacob.e.keller@intel.com>\n---\n builtin/fetch.c  | 20 ++++++++++----------\n builtin/remote.c |  4 ++--\n refs.c           |  4 +++-\n 3 files changed, 15 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 40a0e8d24434..65d606c6de08 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -1383,9 +1383,13 @@ static int prune_refs(struct display_state *display_state,\n \tint result = 0;\n \tstruct ref *ref, *stale_refs = get_stale_heads(rs, ref_map);\n \tstruct strbuf err = STRBUF_INIT;\n+\tstruct string_list refnames = STRING_LIST_INIT_NODUP;\n \tconst char *dangling_msg = dry_run\n-\t\t? _(\"   (%s will become dangling)\")\n-\t\t: _(\"   (%s has become dangling)\");\n+\t\t? _(\"   %s will become dangling after %s is deleted\")\n+\t\t: _(\"   %s has become dangling after %s was deleted\");\n+\n+\tfor (ref = stale_refs; ref; ref = ref->next)\n+\t\tstring_list_append(&refnames, ref->name);\n \n \tif (!dry_run) {\n \t\tif (transaction) {\n@@ -1396,15 +1400,9 @@ static int prune_refs(struct display_state *display_state,\n \t\t\t\t\tgoto cleanup;\n \t\t\t}\n \t\t} else {\n-\t\t\tstruct string_list refnames = STRING_LIST_INIT_NODUP;\n-\n-\t\t\tfor (ref = stale_refs; ref; ref = ref->next)\n-\t\t\t\tstring_list_append(&refnames, ref->name);\n-\n \t\t\tresult = refs_delete_refs(get_main_ref_store(the_repository),\n \t\t\t\t\t\t  \"fetch: prune\", &refnames,\n \t\t\t\t\t\t  0);\n-\t\t\tstring_list_clear(&refnames, 0);\n \t\t}\n \t}\n \n@@ -1416,12 +1414,14 @@ static int prune_refs(struct display_state *display_state,\n \t\t\t\t\t   _(\"(none)\"), ref->name,\n \t\t\t\t\t   &ref->new_oid, &ref->old_oid,\n \t\t\t\t\t   summary_width);\n-\t\t\trefs_warn_dangling_symref(get_main_ref_store(the_repository),\n-\t\t\t\t\t\t  stderr, dangling_msg, ref->name);\n \t\t}\n+\t\tstring_list_sort(&refnames);\n+\t\trefs_warn_dangling_symrefs(get_main_ref_store(the_repository),\n+\t\t\t\t\t   stderr, dangling_msg, &refnames);\n \t}\n \n cleanup:\n+\tstring_list_clear(&refnames, 0);\n \tstrbuf_release(&err);\n \tfree_refs(stale_refs);\n \treturn result;\ndiff --git a/builtin/remote.c b/builtin/remote.c\nindex 0d6755bcb71e..4de7dd373ae5 100644\n--- a/builtin/remote.c\n+++ b/builtin/remote.c\n@@ -1522,8 +1522,8 @@ static int prune_remote(const char *remote, int dry_run)\n \tstruct string_list refs_to_prune = STRING_LIST_INIT_NODUP;\n \tstruct string_list_item *item;\n \tconst char *dangling_msg = dry_run\n-\t\t? _(\" %s will become dangling!\")\n-\t\t: _(\" %s has become dangling!\");\n+\t\t? _(\" %s will become dangling after %s is deleted!\")\n+\t\t: _(\" %s has become dangling after %s was deleted!\");\n \n \tget_remote_ref_states(remote, &states, GET_REF_STATES);\n \ndiff --git a/refs.c b/refs.c\nindex dce5c49ca2ba..e2075a98c844 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -461,7 +461,9 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU\n \t\treturn 0;\n \t}\n \n-\tfprintf(d->fp, d->msg_fmt, refname);\n+\tskip_prefix(refname, \"refs/remotes/\", &refname);\n+\tskip_prefix(resolves_to, \"refs/remotes/\", &resolves_to);\n+\tfprintf(d->fp, d->msg_fmt, refname, resolves_to);\n \tfputc('\\n', d->fp);\n \treturn 0;\n }\n-- \n2.50.0.84.g5d85fe910b.dirty\n\n"},{"id":"520618","messageId":"20250623234327.335490-3-phil.hord@gmail.com","threadId":"63685","inReplyTo":"20250623234327.335490-1-phil.hord@gmail.com","subject":"[PATCH v2 2/2] refs: remove old refs_warn_dangling_symref","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2025-06-23T23:43:27Z","receivedAt":"2025-06-23T23:44:17Z","isPatch":true,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"From: Phil Hord <phil.hord@gmail.com>\n\nThe dangling warning function that takes a single ref to search for\nis no longer used.  Remove it.\n\nSigned-off-by: Phil Hord <phil.hord@gmail.com>\n---\n refs.c | 17 +----------------\n 1 file changed, 1 insertion(+), 16 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex e2075a98c844..a9fbb0c8f23c 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -438,7 +438,6 @@ static int for_each_filter_refs(const char *refname, const char *referent,\n struct warn_if_dangling_data {\n \tstruct ref_store *refs;\n \tFILE *fp;\n-\tconst char *refname;\n \tconst struct string_list *refnames;\n \tconst char *msg_fmt;\n };\n@@ -455,9 +454,7 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU\n \n \tresolves_to = refs_resolve_ref_unsafe(d->refs, refname, 0, NULL, NULL);\n \tif (!resolves_to\n-\t    || (d->refname\n-\t\t? strcmp(resolves_to, d->refname)\n-\t\t: !string_list_has_string(d->refnames, resolves_to))) {\n+\t    || !string_list_has_string(d->refnames, resolves_to)) {\n \t\treturn 0;\n \t}\n \n@@ -468,18 +465,6 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU\n \treturn 0;\n }\n \n-void refs_warn_dangling_symref(struct ref_store *refs, FILE *fp,\n-\t\t\t       const char *msg_fmt, const char *refname)\n-{\n-\tstruct warn_if_dangling_data data = {\n-\t\t.refs = refs,\n-\t\t.fp = fp,\n-\t\t.refname = refname,\n-\t\t.msg_fmt = msg_fmt,\n-\t};\n-\trefs_for_each_rawref(refs, warn_if_dangling_symref, &data);\n-}\n-\n void refs_warn_dangling_symrefs(struct ref_store *refs, FILE *fp,\n \t\t\t\tconst char *msg_fmt, const struct string_list *refnames)\n {\n-- \n2.50.0.84.g5d85fe910b.dirty\n\n"},{"id":"520633","messageId":"20250624104904.GE636332@coredump.intra.peff.net","threadId":"63685","inReplyTo":"20250623234327.335490-2-phil.hord@gmail.com","subject":"Re: [PATCH v2 1/2] fetch-prune: optimize dangling-ref reporting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-06-24T10:49:04Z","receivedAt":"2025-06-24T10:49:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 23, 2025 at 04:43:26PM -0700, Phil Hord wrote:\n\n> diff --git a/builtin/fetch.c b/builtin/fetch.c\n> index 40a0e8d24434..65d606c6de08 100644\n> --- a/builtin/fetch.c\n> +++ b/builtin/fetch.c\n> @@ -1383,9 +1383,13 @@ static int prune_refs(struct display_state *display_state,\n>  \tint result = 0;\n>  \tstruct ref *ref, *stale_refs = get_stale_heads(rs, ref_map);\n>  \tstruct strbuf err = STRBUF_INIT;\n> +\tstruct string_list refnames = STRING_LIST_INIT_NODUP;\n>  \tconst char *dangling_msg = dry_run\n> -\t\t? _(\"   (%s will become dangling)\")\n> -\t\t: _(\"   (%s has become dangling)\");\n> +\t\t? _(\"   %s will become dangling after %s is deleted\")\n> +\t\t: _(\"   %s has become dangling after %s was deleted\");\n\nThis approach seems reasonable. It is a little ugly that\nrefs_warn_dangling_symrefs() takes a printf-formatted string that must\ncontain the correct number of \"%s\" fields (and that we get no compiler\nwarnings if we get it wrong).\n\nBut that is not really new in your series. Given that there are two\ncallers and they use (almost) the same string, I wonder if we could\nrefactor the interface. We'd need to pass in the indentation level, and\nthe dry-run flag.\n\nI guess alternatively, we could have a function which passes back a\nstrvec or similar of danglers, but then both call sites would have more\nprinting boilerplate. I dunno. Maybe we should just avert our eyes and\nlive with it. ;)\n\n> diff --git a/refs.c b/refs.c\n> index dce5c49ca2ba..e2075a98c844 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -461,7 +461,9 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU\n>  \t\treturn 0;\n>  \t}\n>  \n> -\tfprintf(d->fp, d->msg_fmt, refname);\n> +\tskip_prefix(refname, \"refs/remotes/\", &refname);\n> +\tskip_prefix(resolves_to, \"refs/remotes/\", &resolves_to);\n> +\tfprintf(d->fp, d->msg_fmt, refname, resolves_to);\n>  \tfputc('\\n', d->fp);\n>  \treturn 0;\n\nThis prefix handling feels kind of ad-hoc. Should we use something like\nrefs_shorten_unambiguous_ref() to follow the usual rules?\n\nThis is also shortening the symref name, which didn't happen before.\nArguably that should happen in a separate patch, but I can live with it\neither way.\n\n-Peff\n"}]}