{"thread":{"id":"51855","subject":"[PATCH 0/1] fetch: Cache the want OIDs for faster lookup","startedAt":"2019-09-15T21:18:10Z","lastAt":"2019-09-16T20:01:37Z","messageCount":6,"participants":["Masaya Suzuki","Derrick Stolee","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"382398","messageId":"20190915211802.207715-1-masayasuzuki@google.com","threadId":"51855","inReplyTo":null,"subject":"[PATCH 0/1] fetch: Cache the want OIDs for faster lookup","fromName":"Masaya Suzuki","fromEmail":"masayasuzuki@google.com","sentAt":"2019-09-15T21:18:01Z","receivedAt":"2019-09-15T21:18:10Z","isPatch":true,"sender":{"key":"masayasuzuki@google.com","avatar":"https://avatars.githubusercontent.com/u/21878?v=4"},"body":"When mirroring a repository with a lot of refs, there is a case where the client\ntakes a long time to calculate the want OIDs. This is observable with Chromium's\nrepository for example.\n\n$ mkdir testing\n$ cd testing\n$ git init . --bare\n$ git remote add origin master https://chromium.googlesource.com/chromium/src --mirror=fetch\n$ git fetch origin\n\nWith the commands above, it takes a long time before sending a fetch request. I\nstopped the command after 15 minutes.\n\nDebugging this, it seems most of the time is spent on iterating the want refs to\nsee OIDs are included there. This patch speeds up this process by using oid_set.\nNow the client can send a fetch request almost immediately.\n\nMasaya Suzuki (1):\n  fetch: Cache the want OIDs for faster lookup\n\n builtin/fetch.c | 18 ++++++++++--------\n 1 file changed, 10 insertions(+), 8 deletions(-)\n\n-- \n2.23.0.237.gc6a4ce50a0-goog\n\n"},{"id":"382399","messageId":"20190915211802.207715-2-masayasuzuki@google.com","threadId":"51855","inReplyTo":"20190915211802.207715-1-masayasuzuki@google.com","subject":"[PATCH 1/1] fetch: Cache the want OIDs for faster lookup","fromName":"Masaya Suzuki","fromEmail":"masayasuzuki@google.com","sentAt":"2019-09-15T21:18:02Z","receivedAt":"2019-09-15T21:18:28Z","isPatch":true,"sender":{"key":"masayasuzuki@google.com","avatar":"https://avatars.githubusercontent.com/u/21878?v=4"},"body":"During git-fetch, the client checks if the advertised tags' OIDs are\nalready in the fetch request's want OID set. This check is done in a\nlinear scan. For a repository that has a lot of refs, repeating this\nscan takes 15+ minutes. In order to speed this up, create a oid_set for\nother refs' OIDs.\n\nSigned-off-by: Masaya Suzuki <masayasuzuki@google.com>\n---\n builtin/fetch.c | 18 ++++++++++--------\n 1 file changed, 10 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 54d6b01892..51a276dfaa 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -7,6 +7,7 @@\n #include \"refs.h\"\n #include \"refspec.h\"\n #include \"object-store.h\"\n+#include \"oidset.h\"\n #include \"commit.h\"\n #include \"builtin.h\"\n #include \"string-list.h\"\n@@ -243,15 +244,13 @@ static void add_merge_config(struct ref **head,\n \t}\n }\n \n-static int will_fetch(struct ref **head, const unsigned char *sha1)\n+static void create_fetch_oidset(struct ref **head, struct oidset *out)\n {\n \tstruct ref *rm = *head;\n \twhile (rm) {\n-\t\tif (hasheq(rm->old_oid.hash, sha1))\n-\t\t\treturn 1;\n+\t\toidset_insert(out, &rm->old_oid);\n \t\trm = rm->next;\n \t}\n-\treturn 0;\n }\n \n struct refname_hash_entry {\n@@ -317,6 +316,7 @@ static void find_non_local_tags(const struct ref *refs,\n {\n \tstruct hashmap existing_refs;\n \tstruct hashmap remote_refs;\n+\tstruct oidset fetch_oids = OIDSET_INIT;\n \tstruct string_list remote_refs_list = STRING_LIST_INIT_NODUP;\n \tstruct string_list_item *remote_ref_item;\n \tconst struct ref *ref;\n@@ -324,6 +324,7 @@ static void find_non_local_tags(const struct ref *refs,\n \n \trefname_hash_init(&existing_refs);\n \trefname_hash_init(&remote_refs);\n+\tcreate_fetch_oidset(head, &fetch_oids);\n \n \tfor_each_ref(add_one_refname, &existing_refs);\n \tfor (ref = refs; ref; ref = ref->next) {\n@@ -340,9 +341,9 @@ static void find_non_local_tags(const struct ref *refs,\n \t\t\tif (item &&\n \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n-\t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n+\t\t\t    !oidset_contains(&fetch_oids, &ref->old_oid) &&\n \t\t\t    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&\n-\t\t\t    !will_fetch(head, item->oid.hash))\n+\t\t\t    !oidset_contains(&fetch_oids, &item->oid))\n \t\t\t\tclear_item(item);\n \t\t\titem = NULL;\n \t\t\tcontinue;\n@@ -356,7 +357,7 @@ static void find_non_local_tags(const struct ref *refs,\n \t\t */\n \t\tif (item &&\n \t\t    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&\n-\t\t    !will_fetch(head, item->oid.hash))\n+\t\t    !oidset_contains(&fetch_oids, &item->oid))\n \t\t\tclear_item(item);\n \n \t\titem = NULL;\n@@ -377,7 +378,7 @@ static void find_non_local_tags(const struct ref *refs,\n \t */\n \tif (item &&\n \t    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&\n-\t    !will_fetch(head, item->oid.hash))\n+\t    !oidset_contains(&fetch_oids, &item->oid))\n \t\tclear_item(item);\n \n \t/*\n@@ -404,6 +405,7 @@ static void find_non_local_tags(const struct ref *refs,\n \t}\n \thashmap_free(&remote_refs, 1);\n \tstring_list_clear(&remote_refs_list, 0);\n+\toidset_clear(&fetch_oids);\n }\n \n static struct ref *get_ref_map(struct remote *remote,\n-- \n2.23.0.237.gc6a4ce50a0-goog\n\n"},{"id":"382410","messageId":"bbc3ef83-7ff9-deeb-2b7d-734112fc2418@gmail.com","threadId":"51855","inReplyTo":"20190915211802.207715-2-masayasuzuki@google.com","subject":"Re: [PATCH 1/1] fetch: Cache the want OIDs for faster lookup","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-09-16T02:35:40Z","receivedAt":"2019-09-16T02:35:45Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/15/2019 5:18 PM, Masaya Suzuki wrote:\n> During git-fetch, the client checks if the advertised tags' OIDs are\n> already in the fetch request's want OID set. This check is done in a\n> linear scan. For a repository that has a lot of refs, repeating this\n> scan takes 15+ minutes. In order to speed this up, create a oid_set for\n> other refs' OIDs.\n\nGood catch! Quadratic performance is never good.\n\nThe patch below looks like it works, but could you also share your\nperformance timings for the 15+ minute case after your patch is\napplied?\n\nThanks,\n-Stolee\n\n> \n> Signed-off-by: Masaya Suzuki <masayasuzuki@google.com>\n> ---\n>  builtin/fetch.c | 18 ++++++++++--------\n>  1 file changed, 10 insertions(+), 8 deletions(-)\n> \n> diff --git a/builtin/fetch.c b/builtin/fetch.c\n> index 54d6b01892..51a276dfaa 100644\n> --- a/builtin/fetch.c\n> +++ b/builtin/fetch.c\n> @@ -7,6 +7,7 @@\n>  #include \"refs.h\"\n>  #include \"refspec.h\"\n>  #include \"object-store.h\"\n> +#include \"oidset.h\"\n>  #include \"commit.h\"\n>  #include \"builtin.h\"\n>  #include \"string-list.h\"\n> @@ -243,15 +244,13 @@ static void add_merge_config(struct ref **head,\n>  \t}\n>  }\n>  \n> -static int will_fetch(struct ref **head, const unsigned char *sha1)\n> +static void create_fetch_oidset(struct ref **head, struct oidset *out)\n>  {\n>  \tstruct ref *rm = *head;\n>  \twhile (rm) {\n> -\t\tif (hasheq(rm->old_oid.hash, sha1))\n> -\t\t\treturn 1;\n> +\t\toidset_insert(out, &rm->old_oid);\n>  \t\trm = rm->next;\n>  \t}\n> -\treturn 0;\n>  }\n>  \n>  struct refname_hash_entry {\n> @@ -317,6 +316,7 @@ static void find_non_local_tags(const struct ref *refs,\n>  {\n>  \tstruct hashmap existing_refs;\n>  \tstruct hashmap remote_refs;\n> +\tstruct oidset fetch_oids = OIDSET_INIT;\n>  \tstruct string_list remote_refs_list = STRING_LIST_INIT_NODUP;\n>  \tstruct string_list_item *remote_ref_item;\n>  \tconst struct ref *ref;\n> @@ -324,6 +324,7 @@ static void find_non_local_tags(const struct ref *refs,\n>  \n>  \trefname_hash_init(&existing_refs);\n>  \trefname_hash_init(&remote_refs);\n> +\tcreate_fetch_oidset(head, &fetch_oids);\n>  \n>  \tfor_each_ref(add_one_refname, &existing_refs);\n>  \tfor (ref = refs; ref; ref = ref->next) {\n> @@ -340,9 +341,9 @@ static void find_non_local_tags(const struct ref *refs,\n>  \t\t\tif (item &&\n>  \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n>  \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n> -\t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n> +\t\t\t    !oidset_contains(&fetch_oids, &ref->old_oid) &&\n>  \t\t\t    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&\n> -\t\t\t    !will_fetch(head, item->oid.hash))\n> +\t\t\t    !oidset_contains(&fetch_oids, &item->oid))\n>  \t\t\t\tclear_item(item);\n>  \t\t\titem = NULL;\n>  \t\t\tcontinue;\n> @@ -356,7 +357,7 @@ static void find_non_local_tags(const struct ref *refs,\n>  \t\t */\n>  \t\tif (item &&\n>  \t\t    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&\n> -\t\t    !will_fetch(head, item->oid.hash))\n> +\t\t    !oidset_contains(&fetch_oids, &item->oid))\n>  \t\t\tclear_item(item);\n>  \n>  \t\titem = NULL;\n> @@ -377,7 +378,7 @@ static void find_non_local_tags(const struct ref *refs,\n>  \t */\n>  \tif (item &&\n>  \t    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&\n> -\t    !will_fetch(head, item->oid.hash))\n> +\t    !oidset_contains(&fetch_oids, &item->oid))\n>  \t\tclear_item(item);\n>  \n>  \t/*\n> @@ -404,6 +405,7 @@ static void find_non_local_tags(const struct ref *refs,\n>  \t}\n>  \thashmap_free(&remote_refs, 1);\n>  \tstring_list_clear(&remote_refs_list, 0);\n> +\toidset_clear(&fetch_oids);\n>  }\n>  \n>  static struct ref *get_ref_map(struct remote *remote,\n> \n\n"},{"id":"382411","messageId":"CAJB1erWRt-v5jVCkmSx-aE_BwijKZ5aUTkXajvtB4RK0y+6uRA@mail.gmail.com","threadId":"51855","inReplyTo":"bbc3ef83-7ff9-deeb-2b7d-734112fc2418@gmail.com","subject":"Re: [PATCH 1/1] fetch: Cache the want OIDs for faster lookup","fromName":"Masaya Suzuki","fromEmail":"masayasuzuki@google.com","sentAt":"2019-09-16T04:28:37Z","receivedAt":"2019-09-16T04:28:51Z","isPatch":true,"sender":{"key":"masayasuzuki@google.com","avatar":"https://avatars.githubusercontent.com/u/21878?v=4"},"body":"On Sun, Sep 15, 2019 at 7:35 PM Derrick Stolee <stolee@gmail.com> wrote:\n>\n> On 9/15/2019 5:18 PM, Masaya Suzuki wrote:\n> > During git-fetch, the client checks if the advertised tags' OIDs are\n> > already in the fetch request's want OID set. This check is done in a\n> > linear scan. For a repository that has a lot of refs, repeating this\n> > scan takes 15+ minutes. In order to speed this up, create a oid_set for\n> > other refs' OIDs.\n>\n> Good catch! Quadratic performance is never good.\n>\n> The patch below looks like it works, but could you also share your\n> performance timings for the 15+ minute case after your patch is\n> applied?\n\nWith the following code change, I measured the time for\nfind_non_local_tags. It shows 215 msec with the example commands. (I\ndidn't measure entire fetch time as good portion of the time is spent\non the server side.)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 51a276dfaa..d3b06c733d 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -25,6 +25,7 @@\n #include \"list-objects-filter-options.h\"\n #include \"commit-reach.h\"\n #include \"branch.h\"\n+#include <time.h>\n\n #define FORCED_UPDATES_DELAY_WARNING_IN_MS (10 * 1000)\n\n@@ -322,8 +323,11 @@ static void find_non_local_tags(const struct ref *refs,\n        const struct ref *ref;\n        struct refname_hash_entry *item = NULL;\n\n+       struct timespec start, end;\n+\n        refname_hash_init(&existing_refs);\n        refname_hash_init(&remote_refs);\n+       clock_gettime(CLOCK_MONOTONIC, &start);\n        create_fetch_oidset(head, &fetch_oids);\n\n        for_each_ref(add_one_refname, &existing_refs);\n@@ -405,6 +409,12 @@ static void find_non_local_tags(const struct ref *refs,\n        }\n        hashmap_free(&remote_refs, 1);\n        string_list_clear(&remote_refs_list, 0);\n+       clock_gettime(CLOCK_MONOTONIC, &end);\n+       {\n+               uint64_t millisec = (end.tv_sec - start.tv_sec) * 1000\n+ (end.tv_nsec - start.tv_nsec) / 1000000;\n+               fprintf(stderr, \"find_non_local_tags: %ld msec\\n\", millisec);\n+       }\n+\n        oidset_clear(&fetch_oids);\n }\n"},{"id":"382412","messageId":"20190916043454.GA18026@sigill.intra.peff.net","threadId":"51855","inReplyTo":"20190915211802.207715-2-masayasuzuki@google.com","subject":"Re: [PATCH 1/1] fetch: Cache the want OIDs for faster lookup","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-09-16T04:34:55Z","receivedAt":"2019-09-16T04:34:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Sep 15, 2019 at 02:18:02PM -0700, Masaya Suzuki wrote:\n\n> During git-fetch, the client checks if the advertised tags' OIDs are\n> already in the fetch request's want OID set. This check is done in a\n> linear scan. For a repository that has a lot of refs, repeating this\n> scan takes 15+ minutes. In order to speed this up, create a oid_set for\n> other refs' OIDs.\n\nGood find. I was curious why nobody noticed it sooner, but I think a key\nelement in your chromium example is the use of \"--mirror\", which brings\nin a bunch of refs which would not normally be grabbed. There are only\nabout 17k heads and tags, but over 1.5M entries in refs/changes.\nQuadratically speaking, that's almost 8000 times worse, so your\n15-minute delay is only 1/10th of a second in the non-mirror case.\n\nMostly I was wondering if this might have been a recent regression. But\nit looks rather old:\n\n> -static int will_fetch(struct ref **head, const unsigned char *sha1)\n> +static void create_fetch_oidset(struct ref **head, struct oidset *out)\n>  {\n>  \tstruct ref *rm = *head;\n>  \twhile (rm) {\n> -\t\tif (hasheq(rm->old_oid.hash, sha1))\n> -\t\t\treturn 1;\n> +\t\toidset_insert(out, &rm->old_oid);\n>  \t\trm = rm->next;\n>  \t}\n> -\treturn 0;\n>  }\n\nThis function comes from cf7f929a10 (Teach git-fetch to grab a tag at\nthe same time as a commit, 2008-03-02). As explained in that commit\nmessage, this technique can't actually get all the tags we're looking\nfor. It was around the same time, in 348e390b17 (Teach\nfetch-pack/upload-pack about --include-tag, 2008-03-03), that we added\nan extension to do this reliably.\n\nSo it _might_ even be possible to get rid of this code entirely, if we\ndon't care about pre-2008 versions of Git (we'd still get the right\nanswer from them; it would just take an extra round-trip).\n\nThat said, it seems like a good idea to do this obvious and safe\nconversion in the near term, and we can look at removing it entirely as\na separate topic. The cost of the oidset isn't too bad (~30MB, I guess\neven for that pathological chromium case).\n\n> @@ -324,6 +324,7 @@ static void find_non_local_tags(const struct ref *refs,\n>  \n>  \trefname_hash_init(&existing_refs);\n>  \trefname_hash_init(&remote_refs);\n> +\tcreate_fetch_oidset(head, &fetch_oids);\n>  \n>  \tfor_each_ref(add_one_refname, &existing_refs);\n>  \tfor (ref = refs; ref; ref = ref->next) {\n> @@ -340,9 +341,9 @@ static void find_non_local_tags(const struct ref *refs,\n>  \t\t\tif (item &&\n>  \t\t\t    !has_object_file_with_flags(&ref->old_oid,\n>  \t\t\t\t\t\t\tOBJECT_INFO_QUICK) &&\n> -\t\t\t    !will_fetch(head, ref->old_oid.hash) &&\n> +\t\t\t    !oidset_contains(&fetch_oids, &ref->old_oid) &&\n>  \t\t\t    !has_object_file_with_flags(&item->oid, OBJECT_INFO_QUICK) &&\n> -\t\t\t    !will_fetch(head, item->oid.hash))\n> +\t\t\t    !oidset_contains(&fetch_oids, &item->oid))\n>  \t\t\t\tclear_item(item);\n>  \t\t\titem = NULL;\n>  \t\t\tcontinue;\n\nOne thing to check is whether the list we feed to will_fetch ever gets\nupdated in the loop that checks it (i.e., do we need to be adding or\nclearing elements in the oidset).\n\nI _think_ the answer is no, because we modify only the \"refs\" list in\nthat loop (via clear_item()), but the will_fetch() check is on the\nhead/tail we receive (which isn't updated until later). Both of those\nlists are passed into the function, but I didn't trace it all the way up\nto make sure they are not aliases.\n\n-Peff\n"},{"id":"382453","messageId":"xmqqr24g9fj7.fsf@gitster-ct.c.googlers.com","threadId":"51855","inReplyTo":"20190915211802.207715-1-masayasuzuki@google.com","subject":"Re: [PATCH 0/1] fetch: Cache the want OIDs for faster lookup","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-09-16T20:01:32Z","receivedAt":"2019-09-16T20:01:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Masaya Suzuki <masayasuzuki@google.com> writes:\n\n> Debugging this, it seems most of the time is spent on iterating the want refs to\n> see OIDs are included there. This patch speeds up this process by using oid_set.\n> Now the client can send a fetch request almost immediately.\n\nWonderful.  Thanks.\n"}]}