Skip to contentSkip to conversation

Speed up mirror-fetches with many refs

PATCH Superseded Patrick Steinhardt 5 participants 48 messages Aug 20, 2021 – Sep 8, 2021

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

PATCH 1/6 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 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
index 405afe9bdf..73f5b286d5 100644
@@ -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
#2 lore raw

Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph

Quoted 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_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:

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

#3 lore raw

Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph

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.

#4 lore raw

Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph

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):

    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

#5 lore raw

Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph

Quoted 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

#6 lore raw

PATCH 2/6 fetch: avoid unpacking headers in object existence check

In reply to Patrick Steinhardt

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
index 73f5b286d5..5fd0f7c791 100644
@@ -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
#7 lore raw

Re: [PATCH 2/6] fetch: avoid unpacking headers in object existence check

Quoted 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 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 +0 -1
index 73f5b286d5..5fd0f7c791 100644
@@ -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 -2
 	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)) {

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

#8 lore raw

PATCH 3/6 connected: refactor iterator to return next object ID directly

In reply to 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 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
index a74558f30c..817a651936 100644
@@ -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
index 5fd0f7c791..76ce73ccf5 100644
@@ -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
index a419de5b38..0abda033bc 100644
@@ -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
index b5f9523a5f..374b145355 100644
@@ -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
index 8d5a6b3ad6..56cc95be2d 100644
@@ -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
index 0bf7ed7e47..1a6242cd71 100644
@@ -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
#9 lore raw

Re: [PATCH 3/6] connected: refactor iterator to return next object ID directly

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 NULL pointers 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

#10 lore raw

Re: [PATCH 3/6] connected: refactor iterator to return next object ID directly

Quoted 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 NULL pointers 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.

#11 lore raw

Re: [PATCH 3/6] connected: refactor iterator to return next object ID directly

In reply to Patrick Steinhardt

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

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
---
 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
index a74558f30c..817a651936 100644
@@ -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
index 5fd0f7c791..76ce73ccf5 100644
@@ -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
index a419de5b38..0abda033bc 100644
@@ -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
index b5f9523a5f..374b145355 100644
@@ -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
index 8d5a6b3ad6..56cc95be2d 100644

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
index 0bf7ed7e47..1a6242cd71 100644
@@ -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,
#12 lore raw

Re: [PATCH 3/6] connected: refactor iterator to return next object ID directly

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

Quoted 8 lines

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.

Right, will change the signature and re-benchmark. I'd be surprised if it significantly changed the picture, but let's see.

Patrick

#13 lore raw

PATCH 4/6 fetch-pack: optimize loading of refs via commit graph

In reply to 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:

    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
index 1a6242cd71..c57faf278f 100644
@@ -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
#14 lore raw

Re: [PATCH 4/6] fetch-pack: optimize loading of refs via commit graph

Quoted 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 -1
 	if (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

#15 lore raw

PATCH 5/6 fetch: refactor fetch refs to be more extendable

In reply to 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 | 33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)
builtin/fetch.c +21 -12
index 76ce73ccf5..20fcfe0f45 100644
@@ -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
#16 lore raw

Re: [PATCH 5/6] fetch: refactor fetch refs to be more extendable

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.

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

#17 lore raw

PATCH 6/6 fetch: avoid second connectivity check if we already have all objects

In reply to 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.

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
index 20fcfe0f45..088a8af13b 100644
@@ -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
#18 lore raw

Re: [PATCH 6/6] fetch: avoid second connectivity check if we already have all objects

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 call fetch_refs() followed by consume_refs(), which is the only caller of store_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

#19 lore raw

Re: [PATCH 6/6] fetch: avoid second connectivity check if we already have all objects

Quoted 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 call fetch_refs() followed by consume_refs(), which is the only caller of store_updated_refs().

Quoted 3 lines

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?

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

#20 lore raw
In reply to Patrick Steinhardt

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

#21 lore raw
In reply to Patrick Steinhardt
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.

#22 lore raw

v2 cover Speed up mirror-fetches with many refs

In reply to Patrick Steinhardt

Hi,

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 objects
Signature · 1 line
2.33.0
#23 lore raw

PATCH v2 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 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
index e064687dbd..91d1301613 100644
@@ -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
#24 lore raw

Re: [PATCH v2 1/7] fetch: speed up lookup of want refs via commit-graph

Quoted 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

#25 lore raw

PATCH v2 2/7 fetch: avoid unpacking headers in object existence check

In reply to Patrick Steinhardt

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
index 91d1301613..01513e6aea 100644
@@ -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
#26 lore raw

PATCH v2 3/7 connected: refactor iterator to return next object ID directly

In reply to 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 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
index 66fe66679c..4a1056fcc2 100644
@@ -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
index 01513e6aea..cdf0d0d671 100644
@@ -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
index 2d1f97e1ca..041e915454 100644
@@ -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
index b5f9523a5f..cf68e37a97 100644
@@ -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
index 8d5a6b3ad6..6e59c92aa3 100644
@@ -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
index 0bf7ed7e47..e6ec79f81a 100644
@@ -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
#27 lore raw

PATCH v2 4/7 fetch-pack: optimize loading of refs via commit graph

In reply to 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:

    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
index e6ec79f81a..dc800879cb 100644
@@ -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
#28 lore raw

PATCH v2 5/7 fetch: refactor fetch refs to be more extendable

In reply to 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 | 26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)
builtin/fetch.c +17 -9
index cdf0d0d671..da0e283288 100644
@@ -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
#29 lore raw

