fetch --prune performance problem
v4 cover fetch --prune performance problem
From: Phil Hord <[email protected]>
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.
V3 forgot to include the first commit in the series (I forgot it grew). So here's V4.
Phil Hord (3):
fetch-prune: optimize dangling-ref reporting
refs: remove old refs_warn_dangling_symref clean up interface for refs_warn_dangling_symrefs
builtin/fetch.c | 19 ++++++++----------- builtin/remote.c | 5 +---- refs.c | 34 ++++++++++++---------------------- refs.h | 5 ++--- 4 files changed, 23 insertions(+), 40 deletions(-)
Signature · 1 line
2.50.0.149.g1bab277d62
PATCH v4 1/3 fetch-prune: optimize dangling-ref reporting
From: Phil Hord <[email protected]>
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. Change the message to include the original refname since the message is no longer printed immediately after the line that did just print the refname.
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 a second.
--- builtin/fetch.c | 20 ++++++++++---------- builtin/remote.c | 4 ++-- refs.c | 2 +- 3 files changed, 13 insertions(+), 13 deletions(-)
builtin/fetch.c +10 -10
@@ -1383,9 +1383,13 @@ 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)" ); + ?_ (" %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);if (!dry_run) {if (transaction) {
@@ -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;
builtin/remote.c +2 -2
@@ -1522,8 +1522,8 @@ static int prune_remote(const char *remote, int dry_run)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!" ) - :_ (" %s has become dangling!" ); + ?_ (" %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 );
refs.c +1 -1
@@ -461,7 +461,7 @@ static int warn_if_dangling_symref(const char *refname, const char *referent UNUreturn 0 ; } -fprintf (d->fp, d->msg_fmt, refname); +fprintf (d->fp, d->msg_fmt, refname, resolves_to);fputc ('\n' , d->fp);return 0 ; }
Signature · 1 line
2.50.0.149.g1bab277d62
PATCH v4 2/3 refs: remove old refs_warn_dangling_symref
In reply to Phil HordFrom: Phil Hord <[email protected]>
The dangling warning function that takes a single ref to search for is no longer used. Remove it.
--- refs.c | 17 +---------------- refs.h | 2 -- 2 files changed, 1 insertion(+), 18 deletions(-)
refs.c +1 -16
@@ -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 UNUreturn 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) {
refs.h +0 -2
@@ -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);
Signature · 1 line
2.50.0.149.g1bab277d62
PATCH v4 3/3 clean up interface for refs_warn_dangling_symrefs
In reply to Phil HordFrom: Phil Hord <[email protected]>
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.
--- builtin/fetch.c | 5 +---- builtin/remote.c | 5 +---- refs.c | 17 +++++++++++------ refs.h | 3 ++- 4 files changed, 15 insertions(+), 15 deletions(-)
builtin/fetch.c +1 -4
@@ -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:
builtin/remote.c +1 -4
@@ -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);
refs.c +11 -6
@@ -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 UNUreturn 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); }
refs.h +2 -1
@@ -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()
Signature · 1 line
2.50.0.149.g1bab277d62
Re: [PATCH v4 3/3] clean up interface for refs_warn_dangling_symrefs
Quoted 10 lines · Phil Hord
The
refs_warn_dangling_symrefsinterface 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_runflag so the decision logic can be handled where needed.
Thanks, I think the result is nicer. I have two comments, but I don't think either will merit a re-roll.
Quoted 11 lines
builtin/fetch.c +0
-3@@ -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);
builtin/fetch.c static int prune_refs(struct display_state *display_state, · line 1418
Quoted 6 lines
builtin/fetch.c +1
-1@@ -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); }
I had imagined passing in an "int indent", and not an arbitrary string. But passing in the string is actually more flexible (it really could be any prefix, not just an indentation). I think calling it "prefix" in the actual function might be the more usual term here, but it's probably just bike-shedding.
refs.c static int warn_if_dangling_symref(const char *refname, const char *referent UNU · line 465
Quoted 6 lines
refs.c +4
-2-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);
Translators might find the extra "%s" at the beginning confusing without context. I think you can do something like:
/* TRANSLATORS: The first %s is whitespace indentation. */
or similar. But maybe it would be more obvious as:
fputs(d->indent, d->fp);
fprintf(d->fp, msg, refname, resolves_to);
fputc('\n', d->fp);? I dunno. Maybe putting it all together gives translators more options (e.g., in a RTL language). I don't know much about translation.
Likewise on including the newline in the translated string. I think we usually don't, just because we're mostly passing in strings for error(), etc. But I don't know how much it matters.
-Peff
Quoted 11 lines · Phil Hord
From: Phil Hord <[email protected]>
git fetch --pruneruns 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.
...
V3 forgot to include the first commit in the series (I forgot it grew). So here's V4.
Quoted 4 lines
Phil Hord (3):
fetch-prune: optimize dangling-ref reporting
refs: remove oldrefs_warn_dangling_symrefclean up interface forrefs_warn_dangling_symrefs
It seems that the thread has gone quiet. What's the status of this topic?
Thanks.
Quoted 19 lines · Junio C Hamano
Quoted 11 lines · Phil Hord
From: Phil Hord <[email protected]>
git fetch --pruneruns 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.
...
V3 forgot to include the first commit in the series (I forgot it grew). So here's V4.Quoted 4 lines
Phil Hord (3):
fetch-prune: optimize dangling-ref reporting
refs: remove oldrefs_warn_dangling_symrefclean up interface forrefs_warn_dangling_symrefs
Quoted 4 lines
It seems that the thread has gone quiet. What's the status of this topic?
Thanks.
LGTM
Quoted 13 lines · Junio C Hamano
Quoted 11 lines · Phil Hord
From: Phil Hord <[email protected]>
git fetch --pruneruns 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.
...
V3 forgot to include the first commit in the series (I forgot it grew). So here's V4.
Quoted 7 lines
Quoted 4 lines
Phil Hord (3):
fetch-prune: optimize dangling-ref reporting
refs: remove oldrefs_warn_dangling_symrefclean up interface forrefs_warn_dangling_symrefsIt seems that the thread has gone quiet. What's the status of this topic?
v4 looks fine to me. I raised a few questions about the translation strings, but I don't know if they're meaningful or not.
-Peff