{"thread":{"id":"62517","subject":"git-blame extremely slow in partial clones due to serial object fetching","startedAt":"2024-11-19T20:17:06Z","lastAt":"2024-11-25T00:22:23Z","messageCount":10,"participants":["Burke Libbey","Manoraj K","Jonathan Tan","Junio C Hamano","Han Young","Shubham Kanodia"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"507642","messageId":"B010051F-B182-4DB8-9469-AA2F53781968@shopify.com","threadId":"62517","inReplyTo":null,"subject":"git-blame extremely slow in partial clones due to serial object fetching","fromName":"Burke Libbey","fromEmail":"burke.libbey@shopify.com","sentAt":"2024-11-19T20:16:53Z","receivedAt":"2024-11-19T20:17:06Z","isPatch":false,"sender":{"key":"burke.libbey@shopify.com","avatar":null},"body":"When running git-blame in a partial clone (--filter=blob:none), it fetches\nmissing blob objects one at a time. This can result in thousands of serial fetch\noperations, making blame extremely slow, regardless of network latency.\n\nFor example, in one large repository, blaming a single large file required \nfetching about 6500 objects. Each fetch requiring a round-trip means this \noperation would have taken something on the order of an hour to complete.\n\nThe core issue appears to be in fill_origin_blob(), which is called\nindividually for each blob needed during the blame process. While the blame\nalgorithm does need blob contents to make detailed line-matching decisions,\nit seems like we don't necessarily need the contents just to determine which \nblobs we'llexamine.\n\nIt seems like this could be optimized by batch-fetching the needed objects\nupfront, rather than fetching them one at a time. This would convert O(n)\nround-trips into a small number of batch fetches.\n\nReproduction:\n1. Create a partial clone with --filter=blob:none\n2. Run git blame on a file with significant history\n3. Observe serial fetching of objects in the trace output\n\nLet me know if you need any additional information to investigate this issue.\n\n—burke"},{"id":"507727","messageId":"20241120115910.45681-1-mkenchugonde@atlassian.com","threadId":"62517","inReplyTo":"B010051F-B182-4DB8-9469-AA2F53781968@shopify.com","subject":"Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Manoraj K","fromEmail":"kmr.manu535@gmail.com","sentAt":"2024-11-20T11:59:10Z","receivedAt":"2024-11-20T11:59:15Z","isPatch":false,"sender":{"key":"kmr.manu535@gmail.com","avatar":null},"body":"Hi Burke,\n\n> When running git-blame in a partial clone (--filter=blob:none), it fetches\n> missing blob objects one at a time. This can result in thousands of serial fetch\n> operations, making blame extremely slow, regardless of network latency.\n\nWe are also experiencing this issue with partial clones. Have you found any \nworkarounds since reporting this?\n\nGit team - would appreciate any insights or suggestions on handling this\nperformance bottleneck in the meantime.\n\nBest regards,\nManoraj K\n"},{"id":"507772","messageId":"20241120185228.3204236-1-jonathantanmy@google.com","threadId":"62517","inReplyTo":"B010051F-B182-4DB8-9469-AA2F53781968@shopify.com","subject":"Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2024-11-20T18:52:28Z","receivedAt":"2024-11-20T18:52:31Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Burke Libbey <burke.libbey@shopify.com> writes:\n> The core issue appears to be in fill_origin_blob(), which is called\n> individually for each blob needed during the blame process. While the blame\n> algorithm does need blob contents to make detailed line-matching decisions,\n> it seems like we don't necessarily need the contents just to determine which \n> blobs we'llexamine.\n\nTechnically, we do need the contents, because the contents determine\nwhether we are done with the blame (all lines are accounted for)\nand whether we need to start looking at the blob at a different path\n(because there was a rename).\n\n> It seems like this could be optimized by batch-fetching the needed objects\n> upfront, rather than fetching them one at a time. This would convert O(n)\n> round-trips into a small number of batch fetches.\n\nThat is one possible way (assuming you mean that whenever \"git blame\"\nnotices that a blob is missing, it should walk the commits until a\ncertain depth, collecting all the object IDs for a given path, and\nprefetching all of them). This runs the risk of overfetching, as I\nstated above, but perhaps overfetching is an acceptable tradeoff for\nspeed.\n\nThere are other ways:\n\n - If we can teach the client to collect object IDs for prefetching,\n   perhaps it would be just as easy to teach the server. We could\n   instead make filter-by-path an acceptable argument to pass to \"fetch\n   --filter\", then teach the lazy fetch to use that argument. This also\n   opens the door to future performance improvements - since the server\n   has all the objects, it can give us precisely the objects that we\n   need, and not just give us a quantity of objects based on a heuristic\n   (so the client does not need to say \"give me 10, and if I need more,\n   I'll ask you again\", but can say \"give me all I need to complete\n   the blame). This, however, relies on server implementers to implement\n   and turn on such a feature.\n\n - We could also teach the server to \"blame\" a file for us and then\n   teach the client to stitch together the server's result with the\n   local findings, but this is more complicated.\n\nIt may also be possible that even if we fix this issue, the scale of the\nrepos involved might be such that a user would rather \"blame\" over the\nnetwork (e.g. using a web UI) than download all the relevant blobs (even\nif the blobs were batched into one download).\n\nSo...there are ideas for solutions, but I don't think anyone has\nanalyzed them (or tried them) yet.\n"},{"id":"507792","messageId":"xmqqikshikgz.fsf@gitster.g","threadId":"62517","inReplyTo":"20241120185228.3204236-1-jonathantanmy@google.com","subject":"Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-11-20T22:55:24Z","receivedAt":"2024-11-20T22:55:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> Technically, we do need the contents, ...\n> There are other ways:\n>\n>  - If we can teach the client to collect object IDs for prefetching,\n>    perhaps it would be just as easy to teach the server. We could\n>    instead make filter-by-path an acceptable argument to pass to \"fetch\n>    --filter\", then teach the lazy fetch to use that argument. This also\n>    opens the door to future performance improvements - since the server\n>    has all the objects, it can give us precisely the objects that we\n>    need, and not just give us a quantity of objects based on a heuristic\n>    (so the client does not need to say \"give me 10, and if I need more,\n>    I'll ask you again\", but can say \"give me all I need to complete\n>    the blame). This, however, relies on server implementers to implement\n>    and turn on such a feature.\n\nThis is an interesting half-way point, but I have a suspicion that\nin order for the server side to give you all you need, the server\nside has to do something close to computing the full blame.  Start\nfrom a child commit plus the entire file as input, find blocks of\ntext in that entire file that are different in its parent (these are\nthe lines that are \"blamed\" to the child commit), pass control to\nthe same algorithm but using the parent commit plus the remainder of\nthe file (excluding the lines of text that have already \"blamed\") as\nthe input, rinse and repeat, until the \"remainder of the file\"\nshrinks to empty.  When everything is \"blamed\", you know you can\nstop.\n\nSo, a server that can give you something better than a heuristic\nwould have spent enough cycles to know the final result of \"blame\"\nby the time it knows where it should/can stop, wouldn't it?\n\n>  - We could also teach the server to \"blame\" a file for us and then\n>    teach the client to stitch together the server's result with the\n>    local findings, but this is more complicated.\n\nYour local lazy repository, if you have anything you have to \"stitch\ntogether\", would have your locally modified contents, and for you to\nbe able to make such modifications, it would also have at least the\nblobs from HEAD, which you based your modifications on.  So you\nshould be able to locally run \"git blame @{u}..\" to find lines that\nyour locally modified contents are to be blamed, ask the other side\nto give you a blame for @{u}, and overlay the former on top of the\nlatter.  \n"},{"id":"507804","messageId":"CAG1j3zEEN5EJwTsM3q87gCSqXG4+=DZVvcQdDhoj5Epe-S0nPw@mail.gmail.com","threadId":"62517","inReplyTo":"xmqqikshikgz.fsf@gitster.g","subject":"Re: [External] Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Han Young","fromEmail":"hanyang.tony@bytedance.com","sentAt":"2024-11-21T03:12:12Z","receivedAt":"2024-11-21T03:12:24Z","isPatch":false,"sender":{"key":"hanyang.tony@bytedance.com","avatar":"https://avatars.githubusercontent.com/u/108711387?v=4"},"body":"On Thu, Nov 21, 2024 at 7:00 AM Junio C Hamano <gitster@pobox.com> wrote:\n> >  - We could also teach the server to \"blame\" a file for us and then\n> >    teach the client to stitch together the server's result with the\n> >    local findings, but this is more complicated.\n>\n> Your local lazy repository, if you have anything you have to \"stitch\n> together\", would have your locally modified contents, and for you to\n> be able to make such modifications, it would also have at least the\n> blobs from HEAD, which you based your modifications on.  So you\n> should be able to locally run \"git blame @{u}..\" to find lines that\n> your locally modified contents are to be blamed, ask the other side\n> to give you a blame for @{u}, and overlay the former on top of the\n> latter.\n>\n\nIn $DAY_JOB, we modified the server to run blame for the client.\nTo deal with changes not yet pushed to the server, we let client\npack the local only blobs for the blamed file, alone with the local\nonly commits that touch that file into one packfile and send a\n'remote-blame' request to the server.\n\nServer then unpack the relevant objects into memory\n(by reusing code from git-unpack-objects), run the blame and return\nthe result back to the client. This way we avoided running blame both\ntwice and interleave the results.\n\nIt works quite well in very large repos, with result caching, the speed\ncan be even faster than locally blame on a full repo.\n"},{"id":"507880","messageId":"972d0904-650b-4161-a13c-e3081d55a212@gmail.com","threadId":"62517","inReplyTo":"CAG1j3zEEN5EJwTsM3q87gCSqXG4+=DZVvcQdDhoj5Epe-S0nPw@mail.gmail.com","subject":"Re: [External] Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Shubham Kanodia","fromEmail":"shubham.kanodia10@gmail.com","sentAt":"2024-11-22T03:32:08Z","receivedAt":"2024-11-22T03:32:13Z","isPatch":false,"sender":{"key":"shubham.kanodia10@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8946207?v=4"},"body":"\n\nOn 21/11/24 8:42 am, Han Young wrote:\n> On Thu, Nov 21, 2024 at 7:00 AM Junio C Hamano <gitster@pobox.com> wrote:\n>>>   - We could also teach the server to \"blame\" a file for us and then\n>>>     teach the client to stitch together the server's result with the\n>>>     local findings, but this is more complicated.\n>>\n>> Your local lazy repository, if you have anything you have to \"stitch\n>> together\", would have your locally modified contents, and for you to\n>> be able to make such modifications, it would also have at least the\n>> blobs from HEAD, which you based your modifications on.  So you\n>> should be able to locally run \"git blame @{u}..\" to find lines that\n>> your locally modified contents are to be blamed, ask the other side\n>> to give you a blame for @{u}, and overlay the former on top of the\n>> latter.\n>>\n> \n> In $DAY_JOB, we modified the server to run blame for the client.\n> To deal with changes not yet pushed to the server, we let client\n> pack the local only blobs for the blamed file, alone with the local\n> only commits that touch that file into one packfile and send a\n> 'remote-blame' request to the server.\n> \n> Server then unpack the relevant objects into memory\n> (by reusing code from git-unpack-objects), run the blame and return\n> the result back to the client. This way we avoided running blame both\n> twice and interleave the results.\n> \n> It works quite well in very large repos, with result caching, the speed\n> can be even faster than locally blame on a full repo.\n\nIn a large sized partially cloned repo that I have, a `git blame` can \ntake several minutes and network roundtrips.\n\nJunio — would it make sense to add an option (and config) for `git \nblame` that limits how far back it looks for fetching blobs? This would \nprevent someone accidently firing several cascading calls as they open \nnew files in an editor that does git blame by default (IntelliJ) or \npopular plugins (GitLens for VSCode) that can startup multiple heavy git \nprocesses and bring a user's system to a crawl.\n"},{"id":"507888","messageId":"xmqqv7wf8ydw.fsf@gitster.g","threadId":"62517","inReplyTo":"972d0904-650b-4161-a13c-e3081d55a212@gmail.com","subject":"Re: [External] Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-11-22T08:29:31Z","receivedAt":"2024-11-22T08:29:35Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shubham Kanodia <shubham.kanodia10@gmail.com> writes:\n\n> Junio — would it make sense to add an option (and config) for `git\n> blame` that limits how far back it looks for fetching blobs?\n\nNo, I do not think it would.\n\nWhat would our workaround for the next one when people say \"oh, 'git\nlog -p' fetches blobs on demand and latency kills me\"?  Yet another\nsuch an option only for 'git log'?\n\n"},{"id":"507890","messageId":"dd8b5cdb-2ce8-4ad6-ae96-197fa898b206@gmail.com","threadId":"62517","inReplyTo":"xmqqv7wf8ydw.fsf@gitster.g","subject":"Re: [External] Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Shubham Kanodia","fromEmail":"shubham.kanodia10@gmail.com","sentAt":"2024-11-22T08:51:47Z","receivedAt":"2024-11-22T08:51:51Z","isPatch":false,"sender":{"key":"shubham.kanodia10@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8946207?v=4"},"body":"\n\nOn 22/11/24 1:59 pm, Junio C Hamano wrote:\n> Shubham Kanodia <shubham.kanodia10@gmail.com> writes:\n> \n>> Junio — would it make sense to add an option (and config) for `git\n>> blame` that limits how far back it looks for fetching blobs?\n> \n> No, I do not think it would.\n> \n> What would our workaround for the next one when people say \"oh, 'git\n> log -p' fetches blobs on demand and latency kills me\"?  Yet another\n> such an option only for 'git log'?\n> \n\nI'm guessing `git log` already provides options to limit history using \n`-n` or `--since` so ideally its not unbounded if you use those, unlike \nwith `git blame`?\n\n\nI understand our concerns regarding adding new config options though. \nBetween the solutions discussed in this thread — batching, adding server \nside support, (or another) — what do you think could be a good track to \npursue here because this makes using `git blame` on larger partially \ncloned repos a possible footgun.\n\n\n"},{"id":"507949","messageId":"20241122175536.510952-1-jonathantanmy@google.com","threadId":"62517","inReplyTo":"dd8b5cdb-2ce8-4ad6-ae96-197fa898b206@gmail.com","subject":"Re: [External] Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2024-11-22T17:55:35Z","receivedAt":"2024-11-22T17:55:40Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Shubham Kanodia <shubham.kanodia10@gmail.com> writes:\n> \n> \n> On 22/11/24 1:59 pm, Junio C Hamano wrote:\n> > Shubham Kanodia <shubham.kanodia10@gmail.com> writes:\n> > \n> >> Junio — would it make sense to add an option (and config) for `git\n> >> blame` that limits how far back it looks for fetching blobs?\n> > \n> > No, I do not think it would.\n> > \n> > What would our workaround for the next one when people say \"oh, 'git\n> > log -p' fetches blobs on demand and latency kills me\"?  Yet another\n> > such an option only for 'git log'?\n> > \n> \n> I'm guessing `git log` already provides options to limit history using \n> `-n` or `--since` so ideally its not unbounded if you use those, unlike \n> with `git blame`?\n\n`git blame` also has options. See \"SPECIFYING RANGES\" in its man page,\nwhich teaches you how to specify revision ranges (and also line ranges,\nbut that is not relevant here).\n\n> I understand our concerns regarding adding new config options though. \n> Between the solutions discussed in this thread — batching, adding server \n> side support, (or another) — what do you think could be a good track to \n> pursue here because this makes using `git blame` on larger partially \n> cloned repos a possible footgun.\n\nTypically questions like this should be answered by the person who is\nactually going to pursue the track. If you'd like to pursue a track but\ndon't know which to pursue, maybe start with what you believe the best\nsolution to be. It seems that you think that limiting either the number\nof blobs fetched or the time range of the commits to be considered is\nbest, so maybe you could try one of them.\n\nLimiting the time range is already possible, so I'll provide my ideas\naboult limiting the number of blobs fetched. You can detect when\na blob is missing (and therefore needs to be fetched) by a flag in\noid_object_info_extended() (or use has_object()), so you can count the\nnumber of blobs fetched as the blame is being run. My biggest concern\nis that there is no good limit - I suspect that for a file that is\nextensively changed, 10 blobs is too few and you'll need something like\n50 blobs. But 50 blobs means 50 RTTs, which also might be too much for\nan end user. But in any case, you know your users' needs better than\nwe do.\n"},{"id":"507998","messageId":"xmqq4j3w9n7n.fsf@gitster.g","threadId":"62517","inReplyTo":"20241122175536.510952-1-jonathantanmy@google.com","subject":"Re: [External] Re: git-blame extremely slow in partial clones due to serial object fetching","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-11-25T00:22:20Z","receivedAt":"2024-11-25T00:22:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> number of blobs fetched as the blame is being run. My biggest concern\n> is that there is no good limit - I suspect that for a file that is\n> extensively changed, 10 blobs is too few and you'll need something like\n> 50 blobs. But 50 blobs means 50 RTTs, which also might be too much for\n> an end user.\n\nDepending on the project, size of a typical change to a blob may be\ndifferent, so \"10 commits that touched this blob\" may touch 20% of\nthe contents in one project, but in another that tends to prefer\nfiner-grained commits, it may take 50 commits to make the same\namount of change.\n\nI agree with you that there is no good default that fits all\nprojects.\n\nDo 50 blobs have to mean 50 RTTs?  I wonder if there is a good way\nto say \"please give me all necessary tree and blob objects to\ncomplete the blobs at path $F for the past 50 commits\" to the lazy\nfetch machinery and receive a single pack that contain all the\nobjects that are listed in \"git rev-list --objects HEAD~50.. -- $F\"?\n\nI am not sure what should happen in the commit in that range where\nthe path $F appears (meaning: the path did not exist, and its\ncontents came from a different path in the parent of that commit).\nYou'd need (a subset of) objects in \"git rev-list --objects C^!\" for\nthat commit to find out where it came from, but what subset should\nwe use?  Fully hydrating the trees of these commits at the rename\nboundary would ensure you'd catch the same rename in a non-lazy\nrepository, but that is way too much more than what the user can\nafford (otherwise, you wouldn't be using a narrow clone in the first\nplace).  So, I dunno.\n\n"}]}