Speed up mirror-fetches with many refs
PATCH 1/6 fetch: speed up lookup of want refs via commit-graph
In reply to Patrick SteinhardtWhen updating our local refs based on the refs fetched from the remote, we need to iterate through all requested refs and load their respective commits such that we can determine whether they need to be appended to FETCH_HEAD or not. In cases where we're fetching from a remote with exceedingly many refs, resolving these refs can be quite expensive given that we repeatedly need to unpack object headers for each of the referenced objects.
Speed this up by opportunistcally trying to resolve object IDs via the commit graph: more likely than not, they're going to be a commit anyway, and this lets us avoid having to unpack object headers completely in case the object is a commit that is part of the commit-graph. This significantly speeds up mirror-fetches in a real-world repository with 2.3M refs:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 56.942 s ± 0.449 s [User: 53.360 s, System: 5.356 s]
Range (min … max): 56.372 s … 57.533 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 33.657 s ± 0.167 s [User: 30.302 s, System: 5.181 s]
Range (min … max): 33.454 s … 33.844 s 5 runs
Summary
'HEAD: git-fetch' ran
1.69 ± 0.02 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-)
builtin/fetch.c +8 -5
@@ -1131,11 +1131,14 @@ static int store_updated_refs(const char *raw_url, const char *remote_name,continue ; } - commit =lookup_commit_reference_gently (the_repository, - &rm->old_oid, -1 ); -if (!commit) - rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ; + commit =lookup_commit_in_graph (the_repository, &rm->old_oid); +if (!commit) { + commit =lookup_commit_reference_gently (the_repository, + &rm->old_oid, +1 ); +if (!commit) + rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ; + }if (rm->fetch_head_status != want_status)continue ;
Signature · 1 line
2.33.0
cover Speed up mirror-fetches with many refs
Hi,
I've taken another look at fetches in the context of repos with a huge amount of refs. This time around, I've taken a look at mirror fetches:
in our notorious repo with 2.3M refs, these mirror fetches can take up to several minutes of time even if there are no changes at all.
As it turns out, many of the issues are again caused by loading and dereferencing refs. This patch series thus mostly focusses on optimizing the patterns there, where the biggest win is to opportunistically load refs via commit-graphs. The following numbers were all calculated for a mirror-fetch of above 2.3M refs repo on the local disk:
- Patch 1 speeds up the way we look up commits when appending to FETCH_HEAD via the commit-graph, resulting in a ~40% speedup.
- Patch 2 optimizes the way we check for object existence for a 7% speedup.
- Patch 3 is a cleanup patch which changes the iterator functions passed to our connectivity checks. I was hoping for a speedup given that we can now avoid copying objects (which could have an effect with 2.3M copied OIDs), but unfortunately it didn't. In any case, I still think that the end result is much cleaner.
- Patch 4 optimizes git-fetch-pack(1) to use the commit-graph. This is a small win of about ~2%. It's debatable whether this patch is worth it.
- Patch 5 is a preparatory commit which refactors fetch_refs() to be more readily extendable.
- Patch 6 optimizes an edge case where we're doing two connectivity checks even if the first connectivity check noticed we already had all objects locally available, skipping the fetch. This brings a 15% speedup.
In combination with my previous optimizations for git-fetch-pack(1) and the connectivity check, this improves performance from 71s (ps/fetch-pack-load-refs-optim), to 54s (ps/connectivity-optim) to 26s (this series).
Note that this series depends on ps/connectivity-optim and thus only applies on top of next.
Patrick
[1]: <08519b8ab6f395cffbcd5e530bfba6aaf64241a2.1628085347.git.ps@pks.im>
Patrick Steinhardt (6):
fetch: speed up lookup of want refs via commit-graph
fetch: avoid unpacking headers in object existence check
connected: refactor iterator to return next object ID directly
fetch-pack: optimize loading of refs via commit graph
fetch: refactor fetch refs to be more extendable
fetch: avoid second connectivity check if we already have all objects
builtin/clone.c | 8 ++-- builtin/fetch.c | 84 +++++++++++++++++++++++------------------- builtin/receive-pack.c | 17 ++++----- connected.c | 15 ++++---- connected.h | 2 +- fetch-pack.c | 14 ++++--- 6 files changed, 74 insertions(+), 66 deletions(-)
Signature · 1 line
2.33.0
PATCH 2/6 fetch: avoid unpacking headers in object existence check
When updating local refs after the fetch has transferred all objects, we do an object existence test as a safety guard to avoid updating a ref to an object which we don't have. We do so via oid_object_info(): if it returns an error, then we know the object does not exist.
One side effect of oid_object_info() is that it parses the object's type, and to do so it must unpack the object header. This is completely
pointless: we don't care for the type, but only want to assert that the object exists.
Refactor the code to use repo_has_object_file(), which both makes the code's intent clearer and is also faster because it does not unpack object headers. In a real-world repo with 2.3M refs, this results in a small speedup when doing a mirror-fetch:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 33.686 s ± 0.176 s [User: 30.119 s, System: 5.262 s]
Range (min … max): 33.512 s … 33.944 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 31.247 s ± 0.195 s [User: 28.135 s, System: 5.066 s]
Range (min … max): 30.948 s … 31.472 s 5 runs
Summary
'HEAD: git-fetch' ran
1.08 ± 0.01 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-)
builtin/fetch.c +1 -3
@@ -846,13 +846,11 @@ static int update_local_ref(struct ref *ref, int summary_width) {struct commit *current =NULL , *updated; -enum object_type type;struct branch *current_branch =branch_get (NULL );const char *pretty_ref =prettify_refname (ref->name);int fast_forward =0 ; - type =oid_object_info (the_repository, &ref->new_oid,NULL ); -if (type <0 ) +if (!repo_has_object_file (the_repository, &ref->new_oid))die (_ ("object %s not found" ),oid_to_hex (&ref->new_oid));if (oideq (&ref->old_oid, &ref->new_oid)) {
Signature · 1 line
2.33.0
PATCH 3/6 connected: refactor iterator to return next object ID directly
In reply to Patrick SteinhardtThe object ID iterator used by the connectivity checks returns the next object ID via an out-parameter and then uses a return code to indicate whether an item was found. This is a bit roundabout: instead of a separate error code, we can just retrun the next object ID directly and use NULL pointers as indicator that the iterator got no items left. Furthermore, this avoids a copy of the object ID.
Refactor the iterator and all its implementations to return object IDs directly. While I was honestly hoping for a small speedup given that we can now avoid a copy, both versions perform the same. Still, the end result is easier to understand and thus it makes sense to keep this refactoring regardless.
--- builtin/clone.c | 8 +++----- builtin/fetch.c | 7 +++---- builtin/receive-pack.c | 17 +++++++---------- connected.c | 15 ++++++++------- connected.h | 2 +- fetch-pack.c | 7 +++---- 6 files changed, 25 insertions(+), 31 deletions(-)
builtin/clone.c +3 -5
@@ -544,7 +544,7 @@ static void write_followtags(const struct ref *refs, const char *msg) } } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;
@@ -555,13 +555,11 @@ static int iterate_ref_map(void *cb_data, struct object_id *oid)*/ while (ref && !ref->peer_ref) ref = ref->next; -/* Returning -1 notes "end of list" to the caller. */ if (!ref) -return -1 ; +return NULL ; -oidcpy (oid, &ref->old_oid); *rm = ref->next; -return 0 ; +return &ref->old_oid; } static void update_remote_refs(const struct ref *refs,
builtin/fetch.c +3 -4
@@ -962,7 +962,7 @@ static int update_local_ref(struct ref *ref, } } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;
@@ -970,10 +970,9 @@ static int iterate_ref_map(void *cb_data, struct object_id *oid)while (ref && ref->status ==REF_STATUS_REJECT_SHALLOW ) ref = ref->next;if (!ref) -return -1 ;/* end of the list */ +return NULL ; *rm = ref->next; -oidcpy (oid, &ref->old_oid); -return 0 ; +return &ref->old_oid; }struct fetch_head {
builtin/receive-pack.c +7 -10
@@ -1307,7 +1307,7 @@ static void refuse_unconfigured_deny_delete_current(void)rp_error ("%s" ,_ (refuse_unconfigured_deny_delete_current_msg)); } -static int command_singleton_iterator (void *cb_data,struct object_id *oid); +static struct object_id *command_singleton_iterator (void *cb_data);static int update_shallow_ref (struct command *cmd,struct shallow_info *si) {struct shallow_lock shallow_lock =SHALLOW_LOCK_INIT ;
@@ -1725,16 +1725,15 @@ static void check_aliased_updates(struct command *commands)string_list_clear (&ref_list,0 ); } -static int command_singleton_iterator (void *cb_data,struct object_id *oid) +static struct object_id *command_singleton_iterator (void *cb_data) {struct command **cmd_list = cb_data;struct command *cmd = *cmd_list;if (!cmd ||is_null_oid (&cmd->new_oid)) -return -1 ;/* end of list */ +return NULL ; *cmd_list =NULL ;/* this returns only one */ -oidcpy (oid, &cmd->new_oid); -return 0 ; +return &cmd->new_oid; } static void set_connectivity_errors(struct command *commands,
@@ -1764,7 +1763,7 @@ struct iterate_data {struct shallow_info *si; }; -static int iterate_receive_command_list (void *cb_data,struct object_id *oid) +static struct object_id *iterate_receive_command_list (void *cb_data) {struct iterate_data *data = cb_data;struct command **cmd_list = &data->cmds;
@@ -1775,13 +1774,11 @@ static int iterate_receive_command_list(void *cb_data, struct object_id *oid)/* to be checked in update_shallow_ref() */ continue ;if (!is_null_oid (&cmd->new_oid) && !cmd->skip_update) { -oidcpy (oid, &cmd->new_oid); *cmd_list = cmd->next; -return 0 ; +return &cmd->new_oid; } } - *cmd_list =NULL ; -return -1 ;/* end of list */ +return NULL ; }static void reject_updates_to_hidden (struct command *commands)
connected.c +8 -7
@@ -24,7 +24,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,struct child_process rev_list =CHILD_PROCESS_INIT ;FILE *rev_list_in;struct check_connected_options defaults =CHECK_CONNECTED_INIT ; -struct object_id oid; +struct object_id *oid;int err =0 ;struct packed_git *new_pack =NULL ;struct transport *transport;
@@ -34,7 +34,8 @@ int check_connected(oid_iterate_fn fn, void *cb_data, opt = &defaults; transport = opt->transport; -if (fn (cb_data, &oid)) { + oid =fn (cb_data); +if (!oid) {if (opt->err_fd)close (opt->err_fd);return err;
@@ -73,7 +74,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,for (p =get_all_packs (the_repository); p; p = p->next) {if (!p->pack_promisor)continue ; -if (find_pack_entry_one (oid.hash, p)) +if (find_pack_entry_one (oid->hash, p)) goto promisor_pack_found; }/*
@@ -83,7 +84,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data, goto no_promisor_pack_found; promisor_pack_found: ; - }while (!fn (cb_data, &oid)); + }while ((oid =fn (cb_data)) !=NULL );return 0 ; }
@@ -133,12 +134,12 @@ int check_connected(oid_iterate_fn fn, void *cb_data,* are sure the ref is good and not sending it to * rev-list for verification. */ -if (new_pack &&find_pack_entry_one (oid.hash, new_pack)) +if (new_pack &&find_pack_entry_one (oid->hash, new_pack))continue ; -if (fprintf (rev_list_in,"%s\n" ,oid_to_hex (&oid)) <0 ) +if (fprintf (rev_list_in,"%s\n" ,oid_to_hex (oid)) <0 )break ; - }while (!fn (cb_data, &oid)); + }while ((oid =fn (cb_data)) !=NULL );if (ferror (rev_list_in) ||fflush (rev_list_in)) {if (errno !=EPIPE && errno !=EINVAL )
connected.h +1 -1
@@ -9,7 +9,7 @@ struct transport;* When called after returning the name for the last object, return -1 * to signal EOF, otherwise return 0. */ -typedef int (*oid_iterate_fn )(void *,struct object_id *oid); +typedef struct object_id *(*oid_iterate_fn )(void *);/* * Named-arguments struct for check_connected. All arguments are
fetch-pack.c +3 -4
@@ -1912,16 +1912,15 @@ static void update_shallow(struct fetch_pack_args *args,oid_array_clear (&ref); } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;if (!ref) -return -1 ;/* end of the list */ +return NULL ; *rm = ref->next; -oidcpy (oid, &ref->old_oid); -return 0 ; +return &ref->old_oid; } struct ref *fetch_pack(struct fetch_pack_args *args,
Signature · 1 line
2.33.0
PATCH 4/6 fetch-pack: optimize loading of refs via commit graph
In reply to Patrick SteinhardtIn order to negotiate a packfile, we need to dereference refs to see which commits we have in common with the remote. To do so, we first look up the object's type -- if it's a tag, we peel until we hit a non-tag object. If we hit a commit eventually, then we return that commit.
In case the object ID points to a commit directly, we can avoid the initial lookup of the object type by opportunistically looking up the commit via the commit-graph, if available, which gives us a slight speed bump of about 2% in a huge repository with about 2.3M refs:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 31.634 s ± 0.258 s [User: 28.400 s, System: 5.090 s]
Range (min … max): 31.280 s … 31.896 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 31.129 s ± 0.543 s [User: 27.976 s, System: 5.056 s]
Range (min … max): 30.172 s … 31.479 s 5 runs
Summary
'HEAD: git-fetch' ran
1.02 ± 0.02 times faster than 'HEAD~: git-fetch'In case this fails, we fall back to the old code which peels the objects to a commit.
--- fetch-pack.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
fetch-pack.c +6 -1
@@ -119,6 +119,11 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid, {enum object_type type;struct object_info info = { .typep = &type }; +struct commit *commit; + + commit =lookup_commit_in_graph (the_repository, oid); +if (commit) +return commit;while (1 ) { if (oid_object_info_extended(the_repository, oid, &info,
@@ -139,7 +144,7 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid, }if (type ==OBJ_COMMIT ) { -struct commit *commit =lookup_commit (the_repository, oid); + commit =lookup_commit (the_repository, oid);if (!commit ||repo_parse_commit (the_repository, commit))return NULL ;return commit;
Signature · 1 line
2.33.0
PATCH 5/6 fetch: refactor fetch refs to be more extendable
In reply to Patrick SteinhardtRefactor fetch_refs() code to make it more extendable by explicitly handling error cases. The refactored code should behave the same.
--- builtin/fetch.c | 33 +++++++++++++++++++++------------ 1 file changed, 21 insertions(+), 12 deletions(-)
builtin/fetch.c +21 -12
@@ -1284,20 +1284,29 @@ static int check_exist_and_connected(struct ref *ref_map)static int fetch_refs (struct transport *transport,struct ref *ref_map) { -int ret =check_exist_and_connected (ref_map); -if (ret) { -trace2_region_enter ("fetch" ,"fetch_refs" , the_repository); - ret =transport_fetch_refs (transport, ref_map); -trace2_region_leave ("fetch" ,"fetch_refs" , the_repository); - } +int ret; + +/* +* We don't need to perform a fetch in case we can already satisfy all +* refs. +*/ + ret =check_exist_and_connected (ref_map);if (!ret) -/* -* Keep the new pack's ".keep" file around to allow the caller -* time to update refs to reference the new objects. -*/ return 0 ; -transport_unlock_pack (transport); -return ret; + +trace2_region_enter ("fetch" ,"fetch_refs" , the_repository); + ret =transport_fetch_refs (transport, ref_map); +trace2_region_leave ("fetch" ,"fetch_refs" , the_repository); +if (ret) { +transport_unlock_pack (transport); +return ret; + } + +/* +* Keep the new pack's ".keep" file around to allow the caller +* time to update refs to reference the new objects. +*/ +return 0 ; }/* Update local refs based on the ref values fetched from a remote */
Signature · 1 line
2.33.0
PATCH 6/6 fetch: avoid second connectivity check if we already have all objects
In reply to Patrick SteinhardtWhen fetching refs, we are doing two connectivity checks:
- The first one in fetch_refs() is done such that we can short-circuit the case where we already have all objects referenced by the updated set of refs.
- The second one in store_updated_refs() does a sanity check that we have all objects after we have fetched the packfile.
We always execute both connectivity checks, but this is wasteful in case the first connectivity check already notices that we have all objects locally available.
Refactor the code to do both connectivity checks in fetch_refs(), which allows us to easily skip the second connectivity check if we already have all objects available. This refactoring is safe to do given that we always call fetch_refs() followed by consume_refs(), which is the only caller of store_updated_refs().
This gives us a nice speedup when doing a mirror-fetch in a repository with about 2.3M refs where the fetching repo already has all objects:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 31.232 s ± 0.082 s [User: 27.901 s, System: 5.178 s]
Range (min … max): 31.118 s … 31.301 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 26.616 s ± 0.100 s [User: 23.675 s, System: 4.752 s]
Range (min … max): 26.544 s … 26.788 s 5 runs
Summary
'HEAD: git-fetch' ran
1.17 ± 0.01 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-)
builtin/fetch.c +13 -14
@@ -1068,7 +1068,7 @@ N_("It took %.2f seconds to check forced updates. You can use\n" " to avoid this check.\n");static int store_updated_refs (const char *raw_url,const char *remote_name, -int connectivity_checked,struct ref *ref_map) +struct ref *ref_map) {struct fetch_head fetch_head;struct commit *commit;
@@ -1090,16 +1090,6 @@ static int store_updated_refs(const char *raw_url, const char *remote_name,else url =xstrdup ("foreign" ); -if (!connectivity_checked) { -struct check_connected_options opt =CHECK_CONNECTED_INIT ; - - rm = ref_map; -if (check_connected (iterate_ref_map, &rm, &opt)) { - rc =error (_ ("%s did not send all necessary objects\n" ), url); - goto abort; - } - } -if (atomic_fetch) { transaction =ref_transaction_begin (&err);if (!transaction) {
@@ -1302,6 +1292,18 @@ static int fetch_refs(struct transport *transport, struct ref *ref_map)return ret; } +/* +* If the transport didn't yet check for us, we need to verify +* ourselves that we have obtained all missing objects now. +*/ +if (!transport->smart_options || !transport->smart_options->connectivity_checked) { +if (check_connected (iterate_ref_map, &ref_map,NULL )) { + ret =error (_ ("remote did not send all necessary objects\n" )); +transport_unlock_pack (transport); +return ret; + } + } +/* * Keep the new pack's ".keep" file around to allow the caller * time to update refs to reference the new objects.
@@ -1312,13 +1314,10 @@ static int fetch_refs(struct transport *transport, struct ref *ref_map)/* Update local refs based on the ref values fetched from a remote */ static int consume_refs (struct transport *transport,struct ref *ref_map) { -int connectivity_checked = transport->smart_options - ? transport->smart_options->connectivity_checked :0 ;int ret;trace2_region_enter ("fetch" ,"consume_refs" , the_repository); ret =store_updated_refs (transport->url, transport->remote->name, - connectivity_checked, ref_map);transport_unlock_pack (transport);trace2_region_leave ("fetch" ,"consume_refs" , the_repository);
Signature · 1 line
2.33.0
Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph
In reply to Patrick SteinhardtQuoted 15 lines · Patrick Steinhardt
When updating our local refs based on the refs fetched from the remote, we need to iterate through all requested refs and load their respective commits such that we can determine whether they need to be appended to
FETCH_HEADor not. In cases where we're fetching from a remote with exceedingly many refs, resolving these refs can be quite expensive given that we repeatedly need to unpack object headers for each of the referenced objects.Speed this up by opportunistcally trying to resolve object IDs via the commit graph: more likely than not, they're going to be a commit anyway, and this lets us avoid having to unpack object headers completely in case the object is a commit that is part of the commit-graph. This significantly speeds up mirror-fetches in a real-world repository with 2.3M refs:
Quoted 11 lines
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 56.942 s ± 0.449 s [User: 53.360 s, System: 5.356 s]
Range (min … max): 56.372 s … 57.533 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 33.657 s ± 0.167 s [User: 30.302 s, System: 5.181 s]
Range (min … max): 33.454 s … 33.844 s 5 runs
Summary
'HEAD: git-fetch' ran
1.69 ± 0.02 times faster than 'HEAD~: git-fetch'These numbers are impressive, and it makes sense that performing a binary search on the OID lookup chunk of the commit-graph is faster than doing a binary search on the OIDs across the pack-index(es).
I do worry about the case where annotated tags greatly outnumber branches, so this binary search is extra overhead and the performance may degrade. Would it be worth checking the ref to see if it lies within "refs/heads/" (or even _not_ in "refs/tags/") before doing this commit-graph check?
builtin/fetch.c static int store_updated_refs(const char *raw_url, const char *remote_name, · line 1140
Quoted 12 lines
builtin/fetch.c +7
-5- commit =lookup_commit_reference_gently (the_repository, - &rm->old_oid, -1 ); -if (!commit) - rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ; + commit =lookup_commit_in_graph (the_repository, &rm->old_oid); +if (!commit) { + commit =lookup_commit_reference_gently (the_repository, + &rm->old_oid, +1 ); +if (!commit) + rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ;
nit: I wouldn't nest this last "if (!commit)".
Code will work as advertised.
Thanks,
-Stolee
Re: [PATCH 3/6] connected: refactor iterator to return next object ID directly
In reply to Patrick SteinhardtQuoted 7 lines · Patrick Steinhardt
The object ID iterator used by the connectivity checks returns the next object ID via an out-parameter and then uses a return code to indicate whether an item was found. This is a bit roundabout: instead of a separate error code, we can just retrun the next object ID directly and use
NULLpointers as indicator that the iterator got no items left. Furthermore, this avoids a copy of the object ID.
Quoted 5 lines
Refactor the iterator and all its implementations to return object IDs directly. While I was honestly hoping for a small speedup given that we can now avoid a copy, both versions perform the same. Still, the end result is easier to understand and thus it makes sense to keep this refactoring regardless.
It's too bad about the lack of measurable performance gains, but the new code _is_ doing less, it's just not enough.
I agree that the new code organization is better.
Thanks,
-Stolee
Re: [PATCH 4/6] fetch-pack: optimize loading of refs via commit graph
In reply to Patrick SteinhardtQuoted 10 lines · Patrick Steinhardt
In order to negotiate a packfile, we need to dereference refs to see which commits we have in common with the remote. To do so, we first look up the object's type -- if it's a tag, we peel until we hit a non-tag object. If we hit a commit eventually, then we return that commit.
In case the object ID points to a commit directly, we can avoid the initial lookup of the object type by opportunistically looking up the commit via the commit-graph, if available, which gives us a slight speed bump of about 2% in a huge repository with about 2.3M refs:
Quoted 11 lines
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 31.634 s ± 0.258 s [User: 28.400 s, System: 5.090 s]
Range (min … max): 31.280 s … 31.896 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 31.129 s ± 0.543 s [User: 27.976 s, System: 5.056 s]
Range (min … max): 30.172 s … 31.479 s 5 runs
Summary
'HEAD: git-fetch' ran
1.02 ± 0.02 times faster than 'HEAD~: git-fetch'This 2% gain is nice, especially because you are measuring the end-to-end scenario. If you use GIT_TRACE2_PERF=1 on a few runs, then you could likely isolate some of the regions from mark_complete_and_common_ref() and demonstrate a larger improvement in that focused area.
fetch-pack.c static struct commit *deref_without_lazy_fetch(const struct object_id *oid, · line 126
Quoted 9 lines
fetch-pack.c +5
-0@@ -119,6 +119,11 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid, {enum object_type type;struct object_info info = { .typep = &type }; +struct commit *commit; + + commit =lookup_commit_in_graph (the_repository, oid); +if (commit) +return commit;
Obviously a correct thing to do.
fetch-pack.c static struct commit *deref_without_lazy_fetch(const struct object_id *oid, · line 147
Quoted 3 lines
fetch-pack.c +1
-1if (type ==OBJ_COMMIT ) { -struct commit *commit =lookup_commit (the_repository, oid); + commit =lookup_commit (the_repository, oid);
Re-using the local simplifies this. Good.
Thanks,
-Stolee
Re: [PATCH 5/6] fetch: refactor fetch refs to be more extendable
In reply to Patrick SteinhardtQuoted 2 lines · Patrick Steinhardt
Refactor
fetch_refs()code to make it more extendable by explicitly handling error cases. The refactored code should behave the same.
It took unrolling this diff to understand that this code behaves the same, and it's because of the previous code using "if (!ret) return 0;" to handle two possible ways that 'ret' could become zero.
I agree that the new code makes it clear that we can leave early after a successful call to check_exist_and_connected() and again after a successful call to transport_fetch_refs().
Thanks
-Stolee
Re: [PATCH 6/6] fetch: avoid second connectivity check if we already have all objects
In reply to Patrick SteinhardtQuoted 13 lines · Patrick Steinhardt
When fetching refs, we are doing two connectivity checks:
- The first one in
fetch_refs()is done such that we can short-circuit the case where we already have all objects referenced by the updated set of refs.- The second one in
store_updated_refs()does a sanity check that we have all objects after we have fetched the packfile.We always execute both connectivity checks, but this is wasteful in case the first connectivity check already notices that we have all objects locally available.
Quoted 5 lines
Refactor the code to do both connectivity checks in
fetch_refs(), which allows us to easily skip the second connectivity check if we already have all objects available. This refactoring is safe to do given that we always callfetch_refs()followed byconsume_refs(), which is the only caller ofstore_updated_refs().
Should we try to make it more clear that fetch_refs() must be followed by consume_refs() via a comment above the fetch_refs(), or possibly even its call sites?
Thanks,
-Stolee
On 8/20/2021 6:08 AM, Patrick Steinhardt wrote:
...
Quoted 4 lines
As it turns out, many of the issues are again caused by loading and dereferencing refs. This patch series thus mostly focusses on optimizing the patterns there, where the biggest win is to opportunistically load refs via commit-graphs.
You caught my attention at "commit-graph" and I found your use of them to be interesting. You strike a balance in checking the commit-graph when it is likely to be helpful, and skip the commit-graph when it is not. (For example, PATCH 2 is unlikely to benefit from checking the commit-graph at that point, because we are looking for objects that were just downloaded.)
I read all the patches and checked the full context of the functions to see if there were any issues, but found none. My only comments are about the case of many annotated tags (do we slow down?) and some nitpicks.
Thanks,
-Stolee
Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph
In reply to Derrick StoleeQuoted 5 lines · Derrick Stolee
I do worry about the case where annotated tags greatly outnumber branches, so this binary search is extra overhead and the performance may degrade. Would it be worth checking the ref to see if it lies within "refs/heads/" (or even _not_ in "refs/tags/") before doing this commit-graph check?
Ah, clever.
Re: [PATCH 3/6] connected: refactor iterator to return next object ID directly
In reply to Derrick StoleeQuoted 14 lines · Derrick Stolee
Quoted 7 lines · Patrick Steinhardt
The object ID iterator used by the connectivity checks returns the next object ID via an out-parameter and then uses a return code to indicate whether an item was found. This is a bit roundabout: instead of a separate error code, we can just retrun the next object ID directly and use
NULLpointers as indicator that the iterator got no items left. Furthermore, this avoids a copy of the object ID.Quoted 5 lines
Refactor the iterator and all its implementations to return object IDs directly. While I was honestly hoping for a small speedup given that we can now avoid a copy, both versions perform the same. Still, the end result is easier to understand and thus it makes sense to keep this refactoring regardless.
Quoted 4 lines
It's too bad about the lack of measurable performance gains, but the new code _is_ doing less, it's just not enough.
I agree that the new code organization is better.
The only potential downside I can think of is the loss of ability to convey the reason why it failed to return one by adding new return codes from the function, which I do not immediately see all that useful future extension anyway, so I agree that "we find what we found, or NULL if we don't find" is much straight-forward and easier to understand.
Nicely done.
Thanks.
Re: [PATCH 3/6] connected: refactor iterator to return next object ID directly
In reply to Patrick SteinhardtAm 20.08.21 um 12:08 schrieb Patrick Steinhardt:
Quoted 4 lines
The object ID iterator used by the connectivity checks returns the next object ID via an out-parameter and then uses a return code to indicate whether an item was found. This is a bit roundabout: instead of a separate error code, we can just retrun the next object ID directly and
s/retrun/return/
Quoted 8 lines
use
NULLpointers as indicator that the iterator got no items left. Furthermore, this avoids a copy of the object ID.Refactor the iterator and all its implementations to return object IDs directly. While I was honestly hoping for a small speedup given that we can now avoid a copy, both versions perform the same. Still, the end result is easier to understand and thus it makes sense to keep this refactoring regardless.
check_connected() calls find_pack_entry_one() on the object ID hash, which copies it anyway. Perhaps that and caching prevent the expected speedup?
The private copy made sure check_connected() could not modify the object IDs. It still only reads them with this patch, but the compiler no longer prevents writes. The iterators could return const pointers to restore that guarantee.
Quoted 186 lines
Signed-off-by Patrick Steinhardt <[email protected]>--- builtin/clone.c | 8 +++----- builtin/fetch.c | 7 +++---- builtin/receive-pack.c | 17 +++++++---------- connected.c | 15 ++++++++------- connected.h | 2 +- fetch-pack.c | 7 +++---- 6 files changed, 25 insertions(+), 31 deletions(-)builtin/clone.c +3
-5@@ -544,7 +544,7 @@ static void write_followtags(const struct ref *refs, const char *msg) } } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;@@ -555,13 +555,11 @@ static int iterate_ref_map(void *cb_data, struct object_id *oid)*/ while (ref && !ref->peer_ref) ref = ref->next; -/* Returning -1 notes "end of list" to the caller. */ if (!ref) -return -1 ; +return NULL ; -oidcpy (oid, &ref->old_oid); *rm = ref->next; -return 0 ; +return &ref->old_oid; } static void update_remote_refs(const struct ref *refs,builtin/fetch.c +3
-4@@ -962,7 +962,7 @@ static int update_local_ref(struct ref *ref, } } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;@@ -970,10 +970,9 @@ static int iterate_ref_map(void *cb_data, struct object_id *oid)while (ref && ref->status ==REF_STATUS_REJECT_SHALLOW ) ref = ref->next;if (!ref) -return -1 ;/* end of the list */ +return NULL ; *rm = ref->next; -oidcpy (oid, &ref->old_oid); -return 0 ; +return &ref->old_oid; }struct fetch_head {builtin/receive-pack.c +7
-10@@ -1307,7 +1307,7 @@ static void refuse_unconfigured_deny_delete_current(void)rp_error ("%s" ,_ (refuse_unconfigured_deny_delete_current_msg)); } -static int command_singleton_iterator (void *cb_data,struct object_id *oid); +static struct object_id *command_singleton_iterator (void *cb_data);static int update_shallow_ref (struct command *cmd,struct shallow_info *si) {struct shallow_lock shallow_lock =SHALLOW_LOCK_INIT ;@@ -1725,16 +1725,15 @@ static void check_aliased_updates(struct command *commands)string_list_clear (&ref_list,0 ); } -static int command_singleton_iterator (void *cb_data,struct object_id *oid) +static struct object_id *command_singleton_iterator (void *cb_data) {struct command **cmd_list = cb_data;struct command *cmd = *cmd_list;if (!cmd ||is_null_oid (&cmd->new_oid)) -return -1 ;/* end of list */ +return NULL ; *cmd_list =NULL ;/* this returns only one */ -oidcpy (oid, &cmd->new_oid); -return 0 ; +return &cmd->new_oid; } static void set_connectivity_errors(struct command *commands,@@ -1764,7 +1763,7 @@ struct iterate_data {struct shallow_info *si; }; -static int iterate_receive_command_list (void *cb_data,struct object_id *oid) +static struct object_id *iterate_receive_command_list (void *cb_data) {struct iterate_data *data = cb_data;struct command **cmd_list = &data->cmds;@@ -1775,13 +1774,11 @@ static int iterate_receive_command_list(void *cb_data, struct object_id *oid)/* to be checked in update_shallow_ref() */ continue ;if (!is_null_oid (&cmd->new_oid) && !cmd->skip_update) { -oidcpy (oid, &cmd->new_oid); *cmd_list = cmd->next; -return 0 ; +return &cmd->new_oid; } } - *cmd_list =NULL ; -return -1 ;/* end of list */ +return NULL ; }static void reject_updates_to_hidden (struct command *commands)connected.c +8
-7@@ -24,7 +24,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,struct child_process rev_list =CHILD_PROCESS_INIT ;FILE *rev_list_in;struct check_connected_options defaults =CHECK_CONNECTED_INIT ; -struct object_id oid; +struct object_id *oid;int err =0 ;struct packed_git *new_pack =NULL ;struct transport *transport;@@ -34,7 +34,8 @@ int check_connected(oid_iterate_fn fn, void *cb_data, opt = &defaults; transport = opt->transport; -if (fn (cb_data, &oid)) { + oid =fn (cb_data); +if (!oid) {if (opt->err_fd)close (opt->err_fd);return err;@@ -73,7 +74,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,for (p =get_all_packs (the_repository); p; p = p->next) {if (!p->pack_promisor)continue ; -if (find_pack_entry_one (oid.hash, p)) +if (find_pack_entry_one (oid->hash, p)) goto promisor_pack_found; }/* @@ -83,7 +84,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data, goto no_promisor_pack_found; promisor_pack_found: ; - }while (!fn (cb_data, &oid)); + }while ((oid =fn (cb_data)) !=NULL );return 0 ; }@@ -133,12 +134,12 @@ int check_connected(oid_iterate_fn fn, void *cb_data,* are sure the ref is good and not sending it to * rev-list for verification. */ -if (new_pack &&find_pack_entry_one (oid.hash, new_pack)) +if (new_pack &&find_pack_entry_one (oid->hash, new_pack))continue ; -if (fprintf (rev_list_in,"%s\n" ,oid_to_hex (&oid)) <0 ) +if (fprintf (rev_list_in,"%s\n" ,oid_to_hex (oid)) <0 )break ; - }while (!fn (cb_data, &oid)); + }while ((oid =fn (cb_data)) !=NULL );if (ferror (rev_list_in) ||fflush (rev_list_in)) {if (errno !=EPIPE && errno !=EINVAL )connected.h +0
-0
connected.h struct transport; · line 12
Quoted 5 lines
connected.h +1
-1@@ -9,7 +9,7 @@ struct transport;* When called after returning the name for the last object, return -1 * to signal EOF, otherwise return 0. */ -typedef int (*oid_iterate_fn )(void *,struct object_id *oid); +typedef struct object_id *(*oid_iterate_fn )(void *);
I.e. this would be safer (requires some more const modifiers throughout the code):
typedef const struct object_id * (*oid_iterate_fn)(void *);
Quoted 28 lines
connected.h +0
-0/* * Named-arguments struct for check_connected. All arguments are fetch-pack.c +3
-4@@ -1912,16 +1912,15 @@ static void update_shallow(struct fetch_pack_args *args,oid_array_clear (&ref); } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;if (!ref) -return -1 ;/* end of the list */ +return NULL ; *rm = ref->next; -oidcpy (oid, &ref->old_oid); -return 0 ; +return &ref->old_oid; } struct ref *fetch_pack(struct fetch_pack_args *args,
Quoted 4 lines · Patrick Steinhardt
I've taken another look at fetches in the context of repos with a huge amount of refs. This time around, I've taken a look at mirror fetches:
in our notorious repo with 2.3M refs, these mirror fetches can take up to several minutes of time even if there are no changes at all.
I notice that 4/6 (and no other patch) is not signed-off and wonder if there is a reason (e.g. you are not so comfortable with the idea behind the step or the implementation) or a simple oversight?
Quoted 2 lines
Note that this series depends on ps/connectivity-optim and thus only applies on top of next.
It seems that the dependency of this series is not just 'master' plus 'ps/connectivity-optim' but some more stuff from 'next'. I expact that topics that have been cooking in 'next' during the previous cycle will graduate to 'master' early next week, so perhaps it is easier to handle this kind of "depends on some stuff in 'next'" topics after that happens.
Thanks.
Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph
In reply to Junio C HamanoQuoted 9 lines · Junio C Hamano
Quoted 5 lines · Derrick Stolee
I do worry about the case where annotated tags greatly outnumber branches, so this binary search is extra overhead and the performance may degrade. Would it be worth checking the ref to see if it lies within "refs/heads/" (or even _not_ in "refs/tags/") before doing this commit-graph check?
Ah, clever.
Good idea. Benchmarks for my test repository (which definitely isn't representative, but it's at least some numbers) show that restricting to "refs/heads/" diminishes almost all the gains, while restricting to everything but "refs/tags/" performs almost the same (it's a tiny bit slower, probably because of the added string comparisons):
Benchmark #1: all refs: git-fetch
Time (mean ± σ): 32.959 s ± 0.282 s [User: 29.801 s, System: 5.137 s]
Range (min … max): 32.760 s … 33.158 s 2 runs
Benchmark #2: refs/heads: git-fetch
Time (mean ± σ): 56.955 s ± 0.002 s [User: 53.447 s, System: 5.362 s]
Range (min … max): 56.953 s … 56.957 s 2 runs
Benchmark #3: !refs/tags: git-fetch
Time (mean ± σ): 33.447 s ± 0.003 s [User: 30.160 s, System: 5.027 s]
Range (min … max): 33.444 s … 33.449 s 2 runs
Summary
'all refs: git-fetch' ran
1.01 ± 0.01 times faster than '!refs/tags: git-fetch'
1.73 ± 0.01 times faster than 'refs/heads: git-fetch'This is easily explained by the fact that the test repo has most of its refs neither in "refs/tags/" nor in "refs/heads/", but rather in special namespaces like "refs/merge-requests/", "refs/environments/" or "refs/keep-around/".
I like the idea of excluding "refs/tags/" though: as you point out, chances are high that these don't point to commits but to annotated tags instead. So I'll go with that, thanks!
Patrick
Re: [PATCH 3/6] connected: refactor iterator to return next object ID directly
In reply to René ScharfeQuoted 17 lines · René Scharfe
Am 20.08.21 um 12:08 schrieb Patrick Steinhardt:
Quoted 4 lines
The object ID iterator used by the connectivity checks returns the next object ID via an out-parameter and then uses a return code to indicate whether an item was found. This is a bit roundabout: instead of a separate error code, we can just retrun the next object ID directly and
s/retrun/return/
Quoted 8 lines
use
NULLpointers as indicator that the iterator got no items left. Furthermore, this avoids a copy of the object ID.Refactor the iterator and all its implementations to return object IDs directly. While I was honestly hoping for a small speedup given that we can now avoid a copy, both versions perform the same. Still, the end result is easier to understand and thus it makes sense to keep this refactoring regardless.
Quoted 8 lines
check_connected()callsfind_pack_entry_one()on the object ID hash, which copies it anyway. Perhaps that and caching prevent the expected speedup?The private copy made sure
check_connected()could not modify the object IDs. It still only reads them with this patch, but the compiler no longer prevents writes. The iterators could return const pointers to restore that guarantee.
Right, will change the signature and re-benchmark. I'd be surprised if it significantly changed the picture, but let's see.
Patrick
Re: [PATCH 6/6] fetch: avoid second connectivity check if we already have all objects
In reply to Derrick StoleeQuoted 20 lines · Derrick Stolee
Quoted 13 lines · Patrick Steinhardt
When fetching refs, we are doing two connectivity checks:
- The first one in
fetch_refs()is done such that we can short-circuit the case where we already have all objects referenced by the updated set of refs.- The second one in
store_updated_refs()does a sanity check that we have all objects after we have fetched the packfile.We always execute both connectivity checks, but this is wasteful in case the first connectivity check already notices that we have all objects locally available.
Quoted 5 lines
Refactor the code to do both connectivity checks in
fetch_refs(), which allows us to easily skip the second connectivity check if we already have all objects available. This refactoring is safe to do given that we always callfetch_refs()followed byconsume_refs(), which is the only caller ofstore_updated_refs().
Quoted 3 lines
Should we try to make it more clear that
fetch_refs()must be followed byconsume_refs()via a comment above thefetch_refs(), or possibly even its call sites?
I wasn't quite happy with this outcome, either. How about we instead merge both functions into fetch_and_consume_refs()? Both are quite short, and that makes sure we always call them together to make the requirement explicit.
I'll add another patch to do this refactoring.
Patrick
PATCH v2 1/7 fetch: speed up lookup of want refs via commit-graph
In reply to Patrick SteinhardtWhen updating our local refs based on the refs fetched from the remote, we need to iterate through all requested refs and load their respective commits such that we can determine whether they need to be appended to FETCH_HEAD or not. In cases where we're fetching from a remote with exceedingly many refs, resolving these refs can be quite expensive given that we repeatedly need to unpack object headers for each of the referenced objects.
Speed this up by opportunistcally trying to resolve object IDs via the commit graph. We only do so for any refs which are not in "refs/tags":
more likely than not, these are going to be a commit anyway, and this lets us avoid having to unpack object headers completely in case the object is a commit that is part of the commit-graph. This significantly speeds up mirror-fetches in a real-world repository with 2.3M refs:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 56.482 s ± 0.384 s [User: 53.340 s, System: 5.365 s]
Range (min … max): 56.050 s … 57.045 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 33.727 s ± 0.170 s [User: 30.252 s, System: 5.194 s]
Range (min … max): 33.452 s … 33.871 s 5 runs
Summary
'HEAD: git-fetch' ran
1.67 ± 0.01 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-)
builtin/fetch.c +18 -6
@@ -1074,7 +1074,6 @@ static int store_updated_refs(const char *raw_url, const char *remote_name, int connectivity_checked, struct ref *ref_map) { struct fetch_head fetch_head; -struct commit *commit;int url_len, i, rc =0 ;struct strbuf note =STRBUF_INIT , err =STRBUF_INIT ;struct ref_transaction *transaction =NULL ;
@@ -1122,6 +1121,7 @@ static int store_updated_refs(const char *raw_url, const char *remote_name, want_status <=FETCH_HEAD_IGNORE ; want_status++) {for (rm = ref_map; rm; rm = rm->next) { +struct commit *commit =NULL ;struct ref *ref =NULL ;if (rm->status ==REF_STATUS_REJECT_SHALLOW ) {
@@ -1131,11 +1131,23 @@ static int store_updated_refs(const char *raw_url, const char *remote_name,continue ; } - commit =lookup_commit_reference_gently (the_repository, - &rm->old_oid, -1 ); -if (!commit) - rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ; +/* +* References in "refs/tags/" are often going to point +* to annotated tags, which are not part of the +* commit-graph. We thus only try to look up refs in +* the graph which are not in that namespace to not +* regress performance in repositories with many +* annotated tags. +*/ +if (!starts_with (rm->name,"refs/tags/" )) + commit =lookup_commit_in_graph (the_repository, &rm->old_oid); +if (!commit) { + commit =lookup_commit_reference_gently (the_repository, + &rm->old_oid, +1 ); +if (!commit) + rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ; + }if (rm->fetch_head_status != want_status)continue ;
Signature · 1 line
2.33.0
PATCH v2 2/7 fetch: avoid unpacking headers in object existence check
In reply to Patrick SteinhardtWhen updating local refs after the fetch has transferred all objects, we do an object existence test as a safety guard to avoid updating a ref to an object which we don't have. We do so via oid_object_info(): if it returns an error, then we know the object does not exist.
One side effect of oid_object_info() is that it parses the object's type, and to do so it must unpack the object header. This is completely
pointless: we don't care for the type, but only want to assert that the object exists.
Refactor the code to use repo_has_object_file(), which both makes the code's intent clearer and is also faster because it does not unpack object headers. In a real-world repo with 2.3M refs, this results in a small speedup when doing a mirror-fetch:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 33.686 s ± 0.176 s [User: 30.119 s, System: 5.262 s]
Range (min … max): 33.512 s … 33.944 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 31.247 s ± 0.195 s [User: 28.135 s, System: 5.066 s]
Range (min … max): 30.948 s … 31.472 s 5 runs
Summary
'HEAD: git-fetch' ran
1.08 ± 0.01 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-)
builtin/fetch.c +1 -3
@@ -846,13 +846,11 @@ static int update_local_ref(struct ref *ref, int summary_width) {struct commit *current =NULL , *updated; -enum object_type type;struct branch *current_branch =branch_get (NULL );const char *pretty_ref =prettify_refname (ref->name);int fast_forward =0 ; - type =oid_object_info (the_repository, &ref->new_oid,NULL ); -if (type <0 ) +if (!repo_has_object_file (the_repository, &ref->new_oid))die (_ ("object %s not found" ),oid_to_hex (&ref->new_oid));if (oideq (&ref->old_oid, &ref->new_oid)) {
Signature · 1 line
2.33.0
v2 cover Speed up mirror-fetches with many refs
In reply to Patrick SteinhardtHi,
this is the second version of my patch series to speed up mirror-fetches with many refs. This topic applies on top of Junio's 9d5700f60b (Merge branch 'ps/connectivity-optim' into jch, 2021-08-23).
Changes compared to v1:
- Patch 1/7: I've applied Stolee's proposal to only opportunistically load objects via the commit-graph in case the reference is not in refs/tags/ such that we don't regress repos with many annotated tags.
- Patch 3/7: The return parameter of the iterator is now const to allow further optimizations by the compiler, as suggested by René. I've also re-benchmarked this, and one can now see a very slight performance improvement of ~1%.
- Patch 4/7: Added my missing DCO, as pointed out by Junio.
- Patch 5, 6, 7: I've redone these to make it clearer that the refactoring I'm doing doesn't cause us to miss any object connectivity checks. Most importantly, I've merged fetch_refs() and consume_refs() into fetch_and_consume_refs() in 6/7, which makes the optimization where we elide the second connectivity check in 7/7 trivial.
Thanks for your feedback!
Patrick
Patrick Steinhardt (7):
fetch: speed up lookup of want refs via commit-graph
fetch: avoid unpacking headers in object existence check
connected: refactor iterator to return next object ID directly
fetch-pack: optimize loading of refs via commit graph
fetch: refactor fetch refs to be more extendable
fetch: merge fetching and consuming refs
fetch: avoid second connectivity check if we already have all objects
builtin/clone.c | 8 ++--- builtin/fetch.c | 74 +++++++++++++++++++++++------------------- builtin/receive-pack.c | 17 ++++------ connected.c | 15 +++++---- connected.h | 2 +- fetch-pack.c | 14 +++++--- 6 files changed, 68 insertions(+), 62 deletions(-)
Range-diff against v1:
1: 6872979c45 ! 1: 4a819a6830 fetch: speed up lookup of want refs via commit-graph
@@ Commit message
referenced objects.
Speed this up by opportunistcally trying to resolve object IDs via the
- commit graph: more likely than not, they're going to be a commit anyway,
- and this lets us avoid having to unpack object headers completely in
- case the object is a commit that is part of the commit-graph. This
- significantly speeds up mirror-fetches in a real-world repository with
+ commit graph. We only do so for any refs which are not in "refs/tags":
+ more likely than not, these are going to be a commit anyway, and this
+ lets us avoid having to unpack object headers completely in case the
+ object is a commit that is part of the commit-graph. This significantly
+ speeds up mirror-fetches in a real-world repository with
2.3M refs:
Benchmark #1: HEAD~: git-fetch
- Time (mean ± σ): 56.942 s ± 0.449 s [User: 53.360 s, System: 5.356 s]
- Range (min … max): 56.372 s … 57.533 s 5 runs
+ Time (mean ± σ): 56.482 s ± 0.384 s [User: 53.340 s, System: 5.365 s]
+ Range (min … max): 56.050 s … 57.045 s 5 runs
Benchmark #2: HEAD: git-fetch
- Time (mean ± σ): 33.657 s ± 0.167 s [User: 30.302 s, System: 5.181 s]
- Range (min … max): 33.454 s … 33.844 s 5 runs
+ Time (mean ± σ): 33.727 s ± 0.170 s [User: 30.252 s, System: 5.194 s]
+ Range (min … max): 33.452 s … 33.871 s 5 runs
Summary
'HEAD: git-fetch' ran
- 1.69 ± 0.02 times faster than 'HEAD~: git-fetch'
+ 1.67 ± 0.01 times faster than 'HEAD~: git-fetch'
## builtin/fetch.c ##
+@@ builtin/fetch.c: static int store_updated_refs(const char *raw_url, const char *remote_name,
+ int connectivity_checked, struct ref *ref_map)
+ {
+ struct fetch_head fetch_head;
+- struct commit *commit;
+ int url_len, i, rc = 0;
+ struct strbuf note = STRBUF_INIT, err = STRBUF_INIT;
+ struct ref_transaction *transaction = NULL;
+@@ builtin/fetch.c: static int store_updated_refs(const char *raw_url, const char *remote_name,
+ want_status <= FETCH_HEAD_IGNORE;
+ want_status++) {
+ for (rm = ref_map; rm; rm = rm->next) {
++ struct commit *commit = NULL;
+ struct ref *ref = NULL;
+
+ if (rm->status == REF_STATUS_REJECT_SHALLOW) {
@@ builtin/fetch.c: static int store_updated_refs(const char *raw_url, const char *remote_name,
continue;
}
@@ builtin/fetch.c: static int store_updated_refs(const char *raw_url, const char *
- 1);
- if (!commit)
- rm->fetch_head_status = FETCH_HEAD_NOT_FOR_MERGE;
-+ commit = lookup_commit_in_graph(the_repository, &rm->old_oid);
++ /*
++ * References in "refs/tags/" are often going to point
++ * to annotated tags, which are not part of the
++ * commit-graph. We thus only try to look up refs in
++ * the graph which are not in that namespace to not
++ * regress performance in repositories with many
++ * annotated tags.
++ */
++ if (!starts_with(rm->name, "refs/tags/"))
++ commit = lookup_commit_in_graph(the_repository, &rm->old_oid);
+ if (!commit) {
+ commit = lookup_commit_reference_gently(the_repository,
+ &rm->old_oid,
2: d3dac607f2 = 2: 81ebadabe8 fetch: avoid unpacking headers in object existence check 3: 3bdad7bc8b ! 3: 98e981ced9 connected: refactor iterator to return next object ID directly
@@ Commit message
The object ID iterator used by the connectivity checks returns the next object ID via an out-parameter and then uses a return code to indicate whether an item was found. This is a bit roundabout: instead of a
- separate error code, we can just retrun the next object ID directly and
+ separate error code, we can just return the next object ID directly and
use NULL pointers as indicator that the iterator got no items left. Furthermore, this avoids a copy of the object ID.
Refactor the iterator and all its implementations to return object IDs
- directly. While I was honestly hoping for a small speedup given that we
- can now avoid a copy, both versions perform the same. Still, the end
- result is easier to understand and thus it makes sense to keep this
- refactoring regardless.
+ directly. This brings a tiny performance improvement when doing a mirror-fetch of a repository with about 2.3M refs:
+
+ Benchmark #1: 328dc58b49919c43897240f2eabfa30be2ce32a4~: git-fetch
+ Time (mean ± σ): 30.110 s ± 0.148 s [User: 27.161 s, System: 5.075 s]
+ Range (min … max): 29.934 s … 30.406 s 10 runs
+
+ Benchmark #2: 328dc58b49919c43897240f2eabfa30be2ce32a4: git-fetch
+ Time (mean ± σ): 29.899 s ± 0.109 s [User: 26.916 s, System: 5.104 s]
+ Range (min … max): 29.696 s … 29.996 s 10 runs
+
+ Summary
+ '328dc58b49919c43897240f2eabfa30be2ce32a4: git-fetch' ran
+ 1.01 ± 0.01 times faster than '328dc58b49919c43897240f2eabfa30be2ce32a4~: git-fetch'
+
+ While this 1% speedup could be labelled as statistically insignificant,
+ the speedup is consistent on my machine. Furthermore, this is an end to
+ end test, so it is expected that the improvement in the connectivity
+ check itself is more significant.
@@ builtin/clone.c: static void write_followtags(const struct ref *refs, const char
}
-static int iterate_ref_map(void *cb_data, struct object_id *oid)
-+static struct object_id *iterate_ref_map(void *cb_data) ++static const struct object_id *iterate_ref_map(void *cb_data)
{
struct ref **rm = cb_data;
struct ref *ref = *rm;
@@ builtin/fetch.c: static int update_local_ref(struct ref *ref,
}
-static int iterate_ref_map(void *cb_data, struct object_id *oid)
-+static struct object_id *iterate_ref_map(void *cb_data)
++static const struct object_id *iterate_ref_map(void *cb_data)
{
struct ref **rm = cb_data;
struct ref *ref = *rm;
@@ builtin/receive-pack.c: static void refuse_unconfigured_deny_delete_current(void
}
-static int command_singleton_iterator(void *cb_data, struct object_id *oid);
-+static struct object_id *command_singleton_iterator(void *cb_data); ++static const struct object_id *command_singleton_iterator(void *cb_data);
static int update_shallow_ref(struct command *cmd, struct shallow_info *si) {
struct shallow_lock shallow_lock = SHALLOW_LOCK_INIT;
@@ builtin/receive-pack.c: static void check_aliased_updates(struct command *comman
}
-static int command_singleton_iterator(void *cb_data, struct object_id *oid)
-+static struct object_id *command_singleton_iterator(void *cb_data) ++static const struct object_id *command_singleton_iterator(void *cb_data)
{
struct command **cmd_list = cb_data;
struct command *cmd = *cmd_list;
@@ builtin/receive-pack.c: struct iterate_data {
};
-static int iterate_receive_command_list(void *cb_data, struct object_id *oid)
-+static struct object_id *iterate_receive_command_list(void *cb_data) ++static const struct object_id *iterate_receive_command_list(void *cb_data)
{
struct iterate_data *data = cb_data;
struct command **cmd_list = &data->cmds;
@@ connected.c: int check_connected(oid_iterate_fn fn, void *cb_data,
FILE *rev_list_in;
struct check_connected_options defaults = CHECK_CONNECTED_INIT;
- struct object_id oid;
-+ struct object_id *oid;
++ const struct object_id *oid;
int err = 0;
struct packed_git *new_pack = NULL;
struct transport *transport;
@@ connected.h: struct transport;
* to signal EOF, otherwise return 0.
*/
-typedef int (*oid_iterate_fn)(void *, struct object_id *oid);
-+typedef struct object_id *(*oid_iterate_fn)(void *);
++typedef const struct object_id *(*oid_iterate_fn)(void *);
/*
* Named-arguments struct for check_connected. All arguments are
@@ fetch-pack.c: static void update_shallow(struct fetch_pack_args *args,
}
-static int iterate_ref_map(void *cb_data, struct object_id *oid)
-+static struct object_id *iterate_ref_map(void *cb_data)
++static const struct object_id *iterate_ref_map(void *cb_data)
{
struct ref **rm = cb_data;
struct ref *ref = *rm;
4: 67917af7ce ! 4: 6311203f08 fetch-pack: optimize loading of refs via commit graph
@@ Commit message
In case this fails, we fall back to the old code which peels the objects to a commit.
+ Signed-off-by: Patrick Steinhardt <[email protected]>
+
## fetch-pack.c ##
@@ fetch-pack.c: static struct commit *deref_without_lazy_fetch(const struct object_id *oid,
{
5: 7653f8eabc ! 5: 56a9158ac3 fetch: refactor fetch refs to be more extendable
@@ builtin/fetch.c: static int check_exist_and_connected(struct ref *ref_map)
static int fetch_refs(struct transport *transport, struct ref *ref_map)
{
- int ret = check_exist_and_connected(ref_map);
-- if (ret) {
-- trace2_region_enter("fetch", "fetch_refs", the_repository);
-- ret = transport_fetch_refs(transport, ref_map);
-- trace2_region_leave("fetch", "fetch_refs", the_repository);
-- }
+ int ret;
+
+ /*
@@ builtin/fetch.c: static int check_exist_and_connected(struct ref *ref_map)
+ * refs.
+ */
+ ret = check_exist_and_connected(ref_map);
- if (!ret)
+ if (ret) {
+ trace2_region_enter("fetch", "fetch_refs", the_repository);
+ ret = transport_fetch_refs(transport, ref_map);
+ trace2_region_leave("fetch", "fetch_refs", the_repository);
++ if (ret) {
++ transport_unlock_pack(transport);
++ return ret;
++ }
+ }
+- if (!ret)
- /*
- * Keep the new pack's ".keep" file around to allow the caller
- * time to update refs to reference the new objects.
- */
- return 0;
+- return 0;
- transport_unlock_pack(transport);
- return ret;
+
-+ trace2_region_enter("fetch", "fetch_refs", the_repository);
-+ ret = transport_fetch_refs(transport, ref_map);
-+ trace2_region_leave("fetch", "fetch_refs", the_repository);
-+ if (ret) {
-+ transport_unlock_pack(transport);
-+ return ret;
-+ }
-+
+ /*
+ * Keep the new pack's ".keep" file around to allow the caller
+ * time to update refs to reference the new objects.
6: 646ac90e62 < -: ---------- fetch: avoid second connectivity check if we already have all objects
-: ---------- > 6: 31d9f72edf fetch: merge fetching and consuming refs
-: ---------- > 7: 84e39c847f fetch: avoid second connectivity check if we already have all objectsSignature · 1 line
2.33.0
PATCH v2 3/7 connected: refactor iterator to return next object ID directly
The object ID iterator used by the connectivity checks returns the next object ID via an out-parameter and then uses a return code to indicate whether an item was found. This is a bit roundabout: instead of a separate error code, we can just return the next object ID directly and use NULL pointers as indicator that the iterator got no items left. Furthermore, this avoids a copy of the object ID.
Refactor the iterator and all its implementations to return object IDs
directly. This brings a tiny performance improvement when doing a mirror-fetch of a repository with about 2.3M refs:
Benchmark #1: 328dc58b49919c43897240f2eabfa30be2ce32a4~: git-fetch
Time (mean ± σ): 30.110 s ± 0.148 s [User: 27.161 s, System: 5.075 s]
Range (min … max): 29.934 s … 30.406 s 10 runs
Benchmark #2: 328dc58b49919c43897240f2eabfa30be2ce32a4: git-fetch
Time (mean ± σ): 29.899 s ± 0.109 s [User: 26.916 s, System: 5.104 s]
Range (min … max): 29.696 s … 29.996 s 10 runs
Summary
'328dc58b49919c43897240f2eabfa30be2ce32a4: git-fetch' ran
1.01 ± 0.01 times faster than '328dc58b49919c43897240f2eabfa30be2ce32a4~: git-fetch'While this 1% speedup could be labelled as statistically insignificant, the speedup is consistent on my machine. Furthermore, this is an end to end test, so it is expected that the improvement in the connectivity check itself is more significant.
--- builtin/clone.c | 8 +++----- builtin/fetch.c | 7 +++---- builtin/receive-pack.c | 17 +++++++---------- connected.c | 15 ++++++++------- connected.h | 2 +- fetch-pack.c | 7 +++---- 6 files changed, 25 insertions(+), 31 deletions(-)
builtin/clone.c +3 -5
@@ -657,7 +657,7 @@ static void write_followtags(const struct ref *refs, const char *msg) } } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static const struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;
@@ -668,13 +668,11 @@ static int iterate_ref_map(void *cb_data, struct object_id *oid)*/ while (ref && !ref->peer_ref) ref = ref->next; -/* Returning -1 notes "end of list" to the caller. */ if (!ref) -return -1 ; +return NULL ; -oidcpy (oid, &ref->old_oid); *rm = ref->next; -return 0 ; +return &ref->old_oid; } static void update_remote_refs(const struct ref *refs,
builtin/fetch.c +3 -4
@@ -962,7 +962,7 @@ static int update_local_ref(struct ref *ref, } } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static const struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;
@@ -970,10 +970,9 @@ static int iterate_ref_map(void *cb_data, struct object_id *oid)while (ref && ref->status ==REF_STATUS_REJECT_SHALLOW ) ref = ref->next;if (!ref) -return -1 ;/* end of the list */ +return NULL ; *rm = ref->next; -oidcpy (oid, &ref->old_oid); -return 0 ; +return &ref->old_oid; }struct fetch_head {
builtin/receive-pack.c +7 -10
@@ -1306,7 +1306,7 @@ static void refuse_unconfigured_deny_delete_current(void)rp_error ("%s" ,_ (refuse_unconfigured_deny_delete_current_msg)); } -static int command_singleton_iterator (void *cb_data,struct object_id *oid); +static const struct object_id *command_singleton_iterator (void *cb_data);static int update_shallow_ref (struct command *cmd,struct shallow_info *si) {struct shallow_lock shallow_lock =SHALLOW_LOCK_INIT ;
@@ -1731,16 +1731,15 @@ static void check_aliased_updates(struct command *commands)string_list_clear (&ref_list,0 ); } -static int command_singleton_iterator (void *cb_data,struct object_id *oid) +static const struct object_id *command_singleton_iterator (void *cb_data) {struct command **cmd_list = cb_data;struct command *cmd = *cmd_list;if (!cmd ||is_null_oid (&cmd->new_oid)) -return -1 ;/* end of list */ +return NULL ; *cmd_list =NULL ;/* this returns only one */ -oidcpy (oid, &cmd->new_oid); -return 0 ; +return &cmd->new_oid; } static void set_connectivity_errors(struct command *commands,
@@ -1770,7 +1769,7 @@ struct iterate_data {struct shallow_info *si; }; -static int iterate_receive_command_list (void *cb_data,struct object_id *oid) +static const struct object_id *iterate_receive_command_list (void *cb_data) {struct iterate_data *data = cb_data;struct command **cmd_list = &data->cmds;
@@ -1781,13 +1780,11 @@ static int iterate_receive_command_list(void *cb_data, struct object_id *oid)/* to be checked in update_shallow_ref() */ continue ;if (!is_null_oid (&cmd->new_oid) && !cmd->skip_update) { -oidcpy (oid, &cmd->new_oid); *cmd_list = cmd->next; -return 0 ; +return &cmd->new_oid; } } - *cmd_list =NULL ; -return -1 ;/* end of list */ +return NULL ; }static void reject_updates_to_hidden (struct command *commands)
connected.c +8 -7
@@ -24,7 +24,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,struct child_process rev_list =CHILD_PROCESS_INIT ;FILE *rev_list_in;struct check_connected_options defaults =CHECK_CONNECTED_INIT ; -struct object_id oid; +const struct object_id *oid;int err =0 ;struct packed_git *new_pack =NULL ;struct transport *transport;
@@ -34,7 +34,8 @@ int check_connected(oid_iterate_fn fn, void *cb_data, opt = &defaults; transport = opt->transport; -if (fn (cb_data, &oid)) { + oid =fn (cb_data); +if (!oid) {if (opt->err_fd)close (opt->err_fd);return err;
@@ -73,7 +74,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,for (p =get_all_packs (the_repository); p; p = p->next) {if (!p->pack_promisor)continue ; -if (find_pack_entry_one (oid.hash, p)) +if (find_pack_entry_one (oid->hash, p)) goto promisor_pack_found; }/*
@@ -83,7 +84,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data, goto no_promisor_pack_found; promisor_pack_found: ; - }while (!fn (cb_data, &oid)); + }while ((oid =fn (cb_data)) !=NULL );return 0 ; }
@@ -133,12 +134,12 @@ int check_connected(oid_iterate_fn fn, void *cb_data,* are sure the ref is good and not sending it to * rev-list for verification. */ -if (new_pack &&find_pack_entry_one (oid.hash, new_pack)) +if (new_pack &&find_pack_entry_one (oid->hash, new_pack))continue ; -if (fprintf (rev_list_in,"%s\n" ,oid_to_hex (&oid)) <0 ) +if (fprintf (rev_list_in,"%s\n" ,oid_to_hex (oid)) <0 )break ; - }while (!fn (cb_data, &oid)); + }while ((oid =fn (cb_data)) !=NULL );if (ferror (rev_list_in) ||fflush (rev_list_in)) {if (errno !=EPIPE && errno !=EINVAL )
connected.h +1 -1
@@ -9,7 +9,7 @@ struct transport;* When called after returning the name for the last object, return -1 * to signal EOF, otherwise return 0. */ -typedef int (*oid_iterate_fn )(void *,struct object_id *oid); +typedef const struct object_id *(*oid_iterate_fn )(void *);/* * Named-arguments struct for check_connected. All arguments are
fetch-pack.c +3 -4
@@ -1912,16 +1912,15 @@ static void update_shallow(struct fetch_pack_args *args,oid_array_clear (&ref); } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static const struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;if (!ref) -return -1 ;/* end of the list */ +return NULL ; *rm = ref->next; -oidcpy (oid, &ref->old_oid); -return 0 ; +return &ref->old_oid; } struct ref *fetch_pack(struct fetch_pack_args *args,
Signature · 1 line
2.33.0
PATCH v2 4/7 fetch-pack: optimize loading of refs via commit graph
In reply to Patrick SteinhardtIn order to negotiate a packfile, we need to dereference refs to see which commits we have in common with the remote. To do so, we first look up the object's type -- if it's a tag, we peel until we hit a non-tag object. If we hit a commit eventually, then we return that commit.
In case the object ID points to a commit directly, we can avoid the initial lookup of the object type by opportunistically looking up the commit via the commit-graph, if available, which gives us a slight speed bump of about 2% in a huge repository with about 2.3M refs:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 31.634 s ± 0.258 s [User: 28.400 s, System: 5.090 s]
Range (min … max): 31.280 s … 31.896 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 31.129 s ± 0.543 s [User: 27.976 s, System: 5.056 s]
Range (min … max): 30.172 s … 31.479 s 5 runs
Summary
'HEAD: git-fetch' ran
1.02 ± 0.02 times faster than 'HEAD~: git-fetch'In case this fails, we fall back to the old code which peels the objects to a commit.
--- fetch-pack.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
fetch-pack.c +6 -1
@@ -119,6 +119,11 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid, {enum object_type type;struct object_info info = { .typep = &type }; +struct commit *commit; + + commit =lookup_commit_in_graph (the_repository, oid); +if (commit) +return commit;while (1 ) { if (oid_object_info_extended(the_repository, oid, &info,
@@ -139,7 +144,7 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid, }if (type ==OBJ_COMMIT ) { -struct commit *commit =lookup_commit (the_repository, oid); + commit =lookup_commit (the_repository, oid);if (!commit ||repo_parse_commit (the_repository, commit))return NULL ;return commit;
Signature · 1 line
2.33.0
PATCH v2 5/7 fetch: refactor fetch refs to be more extendable
In reply to Patrick SteinhardtRefactor fetch_refs() code to make it more extendable by explicitly handling error cases. The refactored code should behave the same.
--- builtin/fetch.c | 26 +++++++++++++++++--------- 1 file changed, 17 insertions(+), 9 deletions(-)
builtin/fetch.c +17 -9
@@ -1293,20 +1293,28 @@ static int check_exist_and_connected(struct ref *ref_map)static int fetch_refs (struct transport *transport,struct ref *ref_map) { -int ret =check_exist_and_connected (ref_map); +int ret; + +/* +* We don't need to perform a fetch in case we can already satisfy all +* refs. +*/ + ret =check_exist_and_connected (ref_map);if (ret) {trace2_region_enter ("fetch" ,"fetch_refs" , the_repository); ret =transport_fetch_refs (transport, ref_map);trace2_region_leave ("fetch" ,"fetch_refs" , the_repository); +if (ret) { +transport_unlock_pack (transport); +return ret; + } } -if (!ret) -/* -* Keep the new pack's ".keep" file around to allow the caller -* time to update refs to reference the new objects. -*/ -return 0 ; -transport_unlock_pack (transport); -return ret; + +/* +* Keep the new pack's ".keep" file around to allow the caller +* time to update refs to reference the new objects. +*/ +return 0 ; }/* Update local refs based on the ref values fetched from a remote */
Signature · 1 line
2.33.0
PATCH v2 6/7 fetch: merge fetching and consuming refs
In reply to Patrick SteinhardtThe functions fetch_refs() and consume_refs() must always be called together such that we first obtain all missing objects and then update our local refs to match the remote refs. In a subsequent patch, we'll further require that fetch_refs() must always be called before consume_refs() such that it can correctly assert that we have all objects after the fetch given that we're about to move the connectivity check.
Make this requirement explicit by merging both functions into a single fetch_and_consume_refs() function.
--- builtin/fetch.c | 32 +++++++++++--------------------- 1 file changed, 11 insertions(+), 21 deletions(-)
builtin/fetch.c +11 -21
@@ -1291,8 +1291,9 @@ static int check_exist_and_connected(struct ref *ref_map)return check_connected (iterate_ref_map, &rm, &opt); } -static int fetch_refs (struct transport *transport,struct ref *ref_map) +static int fetch_and_consume_refs (struct transport *transport,struct ref *ref_map) { +int connectivity_checked;int ret;/*
@@ -1304,32 +1305,22 @@ static int fetch_refs(struct transport *transport, struct ref *ref_map)trace2_region_enter ("fetch" ,"fetch_refs" , the_repository); ret =transport_fetch_refs (transport, ref_map);trace2_region_leave ("fetch" ,"fetch_refs" , the_repository); -if (ret) { -transport_unlock_pack (transport); -return ret; - } +if (ret) + goto out; } -/* -* Keep the new pack's ".keep" file around to allow the caller -* time to update refs to reference the new objects. -*/ -return 0 ; -} - -/* Update local refs based on the ref values fetched from a remote */ -static int consume_refs (struct transport *transport,struct ref *ref_map) -{ -int connectivity_checked = transport->smart_options + connectivity_checked = transport->smart_options ? transport->smart_options->connectivity_checked :0 ; -int ret; +trace2_region_enter ("fetch" ,"consume_refs" , the_repository); ret =store_updated_refs (transport->url, transport->remote->name, connectivity_checked, ref_map); -transport_unlock_pack (transport);trace2_region_leave ("fetch" ,"consume_refs" , the_repository); + +out: +transport_unlock_pack (transport);return ret; }
@@ -1518,8 +1509,7 @@ static void backfill_tags(struct transport *transport, struct ref *ref_map)transport_set_option (transport,TRANS_OPT_FOLLOWTAGS ,NULL );transport_set_option (transport,TRANS_OPT_DEPTH ,"0" );transport_set_option (transport,TRANS_OPT_DEEPEN_RELATIVE ,NULL ); -if (!fetch_refs (transport, ref_map)) -consume_refs (transport, ref_map); +fetch_and_consume_refs (transport, ref_map);if (gsecondary) {transport_disconnect (gsecondary);
@@ -1610,7 +1600,7 @@ static int do_fetch(struct transport *transport, transport->url); } } -if (fetch_refs (transport, ref_map) ||consume_refs (transport, ref_map)) { +if (fetch_and_consume_refs (transport, ref_map)) {free_refs (ref_map); retcode =1 ; goto cleanup;
Signature · 1 line
2.33.0
PATCH v2 7/7 fetch: avoid second connectivity check if we already have all objects
In reply to Patrick SteinhardtWhen fetching refs, we are doing two connectivity checks:
- The first one is done such that we can skip fetching refs in the case where we already have all objects referenced by the updated set of refs.
- The second one verifies that we have all objects after we have fetched objects.
We always execute both connectivity checks, but this is wasteful in case the first connectivity check already notices that we have all objects locally available.
Skip the second connectivity check in case we already had all objects available. This gives us a nice speedup when doing a mirror-fetch in a repository with about 2.3M refs where the fetching repo already has all objects:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 30.025 s ± 0.081 s [User: 27.070 s, System: 4.933 s]
Range (min … max): 29.900 s … 30.111 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 25.574 s ± 0.177 s [User: 22.855 s, System: 4.683 s]
Range (min … max): 25.399 s … 25.765 s 5 runs
Summary
'HEAD: git-fetch' ran
1.17 ± 0.01 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)
builtin/fetch.c +3 -4
@@ -1293,7 +1293,7 @@ static int check_exist_and_connected(struct ref *ref_map)static int fetch_and_consume_refs (struct transport *transport,struct ref *ref_map) { -int connectivity_checked; +int connectivity_checked =1 ;int ret;/*
@@ -1307,11 +1307,10 @@ static int fetch_and_consume_refs(struct transport *transport, struct ref *ref_mtrace2_region_leave ("fetch" ,"fetch_refs" , the_repository);if (ret) goto out; + connectivity_checked = transport->smart_options ? + transport->smart_options->connectivity_checked :0 ; } - connectivity_checked = transport->smart_options - ? transport->smart_options->connectivity_checked :0 ; -trace2_region_enter ("fetch" ,"consume_refs" , the_repository); ret = store_updated_refs(transport->url, transport->remote->name,
Signature · 1 line
2.33.0
Quoted 3 lines · Patrick Steinhardt
this is the second version of my patch series to speed up mirror-fetches with many refs. This topic applies on top of Junio's
9d5700f60b(Merge branch 'ps/connectivity-optim' into jch, 2021-08-23).
It is a horrible commit to base anything on. You are taking your patches hostage to all of these other topics.
9d5700f60b Merge branch 'ps/connectivity-optim' into jch 7ad315de2f Merge branch 'js/log-protocol-version' into jch 1726f748f5 Merge branch 'en/ort-becomes-the-default' into jch 23aeecb099 Merge branch 'en/merge-strategy-docs' into jch 568277d458 Merge branch 'en/pull-conflicting-options' into jch 2b316bb006 ### match next
4efa9ea0b6 Merge branch 'ps/fetch-pack-load-refs-optim' into jch b305842ee8 Merge branch 'jt/push-negotiation-fixes' into jch 83b45616f1 Merge branch 'es/trace2-log-parent-process-name' into jch be89aa8c38 Merge branch 'hn/refs-test-cleanup' into jch 256d56ed32 Merge branch 'en/ort-perf-batch-15' into jch 7477fbf53a Merge branch 'js/expand-runtime-prefix' into jch b1453dfd30 Merge branch 'ab/bundle-doc' into jch 1b66e8e89d Merge branch 'zh/ref-filter-raw-data' into jch 1fbf27ddcd Merge branch 'ab/pack-stdin-packs-fix' into jch dcf57bfebb Merge branch 'ab/http-drop-old-curl' into jch 93041f7c57 Merge branch 'ds/add-with-sparse-index' into jch 814a016195 Merge branch 'jc/bisect-sans-show-branch' into jch
A better way to handle a situation like this is to limit your dependencies more explicitly. If you look at what I did to the last round of this topic, you'll see that there is a merge of the 'ps/connectivity-optim' topic into v2.33 followed by application of the patches, like this:
1d576ca7b2 fetch: avoid second connectivity check if we already have all objects 6768595f10 fetch: refactor fetch refs to be more extendable a615d7cf87 fetch-pack: optimize loading of refs via commit graph bfd04fc24c connected: refactor iterator to return next object ID directly 1a387c9f3a fetch: avoid unpacking headers in object existence check f1a4367ec4 fetch: speed up lookup of want refs via commit-graph 3628199d4d Merge branch 'ps/connectivity-optim' into ps/fetch-optim
What I did to your last round was to merge 'ps/connectivity-optim' on top of v2.33 and then queue them. You can do the same for this round (you can tell people "apply these on top of the result of merging topic X, Y and Z on tag V").
df52ef2c3a fetch: avoid second connectivity check if we already have all objects c1721680e4 fetch: merge fetching and consuming refs
5470cbe1be fetch: refactor fetch refs to be more extendable 016a510428 fetch-pack: optimize loading of refs via commit graph f6c7e63cc7 connected: refactor iterator to return next object ID directly 17c8e90df3 fetch: avoid unpacking headers in object existence check a54c245004 fetch: speed up lookup of want refs via commit-graph 3628199d4d Merge branch 'ps/connectivity-optim' into ps/fetch-optim
I had to adjust [4/7] while applying them on top of the same 3628199d4d I created for queuing the previous round, and it would be appreciated if you can double-check the result.
Thanks.
Quoted 1 line · Junio C Hamano
Patrick Steinhardt <[email protected]> writes:
[snip]
Quoted 5 lines
A better way to handle a situation like this is to limit your dependencies more explicitly. If you look at what I did to the last round of this topic, you'll see that there is a merge of the 'ps/connectivity-optim' topic into v2.33 followed by application of the patches, like this:
I wasn't quite sure how to best handle this, but I'll keep this in mind for future iterations/patch series. Thanks for the explanation.
[snip]
Quoted 3 lines
I had to adjust [4/7] while applying them on top of the same
3628199d4dI created for queuing the previous round, and it would be appreciated if you can double-check the result.
The result looks good to me, thanks.
Patrick
Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph
In reply to Patrick SteinhardtQuoted 17 lines · Patrick Steinhardt
Quoted 9 lines · Junio C Hamano
Quoted 5 lines · Derrick Stolee
I do worry about the case where annotated tags greatly outnumber branches, so this binary search is extra overhead and the performance may degrade. Would it be worth checking the ref to see if it lies within "refs/heads/" (or even _not_ in "refs/tags/") before doing this commit-graph check?
Ah, clever.
Good idea. Benchmarks for my test repository (which definitely isn't representative, but it's at least some numbers) show that restricting to "refs/heads/" diminishes almost all the gains, while restricting to everything but "refs/tags/" performs almost the same (it's a tiny bit slower, probably because of the added string comparisons):
Quoted 16 lines
Benchmark #1: all refs: git-fetch
Time (mean ± σ): 32.959 s ± 0.282 s [User: 29.801 s, System: 5.137 s]
Range (min … max): 32.760 s … 33.158 s 2 runs
Benchmark #2: refs/heads: git-fetch
Time (mean ± σ): 56.955 s ± 0.002 s [User: 53.447 s, System: 5.362 s]
Range (min … max): 56.953 s … 56.957 s 2 runs
Benchmark #3: !refs/tags: git-fetch
Time (mean ± σ): 33.447 s ± 0.003 s [User: 30.160 s, System: 5.027 s]
Range (min … max): 33.444 s … 33.449 s 2 runs
Summary
'all refs: git-fetch' ran
1.01 ± 0.01 times faster than '!refs/tags: git-fetch'
1.73 ± 0.01 times faster than 'refs/heads: git-fetch'Thanks for testing both options.
Quoted 4 lines
This is easily explained by the fact that the test repo has most of its refs neither in "refs/tags/" nor in "refs/heads/", but rather in special namespaces like "refs/merge-requests/", "refs/environments/" or "refs/keep-around/".
That makes sense to me. GitHub also stores refs like refs/pull/ so I can understand not wanting to restrict to refs/heads/.
Quoted 3 lines
I like the idea of excluding "refs/tags/" though: as you point out, chances are high that these don't point to commits but to annotated tags instead. So I'll go with that, thanks!
Yeah, that makes sense as a good way forward.
Thanks,
-Stolee
Re: [PATCH v2 1/7] fetch: speed up lookup of want refs via commit-graph
In reply to Patrick SteinhardtQuoted 1 line · Patrick Steinhardt
Speed this up by opportunistcally trying to resolve object IDs via the
s/opportunistcally/opportunistically/
builtin/fetch.c static int store_updated_refs(const char *raw_url, const char *remote_name, · line 1143
Quoted 10 lines
builtin/fetch.c +10
-0+/* +* References in "refs/tags/" are often going to point +* to annotated tags, which are not part of the +* commit-graph. We thus only try to look up refs in +* the graph which are not in that namespace to not +* regress performance in repositories with many +* annotated tags. +*/ +if (!starts_with (rm->name,"refs/tags/" )) + commit =lookup_commit_in_graph (the_repository, &rm->old_oid);
This new logic looks good.
builtin/fetch.c static int store_updated_refs(const char *raw_url, const char *remote_name, · line 1150
Quoted 7 lines
builtin/fetch.c +7
-0+if (!commit) { + commit =lookup_commit_reference_gently (the_repository, + &rm->old_oid, +1 ); +if (!commit) + rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ; + }
Thanks,
-Stolee
Re: [PATCH v2 5/7] fetch: refactor fetch refs to be more extendable
In reply to Patrick SteinhardtQuoted 2 lines · Patrick Steinhardt
Refactor
fetch_refs()code to make it more extendable by explicitly handling error cases. The refactored code should behave the same.
...
builtin/fetch.c static int check_exist_and_connected(struct ref *ref_map)
Quoted 13 lines
builtin/fetch.c +9
-0+/* +* We don't need to perform a fetch in case we can already satisfy all +* refs. +*/ + ret =check_exist_and_connected (ref_map);if (ret) {trace2_region_enter ("fetch" ,"fetch_refs" , the_repository); ret =transport_fetch_refs (transport, ref_map);trace2_region_leave ("fetch" ,"fetch_refs" , the_repository); +if (ret) { +transport_unlock_pack (transport); +return ret; + }> }
I see that this nested organization makes it more clear what cases lead into this error state.
Quoted 4 lines
builtin/fetch.c +0
-4-if (!ret) -/* -* Keep the new pack's ".keep" file around to allow the caller -* time to update refs to reference the new objects.
builtin/fetch.c static int check_exist_and_connected(struct ref *ref_map) · line 1317
Quoted 10 lines
builtin/fetch.c +6
-4-*/ -return 0 ; -transport_unlock_pack (transport); -return ret; + +/* +* Keep the new pack's ".keep" file around to allow the caller +* time to update refs to reference the new objects. +*/ +return 0 ;
And it happens that 'ret' is zero here. Should we keep returning 'ret' or perhaps add an "assert(!ret);" before the return? The assert() doesn't do much, but at minimum would serve as an extra indicator to anyone working in this method in the future.
Thanks,
-Stolee
Re: [PATCH v2 6/7] fetch: merge fetching and consuming refs
In reply to Patrick Steinhardtbuiltin/fetch.c static int fetch_refs(struct transport *transport, struct ref *ref_map) · line 1309
Quoted 6 lines · Patrick Steinhardt
builtin/fetch.c +2
-4-if (ret) { -transport_unlock_pack (transport); -return ret; - } +if (ret) + goto out;
You were just reorganizing this method in the previous patch. This "goto out" trick could have applied there instead, which wouldn't complicate that patch and would simplify this one.
But perhaps it would look strange to have the following ending to the method, even if for only one patch:
return 0;
out:
transport_unlock_pack(transport); return res; }
So, feel free to ignore me here. Decide based on your taste.
Quoted 14 lines
builtin/fetch.c +1
-11} -/* -* Keep the new pack's ".keep" file around to allow the caller -* time to update refs to reference the new objects. -*/ -return 0 ; -} - -/* Update local refs based on the ref values fetched from a remote */ -static int consume_refs (struct transport *transport,struct ref *ref_map) -{ -int connectivity_checked = transport->smart_options + connectivity_checked = transport->smart_options
builtin/fetch.c static int fetch_refs(struct transport *transport, struct ref *ref_map) · line 1320
Quoted 10 lines
builtin/fetch.c +1
-2? transport->smart_options->connectivity_checked :0 ; -int ret; +trace2_region_enter ("fetch" ,"consume_refs" , the_repository); ret =store_updated_refs (transport->url, transport->remote->name, connectivity_checked, ref_map); -transport_unlock_pack (transport);trace2_region_leave ("fetch" ,"consume_refs" , the_repository);
This transport_unlock_pack() is leaving the trace2 region. I think it is unlikely that the loop of unlink_or_warn() calls will take significant time that affects this region, so it should be fine to move it.
Quoted 5 lines
builtin/fetch.c +3
-0+ +out: +transport_unlock_pack (transport);return ret; }
...
builtin/fetch.c static int do_fetch(struct transport *transport, · line 1603
Quoted 12 lines
builtin/fetch.c +2
-3-if (!fetch_refs (transport, ref_map)) -consume_refs (transport, ref_map); +fetch_and_consume_refs (transport, ref_map);if (gsecondary) {transport_disconnect (gsecondary);@@ -1610,7 +1600,7 @@ static int do_fetch(struct transport *transport, transport->url); } } -if (fetch_refs (transport, ref_map) ||consume_refs (transport, ref_map)) { +if (fetch_and_consume_refs (transport, ref_map)) {
The end goal of making these consumers simpler is worth it.
Thanks,
-Stolee
Quoted 12 lines · Patrick Steinhardt
Changes compared to v1:
- Patch 1/7: I've applied Stolee's proposal to only opportunistically load objects via the commit-graph in case the reference is not in refs/tags/ such that we don't regress repos with many annotated tags.
- Patch 3/7: The return parameter of the iterator is now const to allow further optimizations by the compiler, as suggested by René. I've also re-benchmarked this, and one can now see a very slight performance improvement of ~1%.
Quoted 8 lines
- Patch 4/7: Added my missing DCO, as pointed out by Junio.
- Patch 5, 6, 7: I've redone these to make it clearer that the refactoring I'm doing doesn't cause us to miss any object connectivity checks. Most importantly, I've merged
fetch_refs()andconsume_refs()intofetch_and_consume_refs()in 6/7, which makes the optimization where we elide the second connectivity check in 7/7 trivial.
These changes are positive. My read through this set of patches had only a few nit-picks.
Thanks,
-Stolee
Re: [PATCH 2/6] fetch: avoid unpacking headers in object existence check
In reply to Patrick SteinhardtQuoted 42 lines · Patrick Steinhardt
[[PGP Signed Part:Undecided]]
When updating local refs after the fetch has transferred all objects, we do an object existence test as a safety guard to avoid updating a ref to an object which we don't have. We do so viaoid_object_info(): if it returns an error, then we know the object does not exist.One side effect of
oid_object_info()is that it parses the object's type, and to do so it must unpack the object header. This is completely
pointless: we don't care for the type, but only want to assert that the object exists.Refactor the code to use
repo_has_object_file(), which both makes the code's intent clearer and is also faster because it does not unpack object headers. In a real-world repo with 2.3M refs, this results in a small speedup when doing a mirror-fetch:Benchmark #1: HEAD~: git-fetch Time (mean ± σ): 33.686 s ± 0.176 s [User: 30.119 s, System: 5.262 s] Range (min … max): 33.512 s … 33.944 s 5 runs Benchmark #2: HEAD: git-fetch Time (mean ± σ): 31.247 s ± 0.195 s [User: 28.135 s, System: 5.066 s] Range (min … max): 30.948 s … 31.472 s 5 runs Summary 'HEAD: git-fetch' ran 1.08 ± 0.01 times faster than 'HEAD~: git-fetch'Signed-off-by Patrick Steinhardt <[email protected]>--- builtin/fetch.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-)builtin/fetch.c +0
-1@@ -846,13 +846,11 @@ static int update_local_ref(struct ref *ref, int summary_width) {struct commit *current =NULL , *updated; -enum object_type type;
builtin/fetch.c static int update_local_ref(struct ref *ref, · line 856
Quoted 10 lines
builtin/fetch.c +1
-2struct branch *current_branch =branch_get (NULL );const char *pretty_ref =prettify_refname (ref->name);int fast_forward =0 ; - type =oid_object_info (the_repository, &ref->new_oid,NULL ); -if (type <0 ) +if (!repo_has_object_file (the_repository, &ref->new_oid))die (_ ("object %s not found" ),oid_to_hex (&ref->new_oid));if (oideq (&ref->old_oid, &ref->new_oid)) {
I tried grepping the source for any other candidates for a migration to repo_has_object_file(), but this is the only "type = oid_object_info" I could find that didn't care about the type, perhaps there's some callers of *_extended() that could be moved over, but that's less likely, and I didn't check...
Re: [PATCH v2 5/7] fetch: refactor fetch refs to be more extendable
In reply to Derrick StoleeQuoted 3 lines · Derrick Stolee
Quoted 2 lines · Patrick Steinhardt
Refactor
fetch_refs()code to make it more extendable by explicitly handling error cases. The refactored code should behave the same.
[snip]
Quoted 11 lines
Quoted 11 lines
builtin/fetch.c +3
-8-if (!ret) -/* -* Keep the new pack's ".keep" file around to allow the caller -* time to update refs to reference the new objects. -*/ -return 0 ; -transport_unlock_pack (transport); -return ret; + +/* +* Keep the new pack's ".keep" file around to allow the caller
Quoted 8 lines
builtin/fetch.c static int check_exist_and_connected(struct ref *ref_map) · line 1317
Quoted 3 lines
builtin/fetch.c +3
-0+* time to update refs to reference the new objects. +*/ +return 0 ;And it happens that 'ret' is zero here. Should we keep returning 'ret' or perhaps add an "assert(!ret);" before the return? The
assert()doesn't do much, but at minimum would serve as an extra indicator to anyone working in this method in the future.
The assert isn't really needed: in the subsequent patch, we always unlock the packfile on exit.
Patrick
Re: [PATCH v2 6/7] fetch: merge fetching and consuming refs
In reply to Derrick StoleeQuoted 15 lines · Derrick Stolee
builtin/fetch.c static int fetch_refs(struct transport *transport, struct ref *ref_map) · line 1309
Quoted 6 lines · Patrick Steinhardt
builtin/fetch.c +2
-4-if (ret) { -transport_unlock_pack (transport); -return ret; - } +if (ret) + goto out;You were just reorganizing this method in the previous patch. This "goto out" trick could have applied there instead, which wouldn't complicate that patch and would simplify this one.
But perhaps it would look strange to have the following ending to the method, even if for only one patch:
Quoted 8 lines
return 0;out:
transport_unlock_pack(transport); return res; }So, feel free to ignore me here. Decide based on your taste.
I think you've got a point, I'll change this.
Patrick
v3 cover Speed up mirror-fetches with many refs
In reply to Patrick SteinhardtHi,
this is the third version of my patch series to speed up mirror-fetches with many refs. This patch series applies on top of master with ps/connectivity-optim merged into it.
There's only some smallish changes based on Stolee's feedback (thanks for that!):
- A small typo in 1/7.
- A confict fix in 4/7 required now because it's based on master instead of directly on my merged topic.
- I've adjusted patch 5/7 such that I don't have to re-touch the logic in 6/7.
Patrick
Patrick Steinhardt (7):
fetch: speed up lookup of want refs via commit-graph
fetch: avoid unpacking headers in object existence check
connected: refactor iterator to return next object ID directly
fetch-pack: optimize loading of refs via commit graph
fetch: refactor fetch refs to be more extendable
fetch: merge fetching and consuming refs
fetch: avoid second connectivity check if we already have all objects
builtin/clone.c | 8 ++--- builtin/fetch.c | 74 +++++++++++++++++++++++------------------- builtin/receive-pack.c | 17 ++++------ connected.c | 15 +++++---- connected.h | 2 +- fetch-pack.c | 12 ++++--- 6 files changed, 67 insertions(+), 61 deletions(-)
Range-diff against v2:
1: 4a819a6830 ! 1: 8214f04971 fetch: speed up lookup of want refs via commit-graph
@@ Commit message
that we repeatedly need to unpack object headers for each of the referenced objects.
- Speed this up by opportunistcally trying to resolve object IDs via the
+ Speed this up by opportunistically trying to resolve object IDs via the
commit graph. We only do so for any refs which are not in "refs/tags":
more likely than not, these are going to be a commit anyway, and this lets us avoid having to unpack object headers completely in case the
2: 81ebadabe8 = 2: 991a27cb82 fetch: avoid unpacking headers in object existence check 3: 98e981ced9 = 3: ba834803ab connected: refactor iterator to return next object ID directly 4: 6311203f08 ! 4: 99d3316d48 fetch-pack: optimize loading of refs via commit graph
@@ fetch-pack.c: static struct commit *deref_without_lazy_fetch(const struct object
while (1) {
if (oid_object_info_extended(the_repository, oid, &info,
-@@ fetch-pack.c: static struct commit *deref_without_lazy_fetch(const struct object_id *oid,
- }
-
- if (type == OBJ_COMMIT) {
-- struct commit *commit = lookup_commit(the_repository, oid);
-+ commit = lookup_commit(the_repository, oid);
- if (!commit || repo_parse_commit(the_repository, commit))
- return NULL;
- return commit;
5: 56a9158ac3 ! 5: d64888e072 fetch: refactor fetch refs to be more extendable
@@ builtin/fetch.c: static int check_exist_and_connected(struct ref *ref_map)
trace2_region_enter("fetch", "fetch_refs", the_repository);
ret = transport_fetch_refs(transport, ref_map);
trace2_region_leave("fetch", "fetch_refs", the_repository);
-+ if (ret) {
-+ transport_unlock_pack(transport);
-+ return ret;
-+ }
++ if (ret)
++ goto out;
}
- if (!ret)
- /*
@@ builtin/fetch.c: static int check_exist_and_connected(struct ref *ref_map)
- * time to update refs to reference the new objects.
- */
- return 0;
-- transport_unlock_pack(transport);
-- return ret;
+
+ /*
+ * Keep the new pack's ".keep" file around to allow the caller
+ * time to update refs to reference the new objects.
+ */
-+ return 0;
++ return ret;
++
++out:
+ transport_unlock_pack(transport);
+ return ret;
}
-
- /* Update local refs based on the ref values fetched from a remote */
6: 31d9f72edf ! 6: 56ecbfc9c3 fetch: merge fetching and consuming refs
@@ builtin/fetch.c: static int check_exist_and_connected(struct ref *ref_map)
/*
@@ builtin/fetch.c: static int fetch_refs(struct transport *transport, struct ref *ref_map)
- trace2_region_enter("fetch", "fetch_refs", the_repository);
- ret = transport_fetch_refs(transport, ref_map);
- trace2_region_leave("fetch", "fetch_refs", the_repository);
-- if (ret) {
-- transport_unlock_pack(transport);
-- return ret;
-- }
-+ if (ret)
-+ goto out;
+ goto out;
}
- /*
- * Keep the new pack's ".keep" file around to allow the caller
- * time to update refs to reference the new objects.
- */
-- return 0;
+- return ret;
+-
+-out:
+- transport_unlock_pack(transport);
+- return ret;
-}
-
-/* Update local refs based on the ref values fetched from a remote */7: 84e39c847f = 7: c342fc0c69 fetch: avoid second connectivity check if we already have all objects
Signature · 1 line
2.33.0
PATCH v3 1/7 fetch: speed up lookup of want refs via commit-graph
When updating our local refs based on the refs fetched from the remote, we need to iterate through all requested refs and load their respective commits such that we can determine whether they need to be appended to FETCH_HEAD or not. In cases where we're fetching from a remote with exceedingly many refs, resolving these refs can be quite expensive given that we repeatedly need to unpack object headers for each of the referenced objects.
Speed this up by opportunistically trying to resolve object IDs via the commit graph. We only do so for any refs which are not in "refs/tags":
more likely than not, these are going to be a commit anyway, and this lets us avoid having to unpack object headers completely in case the object is a commit that is part of the commit-graph. This significantly speeds up mirror-fetches in a real-world repository with 2.3M refs:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 56.482 s ± 0.384 s [User: 53.340 s, System: 5.365 s]
Range (min … max): 56.050 s … 57.045 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 33.727 s ± 0.170 s [User: 30.252 s, System: 5.194 s]
Range (min … max): 33.452 s … 33.871 s 5 runs
Summary
'HEAD: git-fetch' ran
1.67 ± 0.01 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-)
builtin/fetch.c +18 -6
@@ -1074,7 +1074,6 @@ static int store_updated_refs(const char *raw_url, const char *remote_name, int connectivity_checked, struct ref *ref_map) { struct fetch_head fetch_head; -struct commit *commit;int url_len, i, rc =0 ;struct strbuf note =STRBUF_INIT , err =STRBUF_INIT ;struct ref_transaction *transaction =NULL ;
@@ -1122,6 +1121,7 @@ static int store_updated_refs(const char *raw_url, const char *remote_name, want_status <=FETCH_HEAD_IGNORE ; want_status++) {for (rm = ref_map; rm; rm = rm->next) { +struct commit *commit =NULL ;struct ref *ref =NULL ;if (rm->status ==REF_STATUS_REJECT_SHALLOW ) {
@@ -1131,11 +1131,23 @@ static int store_updated_refs(const char *raw_url, const char *remote_name,continue ; } - commit =lookup_commit_reference_gently (the_repository, - &rm->old_oid, -1 ); -if (!commit) - rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ; +/* +* References in "refs/tags/" are often going to point +* to annotated tags, which are not part of the +* commit-graph. We thus only try to look up refs in +* the graph which are not in that namespace to not +* regress performance in repositories with many +* annotated tags. +*/ +if (!starts_with (rm->name,"refs/tags/" )) + commit =lookup_commit_in_graph (the_repository, &rm->old_oid); +if (!commit) { + commit =lookup_commit_reference_gently (the_repository, + &rm->old_oid, +1 ); +if (!commit) + rm->fetch_head_status =FETCH_HEAD_NOT_FOR_MERGE ; + }if (rm->fetch_head_status != want_status)continue ;
Signature · 1 line
2.33.0
PATCH v3 2/7 fetch: avoid unpacking headers in object existence check
In reply to Patrick SteinhardtWhen updating local refs after the fetch has transferred all objects, we do an object existence test as a safety guard to avoid updating a ref to an object which we don't have. We do so via oid_object_info(): if it returns an error, then we know the object does not exist.
One side effect of oid_object_info() is that it parses the object's type, and to do so it must unpack the object header. This is completely
pointless: we don't care for the type, but only want to assert that the object exists.
Refactor the code to use repo_has_object_file(), which both makes the code's intent clearer and is also faster because it does not unpack object headers. In a real-world repo with 2.3M refs, this results in a small speedup when doing a mirror-fetch:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 33.686 s ± 0.176 s [User: 30.119 s, System: 5.262 s]
Range (min … max): 33.512 s … 33.944 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 31.247 s ± 0.195 s [User: 28.135 s, System: 5.066 s]
Range (min … max): 30.948 s … 31.472 s 5 runs
Summary
'HEAD: git-fetch' ran
1.08 ± 0.01 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-)
builtin/fetch.c +1 -3
@@ -846,13 +846,11 @@ static int update_local_ref(struct ref *ref, int summary_width) {struct commit *current =NULL , *updated; -enum object_type type;struct branch *current_branch =branch_get (NULL );const char *pretty_ref =prettify_refname (ref->name);int fast_forward =0 ; - type =oid_object_info (the_repository, &ref->new_oid,NULL ); -if (type <0 ) +if (!repo_has_object_file (the_repository, &ref->new_oid))die (_ ("object %s not found" ),oid_to_hex (&ref->new_oid));if (oideq (&ref->old_oid, &ref->new_oid)) {
Signature · 1 line
2.33.0
PATCH v3 3/7 connected: refactor iterator to return next object ID directly
In reply to Patrick SteinhardtThe object ID iterator used by the connectivity checks returns the next object ID via an out-parameter and then uses a return code to indicate whether an item was found. This is a bit roundabout: instead of a separate error code, we can just return the next object ID directly and use NULL pointers as indicator that the iterator got no items left. Furthermore, this avoids a copy of the object ID.
Refactor the iterator and all its implementations to return object IDs
directly. This brings a tiny performance improvement when doing a mirror-fetch of a repository with about 2.3M refs:
Benchmark #1: 328dc58b49919c43897240f2eabfa30be2ce32a4~: git-fetch
Time (mean ± σ): 30.110 s ± 0.148 s [User: 27.161 s, System: 5.075 s]
Range (min … max): 29.934 s … 30.406 s 10 runs
Benchmark #2: 328dc58b49919c43897240f2eabfa30be2ce32a4: git-fetch
Time (mean ± σ): 29.899 s ± 0.109 s [User: 26.916 s, System: 5.104 s]
Range (min … max): 29.696 s … 29.996 s 10 runs
Summary
'328dc58b49919c43897240f2eabfa30be2ce32a4: git-fetch' ran
1.01 ± 0.01 times faster than '328dc58b49919c43897240f2eabfa30be2ce32a4~: git-fetch'While this 1% speedup could be labelled as statistically insignificant, the speedup is consistent on my machine. Furthermore, this is an end to end test, so it is expected that the improvement in the connectivity check itself is more significant.
--- builtin/clone.c | 8 +++----- builtin/fetch.c | 7 +++---- builtin/receive-pack.c | 17 +++++++---------- connected.c | 15 ++++++++------- connected.h | 2 +- fetch-pack.c | 7 +++---- 6 files changed, 25 insertions(+), 31 deletions(-)
builtin/clone.c +3 -5
@@ -657,7 +657,7 @@ static void write_followtags(const struct ref *refs, const char *msg) } } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static const struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;
@@ -668,13 +668,11 @@ static int iterate_ref_map(void *cb_data, struct object_id *oid)*/ while (ref && !ref->peer_ref) ref = ref->next; -/* Returning -1 notes "end of list" to the caller. */ if (!ref) -return -1 ; +return NULL ; -oidcpy (oid, &ref->old_oid); *rm = ref->next; -return 0 ; +return &ref->old_oid; } static void update_remote_refs(const struct ref *refs,
builtin/fetch.c +3 -4
@@ -962,7 +962,7 @@ static int update_local_ref(struct ref *ref, } } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static const struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;
@@ -970,10 +970,9 @@ static int iterate_ref_map(void *cb_data, struct object_id *oid)while (ref && ref->status ==REF_STATUS_REJECT_SHALLOW ) ref = ref->next;if (!ref) -return -1 ;/* end of the list */ +return NULL ; *rm = ref->next; -oidcpy (oid, &ref->old_oid); -return 0 ; +return &ref->old_oid; }struct fetch_head {
builtin/receive-pack.c +7 -10
@@ -1306,7 +1306,7 @@ static void refuse_unconfigured_deny_delete_current(void)rp_error ("%s" ,_ (refuse_unconfigured_deny_delete_current_msg)); } -static int command_singleton_iterator (void *cb_data,struct object_id *oid); +static const struct object_id *command_singleton_iterator (void *cb_data);static int update_shallow_ref (struct command *cmd,struct shallow_info *si) {struct shallow_lock shallow_lock =SHALLOW_LOCK_INIT ;
@@ -1731,16 +1731,15 @@ static void check_aliased_updates(struct command *commands)string_list_clear (&ref_list,0 ); } -static int command_singleton_iterator (void *cb_data,struct object_id *oid) +static const struct object_id *command_singleton_iterator (void *cb_data) {struct command **cmd_list = cb_data;struct command *cmd = *cmd_list;if (!cmd ||is_null_oid (&cmd->new_oid)) -return -1 ;/* end of list */ +return NULL ; *cmd_list =NULL ;/* this returns only one */ -oidcpy (oid, &cmd->new_oid); -return 0 ; +return &cmd->new_oid; } static void set_connectivity_errors(struct command *commands,
@@ -1770,7 +1769,7 @@ struct iterate_data {struct shallow_info *si; }; -static int iterate_receive_command_list (void *cb_data,struct object_id *oid) +static const struct object_id *iterate_receive_command_list (void *cb_data) {struct iterate_data *data = cb_data;struct command **cmd_list = &data->cmds;
@@ -1781,13 +1780,11 @@ static int iterate_receive_command_list(void *cb_data, struct object_id *oid)/* to be checked in update_shallow_ref() */ continue ;if (!is_null_oid (&cmd->new_oid) && !cmd->skip_update) { -oidcpy (oid, &cmd->new_oid); *cmd_list = cmd->next; -return 0 ; +return &cmd->new_oid; } } - *cmd_list =NULL ; -return -1 ;/* end of list */ +return NULL ; }static void reject_updates_to_hidden (struct command *commands)
connected.c +8 -7
@@ -24,7 +24,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,struct child_process rev_list =CHILD_PROCESS_INIT ;FILE *rev_list_in;struct check_connected_options defaults =CHECK_CONNECTED_INIT ; -struct object_id oid; +const struct object_id *oid;int err =0 ;struct packed_git *new_pack =NULL ;struct transport *transport;
@@ -34,7 +34,8 @@ int check_connected(oid_iterate_fn fn, void *cb_data, opt = &defaults; transport = opt->transport; -if (fn (cb_data, &oid)) { + oid =fn (cb_data); +if (!oid) {if (opt->err_fd)close (opt->err_fd);return err;
@@ -73,7 +74,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,for (p =get_all_packs (the_repository); p; p = p->next) {if (!p->pack_promisor)continue ; -if (find_pack_entry_one (oid.hash, p)) +if (find_pack_entry_one (oid->hash, p)) goto promisor_pack_found; }/*
@@ -83,7 +84,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data, goto no_promisor_pack_found; promisor_pack_found: ; - }while (!fn (cb_data, &oid)); + }while ((oid =fn (cb_data)) !=NULL );return 0 ; }
@@ -133,12 +134,12 @@ int check_connected(oid_iterate_fn fn, void *cb_data,* are sure the ref is good and not sending it to * rev-list for verification. */ -if (new_pack &&find_pack_entry_one (oid.hash, new_pack)) +if (new_pack &&find_pack_entry_one (oid->hash, new_pack))continue ; -if (fprintf (rev_list_in,"%s\n" ,oid_to_hex (&oid)) <0 ) +if (fprintf (rev_list_in,"%s\n" ,oid_to_hex (oid)) <0 )break ; - }while (!fn (cb_data, &oid)); + }while ((oid =fn (cb_data)) !=NULL );if (ferror (rev_list_in) ||fflush (rev_list_in)) {if (errno !=EPIPE && errno !=EINVAL )
connected.h +1 -1
@@ -9,7 +9,7 @@ struct transport;* When called after returning the name for the last object, return -1 * to signal EOF, otherwise return 0. */ -typedef int (*oid_iterate_fn )(void *,struct object_id *oid); +typedef const struct object_id *(*oid_iterate_fn )(void *);/* * Named-arguments struct for check_connected. All arguments are
fetch-pack.c +3 -4
@@ -1906,16 +1906,15 @@ static void update_shallow(struct fetch_pack_args *args,oid_array_clear (&ref); } -static int iterate_ref_map (void *cb_data,struct object_id *oid) +static const struct object_id *iterate_ref_map (void *cb_data) {struct ref **rm = cb_data;struct ref *ref = *rm;if (!ref) -return -1 ;/* end of the list */ +return NULL ; *rm = ref->next; -oidcpy (oid, &ref->old_oid); -return 0 ; +return &ref->old_oid; } struct ref *fetch_pack(struct fetch_pack_args *args,
Signature · 1 line
2.33.0
PATCH v3 4/7 fetch-pack: optimize loading of refs via commit graph
In reply to Patrick SteinhardtIn order to negotiate a packfile, we need to dereference refs to see which commits we have in common with the remote. To do so, we first look up the object's type -- if it's a tag, we peel until we hit a non-tag object. If we hit a commit eventually, then we return that commit.
In case the object ID points to a commit directly, we can avoid the initial lookup of the object type by opportunistically looking up the commit via the commit-graph, if available, which gives us a slight speed bump of about 2% in a huge repository with about 2.3M refs:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 31.634 s ± 0.258 s [User: 28.400 s, System: 5.090 s]
Range (min … max): 31.280 s … 31.896 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 31.129 s ± 0.543 s [User: 27.976 s, System: 5.056 s]
Range (min … max): 30.172 s … 31.479 s 5 runs
Summary
'HEAD: git-fetch' ran
1.02 ± 0.02 times faster than 'HEAD~: git-fetch'In case this fails, we fall back to the old code which peels the objects to a commit.
--- fetch-pack.c | 5 +++++ 1 file changed, 5 insertions(+)
fetch-pack.c +5 -0
@@ -119,6 +119,11 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid, {enum object_type type;struct object_info info = { .typep = &type }; +struct commit *commit; + + commit =lookup_commit_in_graph (the_repository, oid); +if (commit) +return commit;while (1 ) { if (oid_object_info_extended(the_repository, oid, &info,
Signature · 1 line
2.33.0
PATCH v3 5/7 fetch: refactor fetch refs to be more extendable
In reply to Patrick SteinhardtRefactor fetch_refs() code to make it more extendable by explicitly handling error cases. The refactored code should behave the same.
--- builtin/fetch.c | 24 +++++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-)
builtin/fetch.c +17 -7
@@ -1293,18 +1293,28 @@ static int check_exist_and_connected(struct ref *ref_map)static int fetch_refs (struct transport *transport,struct ref *ref_map) { -int ret =check_exist_and_connected (ref_map); +int ret; + +/* +* We don't need to perform a fetch in case we can already satisfy all +* refs. +*/ + ret =check_exist_and_connected (ref_map);if (ret) {trace2_region_enter ("fetch" ,"fetch_refs" , the_repository); ret =transport_fetch_refs (transport, ref_map);trace2_region_leave ("fetch" ,"fetch_refs" , the_repository); +if (ret) + goto out; } -if (!ret) -/* -* Keep the new pack's ".keep" file around to allow the caller -* time to update refs to reference the new objects. -*/ -return 0 ; + +/* +* Keep the new pack's ".keep" file around to allow the caller +* time to update refs to reference the new objects. +*/ +return ret; + +out:transport_unlock_pack (transport);return ret; }
Signature · 1 line
2.33.0
PATCH v3 6/7 fetch: merge fetching and consuming refs
In reply to Patrick SteinhardtThe functions fetch_refs() and consume_refs() must always be called together such that we first obtain all missing objects and then update our local refs to match the remote refs. In a subsequent patch, we'll further require that fetch_refs() must always be called before consume_refs() such that it can correctly assert that we have all objects after the fetch given that we're about to move the connectivity check.
Make this requirement explicit by merging both functions into a single fetch_and_consume_refs() function.
--- builtin/fetch.c | 30 +++++++++--------------------- 1 file changed, 9 insertions(+), 21 deletions(-)
builtin/fetch.c +9 -21
@@ -1291,8 +1291,9 @@ static int check_exist_and_connected(struct ref *ref_map)return check_connected (iterate_ref_map, &rm, &opt); } -static int fetch_refs (struct transport *transport,struct ref *ref_map) +static int fetch_and_consume_refs (struct transport *transport,struct ref *ref_map) { +int connectivity_checked;int ret;/*
@@ -1308,30 +1309,18 @@ static int fetch_refs(struct transport *transport, struct ref *ref_map) goto out; } -/* -* Keep the new pack's ".keep" file around to allow the caller -* time to update refs to reference the new objects. -*/ -return ret; - -out: -transport_unlock_pack (transport); -return ret; -} - -/* Update local refs based on the ref values fetched from a remote */ -static int consume_refs (struct transport *transport,struct ref *ref_map) -{ -int connectivity_checked = transport->smart_options + connectivity_checked = transport->smart_options ? transport->smart_options->connectivity_checked :0 ; -int ret; +trace2_region_enter ("fetch" ,"consume_refs" , the_repository); ret =store_updated_refs (transport->url, transport->remote->name, connectivity_checked, ref_map); -transport_unlock_pack (transport);trace2_region_leave ("fetch" ,"consume_refs" , the_repository); + +out: +transport_unlock_pack (transport);return ret; }
@@ -1518,8 +1507,7 @@ static void backfill_tags(struct transport *transport, struct ref *ref_map)transport_set_option (transport,TRANS_OPT_FOLLOWTAGS ,NULL );transport_set_option (transport,TRANS_OPT_DEPTH ,"0" );transport_set_option (transport,TRANS_OPT_DEEPEN_RELATIVE ,NULL ); -if (!fetch_refs (transport, ref_map)) -consume_refs (transport, ref_map); +fetch_and_consume_refs (transport, ref_map);if (gsecondary) {transport_disconnect (gsecondary);
@@ -1610,7 +1598,7 @@ static int do_fetch(struct transport *transport, transport->url); } } -if (fetch_refs (transport, ref_map) ||consume_refs (transport, ref_map)) { +if (fetch_and_consume_refs (transport, ref_map)) {free_refs (ref_map); retcode =1 ; goto cleanup;
Signature · 1 line
2.33.0
PATCH v3 7/7 fetch: avoid second connectivity check if we already have all objects
In reply to Patrick SteinhardtWhen fetching refs, we are doing two connectivity checks:
- The first one is done such that we can skip fetching refs in the case where we already have all objects referenced by the updated set of refs.
- The second one verifies that we have all objects after we have fetched objects.
We always execute both connectivity checks, but this is wasteful in case the first connectivity check already notices that we have all objects locally available.
Skip the second connectivity check in case we already had all objects available. This gives us a nice speedup when doing a mirror-fetch in a repository with about 2.3M refs where the fetching repo already has all objects:
Benchmark #1: HEAD~: git-fetch
Time (mean ± σ): 30.025 s ± 0.081 s [User: 27.070 s, System: 4.933 s]
Range (min … max): 29.900 s … 30.111 s 5 runs
Benchmark #2: HEAD: git-fetch
Time (mean ± σ): 25.574 s ± 0.177 s [User: 22.855 s, System: 4.683 s]
Range (min … max): 25.399 s … 25.765 s 5 runs
Summary
'HEAD: git-fetch' ran
1.17 ± 0.01 times faster than 'HEAD~: git-fetch'--- builtin/fetch.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-)
builtin/fetch.c +3 -4
@@ -1293,7 +1293,7 @@ static int check_exist_and_connected(struct ref *ref_map)static int fetch_and_consume_refs (struct transport *transport,struct ref *ref_map) { -int connectivity_checked; +int connectivity_checked =1 ;int ret;/*
@@ -1307,11 +1307,10 @@ static int fetch_and_consume_refs(struct transport *transport, struct ref *ref_mtrace2_region_leave ("fetch" ,"fetch_refs" , the_repository);if (ret) goto out; + connectivity_checked = transport->smart_options ? + transport->smart_options->connectivity_checked :0 ; } - connectivity_checked = transport->smart_options - ? transport->smart_options->connectivity_checked :0 ; -trace2_region_enter ("fetch" ,"consume_refs" , the_repository); ret = store_updated_refs(transport->url, transport->remote->name,
Signature · 1 line
2.33.0
Quoted 10 lines · Patrick Steinhardt
There's only some smallish changes based on Stolee's feedback (thanks for that!):
- A small typo in 1/7.
- A confict fix in 4/7 required now because it's based on master instead of directly on my merged topic.
- I've adjusted patch 5/7 such that I don't have to re-touch the logic in 6/7.
OK, as a sanity check on my end, I've tried to apply this on master and then to merge the result with 'ps/connectivity-optim' topic (i.e. expected endgame for this and the other topic if both of them graduated today without any other topics), and then tried a merge on master to the previous round (i.e. has the other topic already in), and did not see any difference in the end result.
Will replace.
Quoted 13 lines · Junio C Hamano
Quoted 10 lines · Patrick Steinhardt
There's only some smallish changes based on Stolee's feedback (thanks for that!):
- A small typo in 1/7.
- A confict fix in 4/7 required now because it's based on master instead of directly on my merged topic.
- I've adjusted patch 5/7 such that I don't have to re-touch the logic in 6/7.
Quoted 8 lines
OK, as a sanity check on my end, I've tried to apply this on master and then to merge the result with 'ps/connectivity-optim' topic (i.e. expected endgame for this and the other topic if both of them graduated today without any other topics), and then tried a merge on master to the previous round (i.e. has the other topic already in), and did not see any difference in the end result.
Will replace.
OK. Is everybody happy with this version? I am about to mark it for 'next' in the next issue of "What's cooking" report, so please holler if I should wait.