From: Jeff King <peff@peff.net>
To: Kristofer Karlsson <krka@spotify.com>
Cc: git@vger.kernel.org, Derrick Stolee <derrickstolee@github.com>
Subject: Re: limiting git branch --contains
Date: Mon, 8 Jun 2026 19:12:18 -0400 [thread overview]
Message-ID: <20260608231218.GD340696@coredump.intra.peff.net> (raw)
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
next prev parent reply other threads:[~2026-06-08 23:12 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-03-23 18:54 limiting git branch --contains Oswald Buddenhagen
2023-03-23 19:42 ` Junio C Hamano
2023-03-23 20:44 ` Oswald Buddenhagen
2023-03-24 17:23 ` Derrick Stolee
2023-03-24 18:15 ` Oswald Buddenhagen
2023-03-24 18:20 ` Derrick Stolee
2023-03-24 19:02 ` Oswald Buddenhagen
2023-03-24 19:13 ` Jeff King
2023-03-24 19:58 ` Oswald Buddenhagen
2023-03-24 20:45 ` Jeff King
2023-03-24 22:06 ` Oswald Buddenhagen
2023-03-25 6:30 ` Jeff King
2023-03-25 8:05 ` Oswald Buddenhagen
2023-03-24 19:10 ` Jeff King
2026-05-27 7:05 ` Kristofer Karlsson
2026-06-08 23:12 ` Jeff King [this message]
2023-03-23 20:56 ` Felipe Contreras
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20260608231218.GD340696@coredump.intra.peff.net \
--to=peff@peff.net \
--cc=derrickstolee@github.com \
--cc=git@vger.kernel.org \
--cc=krka@spotify.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.