From: Jeff King Date: Mon, 08 Jun 2026 23:12:18 GMT Subject: Re: limiting git branch --contains 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: > 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