{"thread":{"id":"59459","subject":"limiting git branch --contains","startedAt":"2023-03-23T18:54:35Z","lastAt":"2026-06-08T23:12:19Z","messageCount":17,"participants":["Oswald Buddenhagen","Junio C Hamano","Felipe Contreras","Derrick Stolee","Jeff King","Kristofer Karlsson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"474025","messageId":"ZBygZbz5E6jVNp3y@ugly","threadId":"59459","inReplyTo":null,"subject":"limiting git branch --contains","fromName":"Oswald Buddenhagen","fromEmail":"oswald.buddenhagen@gmx.de","sentAt":"2023-03-23T18:54:29Z","receivedAt":"2023-03-23T18:54:35Z","isPatch":false,"body":"moin,\n\ngit branch --contains can be a rather expensive operation in big \nrepositories. as my use case is actually a rather limited search for \ncommits in my local wip branches, it would be helpful to be able to \nspecify exclusions for the rev-walk, say\n\n git branch --contains deadbeef ^origin/master\n\nsuggestions how this is actually already achievable efficiently are of \ncourse welcome as well. ^^\n\nthanks!\n"},{"id":"474034","messageId":"xmqqpm8z8dab.fsf@gitster.g","threadId":"59459","inReplyTo":"ZBygZbz5E6jVNp3y@ugly","subject":"Re: limiting git branch --contains","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-03-23T19:42:52Z","receivedAt":"2023-03-23T19:42:56Z","isPatch":false,"body":"Oswald Buddenhagen writes:\n\n> git branch --contains can be a rather expensive operation in big\n> repositories. as my use case is actually a rather limited search for\n> commits in my local wip branches,...\n\nI can do\n\n $ git branch --list --contains master \\??/\\*\n\nto show only the topic branches that forked from/after 'master', and\nreplacing 'master' with v2.40.0 or any older point and the output\nstarts showing more branches, but the search excludes integration\nbranches like 'next' and 'seen'. Is that what you are after?\n"},{"id":"474044","messageId":"ZBy6Ku+znv/wuOix@ugly","threadId":"59459","inReplyTo":"xmqqpm8z8dab.fsf@gitster.g","subject":"Re: limiting git branch --contains","fromName":"Oswald Buddenhagen","fromEmail":"oswald.buddenhagen@gmx.de","sentAt":"2023-03-23T20:44:26Z","receivedAt":"2023-03-23T20:44:39Z","isPatch":false,"body":"On Thu, Mar 23, 2023 at 12:42:52PM -0700, Junio C Hamano wrote:\n>Oswald Buddenhagen writes:\n>\n>> git branch --contains can be a rather expensive operation in big\n>> repositories. as my use case is actually a rather limited search for\n>> commits in my local wip branches,...\n>\n>I can do\n>\n> $ git branch --list --contains master \\??/\\*\n>\n>to show only the topic branches that forked from/after 'master', and\n>replacing 'master' with v2.40.0 or any older point and the output\n>starts showing more branches, but the search excludes integration\n>branches like 'next' and 'seen'. Is that what you are after?\n>\nnot really.\nthe objective is finding the work branch(es) a given sha1 is coming \nfrom.\nthe problem isn't that the above doesn't work, only that it is insanely \nexpensive - on my old machine it takes half a minute in the linux kernel \ntree.\nthat's an inevitable effect of trying the branches one after another and \nnot being lucky enough to pick the right branch first. at least that's \nwhat appears to be happening.\nthis could be optimized by doing a piecewise descend on all branches \nsimultaneously (which i presume is what merge-base & co. do), but if the \ncommit actually isn't on any local branch at all, we'd still walk to the \nvery root commit(s) - which is rather wasteful when we actually know \nthat we can cut the walks short.\n\nam i making sense?\n"},{"id":"474046","messageId":"CAMP44s3Bxbs6gvzXT336TtXpis6BK2tzYCGhnmMWdYfLgp5zSQ@mail.gmail.com","threadId":"59459","inReplyTo":"ZBygZbz5E6jVNp3y@ugly","subject":"Re: limiting git branch --contains","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2023-03-23T20:56:52Z","receivedAt":"2023-03-23T20:57:47Z","isPatch":false,"body":"On Thu, Mar 23, 2023 at 1:07 PM Oswald Buddenhagen\n wrote:\n>\n> moin,\n>\n> git branch --contains can be a rather expensive operation in big\n> repositories. as my use case is actually a rather limited search for\n> commits in my local wip branches, it would be helpful to be able to\n> specify exclusions for the rev-walk, say\n>\n> git branch --contains deadbeef ^origin/master\n>\n> suggestions how this is actually already achievable efficiently are of\n> course welcome as well. ^^\n\nBecause I saw no way to specify only the actual commits of my\nbranches, I wrote a tool: git-smartlist [1]\n\nIn particular the negate_upstreams helper, which basically goes\nthrough all the branches and does topic1@{u}..topic1\ntopic2@{u}..topic2 etc.\n\n[1] https://github.com/felipec/git-smartlist/blob/master/git-smartlist\n\n-- \nFelipe Contreras\n"},{"id":"474102","messageId":"594a358e-7bd4-e7a1-ad0f-7e41ca1fe767@github.com","threadId":"59459","inReplyTo":"ZBy6Ku+znv/wuOix@ugly","subject":"Re: limiting git branch --contains","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-03-24T17:23:32Z","receivedAt":"2023-03-24T17:23:38Z","isPatch":false,"body":"On 3/23/2023 4:44 PM, Oswald Buddenhagen wrote:\n> On Thu, Mar 23, 2023 at 12:42:52PM -0700, Junio C Hamano wrote:\n>> Oswald Buddenhagen writes:\n>>\n>>> git branch --contains can be a rather expensive operation in big\n>>> repositories. as my use case is actually a rather limited search for\n>>> commits in my local wip branches,...\n>>\n>> I can do\n>>\n>>    $ git branch --list --contains master \\??/\\*\n>>\n>> to show only the topic branches that forked from/after 'master', and\n>> replacing 'master' with v2.40.0 or any older point and the output\n>> starts showing more branches, but the search excludes integration\n>> branches like 'next' and 'seen'.  Is that what you are after?\n>>\n> not really.\n> the objective is finding the work branch(es) a given sha1 is coming from.\n> the problem isn't that the above doesn't work, only that it is insanely expensive - on my old machine it takes half a minute in the linux kernel tree.\n> that's an inevitable effect of trying the branches one after another and not being lucky enough to pick the right branch first. at least that's what appears to be happening.\n> this could be optimized by doing a piecewise descend on all branches simultaneously (which i presume is what merge-base & co. do), but if the commit actually isn't on any local branch at all, we'd still walk to the very root commit(s) - which is rather wasteful when we actually know that we can cut the walks short.\n\nCould you make sure to run 'git commit-graph write --reachable' before\ntesting again?\n\nWhen the commit-graph exists on disk, the algorithm does do a single\nreachability walk from all the initial points. If it does not exist,\nthen each starting point triggers its own reachability walk, which\nis significantly slower. See repo_is_descendant_of() in commit-reach.c\nfor more information on this split.\n\nThanks,\n-Stolee\n"},{"id":"474108","messageId":"ZB3o0seQJVbtPa+j@ugly","threadId":"59459","inReplyTo":"594a358e-7bd4-e7a1-ad0f-7e41ca1fe767@github.com","subject":"Re: limiting git branch --contains","fromName":"Oswald Buddenhagen","fromEmail":"oswald.buddenhagen@gmx.de","sentAt":"2023-03-24T18:15:46Z","receivedAt":"2023-03-24T18:16:11Z","isPatch":false,"body":"On Fri, Mar 24, 2023 at 01:23:32PM -0400, Derrick Stolee wrote:\n>Could you make sure to run 'git commit-graph write --reachable' before\n>testing again?\n>\ni did, didn't help.\n\nbut regardless, even if this would improve things by an order of \nmagnitude (or even two), it would be still wasteful, given that the \nexpected working set contains a few tens commits, while the whole graph \ncontains well over a million commits.\n"},{"id":"474109","messageId":"85f81579-5876-a573-6d35-88b35ab0f290@github.com","threadId":"59459","inReplyTo":"ZB3o0seQJVbtPa+j@ugly","subject":"Re: limiting git branch --contains","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-03-24T18:20:01Z","receivedAt":"2023-03-24T18:20:07Z","isPatch":false,"body":"On 3/24/2023 2:15 PM, Oswald Buddenhagen wrote:\n> On Fri, Mar 24, 2023 at 01:23:32PM -0400, Derrick Stolee wrote:\n>> Could you make sure to run 'git commit-graph write --reachable' before\n>> testing again?\n>>\n> i did, didn't help.\n> \n> but regardless, even if this would improve things by an order of magnitude (or even two), it would be still wasteful, given that the expected working set contains a few tens commits, while the whole graph contains well over a million commits.\n\nHm. The point is that it _should_ improve things by several orders\nof magnitude by using generation numbers to avoid walking a\nsignificant portion of the commits. That is, unless the commit is\nextremely old.\n\nBut what you were originally asking was also about filtering the\nset of branches to pick, instead of just the commits that are\nwalked.\n\nIn that case, perhaps you should use \n\n git for-each-ref --format=\"%(refname)\" --contains= ... \n\nor use ref patterns instead of exact refs, if you have such a\ngrouping?\n\nThanks,\n-Stolee\n"},{"id":"474112","messageId":"ZB3z3e5G3Lrv9g3Y@ugly","threadId":"59459","inReplyTo":"85f81579-5876-a573-6d35-88b35ab0f290@github.com","subject":"Re: limiting git branch --contains","fromName":"Oswald Buddenhagen","fromEmail":"oswald.buddenhagen@gmx.de","sentAt":"2023-03-24T19:02:53Z","receivedAt":"2023-03-24T19:03:14Z","isPatch":false,"body":"On Fri, Mar 24, 2023 at 02:20:01PM -0400, Derrick Stolee wrote:\n>Hm. The point is that it _should_ improve things by several orders\n>of magnitude [...]\n>\nwell, at that point it would be kinda sufficient. ^^\nbut it really doesn't do anything at all (i tried moving away the graph \nfor comparison).\nmaybe the operation just forgets to load the graph?\n\n>But what you were originally asking was also about filtering the\n>set of branches to pick,\n>\ni didn't, i was just misunderstood.\n"},{"id":"474114","messageId":"20230324191009.GA536967@coredump.intra.peff.net","threadId":"59459","inReplyTo":"594a358e-7bd4-e7a1-ad0f-7e41ca1fe767@github.com","subject":"Re: limiting git branch --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2023-03-24T19:10:09Z","receivedAt":"2023-03-24T19:10:14Z","isPatch":false,"body":"On Fri, Mar 24, 2023 at 01:23:32PM -0400, Derrick Stolee wrote:\n\n> Could you make sure to run 'git commit-graph write --reachable' before\n> testing again?\n> \n> When the commit-graph exists on disk, the algorithm does do a single\n> reachability walk from all the initial points. If it does not exist,\n> then each starting point triggers its own reachability walk, which\n> is significantly slower. See repo_is_descendant_of() in commit-reach.c\n> for more information on this split.\n\nI'm a bit confused by that reference. We do switch behavior based on the\npresence of generation numbers in repo_is_descendant_of(). But\nref-filter calls that function from commit_contains(), which is only fed\none ref at a time. So we'll still do several walks, one per ref.\n\nIn commit_contains() we'll use the \"tag algo\" instead of calling\nrepo_is_descendant_of(). It still sees the refs individually, but it\nkeeps a cache to avoid walking over the same parts of history. We didn't\ntraditionally use that algorithm for branches because it has a tendency\nto walk down to the roots (which is OK for tags, where you have old ones\nthat require walking down that far anyway, but not for branches, where\nyou can usually stop at a recent merge base). But now that we have\nreliable generation numbers, we can stop that traversal early.\n\nBut it doesn't look like we actually trigger the tag algo for anything\nbut git-tag. I.e., I wonder if we should be doing something like this:\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 7c0c39fd286..16c1a341bf5 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -712,7 +712,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t struct commit_list *list, struct contains_cache *cache)\n {\n-\tif (filter->with_commit_tag_algo)\n+\tif (filter->with_commit_tag_algo ||\n+\t generation_numbers_enabled(the_repository))\n \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n \treturn repo_is_descendant_of(the_repository, commit, list);\n }\n\nThe speedup is pretty minor compared to using commit-graphs at all.\nDoing \"git for-each-ref --format='%(refname)' --contains HEAD\" on a\nclone of linux.git gets me:\n\n - with no commit graph: 1m40s\n - after \"commit-graph write --reachable\": 30ms\n - plus the patch above; 23ms\n\nSo most of the help comes from not parsing the commit objects (courtesy\nof the commit graph) and perhaps some early cutoffs (due to the use of\ngeneration numbers in repo_is_descendant_of()). Using the cached walk\nhelps a little, but it may be more so for certain patterns of data.\n\nI also scratched my head a little that we are still using\ncommit_contains() at all. I thought we now had functions to do a single\nwalk that would give us an answer for each ref, and that we could\ntrigger that in filter_refs(). And we do have reach_filter() there, but\nI think it only handles --merged/--no-merged.\n\nI admit I haven't kept up with the state of things here, so I'm not sure\nwhat tools we have available.\n\n-Peff\n"},{"id":"474115","messageId":"20230324191302.GB536967@coredump.intra.peff.net","threadId":"59459","inReplyTo":"ZB3z3e5G3Lrv9g3Y@ugly","subject":"Re: limiting git branch --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2023-03-24T19:13:02Z","receivedAt":"2023-03-24T19:13:06Z","isPatch":false,"body":"On Fri, Mar 24, 2023 at 08:02:53PM +0100, Oswald Buddenhagen wrote:\n\n> On Fri, Mar 24, 2023 at 02:20:01PM -0400, Derrick Stolee wrote:\n> > Hm. The point is that it _should_ improve things by several orders\n> > of magnitude [...]\n> > \n> well, at that point it would be kinda sufficient. ^^\n> but it really doesn't do anything at all (i tried moving away the graph for\n> comparison).\n> maybe the operation just forgets to load the graph?\n\nThat seems weird. I get a 3000x speedup just by using building the\ncommit-graph. Are you seeing any change at all? What version of Git are\nyou using?\n\nI'd be curious, too, if you can try the patch I posted elsewhere in the\nthread to see if that improves things.\n\n-Peff\n"},{"id":"474120","messageId":"ZB4A7+LMY+NSaPYE@ugly","threadId":"59459","inReplyTo":"20230324191302.GB536967@coredump.intra.peff.net","subject":"Re: limiting git branch --contains","fromName":"Oswald Buddenhagen","fromEmail":"oswald.buddenhagen@gmx.de","sentAt":"2023-03-24T19:58:39Z","receivedAt":"2023-03-24T19:59:27Z","isPatch":false,"body":"On Fri, Mar 24, 2023 at 03:13:02PM -0400, Jeff King wrote:\n>On Fri, Mar 24, 2023 at 08:02:53PM +0100, Oswald Buddenhagen wrote:\n>> maybe the operation just forgets to load the graph?\n>\nso i strace'd the thing, and there is indeed no appearance of \n'commit-graph' in the log.\n\nso i tried git log --graph ... and still nothing?!\n\nand yes, core.commitgraph is true (originally absent, so same thing).\n\n>That seems weird.\n>\nindeed.\n\nso weird in fact, that i tried another repository. and it works!\n\nso apparently something is wrong with my/the linux repository.\nthings i can imagine contributing to throwing it off somehow:\n\n$ git remote -v\nalsa git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound.git (fetch)\nalsa git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound.git (push)\nhistory git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git (fetch)\nhistory git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git (push)\nlinux-mips git://git.linux-mips.org/pub/scm/ralf/linux (fetch)\nlinux-mips git://git.linux-mips.org/pub/scm/ralf/linux (push)\nlinux-wireless git://git.kernel.org/pub/scm/linux/kernel/git/kvalo/wireless-drivers (fetch)\nlinux-wireless git://git.kernel.org/pub/scm/linux/kernel/git/kvalo/wireless-drivers (push)\norigin git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git (fetch)\norigin git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git (push)\nossi git@github.com:ossilator/linux.git (fetch)\nossi git@github.com:ossilator/linux.git (push)\n\n(the linux-* remotes haven't been pulled for years.)\n\n$ grep replace .git/packed-refs\na3628e41a9946c4fe93d9b2ae5906e1b2184fa8e refs/replace/1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n\n>What version of Git are you using?\n>\nrather recent master. dogfeeding my contributions.\n"},{"id":"474122","messageId":"20230324204504.GB549549@coredump.intra.peff.net","threadId":"59459","inReplyTo":"ZB4A7+LMY+NSaPYE@ugly","subject":"Re: limiting git branch --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2023-03-24T20:45:04Z","receivedAt":"2023-03-24T20:45:11Z","isPatch":false,"body":"On Fri, Mar 24, 2023 at 08:58:39PM +0100, Oswald Buddenhagen wrote:\n\n> On Fri, Mar 24, 2023 at 03:13:02PM -0400, Jeff King wrote:\n> > On Fri, Mar 24, 2023 at 08:02:53PM +0100, Oswald Buddenhagen wrote:\n> > > maybe the operation just forgets to load the graph?\n> > \n> so i strace'd the thing, and there is indeed no appearance of 'commit-graph'\n> in the log.\n> \n> so i tried git log --graph ... and still nothing?!\n\nThat \"--graph\" option is unrelated. It asks for Git to draw a graph in\nthe output. Commit-graph is a fancy name for \"a cache file which stores\nsome metadata about commits so we can quickly answer graph-like queries\nsuch as ancestry, etc\".\n\n> so weird in fact, that i tried another repository. and it works!\n> \n> so apparently something is wrong with my/the linux repository.\n> things i can imagine contributing to throwing it off somehow:\n> \n> $ git remote -v\n> alsa git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound.git (fetch)\n> alsa git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound.git (push)\n> history git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git (fetch)\n> history git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git (push)\n> linux-mips git://git.linux-mips.org/pub/scm/ralf/linux (fetch)\n> linux-mips git://git.linux-mips.org/pub/scm/ralf/linux (push)\n> linux-wireless git://git.kernel.org/pub/scm/linux/kernel/git/kvalo/wireless-drivers (fetch)\n> linux-wireless git://git.kernel.org/pub/scm/linux/kernel/git/kvalo/wireless-drivers (push)\n> origin git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git (fetch)\n> origin git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git (push)\n> ossi git@github.com:ossilator/linux.git (fetch)\n> ossi git@github.com:ossilator/linux.git (push)\n> \n> (the linux-* remotes haven't been pulled for years.)\n> \n> $ grep replace .git/packed-refs\n> a3628e41a9946c4fe93d9b2ae5906e1b2184fa8e refs/replace/1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n\nAh, that is your problem. When \"replace\" refs are in use, the data\nstored in the commit-graph can't reliably be used. It is storing\ninvariants like \"commit XYZ is the Nth generation from the root\", which\nis an immutable property of a commit with a given hash. But as soon as\nyou use grafts or replace refs, now we don't know if that information is\nvalid or not (not just for the replaced commit, but for any of its\nancestors which might have been replaced). So the whole thing is\ndisabled.\n\nI'd guess you are grafting the \"history\" remote's contents onto the\nstart of Linus's repo. It's probably better to do that in a one-off\nrepository, rather than your day-to-day working one. But you can also\nflip it off and on at will. Try:\n\n git -c core.useReplaceRefs=false branch --contains ...\n\nwhich I think should get faster. And likewise you can set it to \"false\"\nin your config for day-to-day use, and then flip it on when you want to\nrun a command that you think might query all the way down into ancient\nhistory.\n\nIf it does make things faster for you, I'd still be curious to see the\ndifference between \"just commit graphs\" and \"commit graphs plus the\npatch I showed earlier\". I think it should make things faster, but if\nit's only a few milliseconds on average, it's not that urgent to pursue.\n\n-Peff\n"},{"id":"474135","messageId":"ZB4e/yE+25W66z6S@ugly","threadId":"59459","inReplyTo":"20230324204504.GB549549@coredump.intra.peff.net","subject":"Re: limiting git branch --contains","fromName":"Oswald Buddenhagen","fromEmail":"oswald.buddenhagen@gmx.de","sentAt":"2023-03-24T22:06:55Z","receivedAt":"2023-03-24T22:07:24Z","isPatch":false,"body":"On Fri, Mar 24, 2023 at 04:45:04PM -0400, Jeff King wrote:\n>On Fri, Mar 24, 2023 at 08:58:39PM +0100, Oswald Buddenhagen wrote:\n>> so i tried git log --graph ... and still nothing?!\n>\n>That \"--graph\" option is unrelated. It asks for Git to draw a graph in\n>the output.\n>\ni know. it just happens to be the go-to example from derrick's blog post \nabout commit-graph, so that not working was a dead giveaway that \nsomething is really wrong.\n\n>> a3628e41a9946c4fe93d9b2ae5906e1b2184fa8e refs/replace/1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\n>\n>Ah, that is your problem. When \"replace\" refs are in use, the data\n>stored in the commit-graph can't reliably be used. [...]\n>\nwhy isn't the commit-graph built with the replaces applied (and tagged \nby a hash of the used replaces, so we know when to ignore it)?\n\nat minimum, i'd expect a warning giving a reason when the graph is \nignored.\n\n> git -c core.useReplaceRefs=false branch --contains ...\n>\n>which I think should get faster.\n>\nyes, that works. and _rather_ convincingly, to put it that way.\n\n>I'd still be curious to see the\n>difference between \"just commit graphs\" and \"commit graphs plus the\n>patch I showed earlier\". I think it should make things faster, but if\n>it's only a few milliseconds on average, it's not that urgent to pursue.\n>\nif there is a speed difference at all, it gets drowned out by the noise.\n"},{"id":"474149","messageId":"20230325063035.GA562387@coredump.intra.peff.net","threadId":"59459","inReplyTo":"ZB4e/yE+25W66z6S@ugly","subject":"Re: limiting git branch --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2023-03-25T06:30:35Z","receivedAt":"2023-03-25T06:30:41Z","isPatch":false,"body":"On Fri, Mar 24, 2023 at 11:06:55PM +0100, Oswald Buddenhagen wrote:\n\n> > Ah, that is your problem. When \"replace\" refs are in use, the data\n> > stored in the commit-graph can't reliably be used. [...]\n> > \n> why isn't the commit-graph built with the replaces applied (and tagged by a\n> hash of the used replaces, so we know when to ignore it)?\n\nI think a similar idea has come up before, but we decided to do the\nsimplest safe thing (disabling optimizations) to start with. And then\nsomebody who really cared about making optimizations work with commit\ngraphs could come along and do so later. Nobody has yet; you could be\nthat someone. ;)\n\n> at minimum, i'd expect a warning giving a reason when the graph is ignored.\n\nThat might be reasonable. The commit graph is an optimization, so we'd\nnever produce a wrong answer by ignoring it. And since the fallback was\nthe status quo before the optimizations were implemented, it didn't seem\nlike that big a deal. But these days the performance many of us expect\nis with those optimizations, so perhaps the tables have turned.\n\nI do think there might be some complications, though. I think we may\nbuild commit graphs by default these days during \"gc\" and even\nincrementally after \"fetch\". If we warned when the graphs are disabled,\nit basically means that every command in a repo with replace refs would\nissue the warning.\n\n> > I'd still be curious to see the\n> > difference between \"just commit graphs\" and \"commit graphs plus the\n> > patch I showed earlier\". I think it should make things faster, but if\n> > it's only a few milliseconds on average, it's not that urgent to pursue.\n> > \n> if there is a speed difference at all, it gets drowned out by the noise.\n\nOK, thanks for testing. I do think that looking into a true single\ntraversal might make sense, but I don't think we've seen a case yet\nwhere it's a substantial speedup.\n\n-Peff\n"},{"id":"474156","messageId":"ZB6rXKOjOI40khj1@ugly","threadId":"59459","inReplyTo":"20230325063035.GA562387@coredump.intra.peff.net","subject":"Re: limiting git branch --contains","fromName":"Oswald Buddenhagen","fromEmail":"oswald.buddenhagen@gmx.de","sentAt":"2023-03-25T08:05:48Z","receivedAt":"2023-03-25T08:06:09Z","isPatch":false,"body":"On Sat, Mar 25, 2023 at 02:30:35AM -0400, Jeff King wrote:\n> Nobody has yet; you could be that someone. ;)\n>\ndamn ;)\n\n>I do think there might be some complications, though. I think we may\n>build commit graphs by default these days during \"gc\" and even\n>incrementally after \"fetch\". If we warned when the graphs are disabled,\n>it basically means that every command in a repo with replace refs would\n>issue the warning.\n>\nyeah, i thought about that, too ...\n\nit would be easy enough to squelch the warning by manually disabling \nwriting or using the graph. the downside is that if the root cause gets \nfixed, the user would be still missing out (unless they read the \nchangelog and remembered to reconfigure all affected repos).\n\none could make it an advisory message which can be explictly squelched.\n"},{"id":"544140","messageId":"20260527070510.3510836-1-krka@spotify.com","threadId":"59459","inReplyTo":"20230324191009.GA536967@coredump.intra.peff.net","subject":"Re: limiting git branch --contains","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-27T07:05:09Z","receivedAt":"2026-05-27T07:05:14Z","isPatch":false,"body":"Hi!\n\nI'm reviving this old thread because I believe the discussion here\nis still relevant and the patch Peff included is good. I think I\naccidentally created the exact same patch before I found this thread.\n\nI work on a large repo (millions of commits, ~8000 remote tracking\nbranches) where \"git for-each-ref --contains refs/remotes/\"\nwas taking 4+ seconds even with a commit-graph, and much worse for\ndeeper commits. I started investigating and building a more complex\nbatched solution before I realized that the cached DFS algorithm\n(contains_tag_algo) already exists and does exactly what's needed --\nit just wasn't enabled for branches.\n\nWith generation numbers (commit-graph), the cached algorithm is\nstrictly at least as good as the uncached one. Both have the same\nwalk floor -- the generation cutoff in contains_tag_algo is equivalent\nto the STALE boundary in paint_down_to_common. The cache then provides\na pure win: O(total unique commits) instead of O(N * commits per ref).\n\nIn my benchmarks, the improvement is significant and scales with the\nnumber of refs and the depth of the target commit:\n\ngit.git (69K commits, 5826 tags) with commit-graph:\n\n Scenario Master Cached Speedup\n Deep (v2.30.0) 1.08s 292ms 3.7x\n Recent (HEAD~100) 338ms 240ms 1.4x\n Orphan (unreachable) 271ms 241ms 1.1x\n\nLarge monorepo with commit-graph:\n\n Scenario Master Cached Speedup\n HEAD~10000 511ms 239ms 2.1x\n HEAD~50000 4.14s 272ms 15x\n Orphan (unreachable) 4.13s 252ms 16x\n\nI also tested with varying ref counts on git.git. The cached\nalgorithm is faster or tied in every scenario I tested -- the\ncrossover point is around 3-6 refs, below which both complete in\nsingle-digit milliseconds.\n\nWithout commit-graph, the difference is even more dramatic (41-54x\non git.git with 5826 tags), though the theoretical argument is less\nclean: without generation numbers, contains_tag_algo has no walk\nfloor and may traverse to root commits for unreachable targets.\nIn practice the cache still wins for N > 1, but I don't have a\nproof that covers all possible DAG shapes. I think we should start\nby optimizing it for the case where we have generation numbers,\nand maybe keep exploring if there are any meaningful scenarios\nwithout generation numbers where it would actually be a regression.\n\nTo reproduce the benchmarks:\n\n # Setup\n ORPHAN=$(git commit-tree HEAD^{tree} -m \"unreachable\")\n git commit-graph write --reachable\n\n # git.git with 5826 tags\n git for-each-ref --contains v2.30.0 refs/tags/\n\n # Large repo with remote refs\n git for-each-ref --contains HEAD~50000 refs/remotes/\n\n-- Kristofer\n\n"},{"id":"544978","messageId":"20260608231218.GD340696@coredump.intra.peff.net","threadId":"59459","inReplyTo":"20260527070510.3510836-1-krka@spotify.com","subject":"Re: limiting git branch --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-06-08T23:12:18Z","receivedAt":"2026-06-08T23:12:19Z","isPatch":false,"body":"On Wed, May 27, 2026 at 09:05:09AM +0200, Kristofer Karlsson wrote:\n\n> With generation numbers (commit-graph), the cached algorithm is\n> strictly at least as good as the uncached one. Both have the same\n> walk floor -- the generation cutoff in contains_tag_algo is equivalent\n> to the STALE boundary in paint_down_to_common. The cache then provides\n> a pure win: O(total unique commits) instead of O(N * commits per ref).\n> \n> In my benchmarks, the improvement is significant and scales with the\n> number of refs and the depth of the target commit:\n\nYeah, I think this is worth pursuing. Looks like somebody else also\ngenerated a similar patch recently:\n\n https://lore.kernel.org/git/20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com/\n\nBut I think the approach in this thread (to use depth-first only when we\nhave generation numbers) makes more sense.\n\nI cc'd you on that thread.\n\n-Peff\n"}]}