git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: limiting git branch --contains

From
Kristofer Karlsson <krka@spotify.com>
Date
May 27, 2026, 07:05 UTC
Message-ID
<20260527070510.3510836-1-krka@spotify.com>
In-Reply-To
<20230324191009.GA536967@coredump.intra.peff.net>
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
Previous: Jeff KingNext: Jeff King
Message 15 of 17 in “limiting git branch --contains”
  1. Oswald BuddenhagenMar 23, 2023
  2. Junio C HamanoMar 23, 2023
  3. Oswald BuddenhagenMar 23, 2023
  4. Derrick StoleeMar 24, 2023
  5. Oswald BuddenhagenMar 24, 2023
  6. Derrick StoleeMar 24, 2023
  7. Oswald BuddenhagenMar 24, 2023
  8. Jeff KingMar 24, 2023
  9. Oswald BuddenhagenMar 24, 2023
  10. Jeff KingMar 24, 2023
  11. Oswald BuddenhagenMar 24, 2023
  12. Jeff KingMar 25, 2023
  13. Oswald BuddenhagenMar 25, 2023
  14. Jeff KingMar 24, 2023
  15. Kristofer KarlssonMay 27, 2026
  16. Jeff KingJun 8, 2026
  17. Felipe ContrerasMar 23, 2023

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.