Re: git branch --contains is slow with a lot of branches

[Jeff King <peff@peff.net>]

On Tue, Mar 31, 2015 at 10:45:11AM +0900, Mike Hommey wrote:

> Using git branch --contains can be a very expensive thing:
> [...]

Yes, this is well known. It does a separate traversal for each branch,
which is why you noticed that it's linear in the number of branches.

I changed the "tag --contains" algorithm a while ago to do it all in one
traversal. The downside is that it uses a depth-first approach which
means it almost always goes to the roots. This is more appropriate for
tags (as you often have old tags), but less so for branches.

I did some work on a contains() implementation that would is
breadth-first, but handles multiple tips in a single traversal. It needs
a little polish, and then to be hooked into "git branch". This is part
of the proposed GSoC project for unifying "tag -l", "branch -l", and
"for-each-ref".

-Peff