{"thread":{"id":"48005","subject":"[PATCH] fetch-pack.c: use oidset to check existence of loose object","startedAt":"2018-03-08T12:06:55Z","lastAt":"2018-03-14T06:33:29Z","messageCount":20,"participants":["Takuto Ikuta","René Scharfe","Junio C Hamano","Jonathan Tan"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"341282","messageId":"20180308120639.109438-1-tikuta@chromium.org","threadId":"48005","inReplyTo":null,"subject":"[PATCH] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-08T12:06:39Z","receivedAt":"2018-03-08T12:06:55Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"In repository having large number of refs, lstat for non-existing loose\nobjects makes `git fetch` slow.\n\nThis patch stores existing loose objects in hashmap beforehand and use\nit to check existence instead of using lstat.\n\nWith this patch, the number of lstat calls in `git fetch` is reduced\nfrom 411412 to 13794 for chromium repository.\n\nI took time stat of `git fetch` disabling quickfetch for chromium\nrepository 3 time on linux with SSD.\n* with this patch\n8.105s\n8.309s\n7.640s\navg: 8.018s\n\n* master\n12.287s\n11.175s\n12.227s\navg: 11.896s\n\nOn my MacBook Air which has slower lstat.\n* with this patch\n14.501s\n\n* master\n1m16.027s\n\n`git fetch` on slow disk will be improved largely.\n\nSigned-off-by: Takuto Ikuta <tikuta@chromium.org>\n---\n cache.h      |  2 ++\n fetch-pack.c | 22 +++++++++++++++++++---\n sha1_file.c  |  3 +++\n 3 files changed, 24 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d06932ed0..db38db40e 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1773,6 +1773,8 @@ struct object_info {\n #define OBJECT_INFO_SKIP_CACHED 4\n /* Do not retry packed storage after checking packed and loose storage */\n #define OBJECT_INFO_QUICK 8\n+/* Do not check loose object */\n+#define OBJECT_INFO_SKIP_LOOSE 16\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n \n /*\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex d97461296..1658487f7 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -711,6 +711,15 @@ static void mark_alternate_complete(struct object *obj)\n \tmark_complete(&obj->oid);\n }\n \n+static int add_loose_objects_to_set(const struct object_id *oid,\n+\t\t\t\t    const char *path,\n+\t\t\t\t    void *data)\n+{\n+\tstruct oidset* set = (struct oidset*)(data);\n+\toidset_insert(set, oid);\n+\treturn 0;\n+}\n+\n static int everything_local(struct fetch_pack_args *args,\n \t\t\t    struct ref **refs,\n \t\t\t    struct ref **sought, int nr_sought)\n@@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args *args,\n \tint retval;\n \tint old_save_commit_buffer = save_commit_buffer;\n \ttimestamp_t cutoff = 0;\n+\tstruct oidset loose_oid_set = OIDSET_INIT;\n+\n+\tfor_each_loose_object(add_loose_objects_to_set, &loose_oid_set, 0);\n \n \tsave_commit_buffer = 0;\n \n \tfor (ref = *refs; ref; ref = ref->next) {\n \t\tstruct object *o;\n+\t\tunsigned int flag = OBJECT_INFO_QUICK;\n \n-\t\tif (!has_object_file_with_flags(&ref->old_oid,\n-\t\t\t\t\t\tOBJECT_INFO_QUICK))\n-\t\t\tcontinue;\n+\t\tif (!oidset_contains(&loose_oid_set, &ref->old_oid))\n+\t\t\tflag |= OBJECT_INFO_SKIP_LOOSE;\n \n+\t\tif (!has_object_file_with_flags(&ref->old_oid, flag))\n+\t\t\tcontinue;\n \t\to = parse_object(&ref->old_oid);\n \t\tif (!o)\n \t\t\tcontinue;\n@@ -744,6 +758,8 @@ static int everything_local(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\toidset_clear(&loose_oid_set);\n+\n \tif (!args->no_dependents) {\n \t\tif (!args->deepen) {\n \t\t\tfor_each_ref(mark_complete_oid, NULL);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1b94f39c4..c903cbcec 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n \t\tif (find_pack_entry(real, &e))\n \t\t\tbreak;\n \n+\t\tif (flags & OBJECT_INFO_SKIP_LOOSE)\n+\t\t\treturn -1;\n+\n \t\t/* Most likely it's a loose object. */\n \t\tif (!sha1_loose_object_info(real, oi, flags))\n \t\t\treturn 0;\n-- \n2.16.2\n\n"},{"id":"341301","messageId":"c97772f1-dc36-3f2c-b328-6d8bd480ff79@web.de","threadId":"48005","inReplyTo":"20180308120639.109438-1-tikuta@chromium.org","subject":"Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-03-08T17:19:50Z","receivedAt":"2018-03-08T17:20:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 08.03.2018 um 13:06 schrieb Takuto Ikuta:\n> In repository having large number of refs, lstat for non-existing loose\n> objects makes `git fetch` slow.\n> \n> This patch stores existing loose objects in hashmap beforehand and use\n> it to check existence instead of using lstat.\n> \n> With this patch, the number of lstat calls in `git fetch` is reduced\n> from 411412 to 13794 for chromium repository.\n> \n> I took time stat of `git fetch` disabling quickfetch for chromium\n> repository 3 time on linux with SSD.\n> * with this patch\n> 8.105s\n> 8.309s\n> 7.640s\n> avg: 8.018s\n> \n> * master\n> 12.287s\n> 11.175s\n> 12.227s\n> avg: 11.896s\n> \n> On my MacBook Air which has slower lstat.\n> * with this patch\n> 14.501s\n> \n> * master\n> 1m16.027s\n\nNice improvement!\n\n> \n> `git fetch` on slow disk will be improved largely.\n> \n> Signed-off-by: Takuto Ikuta <tikuta@chromium.org>\n> ---\n>   cache.h      |  2 ++\n>   fetch-pack.c | 22 +++++++++++++++++++---\n>   sha1_file.c  |  3 +++\n>   3 files changed, 24 insertions(+), 3 deletions(-)\n> \n> diff --git a/cache.h b/cache.h\n> index d06932ed0..db38db40e 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -1773,6 +1773,8 @@ struct object_info {\n>   #define OBJECT_INFO_SKIP_CACHED 4\n>   /* Do not retry packed storage after checking packed and loose storage */\n>   #define OBJECT_INFO_QUICK 8\n> +/* Do not check loose object */\n> +#define OBJECT_INFO_SKIP_LOOSE 16\n>   extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n>   \n>   /*\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index d97461296..1658487f7 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -711,6 +711,15 @@ static void mark_alternate_complete(struct object *obj)\n>   \tmark_complete(&obj->oid);\n>   }\n>   \n> +static int add_loose_objects_to_set(const struct object_id *oid,\n> +\t\t\t\t    const char *path,\n> +\t\t\t\t    void *data)\n> +{\n> +\tstruct oidset* set = (struct oidset*)(data);\n\nThis cast is not needed (unlike in C++).  And the asterisk should be stuck\nto the variable, not the type (see Documentation/CodingGuidelines).\n\n> +\toidset_insert(set, oid);\n\nIn fact, you could just put \"data\" in here instead of \"set\" (without a\ncast), with no loss in readability or safety.\n\n> +\treturn 0;\n> +}\n> +\n>   static int everything_local(struct fetch_pack_args *args,\n>   \t\t\t    struct ref **refs,\n>   \t\t\t    struct ref **sought, int nr_sought)\n> @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args *args,\n>   \tint retval;\n>   \tint old_save_commit_buffer = save_commit_buffer;\n>   \ttimestamp_t cutoff = 0;\n> +\tstruct oidset loose_oid_set = OIDSET_INIT;\n> +\n> +\tfor_each_loose_object(add_loose_objects_to_set, &loose_oid_set, 0);\n>   \n>   \tsave_commit_buffer = 0;\n>   \n>   \tfor (ref = *refs; ref; ref = ref->next) {\n>   \t\tstruct object *o;\n> +\t\tunsigned int flag = OBJECT_INFO_QUICK;\n>   \n> -\t\tif (!has_object_file_with_flags(&ref->old_oid,\n> -\t\t\t\t\t\tOBJECT_INFO_QUICK))\n> -\t\t\tcontinue;\n> +\t\tif (!oidset_contains(&loose_oid_set, &ref->old_oid))\n> +\t\t\tflag |= OBJECT_INFO_SKIP_LOOSE;\n>   \n> +\t\tif (!has_object_file_with_flags(&ref->old_oid, flag))\n> +\t\t\tcontinue;\n>   \t\to = parse_object(&ref->old_oid);\n>   \t\tif (!o)\n>   \t\t\tcontinue;\n> @@ -744,6 +758,8 @@ static int everything_local(struct fetch_pack_args *args,\n>   \t\t}\n>   \t}\n>   \n> +\toidset_clear(&loose_oid_set);\n> +\n\nThis part looks fine to me.  (Except perhaps call the variable \"flags\"\nbecause you sometimes have two?)\n\nWhy not include packed objects as well?  Probably because packs have\nindexes which can queried quickly to determine object existence, and\nbecause there are only few loose objects in typical repositories,\nright?\n\nA similar cache was introduced by cc817ca3ef (sha1_name: cache\nreaddir(3) results in find_short_object_filename()) to speed up\nfinding unambiguous shorts object hashes.  I wonder if it could be\nused here as well, but I don't see an easy way.\n\n>   \tif (!args->no_dependents) {\n>   \t\tif (!args->deepen) {\n>   \t\t\tfor_each_ref(mark_complete_oid, NULL);\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 1b94f39c4..c903cbcec 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n>   \t\tif (find_pack_entry(real, &e))\n>   \t\t\tbreak;\n>   \n> +\t\tif (flags & OBJECT_INFO_SKIP_LOOSE)\n> +\t\t\treturn -1;\n> +\n>   \t\t/* Most likely it's a loose object. */\n>   \t\tif (!sha1_loose_object_info(real, oi, flags))\n>   \t\t\treturn 0;\n> \n\nThis early return doesn't just skip checking loose objects.  It\nalso skips reloading packs and fetching missing objects for\npartial clones.  That may not be a problem for fetch-pack, but\nit means the flag has a misleading name.  Do you get the same\nperformance improvement if you make it only skip that\nsha1_loose_object_info() call?\n\nRené\n"},{"id":"341306","messageId":"xmqqr2ouwgsd.fsf@gitster-ct.c.googlers.com","threadId":"48005","inReplyTo":"20180308120639.109438-1-tikuta@chromium.org","subject":"Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-08T18:42:10Z","receivedAt":"2018-03-08T18:42:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Takuto Ikuta <tikuta@chromium.org> writes:\n\n> In repository having large number of refs, lstat for non-existing loose\n> objects makes `git fetch` slow.\n\nIt is not immediately clear how \"large number of refs\" and \"lstat\nfor loose objects\" interact with each other to create a problem.\n\"In repository having large number of refs, because such and such\nprocessing needs to do this and that, 'git fetch' ends up doing a\nlot of lstat(2) calls to see if many objects exist in the loose\nform, which makes it slow\".  Please fill in the blanks.\n\n> This patch stores existing loose objects in hashmap beforehand and use\n> it to check existence instead of using lstat.\n>\n> With this patch, the number of lstat calls in `git fetch` is reduced\n> from 411412 to 13794 for chromium repository.\n>\n> I took time stat of `git fetch` disabling quickfetch for chromium\n> repository 3 time on linux with SSD.\n\nNow you drop a clue that would help to fill in the blanks above, but\nI am not sure what the significance of your having to disable\nquickfetch in order to take measurements---it makes it sound as if\nit is an articificial problem that does not exist in real life\n(i.e. when quickfetch is not disabled), but I am getting the feeling\nthat it is not what you wanted to say here.\n\nIn any case, do_fetch_pack() tries to see if all of the tip commits\nwe are going to fetch exist locally, so when you are trying a fetch\nthat grabs huge number of refs (by the way, it means that the first\nsentence of the proposed log message is not quite true---it is \"When\nfetching a large number of refs\", as it does not matter how many\nrefs _we_ have, no?), everything_local() ends up making repeated\ncalls to has_object_file_with_flags() to all of the refs.\n\nI like the idea---this turns \"for each of these many things, check\nif it exists with lstat(2)\" into \"enumerate what exists with\nlstat(2), and then use that for the existence test\"; if you need to\ntry N objects for existence, and you only have M objects loose where\nN is vastly larger than M, it will be a huge win.  If you have very\nmany loose objects and checking only a handful of objects for\nexistence check, you would lose big, though, no?\n\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index d97461296..1658487f7 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -711,6 +711,15 @@ static void mark_alternate_complete(struct object *obj)\n>  \tmark_complete(&obj->oid);\n>  }\n>  \n> +static int add_loose_objects_to_set(const struct object_id *oid,\n> +\t\t\t\t    const char *path,\n> +\t\t\t\t    void *data)\n> +{\n> +\tstruct oidset* set = (struct oidset*)(data);\n\nStyle: in our codebase, asterisk does not stick to the type.\n\n\tstruct oidset *set = (struct oidset *)(data);\n\n> @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args *args,\n>  \tint retval;\n>  \tint old_save_commit_buffer = save_commit_buffer;\n>  \ttimestamp_t cutoff = 0;\n> +\tstruct oidset loose_oid_set = OIDSET_INIT;\n> +\n> +\tfor_each_loose_object(add_loose_objects_to_set, &loose_oid_set, 0);\n\nOK, so this is the \"enumerate all loose objects\" phase.\n\n>  \tsave_commit_buffer = 0;\n>  \n>  \tfor (ref = *refs; ref; ref = ref->next) {\n>  \t\tstruct object *o;\n> +\t\tunsigned int flag = OBJECT_INFO_QUICK;\n\nHmm, OBJECT_INFO_QUICK optimization was added in dfdd4afc\n(\"sha1_file: teach sha1_object_info_extended more flags\",\n2017-06-21), but since 8b4c0103 (\"sha1_file: support lazily fetching\nmissing objects\", 2017-12-08) it appears that passing\nOBJECT_INFO_QUICK down the codepath does not do anything\ninteresting.  Jonathan (cc'ed), are all remaining hits from \"git\ngrep OBJECT_INFO_QUICK\" all dead no-ops these days?\n\n>  \n> -\t\tif (!has_object_file_with_flags(&ref->old_oid,\n> -\t\t\t\t\t\tOBJECT_INFO_QUICK))\n> -\t\t\tcontinue;\n> +\t\tif (!oidset_contains(&loose_oid_set, &ref->old_oid))\n> +\t\t\tflag |= OBJECT_INFO_SKIP_LOOSE;\n>  \n> +\t\tif (!has_object_file_with_flags(&ref->old_oid, flag))\n> +\t\t\tcontinue;\n\nHere, you want a way to say \"I know this does not exist in the loose\nform, so check if it exists in a non-loose form\", and that is why\nyou invented the new flag.\n\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 1b94f39c4..c903cbcec 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n>  \t\tif (find_pack_entry(real, &e))\n>  \t\t\tbreak;\n>  \n> +\t\tif (flags & OBJECT_INFO_SKIP_LOOSE)\n> +\t\t\treturn -1;\n> +\n\nI cannot quite convince myself that this is done at the right layer;\nit smells to be at a bit too low a layer.  This change makes sense\nonly to a caller that is interested in the existence test.  If the\nflag is named after what it does, i.e. \"ignore loose object\", then\nit does sort-of make sense, though.\n\n>  \t\t/* Most likely it's a loose object. */\n>  \t\tif (!sha1_loose_object_info(real, oi, flags))\n>  \t\t\treturn 0;\n"},{"id":"341337","messageId":"20180309131136.219303-1-tikuta@chromium.org","threadId":"48005","inReplyTo":"xmqqr2ouwgsd.fsf@gitster-ct.c.googlers.com","subject":"[PATCH v2 0/1] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-09T13:11:35Z","receivedAt":"2018-03-09T13:13:56Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"I removed unnecessary type cast, added comment in everthing_local(...),\nchanged flag name and updated description.\n\nTakuto Ikuta (1):\n  fetch-pack.c: use oidset to check existence of loose object\n\n cache.h      |  2 ++\n fetch-pack.c | 26 +++++++++++++++++++++++---\n sha1_file.c  |  3 +++\n 3 files changed, 28 insertions(+), 3 deletions(-)\n\n--\n2.16.2\n"},{"id":"341338","messageId":"20180309131136.219303-2-tikuta@chromium.org","threadId":"48005","inReplyTo":"20180309131136.219303-1-tikuta@chromium.org","subject":"[PATCH v2 1/1] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-09T13:11:36Z","receivedAt":"2018-03-09T13:14:17Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"In repository having large number of remote refs, because to check\nexistence of each refs in local repository, 'git fetch' ends up doing a\nlot of lstat(2) calls to see if it exists in loose form, which makes it\nslow.\n\nThis patch enumerates loose objects in hashmap beforehand and uses it to\ncheck existence instead of using lstat(2) to improve performance of\nfetch-pack for repositories having large number of remote refs compared\nto the number of loose objects.\n\nWith this patch, the number of lstat(2) calls in `git fetch` is reduced\nfrom 411412 to 13794 for chromium repository, it has more than 480000\nremote refs.\n\nI took time stat of `git fetch` disabling quickfetch, so that fetch-pack\nruns, for chromium repository 3 time on linux with SSD.\n* with this patch\n8.105s\n8.309s\n7.640s\navg: 8.018s\n\n* master\n12.287s\n11.175s\n12.227s\navg: 11.896s\n\nOn my MacBook Air which has slower lstat(2).\n* with this patch\n14.501s\n\n* master\n1m16.027s\n\n`git fetch` on slow disk will be improved largely.\n\nSigned-off-by: Takuto Ikuta <tikuta@chromium.org>\n---\n cache.h      |  2 ++\n fetch-pack.c | 26 +++++++++++++++++++++++---\n sha1_file.c  |  3 +++\n 3 files changed, 28 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d06932ed0..6a72f54d7 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1773,6 +1773,8 @@ struct object_info {\n #define OBJECT_INFO_SKIP_CACHED 4\n /* Do not retry packed storage after checking packed and loose storage */\n #define OBJECT_INFO_QUICK 8\n+/* Do not check loose object */\n+#define OBJECT_INFO_IGNORE_LOOSE 16\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n \n /*\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex d97461296..ef8b93424 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -711,6 +711,14 @@ static void mark_alternate_complete(struct object *obj)\n \tmark_complete(&obj->oid);\n }\n \n+static int add_loose_objects_to_set(const struct object_id *oid,\n+\t\t\t\t    const char *path,\n+\t\t\t\t    void *data)\n+{\n+\toidset_insert(data, oid);\n+\treturn 0;\n+}\n+\n static int everything_local(struct fetch_pack_args *args,\n \t\t\t    struct ref **refs,\n \t\t\t    struct ref **sought, int nr_sought)\n@@ -719,16 +727,26 @@ static int everything_local(struct fetch_pack_args *args,\n \tint retval;\n \tint old_save_commit_buffer = save_commit_buffer;\n \ttimestamp_t cutoff = 0;\n+\tstruct oidset loose_oid_set = OIDSET_INIT;\n+\n+\t/* Enumerate all loose objects. */\n+\tfor_each_loose_object(add_loose_objects_to_set, &loose_oid_set, 0);\n \n \tsave_commit_buffer = 0;\n \n \tfor (ref = *refs; ref; ref = ref->next) {\n \t\tstruct object *o;\n+\t\tunsigned int flag = OBJECT_INFO_QUICK;\n \n-\t\tif (!has_object_file_with_flags(&ref->old_oid,\n-\t\t\t\t\t\tOBJECT_INFO_QUICK))\n-\t\t\tcontinue;\n+\t\tif (!oidset_contains(&loose_oid_set, &ref->old_oid)) {\n+\t\t\t/* I know this does not exist in the loose form,\n+\t\t\t * so check if it exists in a non-loose form.\n+\t\t\t */\n+\t\t\tflag |= OBJECT_INFO_IGNORE_LOOSE;\n+\t\t}\n \n+\t\tif (!has_object_file_with_flags(&ref->old_oid, flag))\n+\t\t\tcontinue;\n \t\to = parse_object(&ref->old_oid);\n \t\tif (!o)\n \t\t\tcontinue;\n@@ -744,6 +762,8 @@ static int everything_local(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\toidset_clear(&loose_oid_set);\n+\n \tif (!args->no_dependents) {\n \t\tif (!args->deepen) {\n \t\t\tfor_each_ref(mark_complete_oid, NULL);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1b94f39c4..c0a197947 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n \t\tif (find_pack_entry(real, &e))\n \t\t\tbreak;\n \n+\t\tif (flags & OBJECT_INFO_IGNORE_LOOSE)\n+\t\t\treturn -1;\n+\n \t\t/* Most likely it's a loose object. */\n \t\tif (!sha1_loose_object_info(real, oi, flags))\n \t\t\treturn 0;\n-- \n2.16.2\n\n"},{"id":"341340","messageId":"20180309132655.224308-1-tikuta@chromium.org","threadId":"48005","inReplyTo":"20180309131136.219303-2-tikuta@chromium.org","subject":"[PATCH v3] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-09T13:26:55Z","receivedAt":"2018-03-09T13:27:31Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"In repository having large number of remote refs, because to check\nexistence of each refs in local repository, 'git fetch' ends up doing a\nlot of lstat(2) calls to see if it exists in loose form, which makes it\nslow.\n\nThis patch enumerates loose objects in hashmap beforehand and uses it to\ncheck existence instead of using lstat(2) to improve performance of\nfetch-pack for repositories having large number of remote refs compared\nto the number of loose objects.\n\nWith this patch, the number of lstat(2) calls in `git fetch` is reduced\nfrom 411412 to 13794 for chromium repository, it has more than 480000\nremote refs.\n\nI took time stat of `git fetch` disabling quickfetch, so that fetch-pack\nruns, for chromium repository 3 time on linux with SSD.\n* with this patch\n8.105s\n8.309s\n7.640s\navg: 8.018s\n\n* master\n12.287s\n11.175s\n12.227s\navg: 11.896s\n\nOn my MacBook Air which has slower lstat(2).\n* with this patch\n14.501s\n\n* master\n1m16.027s\n\n`git fetch` on slow disk will be improved largely.\n\nSigned-off-by: Takuto Ikuta <tikuta@chromium.org>\n---\n cache.h      |  2 ++\n fetch-pack.c | 26 +++++++++++++++++++++++---\n sha1_file.c  |  3 +++\n 3 files changed, 28 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d06932ed0..6a72f54d7 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1773,6 +1773,8 @@ struct object_info {\n #define OBJECT_INFO_SKIP_CACHED 4\n /* Do not retry packed storage after checking packed and loose storage */\n #define OBJECT_INFO_QUICK 8\n+/* Do not check loose object */\n+#define OBJECT_INFO_IGNORE_LOOSE 16\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n \n /*\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex d97461296..aed4aa213 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -711,6 +711,14 @@ static void mark_alternate_complete(struct object *obj)\n \tmark_complete(&obj->oid);\n }\n \n+static int add_loose_objects_to_set(const struct object_id *oid,\n+\t\t\t\t    const char *path,\n+\t\t\t\t    void *data)\n+{\n+\toidset_insert(data, oid);\n+\treturn 0;\n+}\n+\n static int everything_local(struct fetch_pack_args *args,\n \t\t\t    struct ref **refs,\n \t\t\t    struct ref **sought, int nr_sought)\n@@ -719,16 +727,26 @@ static int everything_local(struct fetch_pack_args *args,\n \tint retval;\n \tint old_save_commit_buffer = save_commit_buffer;\n \ttimestamp_t cutoff = 0;\n+\tstruct oidset loose_oid_set = OIDSET_INIT;\n+\n+\t/* Enumerate all loose objects. */\n+\tfor_each_loose_object(add_loose_objects_to_set, &loose_oid_set, 0);\n \n \tsave_commit_buffer = 0;\n \n \tfor (ref = *refs; ref; ref = ref->next) {\n \t\tstruct object *o;\n+\t\tunsigned int flags = OBJECT_INFO_QUICK;\n \n-\t\tif (!has_object_file_with_flags(&ref->old_oid,\n-\t\t\t\t\t\tOBJECT_INFO_QUICK))\n-\t\t\tcontinue;\n+\t\tif (!oidset_contains(&loose_oid_set, &ref->old_oid)) {\n+\t\t\t/* I know this does not exist in the loose form,\n+\t\t\t * so check if it exists in a non-loose form.\n+\t\t\t */\n+\t\t\tflags |= OBJECT_INFO_IGNORE_LOOSE;\n+\t\t}\n \n+\t\tif (!has_object_file_with_flags(&ref->old_oid, flags))\n+\t\t\tcontinue;\n \t\to = parse_object(&ref->old_oid);\n \t\tif (!o)\n \t\t\tcontinue;\n@@ -744,6 +762,8 @@ static int everything_local(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\toidset_clear(&loose_oid_set);\n+\n \tif (!args->no_dependents) {\n \t\tif (!args->deepen) {\n \t\t\tfor_each_ref(mark_complete_oid, NULL);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1b94f39c4..c0a197947 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n \t\tif (find_pack_entry(real, &e))\n \t\t\tbreak;\n \n+\t\tif (flags & OBJECT_INFO_IGNORE_LOOSE)\n+\t\t\treturn -1;\n+\n \t\t/* Most likely it's a loose object. */\n \t\tif (!sha1_loose_object_info(real, oi, flags))\n \t\t\treturn 0;\n-- \n2.16.2\n\n"},{"id":"341341","messageId":"CALNjmMofu9yupivCo7gHmOTVoFurgyp9CfR1uD-=cLWzq1hVtA@mail.gmail.com","threadId":"48005","inReplyTo":"c97772f1-dc36-3f2c-b328-6d8bd480ff79@web.de","subject":"Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-09T13:42:03Z","receivedAt":"2018-03-09T13:42:52Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"2018-03-09 2:19 GMT+09:00 René Scharfe <l.s.r@web.de>:\n> Am 08.03.2018 um 13:06 schrieb Takuto Ikuta:\n>> +static int add_loose_objects_to_set(const struct object_id *oid,\n>> +                                 const char *path,\n>> +                                 void *data)\n>> +{\n>> +     struct oidset* set = (struct oidset*)(data);\n>\n> This cast is not needed (unlike in C++).  And the asterisk should be stuck\n> to the variable, not the type (see Documentation/CodingGuidelines).\n>\n>> +     oidset_insert(set, oid);\n>\n> In fact, you could just put \"data\" in here instead of \"set\" (without a\n> cast), with no loss in readability or safety.\n>\n\nThank you for review, changed to use data directly in v2.\n\n>> +     return 0;\n>> +}\n>> +\n>>   static int everything_local(struct fetch_pack_args *args,\n>>                           struct ref **refs,\n>>                           struct ref **sought, int nr_sought)\n>> @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args *args,\n>>       int retval;\n>>       int old_save_commit_buffer = save_commit_buffer;\n>>       timestamp_t cutoff = 0;\n>> +     struct oidset loose_oid_set = OIDSET_INIT;\n>> +\n>> +     for_each_loose_object(add_loose_objects_to_set, &loose_oid_set, 0);\n>>\n>>       save_commit_buffer = 0;\n>>\n>>       for (ref = *refs; ref; ref = ref->next) {\n>>               struct object *o;\n>> +             unsigned int flag = OBJECT_INFO_QUICK;\n>>\n>> -             if (!has_object_file_with_flags(&ref->old_oid,\n>> -                                             OBJECT_INFO_QUICK))\n>> -                     continue;\n>> +             if (!oidset_contains(&loose_oid_set, &ref->old_oid))\n>> +                     flag |= OBJECT_INFO_SKIP_LOOSE;\n>>\n>> +             if (!has_object_file_with_flags(&ref->old_oid, flag))\n>> +                     continue;\n>>               o = parse_object(&ref->old_oid);\n>>               if (!o)\n>>                       continue;\n>> @@ -744,6 +758,8 @@ static int everything_local(struct fetch_pack_args *args,\n>>               }\n>>       }\n>>\n>> +     oidset_clear(&loose_oid_set);\n>> +\n>\n> This part looks fine to me.  (Except perhaps call the variable \"flags\"\n> because you sometimes have two?)\n>\n\nChanged flag names.\n\n> Why not include packed objects as well?  Probably because packs have\n> indexes which can queried quickly to determine object existence, and\n> because there are only few loose objects in typical repositories,\n> right?\n>\n\nCorrect. In my target repository, chromium, fetch-pack's slowness\ncomes from many lstat\nto non-existing loose objects for remote refs. I focus on to remove such lstat.\n\n> A similar cache was introduced by cc817ca3ef (sha1_name: cache\n> readdir(3) results in find_short_object_filename()) to speed up\n> finding unambiguous shorts object hashes.  I wonder if it could be\n> used here as well, but I don't see an easy way.\n>\n>>       if (!args->no_dependents) {\n>>               if (!args->deepen) {\n>>                       for_each_ref(mark_complete_oid, NULL);\n>> diff --git a/sha1_file.c b/sha1_file.c\n>> index 1b94f39c4..c903cbcec 100644\n>> --- a/sha1_file.c\n>> +++ b/sha1_file.c\n>> @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n>>               if (find_pack_entry(real, &e))\n>>                       break;\n>>\n>> +             if (flags & OBJECT_INFO_SKIP_LOOSE)\n>> +                     return -1;\n>> +\n>>               /* Most likely it's a loose object. */\n>>               if (!sha1_loose_object_info(real, oi, flags))\n>>                       return 0;\n>>\n>\n> This early return doesn't just skip checking loose objects.  It\n> also skips reloading packs and fetching missing objects for\n> partial clones.  That may not be a problem for fetch-pack, but\n> it means the flag has a misleading name.  Do you get the same\n> performance improvement if you make it only skip that\n> sha1_loose_object_info() call?\n>\n\nI changed the flag name following Junio's suggestion. If we skip\nsha1_loose_object_info call,\nreprepare_packed_git(...) runs for every non-existing refs and git\nfetch becomes slower.\n\nTakuto\n"},{"id":"341342","messageId":"CALNjmMq9gvRzkoYCfXppTVTR5UtvmBZ_4hVuBLB0t7YzR36Wbg@mail.gmail.com","threadId":"48005","inReplyTo":"xmqqr2ouwgsd.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-09T14:12:06Z","receivedAt":"2018-03-09T14:12:56Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"2018-03-09 3:42 GMT+09:00 Junio C Hamano <gitster@pobox.com>:\n> Takuto Ikuta <tikuta@chromium.org> writes:\n>> This patch stores existing loose objects in hashmap beforehand and use\n>> it to check existence instead of using lstat.\n>>\n>> With this patch, the number of lstat calls in `git fetch` is reduced\n>> from 411412 to 13794 for chromium repository.\n>>\n>> I took time stat of `git fetch` disabling quickfetch for chromium\n>> repository 3 time on linux with SSD.\n>\n> Now you drop a clue that would help to fill in the blanks above, but\n> I am not sure what the significance of your having to disable\n> quickfetch in order to take measurements---it makes it sound as if\n> it is an articificial problem that does not exist in real life\n> (i.e. when quickfetch is not disabled), but I am getting the feeling\n> that it is not what you wanted to say here.\n>\n\nYes, I just wanted to say 'git fetch' invokes fetch-pack.\nfetch-pack is skipped when running git fetch repeatedly while\nremote has no update by quickfetch. So I disabled it to see the\nperformance of fetch-pack. In chromium repository, master branch\nis updated several times in an hour, so git fetch invokes fetch-pack\nin such frequency.\n\n> In any case, do_fetch_pack() tries to see if all of the tip commits\n> we are going to fetch exist locally, so when you are trying a fetch\n> that grabs huge number of refs (by the way, it means that the first\n> sentence of the proposed log message is not quite true---it is \"When\n> fetching a large number of refs\", as it does not matter how many\n> refs _we_ have, no?), everything_local() ends up making repeated\n> calls to has_object_file_with_flags() to all of the refs.\n>\n\nI fixed description by changing 'refs' to 'remote refs'. In my understanding,\ngit tries to check existence of remote refs even if we won't fetch such refs.\n\n> I like the idea---this turns \"for each of these many things, check\n> if it exists with lstat(2)\" into \"enumerate what exists with\n> lstat(2), and then use that for the existence test\"; if you need to\n> try N objects for existence, and you only have M objects loose where\n> N is vastly larger than M, it will be a huge win.  If you have very\n> many loose objects and checking only a handful of objects for\n> existence check, you would lose big, though, no?\n>\n\nYes. But I think the default limit for the number of loose objects, 7000,\ngives us small overhead when we do enumeration of all objects.\n\n>> diff --git a/fetch-pack.c b/fetch-pack.c\n>> index d97461296..1658487f7 100644\n>> --- a/fetch-pack.c\n>> +++ b/fetch-pack.c\n>> @@ -711,6 +711,15 @@ static void mark_alternate_complete(struct object *obj)\n>>       mark_complete(&obj->oid);\n>>  }\n>>\n>> +static int add_loose_objects_to_set(const struct object_id *oid,\n>> +                                 const char *path,\n>> +                                 void *data)\n>> +{\n>> +     struct oidset* set = (struct oidset*)(data);\n>\n> Style: in our codebase, asterisk does not stick to the type.\n>\n>         struct oidset *set = (struct oidset *)(data);\n>\n>> @@ -719,16 +728,21 @@ static int everything_local(struct fetch_pack_args *args,\n>>       int retval;\n>>       int old_save_commit_buffer = save_commit_buffer;\n>>       timestamp_t cutoff = 0;\n>> +     struct oidset loose_oid_set = OIDSET_INIT;\n>> +\n>> +     for_each_loose_object(add_loose_objects_to_set, &loose_oid_set, 0);\n>\n> OK, so this is the \"enumerate all loose objects\" phase.\n>\n>>       save_commit_buffer = 0;\n>>\n>>       for (ref = *refs; ref; ref = ref->next) {\n>>               struct object *o;\n>> +             unsigned int flag = OBJECT_INFO_QUICK;\n>\n> Hmm, OBJECT_INFO_QUICK optimization was added in dfdd4afc\n> (\"sha1_file: teach sha1_object_info_extended more flags\",\n> 2017-06-21), but since 8b4c0103 (\"sha1_file: support lazily fetching\n> missing objects\", 2017-12-08) it appears that passing\n> OBJECT_INFO_QUICK down the codepath does not do anything\n> interesting.  Jonathan (cc'ed), are all remaining hits from \"git\n> grep OBJECT_INFO_QUICK\" all dead no-ops these days?\n>\n\nYes the flag is no-op now, but let me untouched the flag in this patch.\n\n>> diff --git a/sha1_file.c b/sha1_file.c\n>> index 1b94f39c4..c903cbcec 100644\n>> --- a/sha1_file.c\n>> +++ b/sha1_file.c\n>> @@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n>>               if (find_pack_entry(real, &e))\n>>                       break;\n>>\n>> +             if (flags & OBJECT_INFO_SKIP_LOOSE)\n>> +                     return -1;\n>> +\n>\n> I cannot quite convince myself that this is done at the right layer;\n> it smells to be at a bit too low a layer.  This change makes sense\n> only to a caller that is interested in the existence test.  If the\n> flag is named after what it does, i.e. \"ignore loose object\", then\n> it does sort-of make sense, though.\n>\n\nCouldn't come up with good alternative for this, I followed your\nflag name suggestion in patch v3.\n\nTakuto\n"},{"id":"341362","messageId":"xmqqd10d6ser.fsf@gitster-ct.c.googlers.com","threadId":"48005","inReplyTo":"CALNjmMq9gvRzkoYCfXppTVTR5UtvmBZ_4hVuBLB0t7YzR36Wbg@mail.gmail.com","subject":"Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-09T18:00:12Z","receivedAt":"2018-03-09T18:00:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Takuto Ikuta <tikuta@chromium.org> writes:\n\n> Yes, I just wanted to say 'git fetch' invokes fetch-pack.\n> fetch-pack is skipped when running git fetch repeatedly while\n> remote has no update by quickfetch. So I disabled it to see the\n> performance of fetch-pack. In chromium repository, master branch\n> is updated several times in an hour, so git fetch invokes fetch-pack\n> in such frequency.\n\nI do understand that if you run \"git fetch\" against the same place\nin quick succession three times, the first one may cost a lot (not\njust that it has to do the everything_local() computation that you\ncare about, it also has to actually do the network transfer), while\nthe second and third ones that are done before anything new happens\non the other end will not involve everything_local() overhead thanks\nto quickfetch.\n\nA \"fetch\" that is run against a remote that has nothing new, but\nstill triggers everything_local() only because quickfetch is\ndisabled, is an artificial case that has no relevance to the real\nworld, I suspect, because the quickfetch optimization is to solve\nthe \"there is nothing to be done, still do_fetch_pack() spends so\nmuch cycles only to realize that it does not have anything to do,\nwhy?\" issue.\n\nIsn't running the \"git fetch\" command with the \"--dry-run\" option\nmany times in quick succession a lot closer to what you really want\nto measure, I wonder?  That way, your first fetch won't be touching\nthe state of the local side to affect your second and subsequent\nfetches.\n\n>> In any case, do_fetch_pack() tries to see if all of the tip commits\n>> we are going to fetch exist locally, so when you are trying a fetch\n>> that grabs huge number of refs (by the way, it means that the first\n>> sentence of the proposed log message is not quite true---it is \"When\n>> fetching a large number of refs\", as it does not matter how many\n>> refs _we_ have, no?), everything_local() ends up making repeated\n>> calls to has_object_file_with_flags() to all of the refs.\n>\n> I fixed description by changing 'refs' to 'remote refs'. In my understanding,\n> git tries to check existence of remote refs even if we won't fetch such refs.\n\nDuring fetch, everything_local() tries to mark common part by\nwalking the refs the other side advertised upon the first contact,\nso it is correct that the number of checks is not reduced in a fetch\nthat does not fetch many refs, but the number of remote-tracking refs\nyou have has no effect, so I doubt such a rephrasing would make the\ndescription more understandable.  \"When fetching from a repository\nwith large number of refs\" is probably what you want to say, no?\n\n> Yes. But I think the default limit for the number of loose objects, 7000,\n> gives us small overhead when we do enumeration of all objects.\n\nHmph, I didn't see the code that does the estimation of loose object\ncount before starting to enumerate, though.\n\n>> Hmm, OBJECT_INFO_QUICK optimization was added in dfdd4afc\n>> (\"sha1_file: teach sha1_object_info_extended more flags\",\n>> 2017-06-21), but since 8b4c0103 (\"sha1_file: support lazily fetching\n>> missing objects\", 2017-12-08) it appears that passing\n>> OBJECT_INFO_QUICK down the codepath does not do anything\n>> interesting.  Jonathan (cc'ed), are all remaining hits from \"git\n>> grep OBJECT_INFO_QUICK\" all dead no-ops these days?\n>\n> Yes the flag is no-op now, but let me untouched the flag in this patch.\n\nYeah, I do not want you to be touching that in this change.  It is\nan independent/orthogonal clean-up.\n\nThanks.\n"},{"id":"341369","messageId":"xmqqa7vh595b.fsf@gitster-ct.c.googlers.com","threadId":"48005","inReplyTo":"xmqqd10d6ser.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] fetch-pack.c: use oidset to check existence of loose object","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-09T19:41:36Z","receivedAt":"2018-03-09T19:41:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n>> Yes. But I think the default limit for the number of loose objects, 7000,\n>> gives us small overhead when we do enumeration of all objects.\n>\n> Hmph, I didn't see the code that does the estimation of loose object\n> count before starting to enumerate, though.\n\nAnother thing the code could do to avoid negative consequences on\nprojects that look quite different from yours (e.g. the other side\ndoes not have insane number of refs, but there are locally quite a\nfew loose objects) is to count how many entries are on *refs list\nbefore we decide to enumerate all loose objects.  When the refs list\nis relatively shorter than the estimated number of loose objects\n(you can actually do the estimation based on sampling, or just rely\non your assumed 7k), it may be a win _not_ to trigger the new code\nyou are adding to this codepath with this patch.  I would imagine\nthat the simplest implementaion may just count \n\n\tfor (ref = *refs, count = 0; ref && count++ < LIMIT; ref = ref->next)\n\t\t;\n\tuse_oidset_optim = (LIMIT <= count);\n\t\t\nassuming your \"up to 7k loose objects\" and then experimenting to\ndetermine the LIMIT which is a rough number of refs that makes the\noidset optimization worthwhile.\n\nWe need a bit better/descriptive name for the LIMIT, if we go that\nroute, though.\n\nThanks.\n\n\n \n"},{"id":"341370","messageId":"xmqq606558k2.fsf@gitster-ct.c.googlers.com","threadId":"48005","inReplyTo":"20180309132655.224308-1-tikuta@chromium.org","subject":"Re: [PATCH v3] fetch-pack.c: use oidset to check existence of loose object","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-09T19:54:21Z","receivedAt":"2018-03-09T19:54:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Takuto Ikuta <tikuta@chromium.org> writes:\n\n> In repository having large number of remote refs, because to check\n\nIsn't this \"When fetching from a repository with large number of\nrefs,\"?  The number of refs (whether it is local or remote-tracking)\nthe local side has has nothing to do with the issue you are\naddressing, no?\n\n> existence of each refs in local repository, 'git fetch' ends up doing a\n> lot of lstat(2) calls to see if it exists in loose form, which makes it\n> slow.\n\nOther than that, the above description reads much better and makes\nthe result easier to understand.\n\n> This patch enumerates loose objects in hashmap beforehand and uses it to\n> check existence instead of using lstat(2) to improve performance of\n> fetch-pack for repositories having large number of remote refs compared\n> to the number of loose objects.\n\nWe'd rather write this paragraph as if giving an order to the\ncodebase \"to be like so\", e.g.\n\n\tInstead of making as many lstat(2) calls as the refs the\n\tremote side advertised to see if these objects exist in the\n\tloose form, first enumerate all the existing loose objects\n\tin hashmap beforehand and use it to check existence of\n\tthem...\n\n> I took time stat of `git fetch` disabling quickfetch, so that fetch-pack\n\nI still do not know if a benchmark with quickfetch disabled gives\nrelevant numbers, for reasons I gave earlier.  The relative numbers\nbetween Linux and MacBook look quite convincing, as they illustrate\ndifferences of lstat(2) performance on these platforms.\n\n>  \tfor (ref = *refs; ref; ref = ref->next) {\n>  \t\tstruct object *o;\n> +\t\tunsigned int flags = OBJECT_INFO_QUICK;\n>  \n> -\t\tif (!has_object_file_with_flags(&ref->old_oid,\n> -\t\t\t\t\t\tOBJECT_INFO_QUICK))\n> -\t\t\tcontinue;\n> +\t\tif (!oidset_contains(&loose_oid_set, &ref->old_oid)) {\n> +\t\t\t/* I know this does not exist in the loose form,\n> +\t\t\t * so check if it exists in a non-loose form.\n> +\t\t\t */\n\n\t/*\n\t * Our multi-line comment looks like this,\n\t * with opening slash-asterisk and closing\n\t * asterisk-slash on their own lines.\n\t */\n\nThanks.\n"},{"id":"341393","messageId":"20180310123445.79609-1-tikuta@chromium.org","threadId":"48005","inReplyTo":"20180309132655.224308-1-tikuta@chromium.org","subject":"[PATCH v4] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-10T12:34:45Z","receivedAt":"2018-03-10T12:35:23Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"In repository having large number of remote refs, because to check\nexistence of each refs in local repository to packed and loose objects,\n'git fetch' ends up doing a lot of lstat(2) to non-existing loose form,\nwhich makes it slow.\n\nInstead of making as many lstat(2) calls as the refs the remote side\nadvertised to see if these objects exist in the loose form, first\nenumerate all the existing loose objects in hashmap beforehand and use\nit to check existence of them if the number of refs is larger than the\nnumber of loose objects.\n\nWith this patch, the number of lstat(2) calls in `git fetch` is reduced\nfrom 411412 to 13794 for chromium repository, it has more than 480000\nremote refs.\n\nI took time stat of `git fetch` disabling quickfetch, so that fetch-pack\nruns, for chromium repository 3 time on linux with SSD.\n* with this patch\n8.105s\n8.309s\n7.640s\navg: 8.018s\n\n* master\n12.287s\n11.175s\n12.227s\navg: 11.896s\n\nOn my MacBook Air which has slower lstat(2).\n* with this patch\n14.501s\n\n* master\n1m16.027s\n\n`git fetch` on slow disk will be improved largely.\n\nSigned-off-by: Takuto Ikuta <tikuta@chromium.org>\n---\n cache.h      |  2 ++\n fetch-pack.c | 45 ++++++++++++++++++++++++++++++++++++++++++---\n sha1_file.c  |  3 +++\n 3 files changed, 47 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d06932ed0..6a72f54d7 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1773,6 +1773,8 @@ struct object_info {\n #define OBJECT_INFO_SKIP_CACHED 4\n /* Do not retry packed storage after checking packed and loose storage */\n #define OBJECT_INFO_QUICK 8\n+/* Do not check loose object */\n+#define OBJECT_INFO_IGNORE_LOOSE 16\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n \n /*\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex d97461296..92b9bb4d9 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -711,6 +711,28 @@ static void mark_alternate_complete(struct object *obj)\n \tmark_complete(&obj->oid);\n }\n \n+struct loose_object_iter {\n+\tstruct oidset *loose_object_set;\n+\tstruct ref *refs;\n+};\n+\n+/*\n+ *  If the number of refs is not larger than the number of loose objects,\n+ *  this function stops inserting and returns false.\n+ */\n+static int add_loose_objects_to_set(const struct object_id *oid,\n+\t\t\t\t    const char *path,\n+\t\t\t\t    void *data)\n+{\n+\tstruct loose_object_iter *iter = data;\n+\toidset_insert(iter->loose_object_set, oid);\n+\tif (iter->refs == NULL)\n+\t\treturn 1;\n+\n+\titer->refs = iter->refs->next;\n+\treturn 0;\n+}\n+\n static int everything_local(struct fetch_pack_args *args,\n \t\t\t    struct ref **refs,\n \t\t\t    struct ref **sought, int nr_sought)\n@@ -719,16 +741,31 @@ static int everything_local(struct fetch_pack_args *args,\n \tint retval;\n \tint old_save_commit_buffer = save_commit_buffer;\n \ttimestamp_t cutoff = 0;\n+\tstruct oidset loose_oid_set = OIDSET_INIT;\n+\tint use_oidset = 0;\n+\tstruct loose_object_iter iter = {&loose_oid_set, *refs};\n+\n+\t/* Enumerate all loose objects or know refs are not so many. */\n+\tuse_oidset = !for_each_loose_object(add_loose_objects_to_set,\n+\t\t\t\t\t    &iter, 0);\n \n \tsave_commit_buffer = 0;\n \n \tfor (ref = *refs; ref; ref = ref->next) {\n \t\tstruct object *o;\n+\t\tunsigned int flags = OBJECT_INFO_QUICK;\n \n-\t\tif (!has_object_file_with_flags(&ref->old_oid,\n-\t\t\t\t\t\tOBJECT_INFO_QUICK))\n-\t\t\tcontinue;\n+\t\tif (use_oidset &&\n+\t\t    !oidset_contains(&loose_oid_set, &ref->old_oid)) {\n+\t\t\t/*\n+\t\t\t * I know this does not exist in the loose form,\n+\t\t\t * so check if it exists in a non-loose form.\n+\t\t\t */\n+\t\t\tflags |= OBJECT_INFO_IGNORE_LOOSE;\n+\t\t}\n \n+\t\tif (!has_object_file_with_flags(&ref->old_oid, flags))\n+\t\t\tcontinue;\n \t\to = parse_object(&ref->old_oid);\n \t\tif (!o)\n \t\t\tcontinue;\n@@ -744,6 +781,8 @@ static int everything_local(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\toidset_clear(&loose_oid_set);\n+\n \tif (!args->no_dependents) {\n \t\tif (!args->deepen) {\n \t\t\tfor_each_ref(mark_complete_oid, NULL);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1b94f39c4..c0a197947 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n \t\tif (find_pack_entry(real, &e))\n \t\t\tbreak;\n \n+\t\tif (flags & OBJECT_INFO_IGNORE_LOOSE)\n+\t\t\treturn -1;\n+\n \t\t/* Most likely it's a loose object. */\n \t\tif (!sha1_loose_object_info(real, oi, flags))\n \t\t\treturn 0;\n-- \n2.16.2\n\n"},{"id":"341394","messageId":"20180310124643.82666-1-tikuta@chromium.org","threadId":"48005","inReplyTo":"20180310123445.79609-1-tikuta@chromium.org","subject":"[PATCH v5] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-10T12:46:43Z","receivedAt":"2018-03-10T12:47:03Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"In repository having large number of remote refs, because to check\nexistence of each refs in local repository to packed and loose objects,\n'git fetch' ends up doing a lot of lstat(2) to non-existing loose form,\nwhich makes it slow.\n\nInstead of making as many lstat(2) calls as the refs the remote side\nadvertised to see if these objects exist in the loose form, first\nenumerate all the existing loose objects in hashmap beforehand and use\nit to check existence of them if the number of refs is larger than the\nnumber of loose objects.\n\nWith this patch, the number of lstat(2) calls in `git fetch` is reduced\nfrom 411412 to 13794 for chromium repository, it has more than 480000\nremote refs.\n\nI took time stat of `git fetch` when fetch-pack happens for chromium\nrepository 3 times on linux with SSD.\n* with this patch\n8.105s\n8.309s\n7.640s\navg: 8.018s\n\n* master\n12.287s\n11.175s\n12.227s\navg: 11.896s\n\nOn my MacBook Air which has slower lstat(2).\n* with this patch\n14.501s\n\n* master\n1m16.027s\n\n`git fetch` on slow disk will be improved largely.\n\nSigned-off-by: Takuto Ikuta <tikuta@chromium.org>\n---\n cache.h      |  2 ++\n fetch-pack.c | 45 ++++++++++++++++++++++++++++++++++++++++++---\n sha1_file.c  |  3 +++\n 3 files changed, 47 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d06932ed0..6a72f54d7 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1773,6 +1773,8 @@ struct object_info {\n #define OBJECT_INFO_SKIP_CACHED 4\n /* Do not retry packed storage after checking packed and loose storage */\n #define OBJECT_INFO_QUICK 8\n+/* Do not check loose object */\n+#define OBJECT_INFO_IGNORE_LOOSE 16\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n \n /*\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex d97461296..92b9bb4d9 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -711,6 +711,28 @@ static void mark_alternate_complete(struct object *obj)\n \tmark_complete(&obj->oid);\n }\n \n+struct loose_object_iter {\n+\tstruct oidset *loose_object_set;\n+\tstruct ref *refs;\n+};\n+\n+/*\n+ *  If the number of refs is not larger than the number of loose objects,\n+ *  this function stops inserting and returns false.\n+ */\n+static int add_loose_objects_to_set(const struct object_id *oid,\n+\t\t\t\t    const char *path,\n+\t\t\t\t    void *data)\n+{\n+\tstruct loose_object_iter *iter = data;\n+\toidset_insert(iter->loose_object_set, oid);\n+\tif (iter->refs == NULL)\n+\t\treturn 1;\n+\n+\titer->refs = iter->refs->next;\n+\treturn 0;\n+}\n+\n static int everything_local(struct fetch_pack_args *args,\n \t\t\t    struct ref **refs,\n \t\t\t    struct ref **sought, int nr_sought)\n@@ -719,16 +741,31 @@ static int everything_local(struct fetch_pack_args *args,\n \tint retval;\n \tint old_save_commit_buffer = save_commit_buffer;\n \ttimestamp_t cutoff = 0;\n+\tstruct oidset loose_oid_set = OIDSET_INIT;\n+\tint use_oidset = 0;\n+\tstruct loose_object_iter iter = {&loose_oid_set, *refs};\n+\n+\t/* Enumerate all loose objects or know refs are not so many. */\n+\tuse_oidset = !for_each_loose_object(add_loose_objects_to_set,\n+\t\t\t\t\t    &iter, 0);\n \n \tsave_commit_buffer = 0;\n \n \tfor (ref = *refs; ref; ref = ref->next) {\n \t\tstruct object *o;\n+\t\tunsigned int flags = OBJECT_INFO_QUICK;\n \n-\t\tif (!has_object_file_with_flags(&ref->old_oid,\n-\t\t\t\t\t\tOBJECT_INFO_QUICK))\n-\t\t\tcontinue;\n+\t\tif (use_oidset &&\n+\t\t    !oidset_contains(&loose_oid_set, &ref->old_oid)) {\n+\t\t\t/*\n+\t\t\t * I know this does not exist in the loose form,\n+\t\t\t * so check if it exists in a non-loose form.\n+\t\t\t */\n+\t\t\tflags |= OBJECT_INFO_IGNORE_LOOSE;\n+\t\t}\n \n+\t\tif (!has_object_file_with_flags(&ref->old_oid, flags))\n+\t\t\tcontinue;\n \t\to = parse_object(&ref->old_oid);\n \t\tif (!o)\n \t\t\tcontinue;\n@@ -744,6 +781,8 @@ static int everything_local(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\toidset_clear(&loose_oid_set);\n+\n \tif (!args->no_dependents) {\n \t\tif (!args->deepen) {\n \t\t\tfor_each_ref(mark_complete_oid, NULL);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1b94f39c4..c0a197947 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n \t\tif (find_pack_entry(real, &e))\n \t\t\tbreak;\n \n+\t\tif (flags & OBJECT_INFO_IGNORE_LOOSE)\n+\t\t\treturn -1;\n+\n \t\t/* Most likely it's a loose object. */\n \t\tif (!sha1_loose_object_info(real, oi, flags))\n \t\t\treturn 0;\n-- \n2.16.2\n\n"},{"id":"341396","messageId":"CALNjmMqBbZTFVRnc__wewWy3808n9J9xfgu8ZH-FWyWJKvqb9w@mail.gmail.com","threadId":"48005","inReplyTo":"xmqq606558k2.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-10T13:19:15Z","receivedAt":"2018-03-10T13:20:05Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"2018-03-10 3:00 GMT+09:00 Junio C Hamano <gitster@pobox.com>:\n> Takuto Ikuta <tikuta@chromium.org> writes:\n>\n>> Yes, I just wanted to say 'git fetch' invokes fetch-pack.\n>> fetch-pack is skipped when running git fetch repeatedly while\n>> remote has no update by quickfetch. So I disabled it to see the\n>> performance of fetch-pack. In chromium repository, master branch\n>> is updated several times in an hour, so git fetch invokes fetch-pack\n>> in such frequency.\n>\n> I do understand that if you run \"git fetch\" against the same place\n> in quick succession three times, the first one may cost a lot (not\n> just that it has to do the everything_local() computation that you\n> care about, it also has to actually do the network transfer), while\n> the second and third ones that are done before anything new happens\n> on the other end will not involve everything_local() overhead thanks\n> to quickfetch.\n>\n> A \"fetch\" that is run against a remote that has nothing new, but\n> still triggers everything_local() only because quickfetch is\n> disabled, is an artificial case that has no relevance to the real\n> world, I suspect, because the quickfetch optimization is to solve\n> the \"there is nothing to be done, still do_fetch_pack() spends so\n> much cycles only to realize that it does not have anything to do,\n> why?\" issue.\n>\n\nI changed not to say \"disabling quickfetch\" in v5 description.\nActually, I'd like to take several stats on linux because the perf difference\nis small and it can be affected by network and quickfetch.\n\n> Isn't running the \"git fetch\" command with the \"--dry-run\" option\n> many times in quick succession a lot closer to what you really want\n> to measure, I wonder?  That way, your first fetch won't be touching\n> the state of the local side to affect your second and subsequent\n> fetches.\n>\n\nLooks no? Even when I use --dry-run, second run did not invoke fetch-pack.\n\n>>> In any case, do_fetch_pack() tries to see if all of the tip commits\n>>> we are going to fetch exist locally, so when you are trying a fetch\n>>> that grabs huge number of refs (by the way, it means that the first\n>>> sentence of the proposed log message is not quite true---it is \"When\n>>> fetching a large number of refs\", as it does not matter how many\n>>> refs _we_ have, no?), everything_local() ends up making repeated\n>>> calls to has_object_file_with_flags() to all of the refs.\n>>\n>> I fixed description by changing 'refs' to 'remote refs'. In my understanding,\n>> git tries to check existence of remote refs even if we won't fetch such refs.\n>\n> During fetch, everything_local() tries to mark common part by\n> walking the refs the other side advertised upon the first contact,\n> so it is correct that the number of checks is not reduced in a fetch\n> that does not fetch many refs, but the number of remote-tracking refs\n> you have has no effect, so I doubt such a rephrasing would make the\n> description more understandable.  \"When fetching from a repository\n> with large number of refs\" is probably what you want to say, no?\n>\n\nFor refs existing in local repository, everything_local looks to be able to find\ncorresponding object from packed or loose objects. And if it exists,\nI think, cost of lstat(2) is relatively smaller than other operations.\nBut for remote refs, everything_local fails to find it from packed\nobject (this check is fast)\nand it tries to find loose object by using lstat(2), and this fails and slow.\nMy patch is to skip this lstat(2) to non-existing ref objects for repositories\nhaving large number of remote refs.\n\n2018-03-10 4:41 GMT+09:00 Junio C Hamano <gitster@pobox.com>:\n> Junio C Hamano <gitster@pobox.com> writes:\n>\n>>> Yes. But I think the default limit for the number of loose objects, 7000,\n>>> gives us small overhead when we do enumeration of all objects.\n>>\n>> Hmph, I didn't see the code that does the estimation of loose object\n>> count before starting to enumerate, though.\n>\n> Another thing the code could do to avoid negative consequences on\n> projects that look quite different from yours (e.g. the other side\n> does not have insane number of refs, but there are locally quite a\n> few loose objects) is to count how many entries are on *refs list\n> before we decide to enumerate all loose objects.  When the refs list\n> is relatively shorter than the estimated number of loose objects\n> (you can actually do the estimation based on sampling, or just rely\n> on your assumed 7k), it may be a win _not_ to trigger the new code\n> you are adding to this codepath with this patch.  I would imagine\n> that the simplest implementaion may just count\n>\n>         for (ref = *refs, count = 0; ref && count++ < LIMIT; ref = ref->next)\n>                 ;\n>         use_oidset_optim = (LIMIT <= count);\n>\n> assuming your \"up to 7k loose objects\" and then experimenting to\n> determine the LIMIT which is a rough number of refs that makes the\n> oidset optimization worthwhile.\n>\n> We need a bit better/descriptive name for the LIMIT, if we go that\n> route, though.\n>\n\nSorry, 7000 was wrong. I wanted to say the default number of gc.auto, 6700.\nI changed to count refs in for_each_loose_object(), and use it to\ndetermine whether\nwe use oidset or not.\n\n2018-03-10 4:54 GMT+09:00 Junio C Hamano <gitster@pobox.com>:\n> Takuto Ikuta <tikuta@chromium.org> writes:\n>\n>> In repository having large number of remote refs, because to check\n>\n> Isn't this \"When fetching from a repository with large number of\n> refs,\"?  The number of refs (whether it is local or remote-tracking)\n> the local side has has nothing to do with the issue you are\n> addressing, no?\n>\n\nYes it has nothing to do with the issue. At least, my patch won't change\nperformance of git fetch for the repository having large number of local refs.\n\n>> existence of each refs in local repository, 'git fetch' ends up doing a\n>> lot of lstat(2) calls to see if it exists in loose form, which makes it\n>> slow.\n>\n> Other than that, the above description reads much better and makes\n> the result easier to understand.\n>\n>> This patch enumerates loose objects in hashmap beforehand and uses it to\n>> check existence instead of using lstat(2) to improve performance of\n>> fetch-pack for repositories having large number of remote refs compared\n>> to the number of loose objects.\n>\n> We'd rather write this paragraph as if giving an order to the\n> codebase \"to be like so\", e.g.\n>\n>         Instead of making as many lstat(2) calls as the refs the\n>         remote side advertised to see if these objects exist in the\n>         loose form, first enumerate all the existing loose objects\n>         in hashmap beforehand and use it to check existence of\n>         them...\n>\n\nThanks, I changed description like it.\n\n>> I took time stat of `git fetch` disabling quickfetch, so that fetch-pack\n>\n> I still do not know if a benchmark with quickfetch disabled gives\n> relevant numbers, for reasons I gave earlier.  The relative numbers\n> between Linux and MacBook look quite convincing, as they illustrate\n> differences of lstat(2) performance on these platforms.\n>\n>>       for (ref = *refs; ref; ref = ref->next) {\n>>               struct object *o;\n>> +             unsigned int flags = OBJECT_INFO_QUICK;\n>>\n>> -             if (!has_object_file_with_flags(&ref->old_oid,\n>> -                                             OBJECT_INFO_QUICK))\n>> -                     continue;\n>> +             if (!oidset_contains(&loose_oid_set, &ref->old_oid)) {\n>> +                     /* I know this does not exist in the loose form,\n>> +                      * so check if it exists in a non-loose form.\n>> +                      */\n>\n>         /*\n>          * Our multi-line comment looks like this,\n>          * with opening slash-asterisk and closing\n>          * asterisk-slash on their own lines.\n>          */\n>\n\nI fixed.\n\n\nThanks, Takuto\n"},{"id":"341553","messageId":"20180313153029.257296-1-jonathantanmy@google.com","threadId":"48005","inReplyTo":"xmqqr2ouwgsd.fsf@gitster-ct.c.googlers.com","subject":"[PATCH] sha1_file: restore OBJECT_INFO_QUICK functionality","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-03-13T15:30:29Z","receivedAt":"2018-03-13T16:54:04Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Support for the OBJECT_INFO_QUICK flag in sha1_object_info_extended()\nwas added in commit dfdd4afcf9 (\"sha1_file: teach\nsha1_object_info_extended more flags\", 2017-06-26) in order to support\ncommit e83e71c5e1 (\"sha1_file: refactor has_sha1_file_with_flags\",\n2017-06-26), but it was inadvertently removed in commit 8b4c0103a9\n(\"sha1_file: support lazily fetching missing objects\", 2017-12-08).\n\nRestore this functionality.\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\n> Hmm, OBJECT_INFO_QUICK optimization was added in dfdd4afc\n> (\"sha1_file: teach sha1_object_info_extended more flags\",\n> 2017-06-21), but since 8b4c0103 (\"sha1_file: support lazily fetching\n> missing objects\", 2017-12-08) it appears that passing\n> OBJECT_INFO_QUICK down the codepath does not do anything\n> interesting.  Jonathan (cc'ed), are all remaining hits from \"git\n> grep OBJECT_INFO_QUICK\" all dead no-ops these days?\n\nThey are, but they are not supposed to be. Here is a patch correcting\nthat.\n---\n sha1_file.c | 8 +++++---\n 1 file changed, 5 insertions(+), 3 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1b94f39c4..cc0f43ea8 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1267,9 +1267,11 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n \t\t\treturn 0;\n \n \t\t/* Not a loose object; someone else may have just packed it. */\n-\t\treprepare_packed_git();\n-\t\tif (find_pack_entry(real, &e))\n-\t\t\tbreak;\n+\t\tif (!(flags & OBJECT_INFO_QUICK)) {\n+\t\t\treprepare_packed_git();\n+\t\t\tif (find_pack_entry(real, &e))\n+\t\t\t\tbreak;\n+\t\t}\n \n \t\t/* Check if it is a missing object */\n \t\tif (fetch_if_missing && repository_format_partial_clone &&\n-- \n2.16.2.660.g709887971b-goog\n\n"},{"id":"341558","messageId":"xmqqo9jr3lrt.fsf@gitster-ct.c.googlers.com","threadId":"48005","inReplyTo":"CALNjmMqBbZTFVRnc__wewWy3808n9J9xfgu8ZH-FWyWJKvqb9w@mail.gmail.com","subject":"Re: [PATCH v3] fetch-pack.c: use oidset to check existence of loose object","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-13T17:53:10Z","receivedAt":"2018-03-13T17:53:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Takuto Ikuta <tikuta@chromium.org> writes:\n\n>> During fetch, everything_local() tries to mark common part by\n>> walking the refs the other side advertised upon the first contact,\n>> so it is correct that the number of checks is not reduced in a fetch\n>> that does not fetch many refs, but the number of remote-tracking refs\n>> you have has no effect, so I doubt such a rephrasing would make the\n>> description more understandable.  \"When fetching from a repository\n>> with large number of refs\" is probably what you want to say, no?\n>\n> For refs existing in local repository, everything_local looks to be able to find\n> corresponding object from packed or loose objects. And if it exists,\n> I think, cost of lstat(2) is relatively smaller than other operations.\n> But for remote refs, everything_local fails to find it from packed\n> object (this check is fast)\n> and it tries to find loose object by using lstat(2), and this fails and slow.\n> My patch is to skip this lstat(2) to non-existing ref objects for repositories\n> having large number of remote refs.\n\nThis still does not make sense to me, and I suspect that I am\nmisreading you.  In what sense are you using the word \"repository\"\nand \"remote refs\"?\n\nImagine this situation.  I have a local repository A, I fetch from a\nremote repository B but in my repository A, I do *not* use\nremote-tracking refs to remember what the last values of refs at\nrepository B.  Now when I try to fetch a single ref from B into A,\nmany refs B advertises point at objects A has never heard about, and\nthat triggers many lstat(2) that yields ENOENT that is slow.  Your\npatch is to optimize this so that we learn these objects do not\nexist locally without running many lstat(2) to objects and helps\nrepositories (like my repository A) when fetching from a repository\nwith large number of refs (like the repository B).  It does not\nmatter how many \"remote refs\" receiving repository (e.g. my A) has,\nand it does not matter how many \"remote refs\" sending repository\n(e.g. my B) has---whether it is refs/remotes/origin/foo\n(i.e. \"remote\") or refs/heads/foo (i.e. \"local\"), a ref at B that\npoints at an object that is missing at A will cause the same\nlstat(2) at A without your change.\n\nThat is why I think \"When fetching from a repository with large\nnumber of refs\" is what you meant, not \"fetching into a repository\nwith large number of remote refs\" nor \"fetching from a repository\nwith large number of remote refs\".\n\nThanks.\n"},{"id":"341568","messageId":"xmqq7eqf3ign.fsf@gitster-ct.c.googlers.com","threadId":"48005","inReplyTo":"20180310124643.82666-1-tikuta@chromium.org","subject":"Re: [PATCH v5] fetch-pack.c: use oidset to check existence of loose object","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-13T19:04:40Z","receivedAt":"2018-03-13T19:04:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Takuto Ikuta <tikuta@chromium.org> writes:\n\n> +struct loose_object_iter {\n> +\tstruct oidset *loose_object_set;\n> +\tstruct ref *refs;\n> +};\n> +\n> +/*\n> + *  If the number of refs is not larger than the number of loose objects,\n> + *  this function stops inserting and returns false.\n> + */\n> +static int add_loose_objects_to_set(const struct object_id *oid,\n> +\t\t\t\t    const char *path,\n> +\t\t\t\t    void *data)\n> +{\n> +\tstruct loose_object_iter *iter = data;\n> +\toidset_insert(iter->loose_object_set, oid);\n> +\tif (iter->refs == NULL)\n> +\t\treturn 1;\n> +\n> +\titer->refs = iter->refs->next;\n> +\treturn 0;\n> +}\n\nThat's clever.  By traversing the refs list as you iterate over the\nloose objects, you do not do any unnecessary work ;-)\n\nThanks for working on this.\n\n> @@ -719,16 +741,31 @@ static int everything_local(struct fetch_pack_args *args,\n>  \tint retval;\n>  \tint old_save_commit_buffer = save_commit_buffer;\n>  \ttimestamp_t cutoff = 0;\n> +\tstruct oidset loose_oid_set = OIDSET_INIT;\n> +\tint use_oidset = 0;\n> +\tstruct loose_object_iter iter = {&loose_oid_set, *refs};\n> +\n> +\t/* Enumerate all loose objects or know refs are not so many. */\n> +\tuse_oidset = !for_each_loose_object(add_loose_objects_to_set,\n> +\t\t\t\t\t    &iter, 0);\n>  \n>  \tsave_commit_buffer = 0;\n>  \n>  \tfor (ref = *refs; ref; ref = ref->next) {\n>  \t\tstruct object *o;\n> +\t\tunsigned int flags = OBJECT_INFO_QUICK;\n>  \n> -\t\tif (!has_object_file_with_flags(&ref->old_oid,\n> -\t\t\t\t\t\tOBJECT_INFO_QUICK))\n> -\t\t\tcontinue;\n> +\t\tif (use_oidset &&\n> +\t\t    !oidset_contains(&loose_oid_set, &ref->old_oid)) {\n> +\t\t\t/*\n> +\t\t\t * I know this does not exist in the loose form,\n> +\t\t\t * so check if it exists in a non-loose form.\n> +\t\t\t */\n> +\t\t\tflags |= OBJECT_INFO_IGNORE_LOOSE;\n> +\t\t}\n>  \n> +\t\tif (!has_object_file_with_flags(&ref->old_oid, flags))\n> +\t\t\tcontinue;\n>  \t\to = parse_object(&ref->old_oid);\n>  \t\tif (!o)\n>  \t\t\tcontinue;\n"},{"id":"341615","messageId":"20180314060511.257985-1-tikuta@chromium.org","threadId":"48005","inReplyTo":"20180310123445.79609-1-tikuta@chromium.org","subject":"[PATCH v6] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-14T06:05:11Z","receivedAt":"2018-03-14T06:06:26Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"When fetching from a repository with large number of refs, because to\ncheck existence of each refs in local repository to packed and loose\nobjects, 'git fetch' ends up doing a lot of lstat(2) to non-existing\nloose form, which makes it slow.\n\nInstead of making as many lstat(2) calls as the refs the remote side\nadvertised to see if these objects exist in the loose form, first\nenumerate all the existing loose objects in hashmap beforehand and use\nit to check existence of them if the number of refs is larger than the\nnumber of loose objects.\n\nWith this patch, the number of lstat(2) calls in `git fetch` is reduced\nfrom 411412 to 13794 for chromium repository, it has more than 480000\nremote refs.\n\nI took time stat of `git fetch` when fetch-pack happens for chromium\nrepository 3 times on linux with SSD.\n* with this patch\n8.105s\n8.309s\n7.640s\navg: 8.018s\n\n* master\n12.287s\n11.175s\n12.227s\navg: 11.896s\n\nOn my MacBook Air which has slower lstat(2).\n* with this patch\n14.501s\n\n* master\n1m16.027s\n\n`git fetch` on slow disk will be improved largely.\n\nSigned-off-by: Takuto Ikuta <tikuta@chromium.org>\n---\n cache.h      |  2 ++\n fetch-pack.c | 45 ++++++++++++++++++++++++++++++++++++++++++---\n sha1_file.c  |  3 +++\n 3 files changed, 47 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d06932ed0..6a72f54d7 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1773,6 +1773,8 @@ struct object_info {\n #define OBJECT_INFO_SKIP_CACHED 4\n /* Do not retry packed storage after checking packed and loose storage */\n #define OBJECT_INFO_QUICK 8\n+/* Do not check loose object */\n+#define OBJECT_INFO_IGNORE_LOOSE 16\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n \n /*\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex d97461296..92b9bb4d9 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -711,6 +711,28 @@ static void mark_alternate_complete(struct object *obj)\n \tmark_complete(&obj->oid);\n }\n \n+struct loose_object_iter {\n+\tstruct oidset *loose_object_set;\n+\tstruct ref *refs;\n+};\n+\n+/*\n+ *  If the number of refs is not larger than the number of loose objects,\n+ *  this function stops inserting and returns false.\n+ */\n+static int add_loose_objects_to_set(const struct object_id *oid,\n+\t\t\t\t    const char *path,\n+\t\t\t\t    void *data)\n+{\n+\tstruct loose_object_iter *iter = data;\n+\toidset_insert(iter->loose_object_set, oid);\n+\tif (iter->refs == NULL)\n+\t\treturn 1;\n+\n+\titer->refs = iter->refs->next;\n+\treturn 0;\n+}\n+\n static int everything_local(struct fetch_pack_args *args,\n \t\t\t    struct ref **refs,\n \t\t\t    struct ref **sought, int nr_sought)\n@@ -719,16 +741,31 @@ static int everything_local(struct fetch_pack_args *args,\n \tint retval;\n \tint old_save_commit_buffer = save_commit_buffer;\n \ttimestamp_t cutoff = 0;\n+\tstruct oidset loose_oid_set = OIDSET_INIT;\n+\tint use_oidset = 0;\n+\tstruct loose_object_iter iter = {&loose_oid_set, *refs};\n+\n+\t/* Enumerate all loose objects or know refs are not so many. */\n+\tuse_oidset = !for_each_loose_object(add_loose_objects_to_set,\n+\t\t\t\t\t    &iter, 0);\n \n \tsave_commit_buffer = 0;\n \n \tfor (ref = *refs; ref; ref = ref->next) {\n \t\tstruct object *o;\n+\t\tunsigned int flags = OBJECT_INFO_QUICK;\n \n-\t\tif (!has_object_file_with_flags(&ref->old_oid,\n-\t\t\t\t\t\tOBJECT_INFO_QUICK))\n-\t\t\tcontinue;\n+\t\tif (use_oidset &&\n+\t\t    !oidset_contains(&loose_oid_set, &ref->old_oid)) {\n+\t\t\t/*\n+\t\t\t * I know this does not exist in the loose form,\n+\t\t\t * so check if it exists in a non-loose form.\n+\t\t\t */\n+\t\t\tflags |= OBJECT_INFO_IGNORE_LOOSE;\n+\t\t}\n \n+\t\tif (!has_object_file_with_flags(&ref->old_oid, flags))\n+\t\t\tcontinue;\n \t\to = parse_object(&ref->old_oid);\n \t\tif (!o)\n \t\t\tcontinue;\n@@ -744,6 +781,8 @@ static int everything_local(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\toidset_clear(&loose_oid_set);\n+\n \tif (!args->no_dependents) {\n \t\tif (!args->deepen) {\n \t\t\tfor_each_ref(mark_complete_oid, NULL);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1b94f39c4..c0a197947 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n \t\tif (find_pack_entry(real, &e))\n \t\t\tbreak;\n \n+\t\tif (flags & OBJECT_INFO_IGNORE_LOOSE)\n+\t\t\treturn -1;\n+\n \t\t/* Most likely it's a loose object. */\n \t\tif (!sha1_loose_object_info(real, oi, flags))\n \t\t\treturn 0;\n-- \n2.16.2.804.g6dcf76e118-goog\n\n"},{"id":"341616","messageId":"CALNjmMqqa1i0=ekqQfNZ5DmA+h7mOGzZcF-RB1A6+Rm8vw80pQ@mail.gmail.com","threadId":"48005","inReplyTo":"xmqqo9jr3lrt.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-14T06:26:46Z","receivedAt":"2018-03-14T06:27:30Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"2018年3月14日(水) 2:53 Junio C Hamano <gitster@pobox.com>:\n\n> Takuto Ikuta <tikuta@chromium.org> writes:\n\n> >> During fetch, everything_local() tries to mark common part by\n> >> walking the refs the other side advertised upon the first contact,\n> >> so it is correct that the number of checks is not reduced in a fetch\n> >> that does not fetch many refs, but the number of remote-tracking refs\n> >> you have has no effect, so I doubt such a rephrasing would make the\n> >> description more understandable.  \"When fetching from a repository\n> >> with large number of refs\" is probably what you want to say, no?\n> >\n> > For refs existing in local repository, everything_local looks to be\nable to find\n> > corresponding object from packed or loose objects. And if it exists,\n> > I think, cost of lstat(2) is relatively smaller than other operations.\n> > But for remote refs, everything_local fails to find it from packed\n> > object (this check is fast)\n> > and it tries to find loose object by using lstat(2), and this fails and\nslow.\n> > My patch is to skip this lstat(2) to non-existing ref objects for\nrepositories\n> > having large number of remote refs.\n\n> This still does not make sense to me, and I suspect that I am\n> misreading you.  In what sense are you using the word \"repository\"\n> and \"remote refs\"?\n\n\nYes, I think I did not understand the terms correctly.\nI meant \"repository\" for repository in remote servers, and \"remote refs\" for\nrefs shown by `git ls-remote`.\n\n> Imagine this situation.  I have a local repository A, I fetch from a\n> remote repository B but in my repository A, I do *not* use\n> remote-tracking refs to remember what the last values of refs at\n> repository B.  Now when I try to fetch a single ref from B into A,\n> many refs B advertises point at objects A has never heard about, and\n> that triggers many lstat(2) that yields ENOENT that is slow.  Your\n> patch is to optimize this so that we learn these objects do not\n> exist locally without running many lstat(2) to objects and helps\n> repositories (like my repository A) when fetching from a repository\n> with large number of refs (like the repository B).  It does not\n> matter how many \"remote refs\" receiving repository (e.g. my A) has,\n> and it does not matter how many \"remote refs\" sending repository\n> (e.g. my B) has---whether it is refs/remotes/origin/foo\n> (i.e. \"remote\") or refs/heads/foo (i.e. \"local\"), a ref at B that\n> points at an object that is missing at A will cause the same\n> lstat(2) at A without your change.\n\n> That is why I think \"When fetching from a repository with large\n> number of refs\" is what you meant, not \"fetching into a repository\n> with large number of remote refs\" nor \"fetching from a repository\n> with large number of remote refs\".\n\n\nThank you for explanation.\nAnd yes, that is exactly I want to do in my patch.\nFixed description in v6.\n\nThanks.\n"},{"id":"341617","messageId":"20180314063242.5759-1-tikuta@chromium.org","threadId":"48005","inReplyTo":"20180314060511.257985-1-tikuta@chromium.org","subject":"[PATCH v7] fetch-pack.c: use oidset to check existence of loose object","fromName":"Takuto Ikuta","fromEmail":"tikuta@chromium.org","sentAt":"2018-03-14T06:32:42Z","receivedAt":"2018-03-14T06:33:29Z","isPatch":true,"sender":{"key":"tikuta@chromium.org","avatar":null},"body":"When fetching from a repository with large number of refs, because to\ncheck existence of each refs in local repository to packed and loose\nobjects, 'git fetch' ends up doing a lot of lstat(2) to non-existing\nloose form, which makes it slow.\n\nInstead of making as many lstat(2) calls as the refs the remote side\nadvertised to see if these objects exist in the loose form, first\nenumerate all the existing loose objects in hashmap beforehand and use\nit to check existence of them if the number of refs is larger than the\nnumber of loose objects.\n\nWith this patch, the number of lstat(2) calls in `git fetch` is reduced\nfrom 411412 to 13794 for chromium repository, it has more than 480000\nremote refs.\n\nI took time stat of `git fetch` when fetch-pack happens for chromium\nrepository 3 times on linux with SSD.\n* with this patch\n8.105s\n8.309s\n7.640s\navg: 8.018s\n\n* master\n12.287s\n11.175s\n12.227s\navg: 11.896s\n\nOn my MacBook Air which has slower lstat(2).\n* with this patch\n14.501s\n\n* master\n1m16.027s\n\n`git fetch` on slow disk will be improved largely.\n\nSigned-off-by: Takuto Ikuta <tikuta@chromium.org>\n---\n cache.h      |  2 ++\n fetch-pack.c | 45 ++++++++++++++++++++++++++++++++++++++++++---\n sha1_file.c  |  3 +++\n 3 files changed, 47 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d06932ed0..6a72f54d7 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1773,6 +1773,8 @@ struct object_info {\n #define OBJECT_INFO_SKIP_CACHED 4\n /* Do not retry packed storage after checking packed and loose storage */\n #define OBJECT_INFO_QUICK 8\n+/* Do not check loose object */\n+#define OBJECT_INFO_IGNORE_LOOSE 16\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n \n /*\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex d97461296..2ea358861 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -711,6 +711,28 @@ static void mark_alternate_complete(struct object *obj)\n \tmark_complete(&obj->oid);\n }\n \n+struct loose_object_iter {\n+\tstruct oidset *loose_object_set;\n+\tstruct ref *refs;\n+};\n+\n+/*\n+ *  If the number of refs is not larger than the number of loose objects,\n+ *  this function stops inserting.\n+ */\n+static int add_loose_objects_to_set(const struct object_id *oid,\n+\t\t\t\t    const char *path,\n+\t\t\t\t    void *data)\n+{\n+\tstruct loose_object_iter *iter = data;\n+\toidset_insert(iter->loose_object_set, oid);\n+\tif (iter->refs == NULL)\n+\t\treturn 1;\n+\n+\titer->refs = iter->refs->next;\n+\treturn 0;\n+}\n+\n static int everything_local(struct fetch_pack_args *args,\n \t\t\t    struct ref **refs,\n \t\t\t    struct ref **sought, int nr_sought)\n@@ -719,16 +741,31 @@ static int everything_local(struct fetch_pack_args *args,\n \tint retval;\n \tint old_save_commit_buffer = save_commit_buffer;\n \ttimestamp_t cutoff = 0;\n+\tstruct oidset loose_oid_set = OIDSET_INIT;\n+\tint use_oidset = 0;\n+\tstruct loose_object_iter iter = {&loose_oid_set, *refs};\n+\n+\t/* Enumerate all loose objects or know refs are not so many. */\n+\tuse_oidset = !for_each_loose_object(add_loose_objects_to_set,\n+\t\t\t\t\t    &iter, 0);\n \n \tsave_commit_buffer = 0;\n \n \tfor (ref = *refs; ref; ref = ref->next) {\n \t\tstruct object *o;\n+\t\tunsigned int flags = OBJECT_INFO_QUICK;\n \n-\t\tif (!has_object_file_with_flags(&ref->old_oid,\n-\t\t\t\t\t\tOBJECT_INFO_QUICK))\n-\t\t\tcontinue;\n+\t\tif (use_oidset &&\n+\t\t    !oidset_contains(&loose_oid_set, &ref->old_oid)) {\n+\t\t\t/*\n+\t\t\t * I know this does not exist in the loose form,\n+\t\t\t * so check if it exists in a non-loose form.\n+\t\t\t */\n+\t\t\tflags |= OBJECT_INFO_IGNORE_LOOSE;\n+\t\t}\n \n+\t\tif (!has_object_file_with_flags(&ref->old_oid, flags))\n+\t\t\tcontinue;\n \t\to = parse_object(&ref->old_oid);\n \t\tif (!o)\n \t\t\tcontinue;\n@@ -744,6 +781,8 @@ static int everything_local(struct fetch_pack_args *args,\n \t\t}\n \t}\n \n+\toidset_clear(&loose_oid_set);\n+\n \tif (!args->no_dependents) {\n \t\tif (!args->deepen) {\n \t\t\tfor_each_ref(mark_complete_oid, NULL);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 1b94f39c4..c0a197947 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1262,6 +1262,9 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n \t\tif (find_pack_entry(real, &e))\n \t\t\tbreak;\n \n+\t\tif (flags & OBJECT_INFO_IGNORE_LOOSE)\n+\t\t\treturn -1;\n+\n \t\t/* Most likely it's a loose object. */\n \t\tif (!sha1_loose_object_info(real, oi, flags))\n \t\t\treturn 0;\n-- \n2.16.2\n\n"}]}