git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Jeff King <peff@peff.net>
Date
Mar 31, 2015, 03:03 UTC
Message-ID
<20150331030357.GA19170@peff.net>
In-Reply-To
<20150331014511.GA28418@glandium.org>
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
Previous: Mike Hommey
Message 2 of 2 in “git branch --contains is slow with a lot of branches”
  1. Mike HommeyMar 31, 2015
  2. Jeff KingMar 31, 2015

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.