Re: limiting git branch --contains

[Derrick Stolee <derrickstolee@github.com>]

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