{"thread":{"id":"65797","subject":"[RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","startedAt":"2026-06-12T11:15:55Z","lastAt":"2026-06-14T11:48:04Z","messageCount":10,"participants":["Kristofer Karlsson","Derrick Stolee","Elijah Newren"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"545366","messageId":"CAL71e4Mp7ewv0UGS8j=iTq6quyxLXzrr0uNDbWR8JKaOsTSVyA@mail.gmail.com","threadId":"65797","inReplyTo":null,"subject":"[RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-12T11:15:43Z","receivedAt":"2026-06-12T11:15:55Z","isPatch":false,"body":"Hi! I previously sent a patch[1] to optimize paint_down_to_common\nfor the single merge-base case. I believe I have found a stronger\noptimization, but before sending a patch I wanted to discuss the\ncorrectness argument.\n\nThe main problem to solve is that computing merge-bases is slow today\nin some scenarios, especially large monorepos with complex graphs.\nThis affects multiple operations, including merge-base and merge-tree.\n\nThe previous patch improved it for the special case of the\nmerge-base being part of the commit-graph and the caller only\nneeding to know about one merge-base.\n\nI have an idea to make it faster for fetching all merge-bases for\ncommon flows in large repos, as long as the commit graph is\nreasonably up to date.\n\nThe key part is the exit condition in paint_down_to_common.\nInstead of waiting for the queue to only contain stale entries,\nit is enough to wait for one of the sides to be exhausted,\ni.e. side 1 is exhausted if no more commits exist in the\ntraversal queue flagged with only PARENT1. For example, if\nthe two sides are origin/HEAD and a small PR branch, the PR\nbranch will quickly become exhausted at the merge-base, while\nthe main side will continue.\n\nNow you may ask: why is that a safe condition?\n\nThe traversal in paint_down_to_common has two logical phases\ndue to the priority queue ordering:\n\n  1. Process all commits with infinite generation numbers.\n     This includes all commits when there is no commit-graph.\n  2. Process all commits with finite generation numbers.\n\nThese happen in strict order -- all INFINITY commits are popped\nbefore any finite-generation commit.\n\nThe optimization only applies after the walk enters the second phase.\nIn the first phase, the traversal behaves exactly as today\nand uses the existing termination condition.\n\nIn the second phase, traversal follows strict topological\norder -- descendants are processed before ancestors. Paint flags\npropagate from each processed commit to its parents, which have\nstrictly lower generation and are therefore not yet examined.\n\nA new merge-base candidate can only form when a PARENT1-only path\nmeets a PARENT2-only path. Once a commit acquires both paint flags\nin this phase, any descendant carrying both paint flags would\nalready have been processed.\n\nOnce one side is exhausted from the queue, no new meeting between\npure sides can occur. Any commit that subsequently acquires both\npaint flags must inherit them from a commit that already had both\nflags -- it is deeper in the graph and cannot affect the final\nmerge-base set. We can stop.\n\nOn a large monorepo with previously expensive merge-base and\nmerge-tree queries, I observed speedups ranging from roughly 300x\nto 1000x. The nice thing is that this works for merge-base --all\nand every internal caller of paint_down_to_common -- we no longer\nhave to restrict the optimization to finding just the first merge-base.\n\nDoes the correctness argument above hold?\n\nHappy to come back with a patch later if the logic holds and the\noverall approach is wanted.\n\nThanks,\nKristofer\n\n[1] https://lore.kernel.org/git/pull.2109.v4.git.1778504352.gitgitgadget@gmail.com/\n"},{"id":"545371","messageId":"0b3f7429-a4fb-4f7a-bf7b-5a0edeb1db52@gmail.com","threadId":"65797","inReplyTo":"CAL71e4Mp7ewv0UGS8j=iTq6quyxLXzrr0uNDbWR8JKaOsTSVyA@mail.gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-12T12:52:50Z","receivedAt":"2026-06-12T12:52:52Z","isPatch":false,"body":"On 6/12/2026 7:15 AM, Kristofer Karlsson wrote:\n> I have an idea to make it faster for fetching all merge-bases for\n> common flows in large repos, as long as the commit graph is\n> reasonably up to date.\n> \n> The key part is the exit condition in paint_down_to_common.\n> Instead of waiting for the queue to only contain stale entries,\n> it is enough to wait for one of the sides to be exhausted,\n> i.e. side 1 is exhausted if no more commits exist in the\n> traversal queue flagged with only PARENT1. For example, if\n> the two sides are origin/HEAD and a small PR branch, the PR\n> branch will quickly become exhausted at the merge-base, while\n> the main side will continue.\n\nGenerally, you'd replace the queue_has_nonstale() condition\nwith a more generic queue_can_halt() condition.\n\n> Now you may ask: why is that a safe condition?\n> \n> The traversal in paint_down_to_common has two logical phases\n> due to the priority queue ordering:\n> \n>   1. Process all commits with infinite generation numbers.\n>      This includes all commits when there is no commit-graph.\n>   2. Process all commits with finite generation numbers.\n> \n> These happen in strict order -- all INFINITY commits are popped\n> before any finite-generation commit.\n> \n> The optimization only applies after the walk enters the second phase.\n> In the first phase, the traversal behaves exactly as today\n> and uses the existing termination condition.\n\nThis would mean that queue_can_halt() would need to know the\nfollowing:\n\n1. If we peek at the top of the queue, is that a commit with\n   infinite generation number? If so, then we can only use\n   queue_has_nonstale().\n\n2. Otherwise, we know that all commits in the queue are ordered\n   topologically and can use a different, faster check. To start,\n   we need to keep going as long as at least one commit has only\n   one side\n\n> In the second phase, traversal follows strict topological\n> order -- descendants are processed before ancestors. Paint flags\n> propagate from each processed commit to its parents, which have\n> strictly lower generation and are therefore not yet examined.\n> \n> A new merge-base candidate can only form when a PARENT1-only path\n> meets a PARENT2-only path. Once a commit acquires both paint flags\n> in this phase, any descendant carrying both paint flags would\n> already have been processed.\n> \n> Once one side is exhausted from the queue, no new meeting between\n> pure sides can occur. Any commit that subsequently acquires both\n> paint flags must inherit them from a commit that already had both\n> flags -- it is deeper in the graph and cannot affect the final\n> merge-base set. We can stop.\n\nThe important thing to realize at this point is that commits in the\nqueue have received flags from their children (children were walked\ntopologically and \"push\" flags to their parents).\n\nThe STALE bit is pushed from commits that have bits for both sides\nof the merge. This isn't something that we can learn from just\nwalking each side: we need some amount of walking within the\nintersection.\n\nThis doesn't matter if we are looking for a single merge base, but\nwhen we want the full set of independent merge bases, then the STALE\nbit becomes very important.\n\n> On a large monorepo with previously expensive merge-base and\n> merge-tree queries, I observed speedups ranging from roughly 300x\n> to 1000x. The nice thing is that this works for merge-base --all\n> and every internal caller of paint_down_to_common -- we no longer\n> have to restrict the optimization to finding just the first merge-base.\n> \n> Does the correctness argument above hold?\n\nI think that it doesn't work when trying to get all merge bases. It\nrequires\n\n\n   A    X\n  /| __/|\n | |/   |\n | B    |\n | |    |\n..........\n | | __/\n  \\|/\n   C\n\nIn this example, B can reach C through some long list of commits.\nThis makes B (and X) have much higher generation number than C.\nAfter exhausting both sides of A...X, we have B and C in the queue\nwith both side bits and neither are stale. But we need to walk\nfrom B to C to discover that C should be stale.\n\n> Happy to come back with a patch later if the logic holds and the\n> overall approach is wanted.\nYou are identifying a point where optimizations are possible, based\non your measurements of the time spent in this walk waiting for\nqueue_has_nonstale() to end the loop. Specifically, the cost of using\na BFS approach is costing time.\n\nOne place that I would recommend here is to take the work you are\ndoing to investigate the behavior of tips_reachable_from_bases()\nor get_reachable_subset() to see if we can use a DFS-based approach\n_in this case_ where we have exhausted both side and are only caring\nabout the STALE bit checking these cases.\n\nRemember that the DFS idea only helps in the case where we find a\npath between commits (B to C in this case) without walking all of the\ncommits above the minimum generation (generation of C). In an alternate\ncase where B and C are truly independent, this would not save any time.\nBut these \"they are mutually unreachable\" cases always require walking\nthe full set based on the generation number. The good news is that the\nvast majority of cases do not actually have multiple independent merge\nbases, so there is potential here.\n\nThanks,\n-Stolee\n\n"},{"id":"545383","messageId":"CAL71e4OmPzpCXh-zZ8NsT6L4zVKnXV1gqiFZ2w0XgMJhD=LArQ@mail.gmail.com","threadId":"65797","inReplyTo":"0b3f7429-a4fb-4f7a-bf7b-5a0edeb1db52@gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-12T14:32:35Z","receivedAt":"2026-06-12T14:32:47Z","isPatch":false,"body":"On 6/12/2026 2:52 PM, Derrick Stolee wrote:\n\n> The STALE bit is pushed from commits that have bits for both sides\n> of the merge. This isn't something that we can learn from just\n> walking each side: we need some amount of walking within the\n> intersection.\n>\n> This doesn't matter if we are looking for a single merge base, but\n> when we want the full set of independent merge bases, then the STALE\n> bit becomes very important.\n\nThank you for the quick and detailed response and your counterexample\ngraph is exactly the right thing to worry about.\n\n>    A    X\n>   /| __/|\n>  | |/   |\n>  | B    |\n>  | |    |\n> ..........\n>  | | __/\n>   \\|/\n>    C\n>\n> In this example, B can reach C through some long list of commits.\n> This makes B (and X) have much higher generation number than C.\n> After exhausting both sides of A...X, we have B and C in the queue\n> with both side bits and neither are stale. But we need to walk\n> from B to C to discover that C should be stale.\n\nI think your response helped me identify a mistake in how I described\nthe halt condition.\n\nThe required condition must then not be simply \"one side exhausted\".\nThe walk must also continue while non-stale P1|P2 commits remain in the\nqueue, since those still need STALE propagation - they are still\nmerge-base candidates.\n\nSo the actual halt condition would be:\n\n    no non-stale P1|P2 candidates in the queue\n    AND (no pure-P1 OR no pure-P2)\n\nIn your example, B and C are both non-stale P1|P2 commits after\nboth sides are exhausted. Therefore the walk continues. When B is\nprocessed it propagates STALE toward C through the d-chain, and\nbecause the finite-generation region is processed in descending\ngeneration order, that propagation reaches C before C is popped.\n\nIf this reasoning is correct, then the walk only terminates after\nmerge-base candidates have either been processed or marked STALE,\nand the counterexample should produce [B] rather than [B, C].\n\nThanks,\nKristofer\n"},{"id":"545387","messageId":"8d0902ca-98b7-44a4-a23b-51de44ab6daa@gmail.com","threadId":"65797","inReplyTo":"CAL71e4OmPzpCXh-zZ8NsT6L4zVKnXV1gqiFZ2w0XgMJhD=LArQ@mail.gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-12T15:04:38Z","receivedAt":"2026-06-12T15:04:41Z","isPatch":false,"body":"On 6/12/2026 10:32 AM, Kristofer Karlsson wrote:\n> The required condition must then not be simply \"one side exhausted\".\n> The walk must also continue while non-stale P1|P2 commits remain in the\n> queue, since those still need STALE propagation - they are still\n> merge-base candidates.\n> \n> So the actual halt condition would be:\n> \n>     no non-stale P1|P2 candidates in the queue\n>     AND (no pure-P1 OR no pure-P2)\n\nAnd since STALE is added only after both P1 and P2 bits, the two\nconditions are identical to how queue_has_nonstale() terminates the\nloop. \n> If this reasoning is correct, then the walk only terminates after\n> merge-base candidates have either been processed or marked STALE,\n> and the counterexample should produce [B] rather than [B, C].\nThat's the correct distinction: we need the set [B] and not [B,C]\nbut we need to discover that B can reach C to remove it from the\nresult set.\n\nI think there is potential merit in \"switching walk modes\" to DFS\nwhen all queued commits have both P1 and P2, but it comes with a\nlot of complications. So tread carefully if you go down this road.\n\nThanks,\n-Stolee\n\n"},{"id":"545392","messageId":"CAL71e4MFb3UUKBr1P4ZwtK3o1gvUHMs+siCpLTXKkW6Vx=BxRg@mail.gmail.com","threadId":"65797","inReplyTo":"8d0902ca-98b7-44a4-a23b-51de44ab6daa@gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-12T15:21:20Z","receivedAt":"2026-06-12T15:21:34Z","isPatch":false,"body":"On Fri, 12 Jun 2026 at 17:04, Derrick Stolee <stolee@gmail.com> wrote:\n> > So the actual halt condition would be:\n> >\n> >     no non-stale P1|P2 candidates in the queue\n> >     AND (no pure-P1 OR no pure-P2)\n>\n> And since STALE is added only after both P1 and P2 bits, the two\n> conditions are identical to how queue_has_nonstale() terminates the\n> loop.\n\nNo, I think this part is different. I can demonstrate with an example queue\nstate: [P1, stale, P1, stale, stale]\nWith the old code, the non-stale tracker would consider this to be non-stale\nsince it still has two P1 commits to process.\nMy new approach would instead consider that a valid halt state - we\ncan't find any new merge-bases at that point.\n\n> > If this reasoning is correct, then the walk only terminates after\n> > merge-base candidates have either been processed or marked STALE,\n> > and the counterexample should produce [B] rather than [B, C].\n> That's the correct distinction: we need the set [B] and not [B,C]\n> but we need to discover that B can reach C to remove it from the\n> result set.\n\nYes, and I think that part works since we visit them in generational order,\nso B can invalidate C before C is reached.\n\n> I think there is potential merit in \"switching walk modes\" to DFS\n> when all queued commits have both P1 and P2, but it comes with a\n> lot of complications. So tread carefully if you go down this road.\n>\n\nOn the DFS point: I may be misunderstanding the suggestion, but my current\napproach depends quite heavily on generation ordering. The reason the\nSTALE propagation is safe is that, in the finite-generation region,\ndescendants are processed before ancestors. If we switch to DFS, I think we\nwould lose that ordering property unless the DFS is constrained in some\nadditional way.\n\nSo I think I may not fully understand the DFS idea, and I am not sure if\nthat type of optimization would be orthogonal to tweaking the halt condition\nor not.\n\nThanks,\nKristofer\n"},{"id":"545396","messageId":"8c06cc48-d036-4d01-98d3-e94b5edb389c@gmail.com","threadId":"65797","inReplyTo":"CAL71e4MFb3UUKBr1P4ZwtK3o1gvUHMs+siCpLTXKkW6Vx=BxRg@mail.gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-12T15:48:31Z","receivedAt":"2026-06-12T15:48:33Z","isPatch":false,"body":"On 6/12/2026 11:21 AM, Kristofer Karlsson wrote:\n> On Fri, 12 Jun 2026 at 17:04, Derrick Stolee <stolee@gmail.com> wrote:\n>>> So the actual halt condition would be:\n>>>\n>>>     no non-stale P1|P2 candidates in the queue\n>>>     AND (no pure-P1 OR no pure-P2)\n>>\n>> And since STALE is added only after both P1 and P2 bits, the two\n>> conditions are identical to how queue_has_nonstale() terminates the\n>> loop.\n> \n> No, I think this part is different. I can demonstrate with an example queue\n> state: [P1, stale, P1, stale, stale]\n> With the old code, the non-stale tracker would consider this to be non-stale\n> since it still has two P1 commits to process.\n> My new approach would instead consider that a valid halt state - we\n> can't find any new merge-bases at that point.\n\nAh. this is indeed the detail I missed. For any i in {1, 2}, if Pi\nonly appears alongside the STALE bit, then we can stop the walk. This\ntracks because the other bit can't contribute any new information.\n\nA data shape that makes this particularly helpful is the \"release\nbranch\" data shape that I used to justify the --negotiation-include\noption [1].\n\n[1] https://lore.kernel.org/git/62e5ef1a4b800cb18b2e934f45303095d545613b.1779207896.git.gitgitgadget@gmail.com/\n\nSuppose developers are merging into 'main' frequently. On occasion,\nthe tip of 'main' is merged into a new 'release' branch. Thus, the\nfirst-parent history of 'release' is long and completely separate\nfrom the commit history of 'main'. To reach the queue_has_nonstale()\nexit condition, we'd need to walk the entire history.\n\nHowever, if we focus on the single-side condition you are proposing,\nwe can stop walking once everything in the queue that is reachable\nform 'main' is also reachable from that top merge-base.\n>>> If this reasoning is correct, then the walk only terminates after\n>>> merge-base candidates have either been processed or marked STALE,\n>>> and the counterexample should produce [B] rather than [B, C].\n>> That's the correct distinction: we need the set [B] and not [B,C]\n>> but we need to discover that B can reach C to remove it from the\n>> result set.\n> \n> Yes, and I think that part works since we visit them in generational order,\n> so B can invalidate C before C is reached.\n> \n>> I think there is potential merit in \"switching walk modes\" to DFS\n>> when all queued commits have both P1 and P2, but it comes with a\n>> lot of complications. So tread carefully if you go down this road.\n>>\n> \n> On the DFS point: I may be misunderstanding the suggestion, but my current\n> approach depends quite heavily on generation ordering. The reason the\n> STALE propagation is safe is that, in the finite-generation region,\n> descendants are processed before ancestors. If we switch to DFS, I think we\n> would lose that ordering property unless the DFS is constrained in some\n> additional way.\nMy thought was focused on the case of \"all queued commits have P1 and P2\"\nand then we could determine which should be non-stale using DFS focused\nonly on the current queued set.\n\nBut I think your single-sided approach is a better way to get the gains\nthat you want. I think that case is much more likely to occur.\n\nThanks for your persistence in working on this through my\nmisunderstanding.\n\nThanks,\n-Stolee\n\n"},{"id":"545443","messageId":"CAL71e4NRvmDagFAJE-0HYwiLPSfhVVQO2qZe-EJPVXxeC4PWqg@mail.gmail.com","threadId":"65797","inReplyTo":"8c06cc48-d036-4d01-98d3-e94b5edb389c@gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-13T09:42:08Z","receivedAt":"2026-06-13T09:42:21Z","isPatch":false,"body":"On Fri, 12 Jun 2026 at 17:48, Derrick Stolee <stolee@gmail.com> wrote:\n> Suppose developers are merging into 'main' frequently. On occasion,\n> the tip of 'main' is merged into a new 'release' branch. Thus, the\n> first-parent history of 'release' is long and completely separate\n> from the commit history of 'main'. To reach the queue_has_nonstale()\n> exit condition, we'd need to walk the entire history.\n>\n> However, if we focus on the single-side condition you are proposing,\n> we can stop walking once everything in the queue that is reachable\n> form 'main' is also reachable from that top merge-base.\n\nExactly - I have a similar example and a minimal reproduction idea\nfor the current problem:\nConsider two graph shapes for `git merge-base H B`:\n\n    Shape 1 (fast):       Shape 2 (slow):\n\n        H   B                 H   B\n        |   |                 |   |\n        A   |                 A   |\n         \\ /                 / \\ /\n          C                 X   C\n          |                 |   |\n          ...                \\ /\n                              D\n                              |\n                              ...\n\nIn shape 2, A is a merge commit with parents C and X.  X\nbranches off from an older commit D on the main line and gets\nmerged back.  This is extremely common in repositories that\nuse merge commits (monorepos, release-branch workflows).\n\nIn both shapes, C is the only merge-base.  But in shape 2, the\nwalk through X's ancestry is P1-only: STALE propagates through\nC's ancestors but never reaches D's lineage.  The max_nonstale\npointer stays alive until D's entire history is drained.\n\nOn a 2.5M-commit monorepo, we measured this directly by creating\ntest commits with `git commit-tree`:\n\n    Shape 1: 10ms\n    Shape 2: 4.85s\n\nBoth running with stock git 2.53 and both found the merge-base C.\n\nA single merge bypass to old history is enough to force the walk\nthrough the entire graph.  In practice, master's history contains\nmany such merge commits, which is why we consistently see 5-7s\nwall-clock time for merge-base queries.\n\nWith per-side tracking, the P2 side exhausts immediately after C\nis found (B's only parent C has been processed), and the walk\nterminates in 6ms regardless of how deep the P1-only bypass goes.\n\nAs you noted, the \"release branch\" shape is another case where\nthis helps -- the main side exhausts at the merge-base while\nrelease's first-parent history is entirely one-sided.\n\n> But I think your single-sided approach is a better way to get the gains\n> that you want. I think that case is much more likely to occur.\n\nThanks for working through this with me. I started thinking the idea\nitself is not strong enough on its own, so I have attempted to\nwrite a more formal correctness proof covering the\ndrain phase, result exactness, and the INFINITY/finite region\nboundary. It is too long to inline (~2000 words) and the high\nlevel argument is already in this thread, so linking it here\ninstead - I consider it optional reading, since it's not really\nlight reading and we can likely make progress without it:\n\n    https://gist.github.com/spkrka/621695aa464df2a8c1837e9abca822e3\n\nThe proof assumes finite generation numbers (commit-graph\npresent). The side-exhaustion check is guarded by\ngeneration < INFINITY in the implementation.\n\nI am far from an expert in logical proofs though, so this may\nnot be strong enough to be useful, but it may be possible to\nfix it - or it will uncover some flaw that invalidates the idea.\n\n> Thanks for your persistence in working on this through my\n> misunderstanding.\n>\n\nTo be fair, I think this was more a case of me not being fully\nable to explain the idea with enough precision initially, so I\nappreciate getting the opportunity to refine it with your very useful\nexample case.\n\nThanks,\nKristofer\n"},{"id":"545452","messageId":"CAL71e4PD+zT2jLjjvC7EuYX5z6v_VafnWOUDHeEDBq2LGOK7Pw@mail.gmail.com","threadId":"65797","inReplyTo":"CAL71e4NRvmDagFAJE-0HYwiLPSfhVVQO2qZe-EJPVXxeC4PWqg@mail.gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-13T14:08:39Z","receivedAt":"2026-06-13T14:08:52Z","isPatch":false,"body":"On Fri, 13 Jun 2026, Kristofer Karlsson wrote:\n> In both shapes, C is the only merge-base.  But in shape 2, the\n> walk through X's ancestry is P1-only: STALE propagates through\n> C's ancestors but never reaches D's lineage.\n\nI have to add a self-correction here:\nSTALE does reach D through the main line.  The real\nissue is that the bypass branch has a low generation number, so\nmax_nonstale keeps the loop alive until the stale frontier\ndrains all the way down.\n\nIn our monorepo, the concrete trigger is imported repositories.\nAn import merge brings in a separate history with its own root\nat generation 0.  As soon as the walk crosses one such import\nabove the merge-base, max_nonstale forces it to drain the\nentire main graph.  Instrumenting paint_down_to_common confirms\nthis: `merge-base --all HEAD HEAD~1000` takes 2.3M steps, of\nwhich almost all are stale.\n\nThanks,\nKristofer\n"},{"id":"545476","messageId":"CABPp-BGq8a-3ocJ+1HCgJutw1SBUvFg6YxtUamryfgEMx3qDYQ@mail.gmail.com","threadId":"65797","inReplyTo":"CAL71e4Mp7ewv0UGS8j=iTq6quyxLXzrr0uNDbWR8JKaOsTSVyA@mail.gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2026-06-14T04:32:23Z","receivedAt":"2026-06-14T04:32:36Z","isPatch":false,"body":"On Fri, Jun 12, 2026 at 4:18 AM Kristofer Karlsson <krka@spotify.com> wrote:\n>\n> Hi! I previously sent a patch[1] to optimize paint_down_to_common\n> for the single merge-base case. I believe I have found a stronger\n> optimization, but before sending a patch I wanted to discuss the\n> correctness argument.\n>\n> The main problem to solve is that computing merge-bases is slow today\n> in some scenarios, especially large monorepos with complex graphs.\n> This affects multiple operations, including merge-base and merge-tree.\n>\n> The previous patch improved it for the special case of the\n> merge-base being part of the commit-graph and the caller only\n> needing to know about one merge-base.\n>\n> I have an idea to make it faster for fetching all merge-bases for\n> common flows in large repos, as long as the commit graph is\n> reasonably up to date.\n>\n> The key part is the exit condition in paint_down_to_common.\n> Instead of waiting for the queue to only contain stale entries,\n> it is enough to wait for one of the sides to be exhausted,\n> i.e. side 1 is exhausted if no more commits exist in the\n> traversal queue flagged with only PARENT1. For example, if\n> the two sides are origin/HEAD and a small PR branch, the PR\n> branch will quickly become exhausted at the merge-base, while\n> the main side will continue.\n>\n> Now you may ask: why is that a safe condition?\n>\n> The traversal in paint_down_to_common has two logical phases\n> due to the priority queue ordering:\n>\n>   1. Process all commits with infinite generation numbers.\n>      This includes all commits when there is no commit-graph.\n>   2. Process all commits with finite generation numbers.\n>\n> These happen in strict order -- all INFINITY commits are popped\n> before any finite-generation commit.\n>\n> The optimization only applies after the walk enters the second phase.\n> In the first phase, the traversal behaves exactly as today\n> and uses the existing termination condition.\n>\n> In the second phase, traversal follows strict topological\n> order -- descendants are processed before ancestors. Paint flags\n> propagate from each processed commit to its parents, which have\n> strictly lower generation and are therefore not yet examined.\n>\n> A new merge-base candidate can only form when a PARENT1-only path\n> meets a PARENT2-only path. Once a commit acquires both paint flags\n> in this phase, any descendant carrying both paint flags would\n> already have been processed.\n>\n> Once one side is exhausted from the queue, no new meeting between\n> pure sides can occur. Any commit that subsequently acquires both\n> paint flags must inherit them from a commit that already had both\n> flags -- it is deeper in the graph and cannot affect the final\n> merge-base set. We can stop.\n>\n> On a large monorepo with previously expensive merge-base and\n> merge-tree queries, I observed speedups ranging from roughly 300x\n> to 1000x. The nice thing is that this works for merge-base --all\n> and every internal caller of paint_down_to_common -- we no longer\n> have to restrict the optimization to finding just the first merge-base.\n>\n> Does the correctness argument above hold?\n>\n> Happy to come back with a patch later if the logic holds and the\n> overall approach is wanted.\n\nWow...it appears this optimization was discovered by 3 separate people\nin the last month.  This optimization was implemented and is live at\nGitHub...but it feels incomplete to me because my version doesn't\nhandle both sides having an infinite generation number (it just falls\nback to the old algorithm when that happens).  I had meant to fix that\nand then upstream it, but other fires have been keeping me busy.  And\nI'm about to go on vacation on Monday.\n\nI uploaded my version at\nhttps://github.com/gitgitgadget/git/pull/2150.  Unfortunately, it\nconflicts with your recent good work in the area due to being based on\na version of main from about a month ago.\n\nDo you want to take this over, rebase it, and extend to the infinite\ngeneration number case?  Or do you want me to rebase and see it\nthrough after my vacation?  Or some other mixture?\n"},{"id":"545487","messageId":"CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com","threadId":"65797","inReplyTo":"CABPp-BGq8a-3ocJ+1HCgJutw1SBUvFg6YxtUamryfgEMx3qDYQ@mail.gmail.com","subject":"Re: [RFC] commit-reach: terminate merge-base walk when one paint side is exhausted","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-14T11:47:51Z","receivedAt":"2026-06-14T11:48:04Z","isPatch":false,"body":"On Sun, 14 Jun 2026 at 06:32, Elijah Newren <newren@gmail.com> wrote:\n> Wow...it appears this optimization was discovered by 3 separate\n> people in the last month. This optimization was implemented and\n> is live at GitHub...but it feels incomplete to me because my\n> version doesn't handle both sides having an infinite generation\n> number (it just falls back to the old algorithm when that\n> happens).\n\nIt is nice to know that multiple people converged on the same idea\nindependently -- that gives me a lot of confidence that we are\nexploiting a real and useful property of the graph/walk structure.\n\n> I uploaded my version at\n> https://github.com/gitgitgadget/git/pull/2150.\n\nI uploaded mine at\nhttps://github.com/gitgitgadget/git/pull/2149 (draft, still\niterating on the series).\n\nI realize this is getting into implementation details before\nthe idea itself has been discussed on the list. I am happy to wait\nwith a formal patch submission until there is more consensus on the\napproach -- but since you shared your implementation, I wanted to\ncompare notes while it is fresh.\n\nI integrated your new t6600 test cases into my branch -- thanks!\nThey exercise important edge cases that my original tests missed.\nI also extended the perf test to cover the case where both tips\nare outside the commit-graph.\n\nAfter looking at your implementation, I also moved from a\nmax-pointer scheme to per-side counters. We ended up with slightly\ndifferent implementations, but they are tracking the same underlying\ncondition: whether either paint side still has non-stale exclusive\ncommits remaining.\n\nThe main behavioral difference is handling of commits outside the\ncommit-graph. Your version disables the optimization once both\nsides have touched such commits, while mine only enables the break\nafter the walk reaches the finite-generation region. This still\nallows the optimization to fire when both tips start outside the\ngraph, as soon as the walk crosses into commits covered by the\ncommit-graph.\n\n> Do you want to take this over, rebase it, and extend to the\n> infinite generation number case? Or do you want me to rebase\n> and see it through after my vacation? Or some other mixture?\n\nI am happy to keep working on this -- starting from either your\nbranch or mine, or some hybrid. I do not have a strong preference\nfor which version it would be based on, but if either of them lands\nI would be happy. Enjoy your vacation!\n\nThanks,\nKristofer\n"}]}