Re: [PATCH v2 5/7] fetch: refactor fetch refs to be more extendable

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.

...

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

#30 lore raw

Re: [PATCH v2 5/7] fetch: refactor fetch refs to be more extendable

Quoted 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

#31 lore raw

PATCH v2 6/7 fetch: merge fetching and consuming refs

In reply to Patrick Steinhardt

The 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
index da0e283288..a1e17edd8b 100644
@@ -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
#32 lore raw

Re: [PATCH v2 6/7] fetch: merge fetching and consuming refs

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:

	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

#33 lore raw

Re: [PATCH v2 6/7] fetch: merge fetching and consuming refs

Quoted 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

#34 lore raw

PATCH v2 7/7 fetch: avoid second connectivity check if we already have all objects

In reply to Patrick Steinhardt

When 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
index a1e17edd8b..e2c952ec67 100644
@@ -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_m
 		trace2_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
#35 lore raw
In reply to Patrick Steinhardt
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.

#36 lore raw
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 3628199d4d I 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

#37 lore raw
In reply to Patrick Steinhardt
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() 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.

These changes are positive. My read through this set of patches had only a few nit-picks.

Thanks,
-Stolee

#38 lore raw

v3 cover Speed up mirror-fetches with many refs

In reply to Patrick Steinhardt

Hi,

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
#39 lore raw

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
index 25740c13df..bd7c0da232 100644
@@ -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
#40 lore raw

PATCH v3 2/7 fetch: avoid unpacking headers in object existence check

In reply to Patrick Steinhardt

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
index bd7c0da232..0b18c47732 100644
@@ -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
#41 lore raw

PATCH v3 3/7 connected: refactor iterator to return next object ID directly

In reply to 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 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
index 66fe66679c..4a1056fcc2 100644
@@ -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
index 0b18c47732..f67fe543ad 100644
@@ -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
index 2d1f97e1ca..041e915454 100644
@@ -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
index b5f9523a5f..cf68e37a97 100644
@@ -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
index 8d5a6b3ad6..6e59c92aa3 100644
@@ -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
index b0c7be717c..7b0e69884d 100644
@@ -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
#42 lore raw

PATCH v3 4/7 fetch-pack: optimize loading of refs via commit graph

In reply to 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:

    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
index 7b0e69884d..da92a5e474 100644
@@ -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
#43 lore raw

PATCH v3 5/7 fetch: refactor fetch refs to be more extendable

In reply to 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 | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)
builtin/fetch.c +17 -7
index f67fe543ad..bafeb3d44b 100644
@@ -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
#44 lore raw

PATCH v3 6/7 fetch: merge fetching and consuming refs

In reply to Patrick Steinhardt

The 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
index bafeb3d44b..09f7742d0f 100644
@@ -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
#45 lore raw

PATCH v3 7/7 fetch: avoid second connectivity check if we already have all objects

In reply to Patrick Steinhardt

When 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
index 09f7742d0f..6fdd01fb01 100644
@@ -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_m
 		trace2_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
#46 lore raw
In reply to Patrick Steinhardt
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.

#47 lore raw
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.