{"thread":{"id":"62423","subject":"[BUG] \"git describe --match\" performance","startedAt":"2024-10-30T04:43:24Z","lastAt":"2024-10-31T19:01:08Z","messageCount":10,"participants":["Josh Poimboeuf","Jeff King","Kristoffer Haugsbakk","Taylor Blau"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"506312","messageId":"20241030044322.b5n3ji2n6gaeo5u6@treble.attlocal.net","threadId":"62423","inReplyTo":null,"subject":"[BUG] \"git describe --match\" performance","fromName":"Josh Poimboeuf","fromEmail":"jpoimboe@kernel.org","sentAt":"2024-10-30T04:43:22Z","receivedAt":"2024-10-30T04:43:24Z","isPatch":false,"sender":{"key":"jpoimboe@kernel.org","avatar":null},"body":"> Thank you for filling out a Git bug report!\n> Please answer the following questions to help us understand your issue.\n> \n> What did you do before the bug happened? (Steps to reproduce your issue)\n\n$ git clone https://github.com/torvalds/linux\n$ cd linux\n$ git checkout c61e41121036\n\n$ time git describe --match=v6.10-rc7 --debug\ndescribe HEAD\nNo exact match on refs or tags, searching to describe\nfinished search at d8470b7c13e11c18cf14a7e3180f0b00e715e4f0\n annotated       1844 v6.10-rc7\ntraversed 1282750 commits\nv6.10-rc7-1844-gc61e41121036\n\nreal\t0m9.243s\nuser\t0m8.940s\nsys\t0m0.268s\n\n$ time git describe\nv6.10-rc7-1844-gc61e41121036\n\nreal\t0m0.149s\nuser\t0m0.111s\nsys\t0m0.036s\n\n> What did you expect to happen? (Expected behavior)\n\nI expected \"git describe --match=v6.10-rc7\" to be faster than plain \"git\ndescribe\".\n\n> What happened instead? (Actual behavior)\n\nIt takes over 9 seconds and traverses 1282750 commits.\n\n(In my actual Linux git repo it's even worse at 15 seconds due to more\ngit history.)\n\n> What's different between what you expected and what actually happened?\n\nOver 9 seconds :-)\n\n> Anything else you want to add:\n\nI see this with both version 2.47.0 and the next branch.\n\nThis command is used by the kernel setlocalversion script, which is run\nfor every kernel build, so it adds 10-15 seconds to every build on an\nuntagged commit.\n\nI suspect the problem is that there's only a single match for\n\"v6.10-rc7\", but it tries to find 10 candidates so it ends up searching\nthe entire history.  But \"--candidates=1\" doesn't seem to help unless I\nadd a second match like so:\n\n$ time git describe --match=v6.10-rc7 --match=v6.10-rc6 --candidates=1\nv6.10-rc7-1844-gc61e41121036\n\nreal\t0m0.112s\nuser\t0m0.081s\nsys\t0m0.031s\n\n> Please review the rest of the bug report below.\n> You can delete any lines you don't wish to share.\n\n[System Info]\ngit version:\ngit version 2.47.0\ncpu: x86_64\nno commit associated with this build\nsizeof-long: 8\nsizeof-size_t: 8\nshell-path: /bin/sh\nlibcurl: 8.6.0\nOpenSSL: OpenSSL 3.2.2 4 Jun 2024\nzlib: 1.3.1.zlib-ng\nuname: Linux 6.10.12-200.fc40.x86_64 #1 SMP PREEMPT_DYNAMIC Mon Sep 30 21:38:25 UTC 2024 x86_64\ncompiler info: gnuc: 14.2\nlibc info: glibc: 2.39\n$SHELL (typically, interactive shell): /bin/bash\n\n\n[Enabled Hooks]\n\n-- \nJosh\n"},{"id":"506384","messageId":"20241031114731.GA608553@coredump.intra.peff.net","threadId":"62423","inReplyTo":"20241030044322.b5n3ji2n6gaeo5u6@treble.attlocal.net","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-31T11:47:31Z","receivedAt":"2024-10-31T11:47:32Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 29, 2024 at 09:43:22PM -0700, Josh Poimboeuf wrote:\n\n> $ time git describe --match=v6.10-rc7 --debug\n> describe HEAD\n> No exact match on refs or tags, searching to describe\n> finished search at d8470b7c13e11c18cf14a7e3180f0b00e715e4f0\n>  annotated       1844 v6.10-rc7\n> traversed 1282750 commits\n> v6.10-rc7-1844-gc61e41121036\n> \n> real\t0m9.243s\n> user\t0m8.940s\n> sys\t0m0.268s\n> \n> $ time git describe\n> v6.10-rc7-1844-gc61e41121036\n> \n> real\t0m0.149s\n> user\t0m0.111s\n> sys\t0m0.036s\n\nThere's more discussion of the actual solution in the nearby thread from\nRasmus. But I did want to note one thing here: when I initially tried to\nreproduce your problem, my \"slow\" case was a lot less bad.\n\nThe reason is that I had a commit graph file to speed up traversal. So\nindependent of the git-describe fix, you might want to try:\n\n  git commit-graph write --reachable\n\nThat reduces the slow case for me by a factor of 10. And likewise other\ntraversal operations should get faster.\n\nI think we'll build the commit graph file by default these days when you\nrun \"git gc\". But we don't build it immediately after cloning. Perhaps\nwe should change that.\n\n-Peff\n"},{"id":"506390","messageId":"20241031151000.svsa7d2ogcdz7hf6@jpoimboe","threadId":"62423","inReplyTo":"20241031114731.GA608553@coredump.intra.peff.net","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Josh Poimboeuf","fromEmail":"jpoimboe@kernel.org","sentAt":"2024-10-31T15:10:00Z","receivedAt":"2024-10-31T15:10:03Z","isPatch":false,"sender":{"key":"jpoimboe@kernel.org","avatar":null},"body":"On Thu, Oct 31, 2024 at 07:47:31AM -0400, Jeff King wrote:\n> On Tue, Oct 29, 2024 at 09:43:22PM -0700, Josh Poimboeuf wrote:\n> \n> > $ time git describe --match=v6.10-rc7 --debug\n> > describe HEAD\n> > No exact match on refs or tags, searching to describe\n> > finished search at d8470b7c13e11c18cf14a7e3180f0b00e715e4f0\n> >  annotated       1844 v6.10-rc7\n> > traversed 1282750 commits\n> > v6.10-rc7-1844-gc61e41121036\n> > \n> > real\t0m9.243s\n> > user\t0m8.940s\n> > sys\t0m0.268s\n> > \n> > $ time git describe\n> > v6.10-rc7-1844-gc61e41121036\n> > \n> > real\t0m0.149s\n> > user\t0m0.111s\n> > sys\t0m0.036s\n> \n> There's more discussion of the actual solution in the nearby thread from\n> Rasmus. But I did want to note one thing here: when I initially tried to\n> reproduce your problem, my \"slow\" case was a lot less bad.\n> \n> The reason is that I had a commit graph file to speed up traversal. So\n> independent of the git-describe fix, you might want to try:\n> \n>   git commit-graph write --reachable\n> \n> That reduces the slow case for me by a factor of 10. And likewise other\n> traversal operations should get faster.\n> \n> I think we'll build the commit graph file by default these days when you\n> run \"git gc\". But we don't build it immediately after cloning. Perhaps\n> we should change that.\n\nHm... I actually ran \"git gc\" and it didn't seem to help at all.\n\n-- \nJosh\n"},{"id":"506391","messageId":"20241031153143.GA2275115@coredump.intra.peff.net","threadId":"62423","inReplyTo":"20241031151000.svsa7d2ogcdz7hf6@jpoimboe","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-31T15:31:43Z","receivedAt":"2024-10-31T15:31:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 31, 2024 at 08:10:00AM -0700, Josh Poimboeuf wrote:\n\n> > I think we'll build the commit graph file by default these days when you\n> > run \"git gc\". But we don't build it immediately after cloning. Perhaps\n> > we should change that.\n> \n> Hm... I actually ran \"git gc\" and it didn't seem to help at all.\n\nWhat version of Git are you running? I think gc enabled it by default in\n31b1de6a09 (commit-graph: turn on commit-graph by default, 2019-08-13),\nwhich is v2.24.0.\n\nYou could also try \"git commit-graph write --reachable\" and see if that\nimproves things. If it doesn't, then maybe you have the reading side\nturned off explicitly for some reason? Try \"git config core.commitgraph\"\nto see if you have that set to \"false\".\n\n-Peff\n"},{"id":"506392","messageId":"469d82f8-4883-4c87-b681-288a0520e745@app.fastmail.com","threadId":"62423","inReplyTo":"20241031114731.GA608553@coredump.intra.peff.net","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Kristoffer Haugsbakk","fromEmail":"kristofferhaugsbakk@fastmail.com","sentAt":"2024-10-31T16:14:01Z","receivedAt":"2024-10-31T16:14:28Z","isPatch":false,"sender":{"key":"kristofferhaugsbakk@fastmail.com","avatar":null},"body":"On Thu, Oct 31, 2024, at 12:47, Jeff King wrote:\n>   git commit-graph write --reachable\n>\n> That reduces the slow case for me by a factor of 10. And likewise other\n> traversal operations should get faster.\n>\n> I think we'll build the commit graph file by default these days when you\n> run \"git gc\". But we don't build it immediately after cloning. Perhaps\n> we should change that.\n>\n> -Peff\n\nThere was this thread from last year where Rohit cloned Linux and the\ncommand took more than twelve seconds.  Then git-commit-graph(1) fixed\nit.\n\nhttps://lore.kernel.org/git/CAKazavxTXwcZFtL2XyU3MpaUR=snWY8w8Lwpco+mkbqm2nWE=w@mail.gmail.com/\n\nIt would be nice if the graph was written on clone.  With the status quo\nyou might think that there is performance bug (if that’s the term)\nsomewhere.  Then you make a reproduction script using git-clone(1) in\norder to have a blank slate.  Of course it reproduces every time.  But\nthe slow git-log(1) doesn’t happen for people who have had the repo long\nenough for a GC to hit.\n"},{"id":"506393","messageId":"20241031162522.3qcolxhgxe4g2zmu@jpoimboe","threadId":"62423","inReplyTo":"20241031153143.GA2275115@coredump.intra.peff.net","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Josh Poimboeuf","fromEmail":"jpoimboe@kernel.org","sentAt":"2024-10-31T16:25:22Z","receivedAt":"2024-10-31T16:25:24Z","isPatch":false,"sender":{"key":"jpoimboe@kernel.org","avatar":null},"body":"On Thu, Oct 31, 2024 at 11:31:43AM -0400, Jeff King wrote:\n> On Thu, Oct 31, 2024 at 08:10:00AM -0700, Josh Poimboeuf wrote:\n> \n> > > I think we'll build the commit graph file by default these days when you\n> > > run \"git gc\". But we don't build it immediately after cloning. Perhaps\n> > > we should change that.\n> > \n> > Hm... I actually ran \"git gc\" and it didn't seem to help at all.\n> \n> What version of Git are you running? I think gc enabled it by default in\n> 31b1de6a09 (commit-graph: turn on commit-graph by default, 2019-08-13),\n> which is v2.24.0.\n> \n> You could also try \"git commit-graph write --reachable\" and see if that\n> improves things. If it doesn't, then maybe you have the reading side\n> turned off explicitly for some reason? Try \"git config core.commitgraph\"\n> to see if you have that set to \"false\".\n\nActually, I take that back.  You're right, in the freshly cloned repo,\n\"git gc\" did help ~10x:\n\n  $ git describe --match=v6.10-rc7\n  v6.10-rc7-1844-gc61e41121036\n  \n  real\t0m10.681s\n  user\t0m9.442s\n  sys\t0m0.507s\n  \n  $ git gc\n  Enumerating objects: 10460179, done.\n  Counting objects: 100% (10460179/10460179), done.\n  Delta compression using up to 12 threads\n  Compressing objects: 100% (1886458/1886458), done.\n  Writing objects: 100% (10460179/10460179), done.\n  Total 10460179 (delta 8517403), reused 10460179 (delta 8517403), pack-reused 0 (from 0)\n  Expanding reachable commits in commit graph: 1310355, done.\n  Writing out commit graph in 5 passes: 100% (6551775/6551775), done.\n  \n  $ time git describe --match=v6.10-rc7\n  v6.10-rc7-1844-gc61e41121036\n  \n  real\t0m1.173s\n  user\t0m1.002s\n  sys\t0m0.136s\n\n\nBut my real development repo, which has many branches and remotes plus\nthe historical git repo grafted, still takes 10+ seconds.\n\n  $ git --version\n  git version 2.47.0\n\n  $ git gc\n  Enumerating objects: 14656254, done.\n  Counting objects: 100% (12534942/12534942), done.\n  Delta compression using up to 12 threads\n  Compressing objects: 100% (1829918/1829918), done.\n  Writing objects: 100% (12534942/12534942), done.\n  Total 12534942 (delta 10652548), reused 12534853 (delta 10652487), pack-reused 0 (from 0)\n  Enumerating cruft objects: 6133, done.\n  Traversing cruft objects: 14736, done.\n  Counting objects: 100% (6133/6133), done.\n  Delta compression using up to 12 threads\n  Compressing objects: 100% (1179/1179), done.\n  Writing objects: 100% (6133/6133), done.\n  Total 6133 (delta 4876), reused 6117 (delta 4865), pack-reused 0 (from 0)\n\n  $ git commit-graph write --reachable\n  Expanding reachable commits in commit graph: 1941353, done.\n  Finding extra edges in commit graph: 100% (1941353/1941353), done.\n  Writing out commit graph in 5 passes: 100% (9706765/9706765), done.\n\n  $ git config core.commitgraph\n  $\n\n  $ git describe --match=v6.12-rc5 --debug\n  describe HEAD\n  No exact match on refs or tags, searching to describe\n  finished search at d8470b7c13e11c18cf14a7e3180f0b00e715e4f0\n   annotated        297 v6.12-rc5\n  traversed 1310258 commits\n  v6.12-rc5-297-ge7427640278f\n  \n  real\t0m11.626s\n  user\t0m11.298s\n  sys\t0m0.289s\n\n\nNote the commit it finishes at is from almost 20 years ago (I have\nhistorical Linux git history grafted in which goes back to 1991):\n\ncommit d8470b7c13e11c18cf14a7e3180f0b00e715e4f0\nAuthor: Karsten Keil <kkeil@suse.de>\nDate:   Thu Apr 21 08:30:30 2005 -0700\n\n    [PATCH] fix for ISDN ippp filtering\n\n    We do not longer use DLT_LINUX_SLL for activ/pass filters but\n    DLT_PPP_WITHDIRECTION witch need 1 as outbound flag.\n\n    Signed-off-by: Karsten Keil <kkeil@suse.de>\n    Signed-off-by: Linus Torvalds <torvalds@osdl.org>\n\n\nPresumably only one candidate matches the \"v6.12-rc5\" glob (which is an\nexact string, not a wildcard) so it tries to find 9 more but never finds\nany?\n\nSince it's not a wildcard pattern, I would expect it to stop immediately\nwhen it reaches the exact match.\n\n-- \nJosh\n"},{"id":"506396","messageId":"20241031170526.GA2277590@coredump.intra.peff.net","threadId":"62423","inReplyTo":"20241031162522.3qcolxhgxe4g2zmu@jpoimboe","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-31T17:05:26Z","receivedAt":"2024-10-31T17:05:27Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 31, 2024 at 09:25:22AM -0700, Josh Poimboeuf wrote:\n\n> But my real development repo, which has many branches and remotes plus\n> the historical git repo grafted, still takes 10+ seconds.\n\nIf grafts are present, the use of the commit-graph is disabled, because\nthe point of the commit-graph is precomputing and caching various\nproperties of commits. Which, absent grafting, are immutable.\n\nI think we talked long ago about computing commit-graphs over the\ngrafted state, and then using those graphs as long as the graft state\nremained the same. But I don't think we ever implemented anything.\n\nAnother possibility (that I don't recall we've ever discussed) is\npartially using commit graphs. Some commit properties, like generation\nnumbers, depend on other commits. So a graft at the bottom of history is\ngoing to rewrite the generations for all of the descendants. But we\ncould still use the graph information to load the parents and trees of\nall of the non-grafted commits. Those are still valid even in a grafted\nsituation, and that's what's providing most of the speed up in this case\n(without it, we're literally zlib inflating each commit we traverse in\norder to find its parents, versus an integer lookup via the\ncommit-graph).\n\nThat might not be _too_ hard to implement. In theory, anyway. :)\n\n> Note the commit it finishes at is from almost 20 years ago (I have\n> historical Linux git history grafted in which goes back to 1991):\n> \n> commit d8470b7c13e11c18cf14a7e3180f0b00e715e4f0\n> Author: Karsten Keil <kkeil@suse.de>\n> Date:   Thu Apr 21 08:30:30 2005 -0700\n> \n>     [PATCH] fix for ISDN ippp filtering\n> \n>     We do not longer use DLT_LINUX_SLL for activ/pass filters but\n>     DLT_PPP_WITHDIRECTION witch need 1 as outbound flag.\n> \n>     Signed-off-by: Karsten Keil <kkeil@suse.de>\n>     Signed-off-by: Linus Torvalds <torvalds@osdl.org>\n> \n> \n> Presumably only one candidate matches the \"v6.12-rc5\" glob (which is an\n> exact string, not a wildcard) so it tries to find 9 more but never finds\n> any?\n> \n> Since it's not a wildcard pattern, I would expect it to stop immediately\n> when it reaches the exact match.\n\nYeah, I think this is just the same issue we've been discussing.\n\n-Peff\n"},{"id":"506397","messageId":"20241031172021.GB2277590@coredump.intra.peff.net","threadId":"62423","inReplyTo":"469d82f8-4883-4c87-b681-288a0520e745@app.fastmail.com","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-31T17:20:21Z","receivedAt":"2024-10-31T17:20:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 31, 2024 at 05:14:01PM +0100, Kristoffer Haugsbakk wrote:\n\n> On Thu, Oct 31, 2024, at 12:47, Jeff King wrote:\n> >   git commit-graph write --reachable\n> >\n> > That reduces the slow case for me by a factor of 10. And likewise other\n> > traversal operations should get faster.\n> >\n> > I think we'll build the commit graph file by default these days when you\n> > run \"git gc\". But we don't build it immediately after cloning. Perhaps\n> > we should change that.\n> >\n> > -Peff\n> \n> There was this thread from last year where Rohit cloned Linux and the\n> command took more than twelve seconds.  Then git-commit-graph(1) fixed\n> it.\n> \n> https://lore.kernel.org/git/CAKazavxTXwcZFtL2XyU3MpaUR=snWY8w8Lwpco+mkbqm2nWE=w@mail.gmail.com/\n\nYeah, there's discussion in the linked thread there about running \"git\ngc\" after clone. If \"gc --auto\" was pruned down to run some minimal\nbits, that might be OK. What we definitely _don't_ want to do is run\n\"git repack\", because it's very expensive to do the full object graph\nwalk (and buys nothing on a freshly cloned repo unless you do the even\nmore expensive \"-f\").\n\nSo the simplest path forward, but which is a little messy, is to just\nrun \"commit-graph write\" after the clone. In fact, we already have\nfetch.writeCommitGraph (though it does still default to \"false\"). I'd\nexpect that to work with clone (since it's conceptually init+fetch), but\nit doesn't seem to. Looks like the code to trigger it is directly in\nbuiltin/fetch.c, and clone triggers the fetch itself internally.\n\nBut I don't think factoring that out and calling it from both places\nwould be too hard.\n\nIt's a bigger question whether people might be annoyed by some extra\ncomputation at clone time. But I suspect it's OK in practice. Even\nignoring the cost of moving it over the network, my 8-core machine takes\nalmost 3 minutes to index the linux.git packfile on clone. Building the\ncommit graph after that takes about 13 seconds.\n\n-Peff\n"},{"id":"506399","messageId":"ZyPTxgSFiQpZG8qe@nand.local","threadId":"62423","inReplyTo":"20241031114731.GA608553@coredump.intra.peff.net","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-31T19:00:22Z","receivedAt":"2024-10-31T19:00:25Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Oct 31, 2024 at 07:47:31AM -0400, Jeff King wrote:\n> I think we'll build the commit graph file by default these days when you\n> run \"git gc\". But we don't build it immediately after cloning. Perhaps\n> we should change that.\n\nI think that would be a reasonable thing to do. We already have\nfetch.writeCommitGraph and gc.writeCommitGraph, so it seems like a\nnatural extension to add clone.writeCommitGraph.\n\nI don't have a strong feeling about what the default should be, although\nI err on the side of \"true\". Most repositories cloned will be small\nenough that writing a commit-graph upon clone shouldn't take too long.\nSo the savings it will provide will be well worth the marginal increase\nin perceived clone time.\n\nThanks,\nTaylor\n"},{"id":"506400","messageId":"ZyPT8lsloCG4QLai@nand.local","threadId":"62423","inReplyTo":"20241031170526.GA2277590@coredump.intra.peff.net","subject":"Re: [BUG] \"git describe --match\" performance","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-31T19:01:06Z","receivedAt":"2024-10-31T19:01:08Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Oct 31, 2024 at 01:05:26PM -0400, Jeff King wrote:\n> I think we talked long ago about computing commit-graphs over the\n> grafted state, and then using those graphs as long as the graft state\n> remained the same. But I don't think we ever implemented anything.\n>\n> Another possibility (that I don't recall we've ever discussed) is\n> partially using commit graphs. Some commit properties, like generation\n> numbers, depend on other commits. So a graft at the bottom of history is\n> going to rewrite the generations for all of the descendants. But we\n> could still use the graph information to load the parents and trees of\n> all of the non-grafted commits. Those are still valid even in a grafted\n> situation, and that's what's providing most of the speed up in this case\n> (without it, we're literally zlib inflating each commit we traverse in\n> order to find its parents, versus an integer lookup via the\n> commit-graph).\n>\n> That might not be _too_ hard to implement. In theory, anyway. :)\n\nAdding Stolee (CC'd), our resident commit-graph expert, to see if they\nhave any thoughts.\n\nThanks,\nTaylor\n"}]}