Re: [PATCH 1/1] fetch: Cache the want OIDs for faster lookup

[Derrick Stolee <stolee@gmail.com>]

On 9/15/2019 5:18 PM, Masaya Suzuki wrote:
> During git-fetch, the client checks if the advertised tags' OIDs are
> already in the fetch request's want OID set. This check is done in a
> linear scan. For a repository that has a lot of refs, repeating this
> scan takes 15+ minutes. In order to speed this up, create a oid_set for
> other refs' OIDs.

Good catch! Quadratic performance is never good.

The patch below looks like it works, but could you also share your
performance timings for the 15+ minute case after your patch is
applied?

Thanks,
-Stolee

> 
> Signed-off-by: Masaya Suzuki <masayasuzuki@google.com>
> ---
>  builtin/fetch.c | 18 ++++++++++--------
>  1 file changed, 10 insertions(+), 8 deletions(-)
> 
> diff --git a/builtin/fetch.c b/builtin/fetch.c
> index 54d6b01892..51a276dfaa 100644
> --- a/builtin/fetch.c
> +++ b/builtin/fetch.c
> @@ -7,6 +7,7 @@
>  #include "refs.h"
>  #include "refspec.h"
>  #include "object-store.h"
> +#include "oidset.h"
>  #include "commit.h"
>  #include "builtin.h"
>  #include "string-list.h"
> @@ -243,15 +244,13 @@ static void add_merge_config(struct ref **head,
>  	}
>  }
>  
> -static int will_fetch(struct ref **head, const unsigned char *sha1)
> +static void create_fetch_oidset(struct ref **head, struct oidset *out)
>  {
>  	struct ref *rm = *head;
>  	while (rm) {
> -		if (hasheq(rm->old_oid.hash, sha1))
> -			return 1;
> +		oidset_insert(out, &rm->old_oid);
>  		rm = rm->next;
>  	}
> -	return 0;
>  }
>  
>  struct refname_hash_entry {
> @@ -317,6 +316,7 @@ static void find_non_local_tags(const struct ref *refs,
>  {
>  	struct hashmap existing_refs;
>  	struct hashmap remote_refs;
> +	struct oidset fetch_oids = OIDSET_INIT;
>  	struct string_list remote_refs_list = STRING_LIST_INIT_NODUP;
>  	struct string_list_item *remote_ref_item;
>  	const struct ref *ref;
> @@ -324,6 +324,7 @@ static void find_non_local_tags(const struct ref *refs,
>  
>  	refname_hash_init(&existing_refs);
>  	refname_hash_init(&remote_refs);
> +	create_fetch_oidset(head, &fetch_oids);
>  
>  	for_each_ref(add_one_refname, &existing_refs);
>  	for (ref = refs; ref; ref = ref->next) {
> @@ -340,9 +341,9 @@ static void find_non_local_tags(const struct ref *refs,
>  			if (item &&
>  			    !has_object_file_with_flags(&ref->old_oid,
>  							OBJECT_INFO_QUICK) &&
> -			    !will_fetch(head, ref->old_oid.hash) &&
> +			    !oidset_contains(&fetch_oids, &ref->old_oid) &&
>  			    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&
> -			    !will_fetch(head, item->oid.hash))
> +			    !oidset_contains(&fetch_oids, &item->oid))
>  				clear_item(item);
>  			item = NULL;
>  			continue;
> @@ -356,7 +357,7 @@ static void find_non_local_tags(const struct ref *refs,
>  		 */
>  		if (item &&
>  		    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&
> -		    !will_fetch(head, item->oid.hash))
> +		    !oidset_contains(&fetch_oids, &item->oid))
>  			clear_item(item);
>  
>  		item = NULL;
> @@ -377,7 +378,7 @@ static void find_non_local_tags(const struct ref *refs,
>  	 */
>  	if (item &&
>  	    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&
> -	    !will_fetch(head, item->oid.hash))
> +	    !oidset_contains(&fetch_oids, &item->oid))
>  		clear_item(item);
>  
>  	/*
> @@ -404,6 +405,7 @@ static void find_non_local_tags(const struct ref *refs,
>  	}
>  	hashmap_free(&remote_refs, 1);
>  	string_list_clear(&remote_refs_list, 0);
> +	oidset_clear(&fetch_oids);
>  }
>  
>  static struct ref *get_ref_map(struct remote *remote,
>