limiting git branch --contains

limiting git branch --contains

[Oswald Buddenhagen]

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!

Re: limiting git branch --contains

[Junio C Hamano]

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

> 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,...

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?

Re: limiting git branch --contains

[Oswald Buddenhagen]

On Thu, Mar 23, 2023 at 12:42:52PM -0700, Junio C Hamano wrote:
>Oswald Buddenhagen <oswald.buddenhagen@gmx.de> writes:
>
>> 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,...
>
>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?
>
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?

Re: limiting git branch --contains

[Derrick Stolee]

On 3/23/2023 4:44 PM, Oswald Buddenhagen wrote:
> On Thu, Mar 23, 2023 at 12:42:52PM -0700, Junio C Hamano wrote:
>> Oswald Buddenhagen <oswald.buddenhagen@gmx.de> writes:
>>
>>> 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,...
>>
>> 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?
>>
> 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.

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

Re: limiting git branch --contains

[Oswald Buddenhagen]

On Fri, Mar 24, 2023 at 01:23:32PM -0400, Derrick Stolee wrote:
>Could you make sure to run 'git commit-graph write --reachable' before
>testing again?
>
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.

Re: limiting git branch --contains

[Derrick Stolee]

On 3/24/2023 2:15 PM, Oswald Buddenhagen wrote:
> On Fri, Mar 24, 2023 at 01:23:32PM -0400, Derrick Stolee wrote:
>> Could you make sure to run 'git commit-graph write --reachable' before
>> testing again?
>>
> 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.

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

Re: limiting git branch --contains

[Oswald Buddenhagen]

On Fri, Mar 24, 2023 at 02:20:01PM -0400, Derrick Stolee wrote:
>Hm. The point is that it _should_ improve things by several orders
>of magnitude [...]
>
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?

>But what you were originally asking was also about filtering the
>set of branches to pick,
>
i didn't, i was just misunderstood.

Re: limiting git branch --contains

[Jeff King]

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

> On Fri, Mar 24, 2023 at 02:20:01PM -0400, Derrick Stolee wrote:
> > Hm. The point is that it _should_ improve things by several orders
> > of magnitude [...]
> > 
> 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?

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

Re: limiting git branch --contains

[Oswald Buddenhagen]

On Fri, Mar 24, 2023 at 03:13:02PM -0400, Jeff King wrote:
>On Fri, Mar 24, 2023 at 08:02:53PM +0100, Oswald Buddenhagen wrote:
>> maybe the operation just forgets to load the graph?
>
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).

>That seems weird.
>
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

>What version of Git are you using?
>
rather recent master. dogfeeding my contributions.

Re: limiting git branch --contains

[Jeff King]

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

> On Fri, Mar 24, 2023 at 03:13:02PM -0400, Jeff King wrote:
> > On Fri, Mar 24, 2023 at 08:02:53PM +0100, Oswald Buddenhagen wrote:
> > > maybe the operation just forgets to load the graph?
> > 
> 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?!

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".

> 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

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

Re: limiting git branch --contains

[Oswald Buddenhagen]

On Fri, Mar 24, 2023 at 04:45:04PM -0400, Jeff King wrote:
>On Fri, Mar 24, 2023 at 08:58:39PM +0100, Oswald Buddenhagen wrote:
>> so i tried git log --graph ... and still nothing?!
>
>That "--graph" option is unrelated. It asks for Git to draw a graph in
>the output.
>
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.

>> a3628e41a9946c4fe93d9b2ae5906e1b2184fa8e refs/replace/1da177e4c3f41524e886b7f1b8a0c1fc7321cac2
>
>Ah, that is your problem. When "replace" refs are in use, the data
>stored in the commit-graph can't reliably be used. [...]
>
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.

>  git -c core.useReplaceRefs=false branch --contains ...
>
>which I think should get faster.
>
yes, that works. and _rather_ convincingly, to put it that way.

>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.
>
if there is a speed difference at all, it gets drowned out by the noise.

Re: limiting git branch --contains

[Jeff King]

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

> > Ah, that is your problem. When "replace" refs are in use, the data
> > stored in the commit-graph can't reliably be used. [...]
> > 
> 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)?

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. ;)

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

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.

> > 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.
> > 
> if there is a speed difference at all, it gets drowned out by the noise.

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

Re: limiting git branch --contains

[Oswald Buddenhagen]

On Sat, Mar 25, 2023 at 02:30:35AM -0400, Jeff King wrote:
> Nobody has yet; you could be that someone. ;)
>
damn ;)

>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.
>
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.

Re: limiting git branch --contains

[Jeff King]

On Fri, Mar 24, 2023 at 01:23:32PM -0400, Derrick Stolee 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.

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:

diff --git a/commit-reach.c b/commit-reach.c
index 7c0c39fd286..16c1a341bf5 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -712,7 +712,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 int commit_contains(struct ref_filter *filter, struct commit *commit,
 		    struct commit_list *list, struct contains_cache *cache)
 {
-	if (filter->with_commit_tag_algo)
+	if (filter->with_commit_tag_algo ||
+	    generation_numbers_enabled(the_repository))
 		return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
 	return repo_is_descendant_of(the_repository, commit, list);
 }

The speedup is pretty minor compared to using commit-graphs at all.
Doing "git for-each-ref --format='%(refname)' --contains HEAD" on a
clone of linux.git gets me:

  - with no commit graph: 1m40s
  - after "commit-graph write --reachable": 30ms
  - plus the patch above; 23ms

So most of the help comes from not parsing the commit objects (courtesy
of the commit graph) and perhaps some early cutoffs (due to the use of
generation numbers in repo_is_descendant_of()). Using the cached walk
helps a little, but it may be more so for certain patterns of data.

I also scratched my head a little that we are still using
commit_contains() at all. I thought we now had functions to do a single
walk that would give us an answer for each ref, and that we could
trigger that in filter_refs(). And we do have reach_filter() there, but
I think it only handles --merged/--no-merged.

I admit I haven't kept up with the state of things here, so I'm not sure
what tools we have available.

-Peff

Re: limiting git branch --contains

[Felipe Contreras]

On Thu, Mar 23, 2023 at 1:07 PM Oswald Buddenhagen
<oswald.buddenhagen@gmx.de> wrote:
>
> 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. ^^

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

-- 
Felipe Contreras