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

[Masaya Suzuki]

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.

Signed-off-by: Masaya Suzuki <masayasuz...@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,
-- 
2.23.0.237.gc6a4ce50a0-goog