{"thread":{"id":"38955","subject":"git branch --contains is slow with a lot of branches","startedAt":"2015-03-31T01:45:11Z","lastAt":"2015-03-31T03:03:58Z","messageCount":2,"participants":["Mike Hommey","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"258722","messageId":"20150331014511.GA28418@glandium.org","threadId":"38955","inReplyTo":null,"subject":"git branch --contains is slow with a lot of branches","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2015-03-31T01:45:11Z","receivedAt":"2015-03-31T01:45:11Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"Hi,\n\nSometimes I want to know what (possibly remote) branch contains a given\ncommit. The repository where I do that has thousands of branches:\n\n$ git for-each-ref | wc -l\n7657\n\nAnd a lot of commits:\n\n$ git rev-list --all | wc -l\n538174\n\nUsing git branch --contains can be a very expensive thing:\n\n$ time git branch --contains 0812b94 --all > /dev/null\n\n  real  3m0.871s\n  user  3m0.828s\n  sys   0m0.084s\n\nI'd argue this shouldn't take much more time than enumerating all revs:\n\n$ time git rev-list --all | wc -l\n538174\n\nreal    0m4.842s\nuser    0m4.488s\nsys     0m1.332s\n\nThis can be reproduced to a certain degree with the git git repo:\n\n$ git clone https://github.com/git/git\n$ cd git\n$ for i in $(seq 1 1000); do git branch branch$i master; done\n$ git gc # will pack the refs\n$ time git rev-list --all | wc -l\n40886\n\nreal    0m0.505s\nuser    0m0.464s\nsys     0m0.108s\n\n$ time git branch --contains v2.0.0 > /dev/null\n\nreal    0m6.207s\nuser    0m6.204s\nsys     0m0.004s\n\n(especially in this case where all branches point to the same commit)\n\nIt's also essentially linear on the number of branches:\n\n$ for i in $(seq 1001 7000); do git branch branch$i master; done\n$ git gc\n$ time git rev-list --all | wc -l\n40886\n\nreal    0m0.493s\nuser    0m0.484s\nsys     0m0.076s\n\n$ time git branch --contains v2.0.0 > /dev/null\n\nreal    0m43.446s\nuser    0m43.436s\nsys     0m0.040s\n\nMike\n"},{"id":"258724","messageId":"20150331030357.GA19170@peff.net","threadId":"38955","inReplyTo":"20150331014511.GA28418@glandium.org","subject":"Re: git branch --contains is slow with a lot of branches","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-31T03:03:58Z","receivedAt":"2015-03-31T03:03:58Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 31, 2015 at 10:45:11AM +0900, Mike Hommey wrote:\n\n> Using git branch --contains can be a very expensive thing:\n> [...]\n\nYes, this is well known. It does a separate traversal for each branch,\nwhich is why you noticed that it's linear in the number of branches.\n\nI changed the \"tag --contains\" algorithm a while ago to do it all in one\ntraversal. The downside is that it uses a depth-first approach which\nmeans it almost always goes to the roots. This is more appropriate for\ntags (as you often have old tags), but less so for branches.\n\nI did some work on a contains() implementation that would is\nbreadth-first, but handles multiple tips in a single traversal. It needs\na little polish, and then to be hooked into \"git branch\". This is part\nof the proposed GSoC project for unifying \"tag -l\", \"branch -l\", and\n\"for-each-ref\".\n\n-Peff\n"}]}