{"thread":{"id":"56214","subject":"[PATCH] fetch-pack: speed up loading of refs via commit graph","startedAt":"2021-08-04T13:56:23Z","lastAt":"2021-08-05T20:42:43Z","messageCount":12,"participants":["Patrick Steinhardt","Derrick Stolee","Junio C Hamano","Jeff King","Ævar Arnfjörð Bjarmason"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"431954","messageId":"08519b8ab6f395cffbcd5e530bfba6aaf64241a2.1628085347.git.ps@pks.im","threadId":"56214","inReplyTo":null,"subject":"[PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-08-04T13:56:11Z","receivedAt":"2021-08-04T13:56:23Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing reference negotiation, git-fetch-pack(1) is loading all refs\nfrom disk in order to determine which commits it has in common with the\nremote repository. This can be quite expensive in repositories with many\nreferences though: in a real-world repository with around 2.2 million\nrefs, fetching a single commit by its ID takes around 44 seconds.\n\nDominating the loading time is decompression and parsing of the objects\nwhich are referenced by commits. Given the fact that we only care about\ncommits (or tags which can be peeled to one) in this context, there is\nthus an easy performance win by switching the parsing logic to make use\nof the commit graph in case we have one available. Like this, we avoid\nhitting the object database to parse these commits but instead only load\nthem from the commit-graph. This results in a significant performance\nboost when executing git-fetch in said repository with 2.2 million refs:\n\n    Benchmark #1: HEAD~: git fetch $remote $commit\n      Time (mean ± σ):     44.168 s ±  0.341 s    [User: 42.985 s, System: 1.106 s]\n      Range (min … max):   43.565 s … 44.577 s    10 runs\n\n    Benchmark #2: HEAD: git fetch $remote $commit\n      Time (mean ± σ):     19.498 s ±  0.724 s    [User: 18.751 s, System: 0.690 s]\n      Range (min … max):   18.629 s … 20.454 s    10 runs\n\n    Summary\n      'HEAD: git fetch $remote $commit' ran\n        2.27 ± 0.09 times faster than 'HEAD~: git fetch $remote $commit'\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n fetch-pack.c | 10 ++++++++--\n 1 file changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex b0c7be717c..0bf7ed7e47 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -137,8 +137,14 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid,\n \t\t\tbreak;\n \t\t}\n \t}\n-\tif (type == OBJ_COMMIT)\n-\t\treturn (struct commit *) parse_object(the_repository, oid);\n+\n+\tif (type == OBJ_COMMIT) {\n+\t\tstruct commit *commit = lookup_commit(the_repository, oid);\n+\t\tif (!commit || repo_parse_commit(the_repository, commit))\n+\t\t\treturn NULL;\n+\t\treturn commit;\n+\t}\n+\n \treturn NULL;\n }\n \n-- \n2.32.0\n\n"},{"id":"431959","messageId":"9532b3a8-baeb-50ac-766e-e9844aa63051@gmail.com","threadId":"56214","inReplyTo":"08519b8ab6f395cffbcd5e530bfba6aaf64241a2.1628085347.git.ps@pks.im","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-08-04T14:55:00Z","receivedAt":"2021-08-04T14:55:05Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/4/2021 9:56 AM, Patrick Steinhardt wrote:\n> When doing reference negotiation, git-fetch-pack(1) is loading all refs\n> from disk in order to determine which commits it has in common with the\n> remote repository. This can be quite expensive in repositories with many\n> references though: in a real-world repository with around 2.2 million\n> refs, fetching a single commit by its ID takes around 44 seconds.\n> \n> Dominating the loading time is decompression and parsing of the objects\n> which are referenced by commits. Given the fact that we only care about\n> commits (or tags which can be peeled to one) in this context, there is\n> thus an easy performance win by switching the parsing logic to make use\n> of the commit graph in case we have one available.\n\nNice find!\n\n> Like this, we avoid\n> hitting the object database to parse these commits but instead only load\n> them from the commit-graph. This results in a significant performance\n> boost when executing git-fetch in said repository with 2.2 million refs:\n> \n>     Benchmark #1: HEAD~: git fetch $remote $commit\n>       Time (mean ± σ):     44.168 s ±  0.341 s    [User: 42.985 s, System: 1.106 s]\n>       Range (min … max):   43.565 s … 44.577 s    10 runs\n> \n>     Benchmark #2: HEAD: git fetch $remote $commit\n>       Time (mean ± σ):     19.498 s ±  0.724 s    [User: 18.751 s, System: 0.690 s]\n>       Range (min … max):   18.629 s … 20.454 s    10 runs\n> \n>     Summary\n>       'HEAD: git fetch $remote $commit' ran\n>         2.27 ± 0.09 times faster than 'HEAD~: git fetch $remote $commit'\n\nThat's a great improvement. I'm sure that the remaining time is dominated\nby ref parsing.\n\n> -\tif (type == OBJ_COMMIT)\n> -\t\treturn (struct commit *) parse_object(the_repository, oid);\n> +\n> +\tif (type == OBJ_COMMIT) {\n> +\t\tstruct commit *commit = lookup_commit(the_repository, oid);\n> +\t\tif (!commit || repo_parse_commit(the_repository, commit))\n> +\t\t\treturn NULL;\n> +\t\treturn commit;\n> +\t}\n> +\n\nAnd this change looks obviously correct to me. I'm glad that the\nimplementation actually doesn't care about the commit-graph, but\ninstead cares about using the \"standard\" parsing approach instead\nof side-stepping the commit-graph via parse_object().\n\nI took a quick look for other instances where we use parse_object()\nbut also know to expect a commit, but did not find one.\n\nThanks,\n-Stolee\n"},{"id":"431969","messageId":"xmqqczqtp0ip.fsf@gitster.g","threadId":"56214","inReplyTo":"08519b8ab6f395cffbcd5e530bfba6aaf64241a2.1628085347.git.ps@pks.im","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-08-04T17:45:02Z","receivedAt":"2021-08-04T17:45:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> -\tif (type == OBJ_COMMIT)\n> -\t\treturn (struct commit *) parse_object(the_repository, oid);\n> +\n> +\tif (type == OBJ_COMMIT) {\n> +\t\tstruct commit *commit = lookup_commit(the_repository, oid);\n> +\t\tif (!commit || repo_parse_commit(the_repository, commit))\n> +\t\t\treturn NULL;\n> +\t\treturn commit;\n> +\t}\n\nOK.\n\nAsking parse_object() to turn an object name to an in-core instance\nof the object is a pretty much standard and generic idiom, but in\nthis codepath, we have already asked for the type and know it must\nbe a commit, so asking parse_commit() that is more specialized makes\nquite a lot of sense.\n\nThanks.\n"},{"id":"431980","messageId":"YQr/vLNjZomIe1ME@coredump.intra.peff.net","threadId":"56214","inReplyTo":"08519b8ab6f395cffbcd5e530bfba6aaf64241a2.1628085347.git.ps@pks.im","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-08-04T20:59:40Z","receivedAt":"2021-08-04T20:59:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 04, 2021 at 03:56:11PM +0200, Patrick Steinhardt wrote:\n\n> When doing reference negotiation, git-fetch-pack(1) is loading all refs\n> from disk in order to determine which commits it has in common with the\n> remote repository. This can be quite expensive in repositories with many\n> references though: in a real-world repository with around 2.2 million\n> refs, fetching a single commit by its ID takes around 44 seconds.\n> \n> Dominating the loading time is decompression and parsing of the objects\n> which are referenced by commits. Given the fact that we only care about\n> commits (or tags which can be peeled to one) in this context, there is\n> thus an easy performance win by switching the parsing logic to make use\n> of the commit graph in case we have one available. Like this, we avoid\n> hitting the object database to parse these commits but instead only load\n> them from the commit-graph. This results in a significant performance\n> boost when executing git-fetch in said repository with 2.2 million refs:\n> \n>     Benchmark #1: HEAD~: git fetch $remote $commit\n>       Time (mean ± σ):     44.168 s ±  0.341 s    [User: 42.985 s, System: 1.106 s]\n>       Range (min … max):   43.565 s … 44.577 s    10 runs\n> \n>     Benchmark #2: HEAD: git fetch $remote $commit\n>       Time (mean ± σ):     19.498 s ±  0.724 s    [User: 18.751 s, System: 0.690 s]\n>       Range (min … max):   18.629 s … 20.454 s    10 runs\n> \n>     Summary\n>       'HEAD: git fetch $remote $commit' ran\n>         2.27 ± 0.09 times faster than 'HEAD~: git fetch $remote $commit'\n\nNice. I've sometimes wondered if parse_object() should be doing this\noptimization itself. Though we'd possibly still want callers (like this\none) to give us more hints, since we already know the type is\nOBJ_COMMIT. Whereas parse_object() would have to discover that itself\n(though we already incur the extra type lookup there to handle blobs).\n\nI wonder where the remaining 20s is going. Do you have a lot of tags in\nyour repository? We'll still parse all of those, which could be\nexpensive. There might be some benefit to using peel_iterated_ref(),\nwhich will make us of packed-ref's peel hints, but:\n\n  - you'd want to double check that we always call this during ref\n    iteration (it looks like we do, and I think peel_iterated_ref()\n    falls back to a normal peel otherwise)\n\n  - for a tag-of-tag-of-X, that will give us the complete peel to X. But\n    it looks like deref_without_lazy_fetch() marks intermediate tags\n    with the COMPLETE flag, too. I'm not sure how important that is\n    (i.e., is it necessary for correctness, or just an optimization, in\n    which case we might be better off guessing that tags are\n    single-layer, as it's by far the common case).\n\nIf we don't go that route, there's another possible speedup: after\nparsing a tag, the type of tag->tagged (if it is not NULL) will be known\nfrom the tag's contents, and we can avoid the oid_object_info_extended()\ntype lookup. It might need some extra surgery to convince the tag-parse\nnot to fetch promisor objects, though.\n\nI'm not sure it would make that big a difference, though. If we save one\ntype-lookup per parsed tag, then the tag parsing is likely to dwarf it.\n\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index b0c7be717c..0bf7ed7e47 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -137,8 +137,14 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid,\n>  \t\t\tbreak;\n>  \t\t}\n>  \t}\n> -\tif (type == OBJ_COMMIT)\n> -\t\treturn (struct commit *) parse_object(the_repository, oid);\n> +\n> +\tif (type == OBJ_COMMIT) {\n> +\t\tstruct commit *commit = lookup_commit(the_repository, oid);\n> +\t\tif (!commit || repo_parse_commit(the_repository, commit))\n> +\t\t\treturn NULL;\n> +\t\treturn commit;\n> +\t}\n\nLooks correct. You're using lookup_commit(), so we'll auto-create the\nstruct as necessary. If there's any kind of type mismatch (say,\npreviously we saw that oid as a non-commit), we'll get NULL there and\nbail, which makes sense. I think the original code could produce\nundefined behavior there if parse_object() found something other than\n\"type\", though in practice that is quite unlikely (since\noid_object_info() would have just gone to the on-disk odb to get the\ntype itself).\n\n-Peff\n"},{"id":"431986","messageId":"xmqqo8acnbfd.fsf@gitster.g","threadId":"56214","inReplyTo":"YQr/vLNjZomIe1ME@coredump.intra.peff.net","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-08-04T21:32:22Z","receivedAt":"2021-08-04T21:32:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Nice. I've sometimes wondered if parse_object() should be doing this\n> optimization itself. Though we'd possibly still want callers (like this\n> one) to give us more hints, since we already know the type is\n> OBJ_COMMIT. Whereas parse_object() would have to discover that itself\n> (though we already incur the extra type lookup there to handle blobs).\n\nAhh, you read one step further than I did ;-) Yes, if we are already\ninspecting type there, doing this optimization inside parse_object()\nbecomes much easier to justify.\n"},{"id":"432054","messageId":"YQt/g0iZxAVgw66o@ncase","threadId":"56214","inReplyTo":"YQr/vLNjZomIe1ME@coredump.intra.peff.net","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-08-05T06:04:51Z","receivedAt":"2021-08-05T06:06:15Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Aug 04, 2021 at 04:59:40PM -0400, Jeff King wrote:\n> On Wed, Aug 04, 2021 at 03:56:11PM +0200, Patrick Steinhardt wrote:\n> \n> > When doing reference negotiation, git-fetch-pack(1) is loading all refs\n> > from disk in order to determine which commits it has in common with the\n> > remote repository. This can be quite expensive in repositories with many\n> > references though: in a real-world repository with around 2.2 million\n> > refs, fetching a single commit by its ID takes around 44 seconds.\n> > \n> > Dominating the loading time is decompression and parsing of the objects\n> > which are referenced by commits. Given the fact that we only care about\n> > commits (or tags which can be peeled to one) in this context, there is\n> > thus an easy performance win by switching the parsing logic to make use\n> > of the commit graph in case we have one available. Like this, we avoid\n> > hitting the object database to parse these commits but instead only load\n> > them from the commit-graph. This results in a significant performance\n> > boost when executing git-fetch in said repository with 2.2 million refs:\n> > \n> >     Benchmark #1: HEAD~: git fetch $remote $commit\n> >       Time (mean ± σ):     44.168 s ±  0.341 s    [User: 42.985 s, System: 1.106 s]\n> >       Range (min … max):   43.565 s … 44.577 s    10 runs\n> > \n> >     Benchmark #2: HEAD: git fetch $remote $commit\n> >       Time (mean ± σ):     19.498 s ±  0.724 s    [User: 18.751 s, System: 0.690 s]\n> >       Range (min … max):   18.629 s … 20.454 s    10 runs\n> > \n> >     Summary\n> >       'HEAD: git fetch $remote $commit' ran\n> >         2.27 ± 0.09 times faster than 'HEAD~: git fetch $remote $commit'\n> \n> Nice. I've sometimes wondered if parse_object() should be doing this\n> optimization itself. Though we'd possibly still want callers (like this\n> one) to give us more hints, since we already know the type is\n> OBJ_COMMIT. Whereas parse_object() would have to discover that itself\n> (though we already incur the extra type lookup there to handle blobs).\n\nWould certainly make it much harder to hit this pitfall. The only thing\none needs to be cautious about is that we need to somehow assert the\nobject still exists in our ODB. Otherwise you may look up a commit via\nthe commit-graph even though the commit doesn't exist anymore.\n\n> Do you have a lot of tags in your repository?\n\nNo, it's only about 2000 tags.\n\n> I wonder where the remaining 20s is going. \n\nRebasing this commit on top of my git-rev-list(1) series [1] for the\nconnectivity check gives another 25% speedup, going down from 20s to 14s\n(numbers are a bit different given that I'm on a different machine right\nnow). From here on, it's multiple things which take time:\n\n    - 20% of the time is spent sorting the refs in\n      `mark_complete_and_common_ref()`. This time around I feel less\n      comfortable to just disable sorting given that it may impact\n      correctness.\n\n    - 30% of the time is spent looking up object types via\n      `oid_object_info_extended()`, where 75% of these lookups come from\n      `deref_without_lazy_fetch()`. This can be improved a bit by doing\n      the `lookup_unknown_object()` dance, buying a modest speedup of\n      ~8%. But this again has memory tradeoffs given that we must\n      allocate the object such that all types would fit.\n\nOther than that I don't see any obvious things in the flame graphs. In\ncase anybody is interested, I've posted flame graphs in our GitLab issue\nat [2], with the state before this patch, with this patch and in\ncombination with [1].\n\n[1]: http://public-inbox.org/git/cover.1627896460.git.ps@pks.im/\n[2]: https://gitlab.com/gitlab-org/gitlab/-/issues/336657#note_642957933\n\n>   - you'd want to double check that we always call this during ref\n>     iteration (it looks like we do, and I think peel_iterated_ref()\n>     falls back to a normal peel otherwise)\n> \n>   - for a tag-of-tag-of-X, that will give us the complete peel to X. But\n>     it looks like deref_without_lazy_fetch() marks intermediate tags\n>     with the COMPLETE flag, too. I'm not sure how important that is\n>     (i.e., is it necessary for correctness, or just an optimization, in\n>     which case we might be better off guessing that tags are\n>     single-layer, as it's by far the common case).\n> \n> If we don't go that route, there's another possible speedup: after\n> parsing a tag, the type of tag->tagged (if it is not NULL) will be known\n> from the tag's contents, and we can avoid the oid_object_info_extended()\n> type lookup. It might need some extra surgery to convince the tag-parse\n> not to fetch promisor objects, though.\n> \n> I'm not sure it would make that big a difference, though. If we save one\n> type-lookup per parsed tag, then the tag parsing is likely to dwarf it.\n\nYeah, I'd assume the same. And in any case, our repo doesn't really have\nany problems with tags given that there's so few of them. So I wouldn't\nreally have the data to back up any performance improvements here.\n\nPatrick\n"},{"id":"432100","messageId":"YQvRTpJ0NGakTy9W@ncase","threadId":"56214","inReplyTo":"YQt/g0iZxAVgw66o@ncase","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-08-05T11:53:50Z","receivedAt":"2021-08-05T11:54:02Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Aug 05, 2021 at 08:04:53AM +0200, Patrick Steinhardt wrote:\n> On Wed, Aug 04, 2021 at 04:59:40PM -0400, Jeff King wrote:\n> > On Wed, Aug 04, 2021 at 03:56:11PM +0200, Patrick Steinhardt wrote:\n[snip]\n> > I wonder where the remaining 20s is going. \n> \n> Rebasing this commit on top of my git-rev-list(1) series [1] for the\n> connectivity check gives another 25% speedup, going down from 20s to 14s\n> (numbers are a bit different given that I'm on a different machine right\n> now). From here on, it's multiple things which take time:\n> \n>     - 20% of the time is spent sorting the refs in\n>       `mark_complete_and_common_ref()`. This time around I feel less\n>       comfortable to just disable sorting given that it may impact\n>       correctness.\n> \n>     - 30% of the time is spent looking up object types via\n>       `oid_object_info_extended()`, where 75% of these lookups come from\n>       `deref_without_lazy_fetch()`. This can be improved a bit by doing\n>       the `lookup_unknown_object()` dance, buying a modest speedup of\n>       ~8%. But this again has memory tradeoffs given that we must\n>       allocate the object such that all types would fit.\n> \n> Other than that I don't see any obvious things in the flame graphs. In\n> case anybody is interested, I've posted flame graphs in our GitLab issue\n> at [2], with the state before this patch, with this patch and in\n> combination with [1].\n> \n> [1]: http://public-inbox.org/git/cover.1627896460.git.ps@pks.im/\n> [2]: https://gitlab.com/gitlab-org/gitlab/-/issues/336657#note_642957933\n\nI've put some more time into this. If rebased on top of v4 of [1], then\nwe can also use `parse_commit_in_graph_gently()` to further speed this\nup from 15.8 seconds to 11.6 seconds with below patch. It's the same\nmemory/speed tradeoff as I'm doing in [1].\n\nI guess I'd still like to treat both series separately for now given\nthat [1] is more involved compared to this patch series here. I'll then\ndo a follow-up when (if?) both series have landed.\n\nPatrick\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 0bf7ed7e47..cc8b2ffa6c 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -119,6 +119,17 @@ static struct commit *deref_without_lazy_fetch(const struct object_id *oid,\n {\n \tenum object_type type;\n \tstruct object_info info = { .typep = &type };\n+\tstruct object *object = lookup_unknown_object(the_repository, oid);\n+\n+\tif (object->type == OBJ_COMMIT)\n+\t\treturn (struct commit *) object;\n+\n+\tif (object->type == OBJ_NONE &&\n+\t    parse_commit_in_graph_gently(the_repository, object) == 0) {\n+\t\tif (!repo_has_object_file(the_repository, oid))\n+\t\t\treturn NULL;\n+\t\treturn (struct commit *) object;\n+\t}\n\n \twhile (1) {\n \t\tif (oid_object_info_extended(the_repository, oid, &info,\n"},{"id":"432119","messageId":"xmqqtuk3luwc.fsf@gitster.g","threadId":"56214","inReplyTo":"YQvRTpJ0NGakTy9W@ncase","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-08-05T16:26:59Z","receivedAt":"2021-08-05T16:27:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> I've put some more time into this. If rebased on top of v4 of [1], then\n> we can also use `parse_commit_in_graph_gently()` to further speed this\n> up from 15.8 seconds to 11.6 seconds with below patch. It's the same\n> memory/speed tradeoff as I'm doing in [1].\n\nSounds good.\n\n> I guess I'd still like to treat both series separately for now given\n> that [1] is more involved compared to this patch series here. I'll then\n> do a follow-up when (if?) both series have landed.\n\nDuring the pre-release freeze (cf. https://tinyurl.com/gitCal), new\ntopics will not \"land\" anywhere so you have two weeks or so to\nstabilize the base topic.  I would prefer not to have to worry about\ninter-dependent multiple topics anyway, especially the ones that are\nnot relevant to the upcoming release during a pre-release period.\n\nThanks.\n"},{"id":"432125","messageId":"87y29fzp5f.fsf@evledraar.gmail.com","threadId":"56214","inReplyTo":"YQr/vLNjZomIe1ME@coredump.intra.peff.net","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-08-05T19:05:59Z","receivedAt":"2021-08-05T19:07:29Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Aug 04 2021, Jeff King wrote:\n\n> [...]\n> If we don't go that route, there's another possible speedup: after\n> parsing a tag, the type of tag->tagged (if it is not NULL) will be known\n> from the tag's contents, and we can avoid the oid_object_info_extended()\n> type lookup. It might need some extra surgery to convince the tag-parse\n> not to fetch promisor objects, though.\n>\n> I'm not sure it would make that big a difference, though. If we save one\n> type-lookup per parsed tag, then the tag parsing is likely to dwarf it.\n\nExcept that the tag type can be a lie, as our tests and some recent\nobject/fsck serieses (not yet integrated) from me show. It can be relied\nupon for >99.99% of cases, but code like that needs to make sure it's\nnot segfaulting or whatever if that relationship doesn't hold.\n"},{"id":"432132","messageId":"YQxKEyHXm2W2Y3M5@coredump.intra.peff.net","threadId":"56214","inReplyTo":"87y29fzp5f.fsf@evledraar.gmail.com","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-08-05T20:29:07Z","receivedAt":"2021-08-05T20:29:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 05, 2021 at 09:05:59PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> \n> On Wed, Aug 04 2021, Jeff King wrote:\n> \n> > [...]\n> > If we don't go that route, there's another possible speedup: after\n> > parsing a tag, the type of tag->tagged (if it is not NULL) will be known\n> > from the tag's contents, and we can avoid the oid_object_info_extended()\n> > type lookup. It might need some extra surgery to convince the tag-parse\n> > not to fetch promisor objects, though.\n> >\n> > I'm not sure it would make that big a difference, though. If we save one\n> > type-lookup per parsed tag, then the tag parsing is likely to dwarf it.\n> \n> Except that the tag type can be a lie, as our tests and some recent\n> object/fsck serieses (not yet integrated) from me show. It can be relied\n> upon for >99.99% of cases, but code like that needs to make sure it's\n> not segfaulting or whatever if that relationship doesn't hold.\n\nYes, but we'd discover that when we called repo_parse_commit(), and\nPatrick's patch already handles failure there.\n\n-Peff\n"},{"id":"432134","messageId":"YQxMsDUNndA2KWbS@coredump.intra.peff.net","threadId":"56214","inReplyTo":"YQt/g0iZxAVgw66o@ncase","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-08-05T20:40:16Z","receivedAt":"2021-08-05T20:40:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 05, 2021 at 08:04:51AM +0200, Patrick Steinhardt wrote:\n\n> > Nice. I've sometimes wondered if parse_object() should be doing this\n> > optimization itself. Though we'd possibly still want callers (like this\n> > one) to give us more hints, since we already know the type is\n> > OBJ_COMMIT. Whereas parse_object() would have to discover that itself\n> > (though we already incur the extra type lookup there to handle blobs).\n> \n> Would certainly make it much harder to hit this pitfall. The only thing\n> one needs to be cautious about is that we need to somehow assert the\n> object still exists in our ODB. Otherwise you may look up a commit via\n> the commit-graph even though the commit doesn't exist anymore.\n\nTrue, though what I really wonder is what exactly people are depending\non parse_object() for. I.e., how many callers care about making sure it\nexists, and how many would be happy to have things magically go faster?\n\nI'm not sure of a good way to answer that question, but I agree it's the\nsticking point on pushing the optimization down to that lower level.\n\n(In case it's not clear, this is all a question for the future, and\nshouldn't hold up your patch).\n\n> > Do you have a lot of tags in your repository?\n> \n> No, it's only about 2000 tags.\n\nHmm. In that case, I wonder if we could be using the ref peel data in\nthe opposite direction:\n\n  0. With modern packed-refs, the file tells us definitely whether an\n     object was peel-able or not.\n\n  1. If it is peel-able, then do the same tag-peeling we do now.  This\n     handles the intermediate stages, etc, and the optimization doesn't\n     help us.\n\n  2. If it isn't peel-able, then we know it's not a tag. We can\n     _guess_ that it's a commit, because most refs that point to\n     non-tags are, and try to look it up in the commit graph.\n\n  3. If we do find it in the commit graph, we win. We saved having to\n     call oid_object_info() to get the type.\n\n  4. If we didn't, then we have to get the real type (it might simply be\n     a commit that isn't in the graph files), and we lose. We did a\n     pointless lookup in the graph file.\n\nI think in general we'd win on balance, because most refs do point to\ncommits. But I'm not sure how big the win would be. You'd have to time\nit on your weird 2M-ref case (though your numbers below suggest it may\nbe a few seconds).\n\n(And I know I'm spouting a lot of micro-optimization ideas here; I won't\nbe offended if you don't feel like following up on them).\n\n> > I wonder where the remaining 20s is going. \n> \n> Rebasing this commit on top of my git-rev-list(1) series [1] for the\n> connectivity check gives another 25% speedup, going down from 20s to 14s\n> (numbers are a bit different given that I'm on a different machine right\n> now). From here on, it's multiple things which take time:\n> \n>     - 20% of the time is spent sorting the refs in\n>       `mark_complete_and_common_ref()`. This time around I feel less\n>       comfortable to just disable sorting given that it may impact\n>       correctness.\n> \n>     - 30% of the time is spent looking up object types via\n>       `oid_object_info_extended()`, where 75% of these lookups come from\n>       `deref_without_lazy_fetch()`. This can be improved a bit by doing\n>       the `lookup_unknown_object()` dance, buying a modest speedup of\n>       ~8%. But this again has memory tradeoffs given that we must\n>       allocate the object such that all types would fit.\n\nThanks, that all makes sense.\n\nI think the suggestion I made above is similar to what you're thinking\nwith lookup_unknown_commit(), but would avoid the extra allocations.\n\n-Peff\n"},{"id":"432136","messageId":"YQxNQJNGOZW6CR6L@coredump.intra.peff.net","threadId":"56214","inReplyTo":"YQvRTpJ0NGakTy9W@ncase","subject":"Re: [PATCH] fetch-pack: speed up loading of refs via commit graph","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-08-05T20:42:40Z","receivedAt":"2021-08-05T20:42:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 05, 2021 at 01:53:50PM +0200, Patrick Steinhardt wrote:\n\n> I've put some more time into this. If rebased on top of v4 of [1], then\n> we can also use `parse_commit_in_graph_gently()` to further speed this\n> up from 15.8 seconds to 11.6 seconds with below patch. It's the same\n> memory/speed tradeoff as I'm doing in [1].\n> \n> I guess I'd still like to treat both series separately for now given\n> that [1] is more involved compared to this patch series here. I'll then\n> do a follow-up when (if?) both series have landed.\n\nHeh, I should have read this before writing my other response. Your\nstrategy here is what I imagined. If you split the find/fill steps from\nparse_commit_in_graph(), then you should be able to speculatively ask\n\"if this is a commit in the graph, fill it in, otherwise do nothing\".\nWhich would solve the memory tradeoff.\n\n-Peff\n"}]}