{"thread":{"id":"63667","subject":"[RFC PATCH 0/2] fetch --prune performance problem","startedAt":"2025-06-18T21:10:54Z","lastAt":"2025-06-23T23:46:35Z","messageCount":14,"participants":["Phil Hord","Junio C Hamano","Jacob Keller","Jeff King","Lidong Yan"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"520369","messageId":"20250618211024.2332525-1-phil.hord@gmail.com","threadId":"63667","inReplyTo":null,"subject":"[RFC PATCH 0/2] fetch --prune performance problem","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2025-06-18T21:08:38Z","receivedAt":"2025-06-18T21:10:54Z","isPatch":true,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"From: Phil Hord \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\nMy patch fixes this for fetch, but it affects the command's output order.\nCurrently the results look like this:\n\n - [deleted] (none) -> origin/bar\n (origin/bar has become dangling)\n - [deleted] (none) -> origin/baz\n - [deleted] (none) -> origin/foo\n (origin/foo has become dangling)\n - [deleted] (none) -> origin/frotz\n\nAfter my change, the order will change so the danglers are reported at the end.\n\n - [deleted] (none) -> origin/bar\n - [deleted] (none) -> origin/baz\n - [deleted] (none) -> origin/foo\n - [deleted] (none) -> origin/frotz\n (origin/bar has become dangling)\n (origin/foo has become dangling)\n\nThe latter format is close to how `git remote prune` works, but the formatting\nis a bit different. I can coerce my change into something that preserves the\noriginal order, but it will be quite a bit messier.\n\nQ: Does anyone care enough about the command output ordering that they think\n it's worth the extra code complexity?\n\nPhil Hord (2):\n fetch-prune: optimize dangling-ref reporting\n refs: remove old refs_warn_dangling_symref\n\n builtin/fetch.c | 16 ++++++++--------\n refs.c | 17 +----------------\n 2 files changed, 9 insertions(+), 24 deletions(-)\n\n-- \n2.50.0.1.gf2ab606906.dirty\n\n"},{"id":"520370","messageId":"20250618211024.2332525-2-phil.hord@gmail.com","threadId":"63667","inReplyTo":"20250618211024.2332525-1-phil.hord@gmail.com","subject":"[RFC PATCH 1/2] fetch-prune: optimize dangling-ref reporting","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2025-06-18T21:08:39Z","receivedAt":"2025-06-18T21:11:06Z","isPatch":true,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"From: Phil Hord \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 4 seconds.\n\nI considered further optimizing this function to be O(N), but this\nrequires ref_store iterators to be sorted, too. I found some suggestions\nthat this is always the case, but I'm not certain it is.\n\nThe current speedup is enough for our needs at the moment.\n\nThis change causes a reordering of the output for any reported dangling\nrefs. Previously they would be reported inline with the \"fetch: prune\"\nmessages. Now they will be reported after all the original prune\nmessages are complete.\n\nSigned-off-by: Phil Hord \n---\n builtin/fetch.c | 16 ++++++++--------\n 1 file changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 40a0e8d24434..11ce51da780a 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -1383,10 +1383,14 @@ 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 \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 \t\t\tfor (ref = stale_refs; ref; ref = ref->next) {\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;\n-- \n2.50.0.1.gf2ab606906.dirty\n\n"},{"id":"520371","messageId":"20250618211024.2332525-3-phil.hord@gmail.com","threadId":"63667","inReplyTo":"20250618211024.2332525-1-phil.hord@gmail.com","subject":"[RFC PATCH 2/2] refs: remove old refs_warn_dangling_symref","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2025-06-18T21:08:40Z","receivedAt":"2025-06-18T21:11:14Z","isPatch":true,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"From: Phil Hord \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 \n---\n refs.c | 17 +----------------\n 1 file changed, 1 insertion(+), 16 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex dce5c49ca2ba..0669d8e07072 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@@ -466,18 +463,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.1.gf2ab606906.dirty\n\n"},{"id":"520375","messageId":"xmqqzfe4d8hy.fsf@gitster.g","threadId":"63667","inReplyTo":"20250618211024.2332525-2-phil.hord@gmail.com","subject":"Re: [RFC PATCH 1/2] fetch-prune: optimize dangling-ref reporting","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-06-18T21:50:49Z","receivedAt":"2025-06-18T21:50:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Phil Hord writes:\n\n> From: Phil Hord \n>\n> When pruning during `git fetch` we check each pruned ref against the\n> ref_store one at a time to decide whether to report it as dangling.\n> This causes every local ref to be scanned for each ref being pruned.\n>\n> If there are N refs in the repo and M refs being pruned, this code is\n> O(M*N). However, `git remote prune` uses a very similar function that\n> is only O(N*log(M)).\n>\n> Remove the wasteful ref scanning for each pruned ref and use the faster\n> version already available in refs_warn_dangling_symrefs.\n>\n> In a repo with 126,000 refs, where I was pruning 28,000 refs, this\n> code made about 3.6 billion calls to strcmp and consumed 410 seconds\n> of CPU. (Invariably in that time, my remote would timeout and the\n> fetch would fail anyway.)\n>\n> After this change, the same operation completes in under 4 seconds.\n\nNice.\n"},{"id":"520385","messageId":"9cc42f04-856b-4967-8668-a47271af061c@intel.com","threadId":"63667","inReplyTo":"20250618211024.2332525-1-phil.hord@gmail.com","subject":"Re: [RFC PATCH 0/2] fetch --prune performance problem","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2025-06-18T23:15:03Z","receivedAt":"2025-06-18T23:15:11Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"\n\nOn 6/18/2025 2:08 PM, Phil Hord wrote:\n> My patch fixes this for fetch, but it affects the command's output order.\n> Currently the results look like this:\n> \n> - [deleted] (none) -> origin/bar\n> (origin/bar has become dangling)\n> - [deleted] (none) -> origin/baz\n> - [deleted] (none) -> origin/foo\n> (origin/foo has become dangling)\n> - [deleted] (none) -> origin/frotz\n> \n> After my change, the order will change so the danglers are reported at the end.\n> \n> - [deleted] (none) -> origin/bar\n> - [deleted] (none) -> origin/baz\n> - [deleted] (none) -> origin/foo\n> - [deleted] (none) -> origin/frotz\n> (origin/bar has become dangling)\n> (origin/foo has become dangling)\n\nPersonally, I like the later output. I have no idea why anyone would be\nspecifically scripting something that depends on the ordering being such\nthat dangling messages are printed immediately.\n"},{"id":"520386","messageId":"905a668a-af3f-4b25-b35b-ba1f7e750b26@intel.com","threadId":"63667","inReplyTo":"20250618211024.2332525-2-phil.hord@gmail.com","subject":"Re: [RFC PATCH 1/2] fetch-prune: optimize dangling-ref reporting","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2025-06-18T23:18:42Z","receivedAt":"2025-06-18T23:18:49Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"\n\nOn 6/18/2025 2:08 PM, Phil Hord wrote:\n> From: Phil Hord \n> \n> When pruning during `git fetch` we check each pruned ref against the\n> ref_store one at a time to decide whether to report it as dangling.\n> This causes every local ref to be scanned for each ref being pruned.\n> \n> If there are N refs in the repo and M refs being pruned, this code is\n> O(M*N). However, `git remote prune` uses a very similar function that\n> is only O(N*log(M)).\n> \n> Remove the wasteful ref scanning for each pruned ref and use the faster\n> version already available in refs_warn_dangling_symrefs.\n> \n> In a repo with 126,000 refs, where I was pruning 28,000 refs, this\n> code made about 3.6 billion calls to strcmp and consumed 410 seconds\n> of CPU. (Invariably in that time, my remote would timeout and the\n> fetch would fail anyway.)\n> \n> After this change, the same operation completes in under 4 seconds.\n> \n\nThe cover letter said \"under a second\". Is this a different example?\n\n> I considered further optimizing this function to be O(N), but this\n> requires ref_store iterators to be sorted, too. I found some suggestions\n> that this is always the case, but I'm not certain it is.\n> \n> The current speedup is enough for our needs at the moment.\n> \n\nYep. Logarithmic scaling grows slow enough that this is probably\nreasonable unless someone wants to put the remaining effort in.\n\n> This change causes a reordering of the output for any reported dangling\n> refs. Previously they would be reported inline with the \"fetch: prune\"\n> messages. Now they will be reported after all the original prune\n> messages are complete.\n> \n\nI think this is reasonable especially for the speedup.\n\n> Signed-off-by: Phil Hord \n> ---\n\nReviewed-by: Jacob Keller \n\n> builtin/fetch.c | 16 ++++++++--------\n> 1 file changed, 8 insertions(+), 8 deletions(-)\n> \n> diff --git a/builtin/fetch.c b/builtin/fetch.c\n> index 40a0e8d24434..11ce51da780a 100644\n> --- a/builtin/fetch.c\n> +++ b/builtin/fetch.c\n> @@ -1383,10 +1383,14 @@ 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> \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> \t\t\tfor (ref = stale_refs; ref; ref = ref->next) {\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;\n\n"},{"id":"520395","messageId":"20250619033746.GA1801319@coredump.intra.peff.net","threadId":"63667","inReplyTo":"9cc42f04-856b-4967-8668-a47271af061c@intel.com","subject":"Re: [RFC PATCH 0/2] fetch --prune performance problem","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-06-19T03:37:46Z","receivedAt":"2025-06-19T03:37:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 18, 2025 at 04:15:03PM -0700, Jacob Keller wrote:\n\n> On 6/18/2025 2:08 PM, Phil Hord wrote:\n> > My patch fixes this for fetch, but it affects the command's output order.\n> > Currently the results look like this:\n> > \n> > - [deleted] (none) -> origin/bar\n> > (origin/bar has become dangling)\n> > - [deleted] (none) -> origin/baz\n> > - [deleted] (none) -> origin/foo\n> > (origin/foo has become dangling)\n> > - [deleted] (none) -> origin/frotz\n> > \n> > After my change, the order will change so the danglers are reported at the end.\n> > \n> > - [deleted] (none) -> origin/bar\n> > - [deleted] (none) -> origin/baz\n> > - [deleted] (none) -> origin/foo\n> > - [deleted] (none) -> origin/frotz\n> > (origin/bar has become dangling)\n> > (origin/foo has become dangling)\n> \n> Personally, I like the later output. I have no idea why anyone would be\n> specifically scripting something that depends on the ordering being such\n> that dangling messages are printed immediately.\n\nI think the original ordering tells you which deletion caused the ref to\nbecome dangling. Phil's example is a little confusing here:\n\n - [deleted] (none) -> origin/bar\n (origin/bar has become dangling)\n\nbecause the name is the same in both cases. A more likely output is that\norigin/HEAD becomes dangling (since it's the only symref Git ever\nautomatically points at a tracking ref). E.g., in this:\n\n git init repo\n cd repo\n \n git commit --allow-empty -m foo\n git branch some\n git branch other\n git branch branches\n \n git clone . child\n cur=$(git symbolic-ref --short HEAD)\n git checkout some\n git branch -d other branches $cur\n \n cd child\n git fetch --prune\n\nThe final fetch output looks like:\n\n - [deleted] (none) -> origin/branches\n - [deleted] (none) -> origin/main\n (refs/remotes/origin/HEAD has become dangling)\n - [deleted] (none) -> origin/other\n\nand we can see that the deletion of \"main\" is what caused the dangling.\n\nThat said, I'm not sure I care that much. I didn't even know we had this\ndangling message, and it's been around for over 15 years!\n\nIf we did want to preserve the ordering, it could be done by taking two\npasses (the first to create a reverse map of deletions to danglers, and\nthen the second to print each ref).\n\nAlternatively, the dangling message could just mention where it the\nnow-dangling symref points at, something like:\n\n - [deleted] (none) -> origin/branches\n - [deleted] (none) -> origin/main\n - [deleted] (none) -> origin/other\n (refs/remotes/origin/HEAD points to the now-deleted origin/main)\n\nI dunno. I guess anybody who really cares can run \"git symbolic-ref\norigin/HEAD\" themselves to get that information.\n\n-Peff\n"},{"id":"520396","messageId":"20250619040033.GB1801319@coredump.intra.peff.net","threadId":"63667","inReplyTo":"20250618211024.2332525-2-phil.hord@gmail.com","subject":"Re: [RFC PATCH 1/2] fetch-prune: optimize dangling-ref reporting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-06-19T04:00:33Z","receivedAt":"2025-06-19T04:00:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 18, 2025 at 02:08:39PM -0700, Phil Hord wrote:\n\n> From: Phil Hord \n> \n> When pruning during `git fetch` we check each pruned ref against the\n> ref_store one at a time to decide whether to report it as dangling.\n> This causes every local ref to be scanned for each ref being pruned.\n> \n> If there are N refs in the repo and M refs being pruned, this code is\n> O(M*N). However, `git remote prune` uses a very similar function that\n> is only O(N*log(M)).\n> \n> Remove the wasteful ref scanning for each pruned ref and use the faster\n> version already available in refs_warn_dangling_symrefs.\n> \n> In a repo with 126,000 refs, where I was pruning 28,000 refs, this\n> code made about 3.6 billion calls to strcmp and consumed 410 seconds\n> of CPU. (Invariably in that time, my remote would timeout and the\n> fetch would fail anyway.)\n> \n> After this change, the same operation completes in under 4 seconds.\n\nVery nice. I left some thoughts on the ordering question elsewhere, but\nI'd be OK with this approach, too.\n\n> I considered further optimizing this function to be O(N), but this\n> requires ref_store iterators to be sorted, too. I found some suggestions\n> that this is always the case, but I'm not certain it is.\n> \n> The current speedup is enough for our needs at the moment.\n\nI think we do guarantee the output order, and for-each-ref at least\ntakes advantage of this since 2e7c6d2f41 (ref-filter: format iteratively\nwith lexicographic refname sorting, 2024-10-21).\n\nThat said, I wouldn't be surprised if there are other n-log-n bits of\nthe code, and we usually consider that \"good enough\". So stopping here\nis probably fine.\n\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> \n> +\tfor (ref = stale_refs; ref; ref = ref->next)\n> +\t\tstring_list_append(&refnames, ref->name);\n\nI was going to suggest using strset over string_list, since I think we\nprefer that these days for a simple set-inclusion check. But...\n\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\n...we are ultimately relying on refs_warn_dangling_symrefs(), so we'd\nhave to update its interface. And we also reuse the list (here, after\nyour patch, but already in remote.c) to pass to refs_delete_refs(). So\nprobably not worth it.\n\n-Peff\n"},{"id":"520400","messageId":"B83B89F8-8129-445C-B4F5-43C86512C114@gmail.com","threadId":"63667","inReplyTo":"20250619040033.GB1801319@coredump.intra.peff.net","subject":"Re: [RFC PATCH 1/2] fetch-prune: optimize dangling-ref reporting","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-06-19T11:01:10Z","receivedAt":"2025-06-19T11:01:25Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Jeff King writes：\n> ...we are ultimately relying on refs_warn_dangling_symrefs(), so we'd\n> have to update its interface. And we also reuse the list (here, after\n> your patch, but already in remote.c) to pass to refs_delete_refs(). So\n> probably not worth it.\n\nThis patch only adds sorting code to prune_refs(), and as far as I can tell,\nprune_refs() is only called once during git fetch. So I was just wondering,\nwould it be problematic if we moved the string_list_sort() into\nrefs_warn_dangling_symref() instead? And if it turns out to be safe, could\nwe perhaps even use strset in refs_warn_dangling_symref()?"},{"id":"520409","messageId":"A68FFEEC-0406-4280-BC7A-67C932141F41@gmail.com","threadId":"63667","inReplyTo":"B83B89F8-8129-445C-B4F5-43C86512C114@gmail.com","subject":"Re: [RFC PATCH 1/2] fetch-prune: optimize dangling-ref reporting","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-06-19T14:41:28Z","receivedAt":"2025-06-19T14:41:42Z","isPatch":true,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Lidong Yan writes：\n> \n> This patch only adds sorting code to prune_refs(), and as far as I can tell,\n> prune_refs() is only called once during git fetch. So I was just wondering,\n> would it be problematic if we moved the string_list_sort() into\n> refs_warn_dangling_symref() instead? And if it turns out to be safe, could\n> we perhaps even use strset in refs_warn_dangling_symref()?\n\nAh, sorry I make a mistake. We can’t sort string_list in refs_warn_dangling_symref()."},{"id":"520415","messageId":"xmqq7c17abw4.fsf@gitster.g","threadId":"63667","inReplyTo":"20250619033746.GA1801319@coredump.intra.peff.net","subject":"Re: [RFC PATCH 0/2] fetch --prune performance problem","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-06-19T17:18:03Z","receivedAt":"2025-06-19T17:18:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> The final fetch output looks like:\n>\n> - [deleted] (none) -> origin/branches\n> - [deleted] (none) -> origin/main\n> (refs/remotes/origin/HEAD has become dangling)\n> - [deleted] (none) -> origin/other\n>\n> and we can see that the deletion of \"main\" is what caused the dangling.\n>\n> That said, I'm not sure I care that much. I didn't even know we had this\n> dangling message, and it's been around for over 15 years!\n\nSame here. I agree that the new output, while it may look prettier,\nloses information. I agree with your conclusion that the user who\nreally cares can check with symbolic-ref themselves.\n"},{"id":"520613","messageId":"f11bf463-0005-43d2-b642-ede130d1f44c@intel.com","threadId":"63667","inReplyTo":"CABURp0p4d0JPg=-cW1OZdFQJ+vNT_0PDd9Rv3oz6toFGqGv5=g@mail.gmail.com","subject":"Re: [RFC PATCH 0/2] fetch --prune performance problem","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2025-06-23T23:32:35Z","receivedAt":"2025-06-23T23:32:50Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"\n\nOn 6/23/2025 4:11 PM, Phil Hord wrote:\n> On Wed, Jun 18, 2025 at 8:37 PM Jeff King wrote:\n>> On Wed, Jun 18, 2025 at 04:15:03PM -0700, Jacob Keller wrote:\n>>> On 6/18/2025 2:08 PM, Phil Hord wrote:\n>>>> My patch fixes this for fetch, but it affects the command's output\n> order.\n>>>> Currently the results look like this:\n>>>>\n>>>> - [deleted] (none) -> origin/bar\n>>>> (origin/bar has become dangling)\n>>>> - [deleted] (none) -> origin/baz\n>>>> - [deleted] (none) -> origin/foo\n>>>> (origin/foo has become dangling)\n>>>> - [deleted] (none) -> origin/frotz\n>>>>\n>>>> After my change, the order will change so the danglers are reported\n> at the end.\n>>>>\n>>>> - [deleted] (none) -> origin/bar\n>>>> - [deleted] (none) -> origin/baz\n>>>> - [deleted] (none) -> origin/foo\n>>>> - [deleted] (none) -> origin/frotz\n>>>> (origin/bar has become dangling)\n>>>> (origin/foo has become dangling)\n>>>\n>>> Personally, I like the later output. I have no idea why anyone would be\n>>> specifically scripting something that depends on the ordering being such\n>>> that dangling messages are printed immediately.\n>>\n>> I think the original ordering tells you which deletion caused the ref to\n>> become dangling. Phil's example is a little confusing here:\n>>\n>> - [deleted] (none) -> origin/bar\n>> (origin/bar has become dangling)\n>>\n>> because the name is the same in both cases. A more likely output is that\n>> origin/HEAD becomes dangling (since it's the only symref Git ever\n>> automatically points at a tracking ref). E.g., in this:\n>>\n>> git init repo\n>> cd repo\n>>\n>> git commit --allow-empty -m foo\n>> git branch some\n>> git branch other\n>> git branch branches\n>>\n>> git clone . child\n>> cur=$(git symbolic-ref --short HEAD)\n>> git checkout some\n>> git branch -d other branches $cur\n>>\n>> cd child\n>> git fetch --prune\n> \n> Thanks for the helpful demo and clarification of the real output.\n> \n>> The final fetch output looks like:\n>>\n>> - [deleted] (none) -> origin/branches\n>> - [deleted] (none) -> origin/main\n>> (refs/remotes/origin/HEAD has become dangling)\n>> - [deleted] (none) -> origin/other\n>>\n>> and we can see that the deletion of \"main\" is what caused the dangling.\n>>\n>> That said, I'm not sure I care that much. I didn't even know we had this\n>> dangling message, and it's been around for over 15 years!\n>>\n>> If we did want to preserve the ordering, it could be done by taking two\n>> passes (the first to create a reverse map of deletions to danglers, and\n>> then the second to print each ref).\n>>\n>> Alternatively, the dangling message could just mention where it the\n>> now-dangling symref points at, something like:\n>>\n>> - [deleted] (none) -> origin/branches\n>> - [deleted] (none) -> origin/main\n>> - [deleted] (none) -> origin/other\n>> (refs/remotes/origin/HEAD points to the now-deleted origin/main)\n> \n> I have a new patch that produces this:\n> \n> + git fetch --prune --dry-run\n> From /tmp/repo/.\n> - [deleted] (none) -> origin/branches\n> - [deleted] (none) -> origin/master\n> - [deleted] (none) -> origin/other\n> origin/HEAD will become dangling after origin/master is deleted\n> \n\n\nIt is a bit weird that this says \"will become dangling after is\ndeleted\" because the deletion already happened.\n"},{"id":"520615","messageId":"xmqq4iw63u1i.fsf@gitster.g","threadId":"63667","inReplyTo":"f11bf463-0005-43d2-b642-ede130d1f44c@intel.com","subject":"Re: [RFC PATCH 0/2] fetch --prune performance problem","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-06-23T23:41:29Z","receivedAt":"2025-06-23T23:41:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jacob Keller writes:\n\n>>> Alternatively, the dangling message could just mention where it the\n>>> now-dangling symref points at, something like:\n>>>\n>>> - [deleted] (none) -> origin/branches\n>>> - [deleted] (none) -> origin/main\n>>> - [deleted] (none) -> origin/other\n>>> (refs/remotes/origin/HEAD points to the now-deleted origin/main)\n>> \n>> I have a new patch that produces this:\n>> \n>> + git fetch --prune --dry-run\n>> From /tmp/repo/.\n>> - [deleted] (none) -> origin/branches\n>> - [deleted] (none) -> origin/master\n>> - [deleted] (none) -> origin/other\n>> origin/HEAD will become dangling after origin/master is deleted\n>> \n>\n>\n> It is a bit weird that this says \"will become dangling after is\n> deleted\" because the deletion already happened.\n\nBut that is with \"--dry-run\". Without it, presumably \n\n origin/HEAD is now dangling since origin/master was deleted\n\nor something, probably.\n"},{"id":"520619","messageId":"628070ea-8fde-4a67-a05d-8d88858cde95@intel.com","threadId":"63667","inReplyTo":"CABURp0q-1FGmD+PJeSQ=xvyDN6ZYn1O7Fh8i1OojfD2WQCqgcw@mail.gmail.com","subject":"Re: [RFC PATCH 0/2] fetch --prune performance problem","fromName":"Jacob Keller","fromEmail":"jacob.e.keller@intel.com","sentAt":"2025-06-23T23:46:16Z","receivedAt":"2025-06-23T23:46:35Z","isPatch":true,"sender":{"key":"jacob.e.keller@intel.com","avatar":"https://avatars.githubusercontent.com/u/874719?v=4"},"body":"\n\nOn 6/23/2025 4:40 PM, Phil Hord wrote:\n> On Mon, Jun 23, 2025 at 4:32 PM Jacob Keller \n>> On 6/23/2025 4:11 PM, Phil Hord wrote:\n>>> I have a new patch that produces this:\n>>>\n>>> + git fetch --prune --dry-run\n>>> From /tmp/repo/.\n>>> - [deleted] (none) -> origin/branches\n>>> - [deleted] (none) -> origin/master\n>>> - [deleted] (none) -> origin/other\n>>> origin/HEAD will become dangling after origin/master is deleted\n>>>\n>>\n>>\n>> It is a bit weird that this says \"will become dangling after is\n>> deleted\" because the deletion already happened.\n> \n> That's because I used the `--dry-run` switch. Sorry for the confusion.\n> \n> + git fetch --prune\n> From /tmp/repo/.\n> - [deleted] (none) -> origin/branches\n> - [deleted] (none) -> origin/master\n> - [deleted] (none) -> origin/other\n> origin/HEAD has become dangling after origin/master was deleted\n> \n\nAha! That is even better that it properly adjusts the text based on\n--dry-run.\n\nI like it.\n\nRegards,\nJake\n"}]}