[PATCH v3 0/2] fetch --prune performance problem

[PATCH v3 0/2] fetch --prune performance problem

[Phil Hord]

From: Phil Hord <phil.hord@gmail.com>

`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.

This version (V3) has three changes from V2:
 - Removes a header declaration I forgot to move previously
 - Cleans up the refs_warn_dangling_symrefs API to be more sane
 - Drops the ref shortening that seems ill-advised in retrospect

Phil Hord (2):
  refs: remove old refs_warn_dangling_symref
  clean up interface for refs_warn_dangling_symrefs

 builtin/fetch.c  |  5 +----
 builtin/remote.c |  5 +----
 refs.c           | 34 ++++++++++++----------------------
 refs.h           |  5 ++---
 4 files changed, 16 insertions(+), 33 deletions(-)

-- 
2.50.0.149.g2f19833911.dirty

[PATCH v3 1/2] refs: remove old refs_warn_dangling_symref

[Phil Hord]

From: Phil Hord <phil.hord@gmail.com>

The dangling warning function that takes a single ref to search for
is no longer used.  Remove it.

Signed-off-by: Phil Hord <phil.hord@gmail.com>
---
 refs.c | 17 +----------------
 refs.h |  2 --
 2 files changed, 1 insertion(+), 18 deletions(-)

diff --git a/refs.c b/refs.c
index 651fb2d41299..07197c239e33 100644
--- a/refs.c
+++ b/refs.c
@@ -438,7 +438,6 @@ static int for_each_filter_refs(const char *refname, const char *referent,
 struct warn_if_dangling_data {
 	struct ref_store *refs;
 	FILE *fp;
-	const char *refname;
 	const struct string_list *refnames;
 	const char *msg_fmt;
 };
@@ -455,9 +454,7 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU
 
 	resolves_to = refs_resolve_ref_unsafe(d->refs, refname, 0, NULL, NULL);
 	if (!resolves_to
-	    || (d->refname
-		? strcmp(resolves_to, d->refname)
-		: !string_list_has_string(d->refnames, resolves_to))) {
+	    || !string_list_has_string(d->refnames, resolves_to)) {
 		return 0;
 	}
 
@@ -466,18 +463,6 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU
 	return 0;
 }
 
-void refs_warn_dangling_symref(struct ref_store *refs, FILE *fp,
-			       const char *msg_fmt, const char *refname)
-{
-	struct warn_if_dangling_data data = {
-		.refs = refs,
-		.fp = fp,
-		.refname = refname,
-		.msg_fmt = msg_fmt,
-	};
-	refs_for_each_rawref(refs, warn_if_dangling_symref, &data);
-}
-
 void refs_warn_dangling_symrefs(struct ref_store *refs, FILE *fp,
 				const char *msg_fmt, const struct string_list *refnames)
 {
diff --git a/refs.h b/refs.h
index 46a6008e07f2..07f21824d480 100644
--- a/refs.h
+++ b/refs.h
@@ -452,8 +452,6 @@ static inline const char *has_glob_specials(const char *pattern)
 	return strpbrk(pattern, "?*[");
 }
 
-void refs_warn_dangling_symref(struct ref_store *refs, FILE *fp,
-			       const char *msg_fmt, const char *refname);
 void refs_warn_dangling_symrefs(struct ref_store *refs, FILE *fp,
 				const char *msg_fmt, const struct string_list *refnames);
 
-- 
2.50.0.149.g2f19833911.dirty

[PATCH v3 2/2] clean up interface for refs_warn_dangling_symrefs

[Phil Hord]

From: Phil Hord <phil.hord@gmail.com>

The refs_warn_dangling_symrefs interface is a bit fragile as it passes
in printf-formatting strings with expectations about the number of
arguments. This patch series made it worse by adding a 2nd positional
argument. But there are only two call sites, and they both use almost
identical display options.

Make this safer by moving the format strings into the function that uses
them to make it easier to see when the arguments don't match. Pass a
prefix string and a dry_run flag so the decision logic can be handled
where needed.

Signed-off-by: Phil Hord <phil.hord@gmail.com>
---
 builtin/fetch.c  |  5 +----
 builtin/remote.c |  5 +----
 refs.c           | 17 +++++++++++------
 refs.h           |  3 ++-
 4 files changed, 15 insertions(+), 15 deletions(-)

diff --git a/builtin/fetch.c b/builtin/fetch.c
index 04d10c9e781a..fc72f2119c56 100644
--- a/builtin/fetch.c
+++ b/builtin/fetch.c
@@ -1384,9 +1384,6 @@ static int prune_refs(struct display_state *display_state,
 	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 after %s is deleted")
-		: _("   %s has become dangling after %s was deleted");
 
 	for (ref = stale_refs; ref; ref = ref->next)
 		string_list_append(&refnames, ref->name);
@@ -1417,7 +1414,7 @@ static int prune_refs(struct display_state *display_state,
 		}
 		string_list_sort(&refnames);
 		refs_warn_dangling_symrefs(get_main_ref_store(the_repository),
-					   stderr, dangling_msg, &refnames);
+					   stderr, "   ", dry_run, &refnames);
 	}
 
 cleanup:
diff --git a/builtin/remote.c b/builtin/remote.c
index 4de7dd373ae5..f672799e0d92 100644
--- a/builtin/remote.c
+++ b/builtin/remote.c
@@ -1521,9 +1521,6 @@ static int prune_remote(const char *remote, int dry_run)
 	struct ref_states states = REF_STATES_INIT;
 	struct string_list refs_to_prune = STRING_LIST_INIT_NODUP;
 	struct string_list_item *item;
-	const char *dangling_msg = dry_run
-		? _(" %s will become dangling after %s is deleted!")
-		: _(" %s has become dangling after %s was deleted!");
 
 	get_remote_ref_states(remote, &states, GET_REF_STATES);
 
@@ -1555,7 +1552,7 @@ static int prune_remote(const char *remote, int dry_run)
 	}
 
 	refs_warn_dangling_symrefs(get_main_ref_store(the_repository),
-				   stdout, dangling_msg, &refs_to_prune);
+				   stdout, " ", dry_run, &refs_to_prune);
 
 	string_list_clear(&refs_to_prune, 0);
 	free_remote_ref_states(&states);
diff --git a/refs.c b/refs.c
index 07197c239e33..5602c18dbd5b 100644
--- a/refs.c
+++ b/refs.c
@@ -439,7 +439,8 @@ struct warn_if_dangling_data {
 	struct ref_store *refs;
 	FILE *fp;
 	const struct string_list *refnames;
-	const char *msg_fmt;
+	const char *indent;
+	int dry_run;
 };
 
 static int warn_if_dangling_symref(const char *refname, const char *referent UNUSED,
@@ -447,7 +448,7 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU
 				   int flags, void *cb_data)
 {
 	struct warn_if_dangling_data *d = cb_data;
-	const char *resolves_to;
+	const char *resolves_to, *msg;
 
 	if (!(flags & REF_ISSYMREF))
 		return 0;
@@ -458,19 +459,23 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNU
 		return 0;
 	}
 
-	fprintf(d->fp, d->msg_fmt, refname, resolves_to);
-	fputc('\n', d->fp);
+	msg = d->dry_run
+		? _("%s%s will become dangling after %s is deleted\n")
+		: _("%s%s has become dangling after %s was deleted\n");
+	fprintf(d->fp, msg, d->indent, refname, resolves_to);
 	return 0;
 }
 
 void refs_warn_dangling_symrefs(struct ref_store *refs, FILE *fp,
-				const char *msg_fmt, const struct string_list *refnames)
+				const char *indent, int dry_run,
+				const struct string_list *refnames)
 {
 	struct warn_if_dangling_data data = {
 		.refs = refs,
 		.fp = fp,
 		.refnames = refnames,
-		.msg_fmt = msg_fmt,
+		.indent = indent,
+		.dry_run = dry_run,
 	};
 	refs_for_each_rawref(refs, warn_if_dangling_symref, &data);
 }
diff --git a/refs.h b/refs.h
index 07f21824d480..25bed4d792e7 100644
--- a/refs.h
+++ b/refs.h
@@ -453,7 +453,8 @@ static inline const char *has_glob_specials(const char *pattern)
 }
 
 void refs_warn_dangling_symrefs(struct ref_store *refs, FILE *fp,
-				const char *msg_fmt, const struct string_list *refnames);
+				const char *indent, int dry_run,
+				const struct string_list *refnames);
 
 /*
  * Flags for controlling behaviour of pack_refs()
-- 
2.50.0.149.g2f19833911.dirty

Re: [PATCH v3 0/2] fetch --prune performance problem

[Junio C Hamano]

Phil Hord <phil.hord@gmail.com> writes:

> This version (V3) has three changes from V2:
>  - Removes a header declaration I forgot to move previously
>  - Cleans up the refs_warn_dangling_symrefs API to be more sane
>  - Drops the ref shortening that seems ill-advised in retrospect
>
> Phil Hord (2):
>   refs: remove old refs_warn_dangling_symref
>   clean up interface for refs_warn_dangling_symrefs

Hmph.  On top of which commit did you base these two patches?
The second one does not apply on top of applying 1/2 on top of
either v2.48.1 (where I queued the last round), v2.50.0 (the obvious
choice for a new development), or 'master'.

$ git am -s <patch-2-of-2.txt
error: patch failed: builtin/fetch.c:1384
error: builtin/fetch.c: patch does not apply
error: patch failed: builtin/remote.c:1521
error: builtin/remote.c: patch does not apply
error: patch failed: refs.c:458
error: refs.c: patch does not apply

Thanks.

Re: [PATCH v3 0/2] fetch --prune performance problem

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Phil Hord <phil.hord@gmail.com> writes:
>
>> This version (V3) has three changes from V2:
>>  - Removes a header declaration I forgot to move previously
>>  - Cleans up the refs_warn_dangling_symrefs API to be more sane
>>  - Drops the ref shortening that seems ill-advised in retrospect
>>
>> Phil Hord (2):
>>   refs: remove old refs_warn_dangling_symref
>>   clean up interface for refs_warn_dangling_symrefs
>
> Hmph.  On top of which commit did you base these two patches?
> The second one does not apply on top of applying 1/2 on top of
> either v2.48.1 (where I queued the last round), v2.50.0 (the obvious
> choice for a new development), or 'master'.
>
> $ git am -s <patch-2-of-2.txt
> error: patch failed: builtin/fetch.c:1384
> error: builtin/fetch.c: patch does not apply
> error: patch failed: builtin/remote.c:1521
> error: builtin/remote.c: patch does not apply
> error: patch failed: refs.c:458
> error: refs.c: patch does not apply
>
> Thanks.

Ah, nevermind.  I'll discard your v3 and will take a look at your v4
instead later.