{"thread":{"id":"62337","subject":"[PATCH] builtin/fetch: iterate symrefs instead of all when checking dangling refs","startedAt":"2024-10-15T03:28:02Z","lastAt":"2024-10-16T07:13:56Z","messageCount":3,"participants":["Liu Zhongbo via GitGitGadget","Taylor Blau","Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"505109","messageId":"pull.1812.git.git.1728962878717.gitgitgadget@gmail.com","threadId":"62337","inReplyTo":null,"subject":"[PATCH] builtin/fetch: iterate symrefs instead of all when checking dangling refs","fromName":"Liu Zhongbo via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-10-15T03:27:58Z","receivedAt":"2024-10-15T03:28:02Z","isPatch":true,"sender":{"key":"name:Liu Zhongbo","avatar":null},"body":"From: Liu Zhongbo <liuzhongbo.6666@bytedance.com>\n\nrefs_warn_dangling_symref() traverse all references to check if there are\nany dangling symbolic references. The complexity is\nO(number of deleted references * total number of references).\nIt will take a lot of time if there are tens of thousands of branches in\nmonorepo.\n\nSo I first identified all the symbolic references, and then only traverse\nin these references. The complexity is\nO (number of deleted references * number of symbolic references).\n\nDue to the infrequent use of symbolic references, there will be significant\nperformance improvements here. In my case, the prune_refs() time has been\nreduced from 20 seconds to 4 seconds.\n\nSigned-off-by: Liu Zhongbo <liuzhongbo.6666@bytedance.com>\n---\n    builtin/fetch: iterate symrefs instead of all refs\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1812%2Flzb6666%2Fspeed_up_prune_refs-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1812/lzb6666/speed_up_prune_refs-v1\nPull-Request: https://github.com/git/git/pull/1812\n\n builtin/fetch.c |  7 +++++--\n refs.c          | 35 ++++++++++++++++++++++++++---------\n refs.h          |  4 +++-\n 3 files changed, 34 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 80a64d0d269..ec4be60cfeb 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -1412,15 +1412,18 @@ static int prune_refs(struct display_state *display_state,\n \n \tif (verbosity >= 0) {\n \t\tint summary_width = transport_summary_width(stale_refs);\n+\t    struct string_list symrefs = STRING_LIST_INIT_NODUP;\n+\t    refs_get_symrefs(get_main_ref_store(the_repository), &symrefs);\n \n \t\tfor (ref = stale_refs; ref; ref = ref->next) {\n \t\t\tdisplay_ref_update(display_state, '-', _(\"[deleted]\"), NULL,\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        refs_warn_dangling_symref(get_main_ref_store(the_repository), stderr,\n+\t\t\t\t      dangling_msg, ref->name, &symrefs);\n \t\t}\n+\t    string_list_clear(&symrefs, 0);\n \t}\n \n cleanup:\ndiff --git a/refs.c b/refs.c\nindex 5f729ed4124..8dd480a7a91 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -463,16 +463,33 @@ 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+static int append_symref(const char *refname, const char *referent UNUSED,\n+\t\t\t const struct object_id *oid UNUSED,\n+\t\t\t int flags, void *cb_data) {\n+    struct string_list *d = cb_data;\n+    if ((flags & REF_ISSYMREF)){\n+        string_list_append(d, refname);\n+    }\n+    return 0;\n+}\n+\n+void refs_get_symrefs(struct ref_store *refs, struct string_list *refnames)\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+\trefs_for_each_rawref(refs, append_symref, refnames);\n+}\n+\n+void refs_warn_dangling_symref(struct ref_store *refs, FILE *fp,\n+                               const char *msg_fmt, const char *refname, struct string_list *symrefs) {\n+    const char *resolves_to;\n+    struct string_list_item *symref;\n+    for_each_string_list_item(symref, symrefs) {\n+        resolves_to = refs_resolve_ref_unsafe(refs, symref->string,\n+                                              0, NULL, NULL);\n+        if (resolves_to && strcmp(resolves_to, refname) == 0) {\n+            fprintf(fp, msg_fmt, symref->string);\n+            fputc('\\n', fp);\n+        }\n+    }\n }\n \n void refs_warn_dangling_symrefs(struct ref_store *refs, FILE *fp,\ndiff --git a/refs.h b/refs.h\nindex 108dfc93b34..d3b65564561 100644\n--- a/refs.h\n+++ b/refs.h\n@@ -394,8 +394,10 @@ static inline const char *has_glob_specials(const char *pattern)\n \treturn strpbrk(pattern, \"?*[\");\n }\n \n+void refs_get_symrefs(struct ref_store *refs, struct string_list *refnames);\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+\t\t\t       const char *msg_fmt, const char *refname, struct string_list *symrefs);\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\nbase-commit: ef8ce8f3d4344fd3af049c17eeba5cd20d98b69f\n-- \ngitgitgadget\n"},{"id":"505195","messageId":"Zw69unaf9JzPOA8i@nand.local","threadId":"62337","inReplyTo":"pull.1812.git.git.1728962878717.gitgitgadget@gmail.com","subject":"Re: [PATCH] builtin/fetch: iterate symrefs instead of all when checking dangling refs","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-15T19:08:42Z","receivedAt":"2024-10-15T19:08:44Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Oct 15, 2024 at 03:27:58AM +0000, Liu Zhongbo via GitGitGadget wrote:\n> From: Liu Zhongbo <liuzhongbo.6666@bytedance.com>\n>\n> refs_warn_dangling_symref() traverse all references to check if there are\n> any dangling symbolic references. The complexity is\n> O(number of deleted references * total number of references).\n> It will take a lot of time if there are tens of thousands of branches in\n> monorepo.\n>\n> So I first identified all the symbolic references, and then only traverse\n> in these references. The complexity is\n> O (number of deleted references * number of symbolic references).\n>\n> Due to the infrequent use of symbolic references, there will be significant\n> performance improvements here. In my case, the prune_refs() time has been\n> reduced from 20 seconds to 4 seconds.\n>\n> Signed-off-by: Liu Zhongbo <liuzhongbo.6666@bytedance.com>\n> ---\n>     builtin/fetch: iterate symrefs instead of all refs\n>\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1812%2Flzb6666%2Fspeed_up_prune_refs-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1812/lzb6666/speed_up_prune_refs-v1\n> Pull-Request: https://github.com/git/git/pull/1812\n>\n>  builtin/fetch.c |  7 +++++--\n>  refs.c          | 35 ++++++++++++++++++++++++++---------\n>  refs.h          |  4 +++-\n>  3 files changed, 34 insertions(+), 12 deletions(-)\n>\n> diff --git a/builtin/fetch.c b/builtin/fetch.c\n> index 80a64d0d269..ec4be60cfeb 100644\n> --- a/builtin/fetch.c\n> +++ b/builtin/fetch.c\n> @@ -1412,15 +1412,18 @@ static int prune_refs(struct display_state *display_state,\n>\n>  \tif (verbosity >= 0) {\n>  \t\tint summary_width = transport_summary_width(stale_refs);\n> +\t    struct string_list symrefs = STRING_LIST_INIT_NODUP;\n> +\t    refs_get_symrefs(get_main_ref_store(the_repository), &symrefs);\n\nWithout reading the contents of the patch below, there appear to be some\nstyle issues here. It seems that the indentation here is incorrect, as\nwell as below throughout the patch.\n\nPlease make sure that the indentation is consistent with the rest of the\nproject's conventions which can be found in\nDocumentation/CodingGuidelines before re-submitting.\n\nThanks,\nTaylor\n"},{"id":"505237","messageId":"Zw9npQrbBzddKxaJ@pks.im","threadId":"62337","inReplyTo":"pull.1812.git.git.1728962878717.gitgitgadget@gmail.com","subject":"Re: [PATCH] builtin/fetch: iterate symrefs instead of all when checking dangling refs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-10-16T07:13:49Z","receivedAt":"2024-10-16T07:13:56Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Oct 15, 2024 at 03:27:58AM +0000, Liu Zhongbo via GitGitGadget wrote:\n> From: Liu Zhongbo <liuzhongbo.6666@bytedance.com>\n> \n> refs_warn_dangling_symref() traverse all references to check if there are\n> any dangling symbolic references. The complexity is\n> O(number of deleted references * total number of references).\n> It will take a lot of time if there are tens of thousands of branches in\n> monorepo.\n> \n> So I first identified all the symbolic references, and then only traverse\n> in these references. The complexity is\n> O (number of deleted references * number of symbolic references).\n\nOkay. I'm a bit curious here, mostly because I would have thought that\nit should be able to make this O(number of deleted refs * logn(existing\nrefs)): for every deleted ref, you should only have to look up whether\nits target exists or not, which typically is O(logn existing refs).\n\nBut let's read on.\n\n> diff --git a/builtin/fetch.c b/builtin/fetch.c\n> index 80a64d0d269..ec4be60cfeb 100644\n> --- a/builtin/fetch.c\n> +++ b/builtin/fetch.c\n> @@ -1412,15 +1412,18 @@ static int prune_refs(struct display_state *display_state,\n>  \n>  \tif (verbosity >= 0) {\n>  \t\tint summary_width = transport_summary_width(stale_refs);\n> +\t    struct string_list symrefs = STRING_LIST_INIT_NODUP;\n> +\t    refs_get_symrefs(get_main_ref_store(the_repository), &symrefs);\n>  \n>  \t\tfor (ref = stale_refs; ref; ref = ref->next) {\n>  \t\t\tdisplay_ref_update(display_state, '-', _(\"[deleted]\"), NULL,\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        refs_warn_dangling_symref(get_main_ref_store(the_repository), stderr,\n> +\t\t\t\t      dangling_msg, ref->name, &symrefs);\n>  \t\t}\n> +\t    string_list_clear(&symrefs, 0);\n>  \t}\n>  \n>  cleanup:\n\nOkay, so here we're now iterating through the refs which we are about to\ndelete. For every such ref, we call `refs_warn_dangling_symref()`, which\niterates through all references in the repository to check whether any\nof them resolves to the passed ref.\n\nThat feels inefficient indeed, and I agree that reading symrefs once is\ngoing to be way more efficient. But open-coding part of the logic here\ndoes not make much sense to me, as the function itself should know to do\nit efficiently.\n\nCan we instead refactor the code to use `refs_warn_dangling_symrefs()`,\nwhich does all of this in a single iteration over all refs? That'd\nremove the need for us to do all of the above as we now only iterate a\nsingle time through all refs, wouldn't it?\n\nThat still isn't quite O(number of deleted refs * logn existing refs) in\ntheory. It's rather O(existing refs * logn deleted refs) as before\nbecause we have to also look up the currently iterader refname in\n`struct warn_if_dangling_data`, which is using a binary search in the\nsorted string list. But I think this should still be way more efficient\ncompared to the current solution, where we iterate through all refs\nmultiple times.\n\nPatrick\n"}]}