moin,

git branch --contains can be a rather expensive operation in big repositories. as my use case is actually a rather limited search for commits in my local wip branches, it would be helpful to be able to specify exclusions for the rev-walk, say

   git branch --contains deadbeef ^origin/master

suggestions how this is actually already achievable efficiently are of course welcome as well. ^^

thanks!

Oswald Buddenhagen <oswald.buddenhagen@gmx.de> writes:

I can do

    $ git branch --list --contains master \??/\*

to show only the topic branches that forked from/after 'master', and replacing 'master' with v2.40.0 or any older point and the output starts showing more branches, but the search excludes integration branches like 'next' and 'seen'. Is that what you are after?

On Thu, Mar 23, 2023 at 12:42:52PM -0700, Junio C Hamano wrote:

not really. the objective is finding the work branch(es) a given sha1 is coming from. 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. 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. 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.

am i making sense?

On Thu, Mar 23, 2023 at 1:07 PM Oswald Buddenhagen <oswald.buddenhagen@gmx.de> wrote:

Because I saw no way to specify only the actual commits of my branches, I wrote a tool: git-smartlist [1]

In particular the negate_upstreams helper, which basically goes through all the branches and does topic1@{u}..topic1 topic2@{u}..topic2 etc.

[1] https://github.com/felipec/git-smartlist/blob/master/git-smartlist

On 3/23/2023 4:44 PM, Oswald Buddenhagen wrote:

Could you make sure to run 'git commit-graph write --reachable' before testing again?

When the commit-graph exists on disk, the algorithm does do a single reachability walk from all the initial points. If it does not exist, then each starting point triggers its own reachability walk, which is significantly slower. See repo_is_descendant_of() in commit-reach.c for more information on this split.

Thanks, -Stolee

On Fri, Mar 24, 2023 at 01:23:32PM -0400, Derrick Stolee wrote:

i did, didn't help.

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.

On 3/24/2023 2:15 PM, Oswald Buddenhagen wrote:

Hm. The point is that it _should_ improve things by several orders of magnitude by using generation numbers to avoid walking a significant portion of the commits. That is, unless the commit is extremely old.

But what you were originally asking was also about filtering the set of branches to pick, instead of just the commits that are walked.

In that case, perhaps you should use 

  git for-each-ref --format="%(refname)" --contains=<oid> <ref1> <ref2> ... <refN>

or use ref patterns instead of exact refs, if you have such a grouping?

Thanks, -Stolee

On Fri, Mar 24, 2023 at 02:20:01PM -0400, Derrick Stolee wrote:

well, at that point it would be kinda sufficient. ^^ but it really doesn't do anything at all (i tried moving away the graph for comparison). maybe the operation just forgets to load the graph?

i didn't, i was just misunderstood.

On Fri, Mar 24, 2023 at 01:23:32PM -0400, Derrick Stolee wrote:

I'm a bit confused by that reference. We do switch behavior based on the presence of generation numbers in repo_is_descendant_of(). But ref-filter calls that function from commit_contains(), which is only fed one ref at a time. So we'll still do several walks, one per ref.

In commit_contains() we'll use the "tag algo" instead of calling repo_is_descendant_of(). It still sees the refs individually, but it keeps a cache to avoid walking over the same parts of history. We didn't traditionally use that algorithm for branches because it has a tendency to walk down to the roots (which is OK for tags, where you have old ones that require walking down that far anyway, but not for branches, where you can usually stop at a recent merge base). But now that we have reliable generation numbers, we can stop that traversal early.

But it doesn't look like we actually trigger the tag algo for anything but git-tag. I.e., I wonder if we should be doing something like this:

On Fri, Mar 24, 2023 at 08:02:53PM +0100, Oswald Buddenhagen wrote:

That seems weird. I get a 3000x speedup just by using building the commit-graph. Are you seeing any change at all? What version of Git are you using?

I'd be curious, too, if you can try the patch I posted elsewhere in the thread to see if that improves things.

-Peff

On Fri, Mar 24, 2023 at 03:13:02PM -0400, Jeff King wrote:

so i strace'd the thing, and there is indeed no appearance of 'commit-graph' in the log.

so i tried git log --graph ... and still nothing?!

and yes, core.commitgraph is true (originally absent, so same thing).

indeed.

so weird in fact, that i tried another repository. and it works!

so apparently something is wrong with my/the linux repository. things i can imagine contributing to throwing it off somehow:

$ git remote -v alsa git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound.git (fetch) alsa git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound.git (push) history git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git (fetch) history git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git (push) linux-mips git://git.linux-mips.org/pub/scm/ralf/linux (fetch) linux-mips git://git.linux-mips.org/pub/scm/ralf/linux (push) linux-wireless git://git.kernel.org/pub/scm/linux/kernel/git/kvalo/wireless-drivers (fetch) linux-wireless git://git.kernel.org/pub/scm/linux/kernel/git/kvalo/wireless-drivers (push) origin git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git (fetch) origin git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git (push) ossi git@github.com:ossilator/linux.git (fetch) ossi git@github.com:ossilator/linux.git (push)

