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

Re: limiting git branch --contains

From
Jeff King <peff@peff.net>
Date
Jun 8, 2026, 23:12 UTC
Message-ID
<20260608231218.GD340696@coredump.intra.peff.net>
In-Reply-To
<20260527070510.3510836-1-krka@spotify.com>
On Wed, May 27, 2026 at 09:05:09AM +0200, Kristofer Karlsson wrote:
Show 8 quoted lines
> 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:

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
Previous: Kristofer KarlssonNext: Felipe Contreras
Message 16 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.