Re: [PATCH 1/1] fetch: Cache the want OIDs for faster lookup
- From
Derrick Stolee <stolee@gmail.com>
- Date
- Sep 16, 2019, 02:35 UTC
- Message-ID
- <bbc3ef83-7ff9-deeb-2b7d-734112fc2418@gmail.com>
- In-Reply-To
- <20190915211802.207715-2-masayasuzuki@google.com>
On 9/15/2019 5:18 PM, Masaya Suzuki wrote:
Show 5 quoted lines
> 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
Show 91 quoted lines
>
> 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,
>