(the linux-* remotes haven't been pulled for years.)

$ grep replace .git/packed-refs a3628e41a9946c4fe93d9b2ae5906e1b2184fa8e refs/replace/1da177e4c3f41524e886b7f1b8a0c1fc7321cac2

rather recent master. dogfeeding my contributions.

On Fri, Mar 24, 2023 at 08:58:39PM +0100, Oswald Buddenhagen wrote:

That "--graph" option is unrelated. It asks for Git to draw a graph in the output. Commit-graph is a fancy name for "a cache file which stores some metadata about commits so we can quickly answer graph-like queries such as ancestry, etc".

Ah, that is your problem. When "replace" refs are in use, the data stored in the commit-graph can't reliably be used. It is storing invariants like "commit XYZ is the Nth generation from the root", which is an immutable property of a commit with a given hash. But as soon as you use grafts or replace refs, now we don't know if that information is valid or not (not just for the replaced commit, but for any of its ancestors which might have been replaced). So the whole thing is disabled.

I'd guess you are grafting the "history" remote's contents onto the start of Linus's repo. It's probably better to do that in a one-off repository, rather than your day-to-day working one. But you can also flip it off and on at will. Try:

  git -c core.useReplaceRefs=false branch --contains ...

which I think should get faster. And likewise you can set it to "false" in your config for day-to-day use, and then flip it on when you want to run a command that you think might query all the way down into ancient history.

If it does make things faster for you, I'd still be curious to see the difference between "just commit graphs" and "commit graphs plus the patch I showed earlier". I think it should make things faster, but if it's only a few milliseconds on average, it's not that urgent to pursue.

-Peff

On Fri, Mar 24, 2023 at 04:45:04PM -0400, Jeff King wrote:

i know. it just happens to be the go-to example from derrick's blog post about commit-graph, so that not working was a dead giveaway that something is really wrong.

why isn't the commit-graph built with the replaces applied (and tagged by a hash of the used replaces, so we know when to ignore it)?

at minimum, i'd expect a warning giving a reason when the graph is ignored.

yes, that works. and _rather_ convincingly, to put it that way.

if there is a speed difference at all, it gets drowned out by the noise.

On Fri, Mar 24, 2023 at 11:06:55PM +0100, Oswald Buddenhagen wrote:

I think a similar idea has come up before, but we decided to do the simplest safe thing (disabling optimizations) to start with. And then somebody who really cared about making optimizations work with commit graphs could come along and do so later. Nobody has yet; you could be that someone. ;)

That might be reasonable. The commit graph is an optimization, so we'd never produce a wrong answer by ignoring it. And since the fallback was the status quo before the optimizations were implemented, it didn't seem like that big a deal. But these days the performance many of us expect is with those optimizations, so perhaps the tables have turned.

I do think there might be some complications, though. I think we may build commit graphs by default these days during "gc" and even incrementally after "fetch". If we warned when the graphs are disabled, it basically means that every command in a repo with replace refs would issue the warning.

OK, thanks for testing. I do think that looking into a true single traversal might make sense, but I don't think we've seen a case yet where it's a substantial speedup.

-Peff

On Sat, Mar 25, 2023 at 02:30:35AM -0400, Jeff King wrote:

damn ;)

yeah, i thought about that, too ...

it would be easy enough to squelch the warning by manually disabling writing or using the graph. the downside is that if the root cause gets fixed, the user would be still missing out (unless they read the changelog and remembered to reconfigure all affected repos).

one could make it an advisory message which can be explictly squelched.

Hi!

I'm reviving this old thread because I believe the discussion here is still relevant and the patch Peff included is good. I think I accidentally created the exact same patch before I found this thread.

I work on a large repo (millions of commits, ~8000 remote tracking branches) where "git for-each-ref --contains <commit> refs/remotes/" was taking 4+ seconds even with a commit-graph, and much worse for deeper commits. I started investigating and building a more complex batched solution before I realized that the cached DFS algorithm (contains_tag_algo) already exists and does exactly what's needed -- it just wasn't enabled for branches.

With generation numbers (commit-graph), the cached algorithm is strictly at least as good as the uncached one. Both have the same walk floor -- the generation cutoff in contains_tag_algo is equivalent to the STALE boundary in paint_down_to_common. The cache then provides a pure win: O(total unique commits) instead of O(N * commits per ref).

In my benchmarks, the improvement is significant and scales with the number of refs and the depth of the target commit:

git.git (69K commits, 5826 tags) with commit-graph:

  Scenario              Master    Cached    Speedup
  Deep (v2.30.0)        1.08s     292ms     3.7x
  Recent (HEAD~100)     338ms     240ms     1.4x
  Orphan (unreachable)  271ms     241ms     1.1x

Large monorepo with commit-graph:

  Scenario              Master    Cached    Speedup
  HEAD~10000            511ms     239ms     2.1x
  HEAD~50000            4.14s     272ms     15x
  Orphan (unreachable)  4.13s     252ms     16x

I also tested with varying ref counts on git.git. The cached algorithm is faster or tied in every scenario I tested -- the crossover point is around 3-6 refs, below which both complete in single-digit milliseconds.

Without commit-graph, the difference is even more dramatic (41-54x on git.git with 5826 tags), though the theoretical argument is less clean: without generation numbers, contains_tag_algo has no walk floor and may traverse to root commits for unreachable targets. In practice the cache still wins for N > 1, but I don't have a proof that covers all possible DAG shapes. I think we should start by optimizing it for the case where we have generation numbers, and maybe keep exploring if there are any meaningful scenarios without generation numbers where it would actually be a regression.

To reproduce the benchmarks:

  # Setup
  ORPHAN=$(git commit-tree HEAD^{tree} -m "unreachable")
  git commit-graph write --reachable

  # git.git with 5826 tags
  git for-each-ref --contains v2.30.0 refs/tags/

  # Large repo with remote refs
  git for-each-ref --contains HEAD~50000 refs/remotes/

-- Kristofer

On Wed, May 27, 2026 at 09:05:09AM +0200, Kristofer Karlsson wrote:

Yeah, I think this is worth pursuing. Looks like somebody else also generated a similar patch recently:

  https://lore.kernel.org/git/20260607-ref-filter-memoized-contains-v1-1-a1972dde9c76@gmail.com/

But I think the approach in this thread (to use depth-first only when we have generation numbers) makes more sense.

I cc'd you on that thread.

-Peff