Re: [RFC PATCH 1/2] fetch-prune: optimize dangling-ref reporting
- From
Jacob Keller <jacob.e.keller@intel.com>
- Date
- Jun 18, 2025, 23:18 UTC
- Message-ID
- <905a668a-af3f-4b25-b35b-ba1f7e750b26@intel.com>
- In-Reply-To
- <20250618211024.2332525-2-phil.hord@gmail.com>
On 6/18/2025 2:08 PM, Phil Hord wrote:
Show 20 quoted lines
> From: Phil Hord <phil.hord@gmail.com> > > When pruning during `git fetch` we check each pruned ref against the > ref_store one at a time to decide whether to report it as dangling. > This causes every local ref to be scanned for each ref being pruned. > > If there are N refs in the repo and M refs being pruned, this code is > O(M*N). However, `git remote prune` uses a very similar function that > is only O(N*log(M)). > > Remove the wasteful ref scanning for each pruned ref and use the faster > version already available in refs_warn_dangling_symrefs. > > In a repo with 126,000 refs, where I was pruning 28,000 refs, this > code made about 3.6 billion calls to strcmp and consumed 410 seconds > of CPU. (Invariably in that time, my remote would timeout and the > fetch would fail anyway.) > > After this change, the same operation completes in under 4 seconds. >
The cover letter said "under a second". Is this a different example?
Show 6 quoted lines
> I considered further optimizing this function to be O(N), but this > requires ref_store iterators to be sorted, too. I found some suggestions > that this is always the case, but I'm not certain it is. > > The current speedup is enough for our needs at the moment. >
Yep. Logarithmic scaling grows slow enough that this is probably reasonable unless someone wants to put the remaining effort in.
Show 5 quoted lines
> This change causes a reordering of the output for any reported dangling > refs. Previously they would be reported inline with the "fetch: prune" > messages. Now they will be reported after all the original prune > messages are complete. >
I think this is reasonable especially for the speedup.
> Signed-off-by: Phil Hord <phil.hord@gmail.com> > ---
Reviewed-by: Jacob Keller <jacob.e.keller@intel.com>
Show 55 quoted lines
> builtin/fetch.c | 16 ++++++++--------
> 1 file changed, 8 insertions(+), 8 deletions(-)
>
> diff --git a/builtin/fetch.c b/builtin/fetch.c
> index 40a0e8d24434..11ce51da780a 100644
> --- a/builtin/fetch.c
> +++ b/builtin/fetch.c
> @@ -1383,10 +1383,14 @@ static int prune_refs(struct display_state *display_state,
> int result = 0;
> struct ref *ref, *stale_refs = get_stale_heads(rs, ref_map);
> struct strbuf err = STRBUF_INIT;
> + struct string_list refnames = STRING_LIST_INIT_NODUP;
> const char *dangling_msg = dry_run
> ? _(" (%s will become dangling)")
> : _(" (%s has become dangling)");
>
> + for (ref = stale_refs; ref; ref = ref->next)
> + string_list_append(&refnames, ref->name);
> +
> if (!dry_run) {
> if (transaction) {
> for (ref = stale_refs; ref; ref = ref->next) {
> @@ -1396,15 +1400,9 @@ static int prune_refs(struct display_state *display_state,
> goto cleanup;
> }
> } else {
> - struct string_list refnames = STRING_LIST_INIT_NODUP;
> -
> - for (ref = stale_refs; ref; ref = ref->next)
> - string_list_append(&refnames, ref->name);
> -
> result = refs_delete_refs(get_main_ref_store(the_repository),
> "fetch: prune", &refnames,
> 0);
> - string_list_clear(&refnames, 0);
> }
> }
>
> @@ -1416,12 +1414,14 @@ static int prune_refs(struct display_state *display_state,
> _("(none)"), ref->name,
> &ref->new_oid, &ref->old_oid,
> summary_width);
> - refs_warn_dangling_symref(get_main_ref_store(the_repository),
> - stderr, dangling_msg, ref->name);
> }
> + string_list_sort(&refnames);
> + refs_warn_dangling_symrefs(get_main_ref_store(the_repository),
> + stderr, dangling_msg, &refnames);
> }
>
> cleanup:
> + string_list_clear(&refnames, 0);
> strbuf_release(&err);
> free_refs(stale_refs);
> return result;