{"thread":{"id":"14617","subject":"q: faster way to integrate/merge lots of topic branches?","startedAt":"2008-07-23T13:05:18Z","lastAt":"2008-07-25T08:46:48Z","messageCount":32,"participants":["Ingo Molnar","Andreas Ericsson","SZEDER Gábor","Sergey Vlasov","Björn Steinbrink","Santi Béjar","Jay Soffian","Miklos Vajna","Junio C Hamano","Linus Torvalds","Pierre Habouzit","Lars Hjemli","Nanako Shiraishi"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"84480","messageId":"20080723130518.GA17462@elte.hu","threadId":"14617","inReplyTo":null,"subject":"q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T13:05:18Z","receivedAt":"2008-07-23T13:05:18Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\nI've got the following, possibly stupid question: is there a way to \nmerge a healthy number of topic branches into the master branch in a \nquicker way, when most of the branches are already merged up?\n\nRight now i've got something like this scripted up:\n\n for B in $(git-branch | cut -c3- ); do git-merge $B; done \n\nIt takes a lot of time to run on even a 3.45GHz box:\n\n real 0m53.228s\n user 0m41.134s\n sys 0m11.405s\n\nI just had a workflow incident where i forgot that this script was \nrunning in one window (53 seconds are a _long_ time to start doing some \nother stuff :-), i switched branches and the script merrily chugged away \nmerging branches into a topic branch i did not intend.\n\nIt iterates over 140 branches - but all of them are already merged up.\n\nAnyone can simulate it by switching to the linus/master branch of the \ncurrent Linux kernel tree, and doing:\n\n time for ((i=0; i<140; i++)); do git-merge v2.6.26; done\n\n real 1m26.397s\n user 1m10.048s\n sys 0m13.944s\n\nOne could argue that determining whether it's all merged up already is a \ncomplex task, but but even this seemingly trivial merge of HEAD into \nHEAD is quite slow:\n\n time for ((i=0; i<140; i++)); do git-merge HEAD; done\n\n real 0m17.871s\n user 0m8.977s\n sys 0m8.396s\n\nI'm wondering whether there are tricks to speed this up. The real script \ni'm using is much longer and obscured with boring details like errors, \nconflicts, etc. - but the above is the gist of it. (and that is what \nmakes it slow primarily)\n\nUsing a speculative Octopus might be one approach, but that runs into \nthe octopus merge limitation at 24 branches, and it also is quite slow \nas well. (and is not equivalent to the serial merge of 140 branches)\n\nI have thought of using the last CommitDate of the topic branch and \ncompare it with the last CommitDate of the master branch [and i can \ntrust those values] - that would be a lot faster - but maybe i'm missing \nsomething trivial that makes that approach unworkable. It would also be \nnice to have a builtin shortcut for that instead of having to go via \n\"git-log --pretty=fuller\" to dump the CommitDate field.\n\nbuiltin-integrate.c perhaps? ;-)\n\n\tIngo\n"},{"id":"84483","messageId":"20080723131736.GA9100@elte.hu","threadId":"14617","inReplyTo":"20080723130518.GA17462@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T13:17:36Z","receivedAt":"2008-07-23T13:17:36Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> I have thought of using the last CommitDate of the topic branch and \n> compare it with the last CommitDate of the master branch [and i can \n> trust those values] - that would be a lot faster - but maybe i'm \n> missing something trivial that makes that approach unworkable. It \n> would also be nice to have a builtin shortcut for that instead of \n> having to go via \"git-log --pretty=fuller\" to dump the CommitDate \n> field.\n\nhm, this method would be fragile if done purely within my integration \nscript, as the timestamp of the head would have to be updated \natomically, while always merging all the topic branches in one such \ntransaction. (so that the timestamps do not get out of sync and a topic \nbranch is not skipped by accident)\n\nSo i guess it's better to just create a separate .git/refs/merge-cache/ \nhierarchy with timestamps of last merged branches and their head sha1 \n... but maybe i'm banging on open doors?\n\n\tIngo\n"},{"id":"84486","messageId":"488734D9.9070703@op5.se","threadId":"14617","inReplyTo":"20080723130518.GA17462@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-07-23T13:40:41Z","receivedAt":"2008-07-23T13:40:41Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Ingo Molnar wrote:\n> I've got the following, possibly stupid question: is there a way to \n> merge a healthy number of topic branches into the master branch in a \n> quicker way, when most of the branches are already merged up?\n> \n> Right now i've got something like this scripted up:\n> \n> for B in $(git-branch | cut -c3- ); do git-merge $B; done \n> \n> It takes a lot of time to run on even a 3.45GHz box:\n> \n> real 0m53.228s\n> user 0m41.134s\n> sys 0m11.405s\n> \n> I just had a workflow incident where i forgot that this script was \n> running in one window (53 seconds are a _long_ time to start doing some \n> other stuff :-), i switched branches and the script merrily chugged away \n> merging branches into a topic branch i did not intend.\n> \n> It iterates over 140 branches - but all of them are already merged up.\n> \n\nWith the builtin merge (which is in next), this should be doable with\nan octopus merge, which will eliminate the branches that are already\nfully merged, resulting in a less-than-140-way merge (thank gods...).\nIt also doesn't have the 24-way cap that the scripted version suffers\nfrom.\n\nIf it does a good job at your rather extreme use-case, I'd say it's\ngood enough for 'master' pretty soon :-)\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"84491","messageId":"20080723174140.b749191a.vsu@altlinux.ru","threadId":"14617","inReplyTo":"20080723130518.GA17462@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2008-07-23T13:41:40Z","receivedAt":"2008-07-23T13:41:40Z","isPatch":false,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"On Wed, 23 Jul 2008 15:05:18 +0200 Ingo Molnar wrote:\n\n> Anyone can simulate it by switching to the linus/master branch of the\n> current Linux kernel tree, and doing:\n>\n> time for ((i=0; i<140; i++)); do git-merge v2.6.26; done\n>\n> real 1m26.397s\n> user 1m10.048s\n> sys 0m13.944s\n\nTiming results here (E6750 @ 2.66GHz):\n41.61s user 3.71s system 99% cpu 45.530 total\n\nHowever, testing whether there is something new to merge could be\nperformed significantly faster:\n\n$ time sh -c 'for ((i=0; i<140; i++)); do [ -n \"$(git rev-list --max-count=1 v2.6.26 ^HEAD)\" ]; done'\nsh -c 5.49s user 0.26s system 99% cpu 5.786 total\n\nThe same loop with \"git merge-base v2.6.26 HEAD\" takes about 40\nseconds here - apparently finding the merge base is the expensive\npart, and it makes sense to avoid it if you expect that most of your\nbranches do not contain anything new to merge.\n"},{"id":"84489","messageId":"20080723134926.GA12888@elte.hu","threadId":"14617","inReplyTo":"20080723131736.GA9100@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T13:49:26Z","receivedAt":"2008-07-23T13:49:26Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> So i guess it's better to just create a separate \n> .git/refs/merge-cache/ hierarchy with timestamps of last merged \n> branches and their head sha1 ... but maybe i'm banging on open doors?\n\nhere's the git-fastmerge script i've whipped up in 10 minutes. It does \nthe trick nicely for me:\n\nfirst run:\n\n real 0m53.228s\n user 0m41.134s\n sys 0m11.405s\n\nsecond run:\n\n real 0m2.751s\n user 0m1.280s\n sys 0m1.491s\n\nor a 20x speedup. Yummie! :-)\n\nIt properly notices when i commit to a topic branch, and it maintains a \nproper matrix of <- merge timestamps. It even embedds the sha1's \nin the timestamp path so it should be quite complete. It should work \nfine across resets, re-merges, etc. too i think. It should work well \nwith renamed branches as well i think. (although i dont do that all that \noften)\n\nIn fact even if i delete the whole .git/mergecache/ hierarchy and run a \n'cold' merge, it's much faster:\n\n real 0m32.129s\n user 0m24.456s\n sys 0m7.603s\n\nBecause many of the branches have the same sha1 so it's already \nhalf-optimized even on the first run.\n\nMuch of the remaining 2.7 seconds overhead comes from the git-log runs \nto retrieve the sha1s, so i guess it could all be made even faster.\n\nNow this scheme assumes that there's a sane underlying filesystem that \ncan take these long pathnames and which has good timestamps (which i \nhave, so it's not a worry for me).\n\nHm?\n\n\tIngo\n\n-----------------{ git-fastmerge }--------------------->\n#!/bin/bash\n\nusage () {\n echo 'usage: git-fastmerge ..'\n exit -1\n}\n\n[ $# = 0 ] && usage\n\nBRANCH=$1\n\nMERGECACHE=.git/mergecache\n\n[ ! -d $MERGECACHE ] && { mkdir $MERGECACHE || usage; }\n\nHEAD_SHA1=$(git-log -1 --pretty=format:\"%H\")\nBRANCH_SHA1=$(git-log -1 --pretty=format:\"%H\" $BRANCH)\n\nCACHE=$MERGECACHE/$HEAD_SHA1/$BRANCH_SHA1\n\n[ -f \"$CACHE\" -a \"$CACHE\" -nt .git/refs/heads/$BRANCH_SHA1 ] && {\n echo \"merge-cache hit on HEAD <= $1\"\n exit 0\n}\n\ngit-merge $1 && {\n mkdir -p $(dirname $CACHE)\n touch $CACHE\n}\n"},{"id":"84490","messageId":"20080723135621.GJ22606@neumann","threadId":"14617","inReplyTo":"20080723130518.GA17462@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"SZEDER Gábor","fromEmail":"szeder@ira.uka.de","sentAt":"2008-07-23T13:56:21Z","receivedAt":"2008-07-23T13:56:21Z","isPatch":false,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"Hi,\n\nOn Wed, Jul 23, 2008 at 03:05:18PM +0200, Ingo Molnar wrote:\n> I've got the following, possibly stupid question: is there a way to \n> merge a healthy number of topic branches into the master branch in a \n> quicker way, when most of the branches are already merged up?\n> \n> Right now i've got something like this scripted up:\n> \n> for B in $(git-branch | cut -c3- ); do git-merge $B; done \nyou cound use 'git branch --no-merged' to list only those branches\nthat have not been merged into your current HEAD.\n\n\nÜdv,\nGábor\n"},{"id":"84492","messageId":"20080723140243.GA6678@elte.hu","threadId":"14617","inReplyTo":"488734D9.9070703@op5.se","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T14:02:43Z","receivedAt":"2008-07-23T14:02:43Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Andreas Ericsson wrote:\n\n> Ingo Molnar wrote:\n>> I've got the following, possibly stupid question: is there a way to \n>> merge a healthy number of topic branches into the master branch in a \n>> quicker way, when most of the branches are already merged up?\n>>\n>> Right now i've got something like this scripted up:\n>>\n>> for B in $(git-branch | cut -c3- ); do git-merge $B; done \n>>\n>> It takes a lot of time to run on even a 3.45GHz box:\n>>\n>> real 0m53.228s\n>> user 0m41.134s\n>> sys 0m11.405s\n>>\n>> I just had a workflow incident where i forgot that this script was \n>> running in one window (53 seconds are a _long_ time to start doing some \n>> other stuff :-), i switched branches and the script merrily chugged \n>> away merging branches into a topic branch i did not intend.\n>>\n>> It iterates over 140 branches - but all of them are already merged up.\n>>\n>\n> With the builtin merge (which is in next), this should be doable with \n> an octopus merge, which will eliminate the branches that are already \n> fully merged, resulting in a less-than-140-way merge (thank gods...). \n> It also doesn't have the 24-way cap that the scripted version suffers \n> from.\n>\n> If it does a good job at your rather extreme use-case, I'd say it's \n> good enough for 'master' pretty soon :-)\n\nhm, while i do love octopus merges [*] for release and bisection-quality \npurposes, for throw-away (delta-)integration runs it's more manageable \nto do a predictable series of one-on-one merges.\n\nIt results in better git-rerere behavior, has easier (to the human) \nconflict resolutions and the octopus merge also falls apart quite easily \nwhen it runs into conflicts. Furthermore, i've often seen octopus merges \nfail while a series of 1:1 merges succeeded.\n\nWhat i could try is to do a speculative octopus merge, in the hope of it \njust going fine - and then fall back to the serial merge if it fails?\n\nThe git-fastmerge approach is probably still faster though - and \ncertainly simpler from a workflow POV.\n\n\tIngo\n\n[*] take a look at these in the Linux kernel -git repo:\n\n gitk 3c1ca43fafea41e38cb2d0c1684119af4c1de547\n gitk 6924d1ab8b7bbe5ab416713f5701b3316b2df85b\n"},{"id":"84493","messageId":"20080723140441.GA9537@elte.hu","threadId":"14617","inReplyTo":"20080723135621.GJ22606@neumann","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T14:04:42Z","receivedAt":"2008-07-23T14:04:42Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* SZEDER Gábor wrote:\n\n> Hi,\n> \n> On Wed, Jul 23, 2008 at 03:05:18PM +0200, Ingo Molnar wrote:\n> > I've got the following, possibly stupid question: is there a way to \n> > merge a healthy number of topic branches into the master branch in a \n> > quicker way, when most of the branches are already merged up?\n> > \n> > Right now i've got something like this scripted up:\n> > \n> > for B in $(git-branch | cut -c3- ); do git-merge $B; done \n> you cound use 'git branch --no-merged' to list only those branches\n> that have not been merged into your current HEAD.\n\nhm, it's very slow:\n\n $ time git branch --no-merged\n [...]\n\n real 0m9.177s\n user 0m9.027s\n sys 0m0.129s\n\nwhen running it on tip/master:\n\n http://people.redhat.com/mingo/tip.git/README\n\n\tIngo\n"},{"id":"84494","messageId":"20080723140608.GC11679@atjola.homenet","threadId":"14617","inReplyTo":"20080723130518.GA17462@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Björn Steinbrink","fromEmail":"b.steinbrink@gmx.de","sentAt":"2008-07-23T14:06:08Z","receivedAt":"2008-07-23T14:06:08Z","isPatch":false,"sender":{"key":"b.steinbrink@gmx.de","avatar":"https://avatars.githubusercontent.com/u/230962?v=4"},"body":"On 2008.07.23 15:05:18 +0200, Ingo Molnar wrote:\n> \n> I've got the following, possibly stupid question: is there a way to \n> merge a healthy number of topic branches into the master branch in a \n> quicker way, when most of the branches are already merged up?\n> \n> Right now i've got something like this scripted up:\n> \n> for B in $(git-branch | cut -c3- ); do git-merge $B; done \n\nNot yet in any release (AFAICT), but with git.git master, you could use:\n\nfor B in $(git branch --no-merged); do git-merge $B; done\n\n\nOr with earlier versions, this should work, but it's a lot slower:\n\nfor B in $(git branch | cut -c3- ); do\n\t[[ -n \"$(git rev-list -1 HEAD..$B)\" ]] && git merge $B;\ndone\n\nBjörn\n"},{"id":"84495","messageId":"8aa486160807230706o20c391f2v60b78973dce62762@mail.gmail.com","threadId":"14617","inReplyTo":"20080723130518.GA17462@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Santi Béjar","fromEmail":"sbejar@gmail.com","sentAt":"2008-07-23T14:06:57Z","receivedAt":"2008-07-23T14:06:57Z","isPatch":false,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Wed, Jul 23, 2008 at 15:05, Ingo Molnar wrote:\n>\n> I've got the following, possibly stupid question: is there a way to\n> merge a healthy number of topic branches into the master branch in a\n> quicker way, when most of the branches are already merged up?\n\nYou could filter upfront the branches that are already merged up with:\n\ngit show-branch --independent \n\nbut it has a limit of 25 refs.\n\nSanti\n"},{"id":"84496","messageId":"20080723140959.GB9537@elte.hu","threadId":"14617","inReplyTo":"20080723174140.b749191a.vsu@altlinux.ru","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T14:09:59Z","receivedAt":"2008-07-23T14:09:59Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"* Sergey Vlasov wrote:\n\n> On Wed, 23 Jul 2008 15:05:18 +0200 Ingo Molnar wrote:\n> \n> > Anyone can simulate it by switching to the linus/master branch of the\n> > current Linux kernel tree, and doing:\n> >\n> > time for ((i=0; i<140; i++)); do git-merge v2.6.26; done\n> >\n> > real 1m26.397s\n> > user 1m10.048s\n> > sys 0m13.944s\n> \n> Timing results here (E6750 @ 2.66GHz):\n> 41.61s user 3.71s system 99% cpu 45.530 total\n> \n> However, testing whether there is something new to merge could be\n> performed significantly faster:\n> \n> $ time sh -c 'for ((i=0; i<140; i++)); do [ -n \"$(git rev-list --max-count=1 v2.6.26 ^HEAD)\" ]; done'\n> sh -c 5.49s user 0.26s system 99% cpu 5.786 total\n> \n> The same loop with \"git merge-base v2.6.26 HEAD\" takes about 40 \n> seconds here - apparently finding the merge base is the expensive \n> part, and it makes sense to avoid it if you expect that most of your \n> branches do not contain anything new to merge.\n\nusing git-fastmerge i get 2.4 seconds:\n\n $ time for ((i=0; i<140; i++)); do git-fastmerge v2.6.26; done\n [...]\n real 0m2.388s\n user 0m1.211s\n sys 0m1.131s\n\nfor something that 'progresses' in a forward manner (which merges do \nfundamentally) nothing beats the performance of a timestamped cache i \nthink.\n\nat least for my usecase.\n\nEven assuming that the filesystem is sane, is my merge-cache \nimplementation semantically equivalent to a git-merge? One detail is \nthat i suspect it is not equivalent in the git-merge --no-ff case. (but \nthat is a not too interesting non-default case anyway)\n\n\tIngo\n"},{"id":"84498","messageId":"20080723141456.GA13556@elte.hu","threadId":"14617","inReplyTo":"20080723140959.GB9537@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T14:14:56Z","receivedAt":"2008-07-23T14:14:56Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> Even assuming that the filesystem is sane, is my merge-cache \n> implementation semantically equivalent to a git-merge? One detail is \n> that i suspect it is not equivalent in the git-merge --no-ff case. \n> (but that is a not too interesting non-default case anyway)\n\nactually, since --no-ff creates a merge commit and thus propagates the \nhead sha1, this should work fine as well.\n\n(besides the small detail that my script has $1 hardcoded so parameters \nare not properly passed onto.)\n\n\tIngo\n"},{"id":"84501","messageId":"76718490807230747w5d0350b8v6feba00fb8837617@mail.gmail.com","threadId":"14617","inReplyTo":"20080723134926.GA12888@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Jay Soffian","fromEmail":"jaysoffian@gmail.com","sentAt":"2008-07-23T14:47:02Z","receivedAt":"2008-07-23T14:47:02Z","isPatch":false,"sender":{"key":"jaysoffian@gmail.com","avatar":"https://avatars.githubusercontent.com/u/155970?v=4"},"body":"On Wed, Jul 23, 2008 at 9:49 AM, Ingo Molnar wrote:\n> #!/bin/bash\n>\n> usage () {\n> echo 'usage: git-fastmerge ..'\n> exit -1\n> }\n>\n> [ $# = 0 ] && usage\n>\n> BRANCH=$1\n>\n> MERGECACHE=.git/mergecache\n>\n> [ ! -d $MERGECACHE ] && { mkdir $MERGECACHE || usage; }\n>\n> HEAD_SHA1=$(git-log -1 --pretty=format:\"%H\")\n> BRANCH_SHA1=$(git-log -1 --pretty=format:\"%H\" $BRANCH)\n>\n> CACHE=$MERGECACHE/$HEAD_SHA1/$BRANCH_SHA1\n>\n> [ -f \"$CACHE\" -a \"$CACHE\" -nt .git/refs/heads/$BRANCH_SHA1 ] && {\n\nShouldn't this be:\n\n[ -f \"$CACHE\" -a \"$CACHE\" -nt .git/refs/heads/$BRANCH ] && {\n\n?\n\nj.\n"},{"id":"84510","messageId":"20080723145622.GA23440@elte.hu","threadId":"14617","inReplyTo":"76718490807230747w5d0350b8v6feba00fb8837617@mail.gmail.com","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T14:56:22Z","receivedAt":"2008-07-23T14:56:22Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Jay Soffian wrote:\n\n> > CACHE=$MERGECACHE/$HEAD_SHA1/$BRANCH_SHA1\n> >\n> > [ -f \"$CACHE\" -a \"$CACHE\" -nt .git/refs/heads/$BRANCH_SHA1 ] && {\n> \n> Shouldn't this be:\n> \n> [ -f \"$CACHE\" -a \"$CACHE\" -nt .git/refs/heads/$BRANCH ] && {\n> \n> ?\n\nyeah, i just figured it out too ... the hard way :)\n\nUpdated script below. This works fine across resets in the master \nbranch.\n\nWhile it's fast in the empty-merge case, it's not as fast as i'd like it \nto be in the almost-empty-merge case.\n\n\tIngo\n\n--------------{ git-fastmerge }-------------------->\n#!/bin/bash\n\nusage () {\n echo 'usage: tip-fastmerge ..'\n exit -1\n}\n\n[ $# = 0 ] && usage\n\nBRANCH=$1\n\nMERGECACHE=.git/mergecache\n\n[ ! -d $MERGECACHE ] && { mkdir $MERGECACHE || usage; }\n\nHEADREF=.git/$(cut -d' ' -f2 .git/HEAD)\n\nHEAD_SHA1=$(git-log -1 --pretty=format:\"%H\")\nBRANCH_SHA1=$(git-log -1 --pretty=format:\"%H\" $BRANCH)\n\nCACHE=$MERGECACHE/$HEAD_SHA1/$BRANCH_SHA1\n\n[ -f \"$CACHE\" -a \"$CACHE\" -nt \"$HEADREF\" ] && {\n# echo \"merge-cache hit on HEAD <= $1\"\n exit 0\n}\n\ngit-merge $1 && {\n mkdir -p $(dirname $CACHE)\n touch $CACHE\n}\n"},{"id":"84513","messageId":"20080723145720.GG32057@genesis.frugalware.org","threadId":"14617","inReplyTo":"488734D9.9070703@op5.se","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Miklos Vajna","fromEmail":"vmiklos@frugalware.org","sentAt":"2008-07-23T14:57:20Z","receivedAt":"2008-07-23T14:57:20Z","isPatch":false,"sender":{"key":"vmiklos@frugalware.org","avatar":"https://gravatar.com/avatar/401c1cbbb3a5d13e650c691a2c71d6fd0b80df1a01bc74d9f1972675dd58f2bd?d=mp&s=160"},"body":"On Wed, Jul 23, 2008 at 03:40:41PM +0200, Andreas Ericsson wrote:\n> With the builtin merge (which is in next)\n\nJust a small correction: it's already in master.\n"},{"id":"84520","messageId":"20080723150621.GA8499@elte.hu","threadId":"14617","inReplyTo":"20080723145622.GA23440@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-23T15:06:21Z","receivedAt":"2008-07-23T15:06:21Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> > Shouldn't this be:\n> > \n> > [ -f \"$CACHE\" -a \"$CACHE\" -nt .git/refs/heads/$BRANCH ] && {\n> > \n> > ?\n> \n> yeah, i just figured it out too ... the hard way :)\n> \n> Updated script below. This works fine across resets in the master \n> branch.\n> \n> While it's fast in the empty-merge case, it's not as fast as i'd like \n> it to be in the almost-empty-merge case.\n\nWhen i update a topic branch, i first get a relatively fast run:\n\n earth4:~/tip> time todo-merge-all\n merging all branches ...\n Auto-merged arch/x86/kernel/genx2apic_uv_x.c\n Merge made by recursive.\n arch/x86/kernel/genx2apic_uv_x.c | 1 -\n 1 files changed, 0 insertions(+), 1 deletions(-)\n ... merge done.\n\n real 0m6.625s\n user 0m3.740s\n sys 0m2.563s\n\nThen on the next run it's slower:\n\n earth4:~/tip> time todo-merge-all\n merging all branches ...\n ... merge done.\n\n real 0m30.823s\n user 0m23.403s\n sys 0m7.545s\n\nthat's unfortunate. The freshly updated topic branch was at the end of \nthe run, now all other topic branches will have to run slow at least \nonce until they become cached again.\n\nPerhaps the cache should update all other current topics to the new \nsha1, to establish the fact that they were not merged this time. (and \nthat they are still not to be merged)\n\n(It's still much faster than completely uncached though, because of the \noverlap in sha1's.)\n\nThird (empty) run is fast again, because it's fully cached:\n\n earth4:~/tip> time todo-merge-all\n merging all branches ...\n ... merge done.\n\n real 0m3.036s\n user 0m1.360s\n sys 0m1.782s\n\nBut it would be nice if the cache worked more intelligently in the \none-topic-updated-only case as well.\n\n\tIngo\n"},{"id":"84561","messageId":"alpine.LFD.1.10.0807231027030.4754@woody.linux-foundation.org","threadId":"14617","inReplyTo":"20080723130518.GA17462@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-23T17:59:01Z","receivedAt":"2008-07-23T17:59:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 23 Jul 2008, Ingo Molnar wrote:\n> \n> I've got the following, possibly stupid question: is there a way to \n> merge a healthy number of topic branches into the master branch in a \n> quicker way, when most of the branches are already merged up?\n> \n> Right now i've got something like this scripted up:\n> \n> for B in $(git-branch | cut -c3- ); do git-merge $B; done \n> \n> It takes a lot of time to run on even a 3.45GHz box:\n> \n> real 0m53.228s\n> user 0m41.134s\n> sys 0m11.405s\n\nThis is almost certainly because a lot of your branches are a long way \nback in the history, and just parsing the commit history is old.\n\nFor example, doing a no-op merge of something old like v2.6.24 (which is \nobviously already merged) takes half a second for me:\n\n\t[torvalds@woody linux]$ time git merge v2.6.24\n\tAlready up-to-date.\n\n\treal\t0m0.546s\n\tuser\t0m0.488s\n\tsys\t0m0.008s\n\nand it gets worse the further back in history you go (going back to 2.6.14 \ntakes a second and a half - plus any IO needed, of course).\n\nAnd just about _all_ of it is literally just unpacking the commits as you \nstart going backwards from the current point, eg:\n\n\t[torvalds@woody linux]$ time ~/git/git merge v2.6.14\n\tAlready up-to-date.\n\treal\t0m1.540s\n\nvs\n\n\t[torvalds@woody linux]$ time git rev-list ..v2.6.14\n\treal\t0m1.407s\n\n(The merge loop isn't quite as optimized as the regular revision \ntraversal, so you see it being slower, but you can still see that it's \nroughly in the same class).\n\nThe merge gets a bit more expensive still if you have enabled merge \nsummaries (because now it traverses the lists twice - once for merge \nbases, once for logs), but that's still a secondary effect (ie it adds \nanother 10% or so to the cost, but the base cost is still very much about \nthe parsing of the commits).\n\nIn fact, the two top entries in a profile look roughly like:\n\n\t102161 70.2727 libz.so.1.2.3 libz.so.1.2.3 (no symbols)\n\t7685 5.2862 git git find_pack_entry_one\n\t...\n\nie 70% of the time is just purely unpacking the data, and another 5% is \njust finding it. We could perhaps improve on it, but not a whole lot.\n\nNow, quite frankly, I don't think that times on the order of one second \nare worth worrying about for _regular_ merges, and the whole (and only) \nreason you see this as a performance problem is that you're basically \nautomating it over a ton of branches, with most of them being old and \nalready merged.\n\nBut that also points to a solution: instead of trying to merge them one at \na time, and doing the costly revision traversal over and over and over \nagain, do the costly thing _once_, and then you can just filter out the \nbranches that aren't interesting.\n\nSo instead of doing\n\n\tfor B in $(git-branch | cut -c3- ); do git-merge $B; done\n\nthe obvious optimization is to add \"--no-merged\" to the \"git branch\" call. \nThat itself is expensive (ie doing \"git branch --no-merged\" will have to \ntraverse at least as far back as the oldest branch), so that phase will be \nAT LEAST as expensive as one of the merges (and probably quite a bit more: \nI suspect \"--no-merged\" isn't very heavily optimized), but if a lot of \nyour branches are already fully merged, it will do all that work _once_, \nand then avoid it for the merges themselves.\n\nSo the _trivial_ solution is to just change it to\n\n\tfor B in $(git branch --no-merged | cut -c3- ); do git-merge $B; done\n\nand that may already fix it in practice for you, bringing the cost down by \na factor of two or more, depending on the exact pattern (of course, it \ncould also make the cost go _up_ - if it turns out that none of the \nbranches are merged).\n\nOther solutions exist, but they get much uglier. Octopus merges are more \nefficient, for example, for all the same reasons - it keeps the commit \ntraversal in a single process, and thus avoids having to re-parse the \nwhole history down to the common base. But they have other problems, of \ncourse.\n\n\t\t\tLinus\n"},{"id":"84560","messageId":"7vy73seb2p.fsf@gitster.siamese.dyndns.org","threadId":"14617","inReplyTo":"20080723140441.GA9537@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-23T17:59:10Z","receivedAt":"2008-07-23T17:59:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ingo Molnar writes:\n\n> * SZEDER Gábor wrote:\n>\n>> you cound use 'git branch --no-merged' to list only those branches\n>> that have not been merged into your current HEAD.\n>\n> hm, it's very slow:\n\nYeah, --no-merged and --merged were done in a quite naïve way.\n\nThe patch needs to be cleaned up by splitting it into multiple steps:\n\n (1) discard everything outside refs/heads and refs/remotes in append_ref();\n why do we even have code to deal with refs/tags to begin with???\n\n (2) change ref_item->sha1 to ref_item->commit (and make has_commit() take\n struct commit);\n\n (3) teach merge_filter code not to do has_commit() for each ref, but use\n revision traversal machinery to compute everything in parallel and in\n one traversal.\n\nbut other than that, this seems to pass the tests, and is obviously\ncorrect ;-)\n\nWith an artificial repository that has \"master\" and 1000 test-$i branches\nwhere they were created by \"git branch test-$i master~$i\":\n\n(with patch)\n$ /usr/bin/time git-branch --no-merged master >/dev/null\n0.12user 0.02system 0:00.15elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+1588minor)pagefaults 0swaps\n\n$ /usr/bin/time git-branch --no-merged test-200 >/dev/null\n0.15user 0.03system 0:00.18elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+1711minor)pagefaults 0swaps\n\n(without patch)\n$ /usr/bin/time git-branch --no-merged master >/dev/null\n0.69user 0.03system 0:00.72elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+2229minor)pagefaults 0swaps\n\n$ /usr/bin/time git-branch --no-merged test-200 >/dev/null\n0.58user 0.03system 0:00.61elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+2248minor)pagefaults 0swaps\n\n---\n\n builtin-branch.c | 68 ++++++++++++++++++++++++++++++++---------------------\n 1 files changed, 41 insertions(+), 27 deletions(-)\n\ndiff --git a/builtin-branch.c b/builtin-branch.c\nindex b885bd1..788e70a 100644\n--- a/builtin-branch.c\n+++ b/builtin-branch.c\n@@ -13,6 +13,8 @@\n #include \"remote.h\"\n #include \"parse-options.h\"\n #include \"branch.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n \n static const char * const builtin_branch_usage[] = {\n \t\"git branch [options] [-r | -a] [--merged | --no-merged]\",\n@@ -181,25 +183,21 @@ static int delete_branches(int argc, const char **argv, int force, int kinds)\n struct ref_item {\n \tchar *name;\n \tunsigned int kind;\n-\tunsigned char sha1[20];\n+\tstruct commit *commit;\n };\n \n struct ref_list {\n+\tstruct rev_info revs;\n \tint index, alloc, maxwidth;\n \tstruct ref_item *list;\n \tstruct commit_list *with_commit;\n \tint kinds;\n };\n \n-static int has_commit(const unsigned char *sha1, struct commit_list *with_commit)\n+static int has_commit(struct commit *commit, struct commit_list *with_commit)\n {\n-\tstruct commit *commit;\n-\n \tif (!with_commit)\n \t\treturn 1;\n-\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\tif (!commit)\n-\t\treturn 0;\n \twhile (with_commit) {\n \t\tstruct commit *other;\n \n@@ -215,6 +213,7 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n {\n \tstruct ref_list *ref_list = (struct ref_list*)(cb_data);\n \tstruct ref_item *newitem;\n+\tstruct commit *commit;\n \tint kind = REF_UNKNOWN_TYPE;\n \tint len;\n \tstatic struct commit_list branch;\n@@ -226,13 +225,15 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n \t} else if (!prefixcmp(refname, \"refs/remotes/\")) {\n \t\tkind = REF_REMOTE_BRANCH;\n \t\trefname += 13;\n-\t} else if (!prefixcmp(refname, \"refs/tags/\")) {\n-\t\tkind = REF_TAG;\n-\t\trefname += 10;\n-\t}\n+\t} else\n+\t\treturn 0;\n+\n+\tcommit = lookup_commit_reference_gently(sha1, 1);\n+\tif (!commit)\n+\t\treturn error(\"branch '%s' does not point at a commit\", refname);\n \n \t/* Filter with with_commit if specified */\n-\tif (!has_commit(sha1, ref_list->with_commit))\n+\tif (!has_commit(commit, ref_list->with_commit))\n \t\treturn 0;\n \n \t/* Don't add types the caller doesn't want */\n@@ -243,30 +244,25 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n \t\tbranch.item = lookup_commit_reference_gently(sha1, 1);\n \t\tif (!branch.item)\n \t\t\tdie(\"Unable to lookup tip of branch %s\", refname);\n-\t\tif (merge_filter == SHOW_NOT_MERGED &&\n-\t\t has_commit(merge_filter_ref, &branch))\n-\t\t\treturn 0;\n-\t\tif (merge_filter == SHOW_MERGED &&\n-\t\t !has_commit(merge_filter_ref, &branch))\n-\t\t\treturn 0;\n+\t\tadd_pending_object(&ref_list->revs,\n+\t\t\t\t (struct object *)branch.item, refname);\n \t}\n \n \t/* Resize buffer */\n \tif (ref_list->index >= ref_list->alloc) {\n \t\tref_list->alloc = alloc_nr(ref_list->alloc);\n \t\tref_list->list = xrealloc(ref_list->list,\n-\t\t\t\tref_list->alloc * sizeof(struct ref_item));\n+\t\t\t\t\t ref_list->alloc * sizeof(struct ref_item));\n \t}\n \n \t/* Record the new item */\n \tnewitem = &(ref_list->list[ref_list->index++]);\n \tnewitem->name = xstrdup(refname);\n \tnewitem->kind = kind;\n-\thashcpy(newitem->sha1, sha1);\n+\tnewitem->commit = commit;\n \tlen = strlen(newitem->name);\n \tif (len > ref_list->maxwidth)\n \t\tref_list->maxwidth = len;\n-\n \treturn 0;\n }\n \n@@ -309,7 +305,13 @@ static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,\n {\n \tchar c;\n \tint color;\n-\tstruct commit *commit;\n+\tstruct commit *commit = item->commit;\n+\n+\tif (merge_filter != NO_FILTER) {\n+\t\tint is_merged = !!(item->commit->object.flags & UNINTERESTING);\n+\t\tif (is_merged != (merge_filter == SHOW_MERGED))\n+\t\t\treturn;\n+\t}\n \n \tswitch (item->kind) {\n \tcase REF_LOCAL_BRANCH:\n@@ -337,7 +339,7 @@ static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,\n \t\tstrbuf_init(&subject, 0);\n \t\tstat[0] = '\\0';\n \n-\t\tcommit = lookup_commit(item->sha1);\n+\t\tcommit = item->commit;\n \t\tif (commit && !parse_commit(commit)) {\n \t\t\tpretty_print_commit(CMIT_FMT_ONELINE, commit,\n \t\t\t\t\t &subject, 0, NULL, NULL, 0, 0);\n@@ -350,7 +352,7 @@ static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,\n \t\tprintf(\"%c %s%-*s%s %s %s%s\\n\", c, branch_get_color(color),\n \t\t maxwidth, item->name,\n \t\t branch_get_color(COLOR_BRANCH_RESET),\n-\t\t find_unique_abbrev(item->sha1, abbrev),\n+\t\t find_unique_abbrev(item->commit->object.sha1, abbrev),\n \t\t stat, sub);\n \t\tstrbuf_release(&subject);\n \t} else {\n@@ -363,22 +365,34 @@ static void print_ref_list(int kinds, int detached, int verbose, int abbrev, str\n {\n \tint i;\n \tstruct ref_list ref_list;\n+\tstruct commit *head_commit = lookup_commit_reference_gently(head_sha1, 1);\n \n \tmemset(&ref_list, 0, sizeof(ref_list));\n \tref_list.kinds = kinds;\n \tref_list.with_commit = with_commit;\n+\tif (merge_filter != NO_FILTER)\n+\t\tinit_revisions(&ref_list.revs, NULL);\n \tfor_each_ref(append_ref, &ref_list);\n+\tif (merge_filter != NO_FILTER) {\n+\t\tstruct commit *filter;\n+\t\tfilter = lookup_commit_reference_gently(merge_filter_ref, 0);\n+\t\tfilter->object.flags |= UNINTERESTING;\n+\t\tadd_pending_object(&ref_list.revs,\n+\t\t\t\t (struct object *) filter, \"\");\n+\t\tref_list.revs.limited = 1;\n+\t\tprepare_revision_walk(&ref_list.revs);\n+\t}\n \n \tqsort(ref_list.list, ref_list.index, sizeof(struct ref_item), ref_cmp);\n \n \tdetached = (detached && (kinds & REF_LOCAL_BRANCH));\n-\tif (detached && has_commit(head_sha1, with_commit)) {\n+\tif (detached && head_commit && has_commit(head_commit, with_commit)) {\n \t\tstruct ref_item item;\n \t\titem.name = xstrdup(\"(no branch)\");\n \t\titem.kind = REF_LOCAL_BRANCH;\n-\t\thashcpy(item.sha1, head_sha1);\n+\t\titem.commit = head_commit;\n \t\tif (strlen(item.name) > ref_list.maxwidth)\n-\t\t\t ref_list.maxwidth = strlen(item.name);\n+\t\t\tref_list.maxwidth = strlen(item.name);\n \t\tprint_ref_item(&item, ref_list.maxwidth, verbose, abbrev, 1);\n \t\tfree(item.name);\n \t}\n"},{"id":"84562","messageId":"alpine.LFD.1.10.0807231100310.4754@woody.linux-foundation.org","threadId":"14617","inReplyTo":"20080723140441.GA9537@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-23T18:04:07Z","receivedAt":"2008-07-23T18:04:07Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nAhh, missed that somebody already suggested it.\n\nOn Wed, 23 Jul 2008, Ingo Molnar wrote:\n> \n> hm, it's very slow:\n> \n> $ time git branch --no-merged\n> [...]\n> \n> real 0m9.177s\n> user 0m9.027s\n> sys 0m0.129s\n> \n> when running it on tip/master:\n> \n> http://people.redhat.com/mingo/tip.git/README\n\nWe can probably speed it up, but more importantly, even if we don't, it's \nslow _once_.\n\nIt's worth taking a 9s hit, if that means that you can then skip half of \nthe merges entirely, and thus win half of the 53s cost. \n\nBut I'll look if there's a way to cut it down from 9s. I suspect it has to \ntraverse the whole history to make 100% sure that something isn't merged, \nbut even that should be faster than 9s.\n\n\t\tLinus\n"},{"id":"84564","messageId":"alpine.LFD.1.10.0807231107450.4754@woody.linux-foundation.org","threadId":"14617","inReplyTo":"alpine.LFD.1.10.0807231100310.4754@woody.linux-foundation.org","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-23T18:12:11Z","receivedAt":"2008-07-23T18:12:11Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 23 Jul 2008, Linus Torvalds wrote:\n> \n> But I'll look if there's a way to cut it down from 9s. I suspect it has to \n> traverse the whole history to make 100% sure that something isn't merged, \n> but even that should be faster than 9s.\n\nHeh. It should be trivially doable _much_ faster, but the has_commit() \nlogic really relies on re-doing the \"in_merge_base()\" thing over and over \nagain (clearing the bits), instead of just populating the object list with \na \"already seen\" bit and lettign that expand over time.\n\nSo using \"git branch --no-merged\" does avoid re-parsing the commits over \nand over again (which is a pretty big win), but the way the code is \nwritten it does end up traversing the commit list fully for every single \nbranch. That's quite horrible.\n\nLars added to Cc list in the hope that he'll be embarrassed enough about \nthe performance to try to fix it ;)\n\n\t\tLinus\n"},{"id":"84581","messageId":"20080723190920.GG20614@artemis.madism.org","threadId":"14617","inReplyTo":"alpine.LFD.1.10.0807231027030.4754@woody.linux-foundation.org","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Pierre Habouzit","fromEmail":"madcoder@artemis.madism.org","sentAt":"2008-07-23T19:09:20Z","receivedAt":"2008-07-23T19:09:20Z","isPatch":false,"sender":{"key":"madcoder@artemis.madism.org","avatar":null},"body":"On Wed, Jul 23, 2008 at 05:59:01PM +0000, Linus Torvalds wrote:\n> In fact, the two top entries in a profile look roughly like:\n> \n> \t102161 70.2727 libz.so.1.2.3 libz.so.1.2.3 (no symbols)\n> \t7685 5.2862 git git find_pack_entry_one\n> \t...\n> \n> ie 70% of the time is just purely unpacking the data, and another 5% is \n> just finding it. We could perhaps improve on it, but not a whole lot.\n\n Well there is an easy way though, that could reduce that: using\nadaptative compression. I proposed a patch once upon a time, that set\nthe compression strengh to 0 for \"small\" objects with a configurable\ncut-off. If you do that, most trees, commits messages and so on aren't\ncompressed, and it will reduce (with IIRC a 5-liner) this time quite\ndramatically.\n\n I could maybe resurect it to see if for people that do the kind of\nthings Ingo does it helps. By setting the cut-off at 1k, I had packs\nbeing less than 1% bigger IIRC. I'll try to find it again and run your\ntests with it to see how much it helps.\n\n [ Of course, it doesn't invalidate the rest of your mail about being\n more clever with git-merge, but still, we could reduce this 70% of\n zlib time quite a lot with that ]\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"84599","messageId":"7v8wvscqtm.fsf@gitster.siamese.dyndns.org","threadId":"14617","inReplyTo":"20080723140441.GA9537@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-23T20:01:57Z","receivedAt":"2008-07-23T20:01:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ingo Molnar writes:\n\n> hm, it's very slow:\n>\n> $ time git branch --no-merged\n> [...]\n>\n> real 0m9.177s\n> user 0m9.027s\n> sys 0m0.129s\n>\n> when running it on tip/master:\n>\n> http://people.redhat.com/mingo/tip.git/README\n\nHmmm, does not reproduce for me with a copy of that repository.\n\n$ time git branch -a --no-merged mingo/master\n linus/master\n mingo/acpi-for-len\n mingo/auto-cpus4096-next\n mingo/auto-kmemcheck-next\n mingo/auto-test\n mingo/auto-test-fixes\n mingo/core/futex-64bit\n mingo/core/kill-the-BKL\n mingo/core/percpu-zerobased\n mingo/cpus4096-for-linus\n mingo/kmemcheck-for-linus\n mingo/stackprotector-for-linus\n mingo/timers/for-linus\n mingo/tip\n mingo/tracing/ftrace\n mingo/tracing/immediates\n mingo/tracing/markers\n mingo/tracing/stopmachine-allcpus\n mingo/tracing/textedit\n mingo/x86/acpi-rename-acpi_nmi\n mingo/x86/audit-speedup\n mingo/x86/crashdump\n mingo/x86/header-guards\n mingo/x86/prototypes\n mingo/x86/sparse-fixes\n mingo/x86/unify-mce\n mingo/x86/x2apic\n\nreal 0m1.442s\nuser 0m1.360s\nsys 0m0.084s\n\nWith the patch I posted earlier, the time becomes:\n\nreal 0m0.600s\nuser 0m0.560s\nsys 0m0.040s\n"},{"id":"84603","messageId":"20080723202722.GA18160@artemis.madism.org","threadId":"14617","inReplyTo":"20080723190920.GG20614@artemis.madism.org","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Pierre Habouzit","fromEmail":"madcoder@artemis.madism.org","sentAt":"2008-07-23T20:27:22Z","receivedAt":"2008-07-23T20:27:22Z","isPatch":false,"sender":{"key":"madcoder@artemis.madism.org","avatar":null},"body":"On Wed, Jul 23, 2008 at 07:09:20PM +0000, Pierre Habouzit wrote:\n> On Wed, Jul 23, 2008 at 05:59:01PM +0000, Linus Torvalds wrote:\n> > In fact, the two top entries in a profile look roughly like:\n> > \n> > \t102161 70.2727 libz.so.1.2.3 libz.so.1.2.3 (no symbols)\n> > \t7685 5.2862 git git find_pack_entry_one\n> > \t...\n> > \n> > ie 70% of the time is just purely unpacking the data, and another 5% is \n> > just finding it. We could perhaps improve on it, but not a whole lot.\n> \n> Well there is an easy way though, that could reduce that: using\n> adaptative compression. I proposed a patch once upon a time, that set\n> the compression strengh to 0 for \"small\" objects with a configurable\n> cut-off. If you do that, most trees, commits messages and so on aren't\n> compressed, and it will reduce (with IIRC a 5-liner) this time quite\n> dramatically.\n> \n> I could maybe resurect it to see if for people that do the kind of\n> things Ingo does it helps. By setting the cut-off at 1k, I had packs\n> being less than 1% bigger IIRC. I'll try to find it again and run your\n> tests with it to see how much it helps.\n\n Unsurprisingly with a 1024o cutoff, the numbers are (first run is\nforced cold-cache with /proc/.../drop_caches, second is the best run of 5):\n\ndefault git:\n\n 3.10user 0.16system 0:08.10elapsed 40%CPU (0avgtext+0avgdata 0maxresident)k\n 116152inputs+0outputs (671major+35286minor)pagefaults 0swaps\n\n 2.01user 0.11system 0:02.12elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+35958minor)pagefaults 0swaps\n\nWith a 1024k cutoff:\n\n 1.16user 0.13system 0:08.29elapsed 15%CPU (0avgtext+0avgdata 0maxresident)k\n 154208inputs+0outputs (947major+39777minor)pagefaults 0swaps\n\n 0.76user 0.06system 0:00.82elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+40724minor)pagefaults 0swaps\n\n\nAccording to [0], a 1k cutoff meant something like a 10% larger pack. 512o\nmeant an almost identical pack in size, but with reduced performance\nimprovements.\n\n\n [0] http://thread.gmane.org/gmane.comp.version-control.git/70019/focus=70250\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"84605","messageId":"20080723204039.GB18160@artemis.madism.org","threadId":"14617","inReplyTo":"20080723202722.GA18160@artemis.madism.org","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Pierre Habouzit","fromEmail":"madcoder@artemis.madism.org","sentAt":"2008-07-23T20:40:39Z","receivedAt":"2008-07-23T20:40:39Z","isPatch":false,"sender":{"key":"madcoder@artemis.madism.org","avatar":null},"body":"On mer, jui 23, 2008 at 08:27:22 +0000, Pierre Habouzit wrote:\n> On Wed, Jul 23, 2008 at 07:09:20PM +0000, Pierre Habouzit wrote:\n> > On Wed, Jul 23, 2008 at 05:59:01PM +0000, Linus Torvalds wrote:\n> > > In fact, the two top entries in a profile look roughly like:\n> > > \n> > > \t102161 70.2727 libz.so.1.2.3 libz.so.1.2.3 (no symbols)\n> > > \t7685 5.2862 git git find_pack_entry_one\n> > > \t...\n> > > \n> > > ie 70% of the time is just purely unpacking the data, and another 5% is \n> > > just finding it. We could perhaps improve on it, but not a whole lot.\n> > \n> > Well there is an easy way though, that could reduce that: using\n> > adaptative compression. I proposed a patch once upon a time, that set\n> > the compression strengh to 0 for \"small\" objects with a configurable\n> > cut-off. If you do that, most trees, commits messages and so on aren't\n> > compressed, and it will reduce (with IIRC a 5-liner) this time quite\n> > dramatically.\n> > \n> > I could maybe resurect it to see if for people that do the kind of\n> > things Ingo does it helps. By setting the cut-off at 1k, I had packs\n> > being less than 1% bigger IIRC. I'll try to find it again and run your\n> > tests with it to see how much it helps.\n> \n> Unsurprisingly with a 1024o cutoff, the numbers are (first run is\n> forced cold-cache with /proc/.../drop_caches, second is the best run of 5):\n> \n> default git:\n> \n> 3.10user 0.16system 0:08.10elapsed 40%CPU (0avgtext+0avgdata 0maxresident)k\n> 116152inputs+0outputs (671major+35286minor)pagefaults 0swaps\n> \n> 2.01user 0.11system 0:02.12elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (0major+35958minor)pagefaults 0swaps\n> \n> With a 1024k cutoff:\n> \n> 1.16user 0.13system 0:08.29elapsed 15%CPU (0avgtext+0avgdata 0maxresident)k\n> 154208inputs+0outputs (947major+39777minor)pagefaults 0swaps\n> \n> 0.76user 0.06system 0:00.82elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (0major+40724minor)pagefaults 0swaps\n\nWith a 512o cutoff:\n\n 1.49user 0.17system 0:07.50elapsed 22%CPU (0avgtext+0avgdata 0maxresident)k\n 127648inputs+0outputs (780major+36687minor)pagefaults 0swaps\n\n 1.54user 0.07system 0:01.61elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+37467minor)pagefaults 0swaps\n\n\nWhat I bench, I see I forgot to mention, is: git merge v2.6.14. And\nthe respective pack sizes:\n\n 214M .git-0/objects/pack/pack-bfeec11abed1ec6d046bc954b94d70ba81716356.pack\n 225M .git-512/objects/pack/pack-bfeec11abed1ec6d046bc954b94d70ba81716356.pack\n 243M .git-1024/objects/pack/pack-bfeec11abed1ec6d046bc954b94d70ba81716356.pack\n\n.git-0 is cheating because it was generated with a way deeper window and\nmemory window that the other ones, but it allow to give rough\nimpressions.\n\n\n-- \n·O· Pierre Habouzit\n··O madcoder@debian.org\nOOO http://www.madism.org\n"},{"id":"84628","messageId":"7v63qwb6d3.fsf_-_@gitster.siamese.dyndns.org","threadId":"14617","inReplyTo":"7vy73seb2p.fsf@gitster.siamese.dyndns.org","subject":"[PATCH 1/2] builtin-branch.c: remove unused code in append_ref() callback function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-23T22:09:12Z","receivedAt":"2008-07-23T22:09:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"We let for_each_ref() to feed all refs to append_ref() but we are only\never interested in local or remote tracking branches.\n\nSigned-off-by: Junio C Hamano \n---\n * I ended up splitting the patch into two, not three as I originally\n thought I would.\n\n builtin-branch.c | 10 +++-------\n 1 files changed, 3 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin-branch.c b/builtin-branch.c\nindex b885bd1..3708a50 100644\n--- a/builtin-branch.c\n+++ b/builtin-branch.c\n@@ -22,10 +22,8 @@ static const char * const builtin_branch_usage[] = {\n \tNULL\n };\n \n-#define REF_UNKNOWN_TYPE 0x00\n #define REF_LOCAL_BRANCH 0x01\n #define REF_REMOTE_BRANCH 0x02\n-#define REF_TAG 0x04\n \n static const char *head;\n static unsigned char head_sha1[20];\n@@ -215,7 +213,7 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n {\n \tstruct ref_list *ref_list = (struct ref_list*)(cb_data);\n \tstruct ref_item *newitem;\n-\tint kind = REF_UNKNOWN_TYPE;\n+\tint kind;\n \tint len;\n \tstatic struct commit_list branch;\n \n@@ -226,10 +224,8 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n \t} else if (!prefixcmp(refname, \"refs/remotes/\")) {\n \t\tkind = REF_REMOTE_BRANCH;\n \t\trefname += 13;\n-\t} else if (!prefixcmp(refname, \"refs/tags/\")) {\n-\t\tkind = REF_TAG;\n-\t\trefname += 10;\n-\t}\n+\t} else\n+\t\treturn 0;\n \n \t/* Filter with with_commit if specified */\n \tif (!has_commit(sha1, ref_list->with_commit))\n-- \n1.6.0.rc0.31.g128c7\n"},{"id":"84630","messageId":"7vtzeg9rhh.fsf_-_@gitster.siamese.dyndns.org","threadId":"14617","inReplyTo":"7vy73seb2p.fsf@gitster.siamese.dyndns.org","subject":"[PATCH] builtin-branch.c: optimize --merged and --no-merged","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-23T22:15:54Z","receivedAt":"2008-07-23T22:15:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"git branch --no-merged $commit\" used to compute the merge base between\nthe tip of each and every branch with the named $commit, but this was\nwasteful when you have many branches. Inside append_ref() we literally\nran has_commit() between the tip of the branch and the merge_filter_ref.\n\nInstead, we can let the revision machinery traverse the history as if we\nare running:\n\n $ git rev-list --branches --not $commit\n\nby queueing the tips of branches we encounter as positive refs (this\nmimicks the \"--branches\" option in the above command line) and then\nappending the merge_filter_ref commit as a negative one, and finally\ncalling prepare_revision_walk() to limit the list..\n\nAfter the traversal is done, branch tips that are reachable from $commit\nare painted UNINTERESTING; they are already fully contained in $commit\n(i.e. --merged). Tips that are not painted UNINTERESTING still have\ncommits that are not reachable from $commit, thus \"--no-merged\" will show\nthem.\n\nWith an artificial repository that has \"master\" and 1000 test-$i branches\nwhere they were created by \"git branch test-$i master~$i\":\n\n (with patch)\n $ /usr/bin/time git-branch --no-merged master >/dev/null\n 0.12user 0.02system 0:00.15elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+1588minor)pagefaults 0swaps\n\n $ /usr/bin/time git-branch --no-merged test-200 >/dev/null\n 0.15user 0.03system 0:00.18elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+1711minor)pagefaults 0swaps\n\n (without patch)\n $ /usr/bin/time git-branch --no-merged master >/dev/null\n 0.69user 0.03system 0:00.72elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+2229minor)pagefaults 0swaps\n\n $ /usr/bin/time git-branch --no-merged test-200 >/dev/null\n 0.58user 0.03system 0:00.61elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+2248minor)pagefaults 0swaps\n\nSigned-off-by: Junio C Hamano \n---\n builtin-branch.c | 59 ++++++++++++++++++++++++++++++++++-------------------\n 1 files changed, 38 insertions(+), 21 deletions(-)\n\ndiff --git a/builtin-branch.c b/builtin-branch.c\nindex 3708a50..5db8ad8 100644\n--- a/builtin-branch.c\n+++ b/builtin-branch.c\n@@ -13,6 +13,8 @@\n #include \"remote.h\"\n #include \"parse-options.h\"\n #include \"branch.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n \n static const char * const builtin_branch_usage[] = {\n \t\"git branch [options] [-r | -a] [--merged | --no-merged]\",\n@@ -179,25 +181,21 @@ static int delete_branches(int argc, const char **argv, int force, int kinds)\n struct ref_item {\n \tchar *name;\n \tunsigned int kind;\n-\tunsigned char sha1[20];\n+\tstruct commit *commit;\n };\n \n struct ref_list {\n+\tstruct rev_info revs;\n \tint index, alloc, maxwidth;\n \tstruct ref_item *list;\n \tstruct commit_list *with_commit;\n \tint kinds;\n };\n \n-static int has_commit(const unsigned char *sha1, struct commit_list *with_commit)\n+static int has_commit(struct commit *commit, struct commit_list *with_commit)\n {\n-\tstruct commit *commit;\n-\n \tif (!with_commit)\n \t\treturn 1;\n-\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\tif (!commit)\n-\t\treturn 0;\n \twhile (with_commit) {\n \t\tstruct commit *other;\n \n@@ -213,6 +211,7 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n {\n \tstruct ref_list *ref_list = (struct ref_list*)(cb_data);\n \tstruct ref_item *newitem;\n+\tstruct commit *commit;\n \tint kind;\n \tint len;\n \tstatic struct commit_list branch;\n@@ -227,8 +226,12 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n \t} else\n \t\treturn 0;\n \n+\tcommit = lookup_commit_reference_gently(sha1, 1);\n+\tif (!commit)\n+\t\treturn error(\"branch '%s' does not point at a commit\", refname);\n+\n \t/* Filter with with_commit if specified */\n-\tif (!has_commit(sha1, ref_list->with_commit))\n+\tif (!has_commit(commit, ref_list->with_commit))\n \t\treturn 0;\n \n \t/* Don't add types the caller doesn't want */\n@@ -239,12 +242,8 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n \t\tbranch.item = lookup_commit_reference_gently(sha1, 1);\n \t\tif (!branch.item)\n \t\t\tdie(\"Unable to lookup tip of branch %s\", refname);\n-\t\tif (merge_filter == SHOW_NOT_MERGED &&\n-\t\t has_commit(merge_filter_ref, &branch))\n-\t\t\treturn 0;\n-\t\tif (merge_filter == SHOW_MERGED &&\n-\t\t !has_commit(merge_filter_ref, &branch))\n-\t\t\treturn 0;\n+\t\tadd_pending_object(&ref_list->revs,\n+\t\t\t\t (struct object *)branch.item, refname);\n \t}\n \n \t/* Resize buffer */\n@@ -258,7 +257,7 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n \tnewitem = &(ref_list->list[ref_list->index++]);\n \tnewitem->name = xstrdup(refname);\n \tnewitem->kind = kind;\n-\thashcpy(newitem->sha1, sha1);\n+\tnewitem->commit = commit;\n \tlen = strlen(newitem->name);\n \tif (len > ref_list->maxwidth)\n \t\tref_list->maxwidth = len;\n@@ -305,7 +304,13 @@ static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,\n {\n \tchar c;\n \tint color;\n-\tstruct commit *commit;\n+\tstruct commit *commit = item->commit;\n+\n+\tif (merge_filter != NO_FILTER) {\n+\t\tint is_merged = !!(item->commit->object.flags & UNINTERESTING);\n+\t\tif (is_merged != (merge_filter == SHOW_MERGED))\n+\t\t\treturn;\n+\t}\n \n \tswitch (item->kind) {\n \tcase REF_LOCAL_BRANCH:\n@@ -333,7 +338,7 @@ static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,\n \t\tstrbuf_init(&subject, 0);\n \t\tstat[0] = '\\0';\n \n-\t\tcommit = lookup_commit(item->sha1);\n+\t\tcommit = item->commit;\n \t\tif (commit && !parse_commit(commit)) {\n \t\t\tpretty_print_commit(CMIT_FMT_ONELINE, commit,\n \t\t\t\t\t &subject, 0, NULL, NULL, 0, 0);\n@@ -346,7 +351,7 @@ static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,\n \t\tprintf(\"%c %s%-*s%s %s %s%s\\n\", c, branch_get_color(color),\n \t\t maxwidth, item->name,\n \t\t branch_get_color(COLOR_BRANCH_RESET),\n-\t\t find_unique_abbrev(item->sha1, abbrev),\n+\t\t find_unique_abbrev(item->commit->object.sha1, abbrev),\n \t\t stat, sub);\n \t\tstrbuf_release(&subject);\n \t} else {\n@@ -359,22 +364,34 @@ static void print_ref_list(int kinds, int detached, int verbose, int abbrev, str\n {\n \tint i;\n \tstruct ref_list ref_list;\n+\tstruct commit *head_commit = lookup_commit_reference_gently(head_sha1, 1);\n \n \tmemset(&ref_list, 0, sizeof(ref_list));\n \tref_list.kinds = kinds;\n \tref_list.with_commit = with_commit;\n+\tif (merge_filter != NO_FILTER)\n+\t\tinit_revisions(&ref_list.revs, NULL);\n \tfor_each_ref(append_ref, &ref_list);\n+\tif (merge_filter != NO_FILTER) {\n+\t\tstruct commit *filter;\n+\t\tfilter = lookup_commit_reference_gently(merge_filter_ref, 0);\n+\t\tfilter->object.flags |= UNINTERESTING;\n+\t\tadd_pending_object(&ref_list.revs,\n+\t\t\t\t (struct object *) filter, \"\");\n+\t\tref_list.revs.limited = 1;\n+\t\tprepare_revision_walk(&ref_list.revs);\n+\t}\n \n \tqsort(ref_list.list, ref_list.index, sizeof(struct ref_item), ref_cmp);\n \n \tdetached = (detached && (kinds & REF_LOCAL_BRANCH));\n-\tif (detached && has_commit(head_sha1, with_commit)) {\n+\tif (detached && head_commit && has_commit(head_commit, with_commit)) {\n \t\tstruct ref_item item;\n \t\titem.name = xstrdup(\"(no branch)\");\n \t\titem.kind = REF_LOCAL_BRANCH;\n-\t\thashcpy(item.sha1, head_sha1);\n+\t\titem.commit = head_commit;\n \t\tif (strlen(item.name) > ref_list.maxwidth)\n-\t\t\t ref_list.maxwidth = strlen(item.name);\n+\t\t\tref_list.maxwidth = strlen(item.name);\n \t\tprint_ref_item(&item, ref_list.maxwidth, verbose, abbrev, 1);\n \t\tfree(item.name);\n \t}\n-- \n1.6.0.rc0.31.g128c7\n"},{"id":"84679","messageId":"8c5c35580807240016y75b69f69h4af47844f57f4539@mail.gmail.com","threadId":"14617","inReplyTo":"7vtzeg9rhh.fsf_-_@gitster.siamese.dyndns.org","subject":"Re: [PATCH] builtin-branch.c: optimize --merged and --no-merged","fromName":"Lars Hjemli","fromEmail":"lh@elementstorage.no","sentAt":"2008-07-24T07:16:22Z","receivedAt":"2008-07-24T07:16:22Z","isPatch":true,"sender":{"key":"lh@elementstorage.no","avatar":null},"body":"On Thu, Jul 24, 2008 at 12:15 AM, Junio C Hamano wrote:\n> Instead, we can let the revision machinery traverse the history as if we\n> are running:\n>\n> $ git rev-list --branches --not $commit\n>\n> by queueing the tips of branches we encounter as positive refs (this\n> mimicks the \"--branches\" option in the above command line) and then\n> appending the merge_filter_ref commit as a negative one, and finally\n> calling prepare_revision_walk() to limit the list..\n\nNice.\n\n\n> @@ -213,6 +211,7 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n> {\n> struct ref_list *ref_list = (struct ref_list*)(cb_data);\n> struct ref_item *newitem;\n> + struct commit *commit;\n> int kind;\n> int len;\n> static struct commit_list branch;\n\nI think you can drop the 'branch' here.\n\n\n> @@ -239,12 +242,8 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,\n> branch.item = lookup_commit_reference_gently(sha1, 1);\n> if (!branch.item)\n> die(\"Unable to lookup tip of branch %s\", refname);\n\n..and here.\n\n\n- if (merge_filter == SHOW_NOT_MERGED &&\n- has_commit(merge_filter_ref, &branch))\n- return 0;\n- if (merge_filter == SHOW_MERGED &&\n- !has_commit(merge_filter_ref, &branch))\n- return 0;\n+ add_pending_object(&ref_list->revs,\n+ (struct object *)branch.item, refname);\n\n\n..and use 'commit' instead of 'branch.item' here.\n\n\n> @@ -305,7 +304,13 @@ static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,\n> {\n> char c;\n> int color;\n> - struct commit *commit;\n> + struct commit *commit = item->commit;\n> +\n> + if (merge_filter != NO_FILTER) {\n> + int is_merged = !!(item->commit->object.flags & UNINTERESTING);\n> + if (is_merged != (merge_filter == SHOW_MERGED))\n> + return;\n> + }\n\n\nA possible issue here is that `git branch -v --[no]-merged` might use\na wrong maxwidth, but I'm not sure if it's even worth fixing.\n\nThanks for cleaning up my mess.\n--\nlarsh\n"},{"id":"84687","messageId":"20080724172929.6117@nanako3.lavabit.com","threadId":"14617","inReplyTo":"7vtzeg9rhh.fsf_-_@gitster.siamese.dyndns.org","subject":"Re: [PATCH] builtin-branch.c: optimize --merged and --no-merged","fromName":"Nanako Shiraishi","fromEmail":"nanako3@lavabit.com","sentAt":"2008-07-24T08:29:29Z","receivedAt":"2008-07-24T08:29:29Z","isPatch":true,"sender":{"key":"nanako3@lavabit.com","avatar":"https://gravatar.com/avatar/3777b9e201c5883a62b1a6fdf7c53f2d712d1d80989146063ea861e33aad72a8?d=mp&s=160"},"body":"Quoting Junio C Hamano writes:\n\n> \"git branch --no-merged $commit\" used to compute the merge base between\n> the tip of each and every branch with the named $commit, but this was\n> wasteful when you have many branches.\n\nI am not sure if I followed the technical description of the patch, but I\nhave a stupid question. How is --merged different from --contains?\n\n-- \nNanako Shiraishi\nhttp://ivory.ap.teacup.com/nanako3/\n"},{"id":"84696","messageId":"8c5c35580807240303o21596dbbrfca9b9fd0991d91a@mail.gmail.com","threadId":"14617","inReplyTo":"20080724172929.6117@nanako3.lavabit.com","subject":"Re: [PATCH] builtin-branch.c: optimize --merged and --no-merged","fromName":"Lars Hjemli","fromEmail":"lh@elementstorage.no","sentAt":"2008-07-24T10:03:25Z","receivedAt":"2008-07-24T10:03:25Z","isPatch":true,"sender":{"key":"lh@elementstorage.no","avatar":null},"body":"On Thu, Jul 24, 2008 at 10:29 AM, Nanako Shiraishi wrote:\n> How is --merged different from --contains?\n\n--merged only shows the branches which are contained by (reachable\nfrom) a specific commit\n--contains only shows the branches which contains (descends from) a\nspecific commit\n\nAnd finally, --no-merged only shows the branches which are not\ncontained by a specific commit\n\n--\nlarsh\n"},{"id":"84728","messageId":"20080724152742.GA23585@elte.hu","threadId":"14617","inReplyTo":"7v8wvscqtm.fsf@gitster.siamese.dyndns.org","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-24T15:27:42Z","receivedAt":"2008-07-24T15:27:42Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Junio C Hamano wrote:\n\n> Ingo Molnar writes:\n> \n> > hm, it's very slow:\n> >\n> > $ time git branch --no-merged\n> > [...]\n> >\n> > real 0m9.177s\n> > user 0m9.027s\n> > sys 0m0.129s\n> >\n> > when running it on tip/master:\n> >\n> > http://people.redhat.com/mingo/tip.git/README\n> \n> Hmmm, does not reproduce for me with a copy of that repository.\n\nperhaps you need to run tip-create-local-branches.sh to create all the \nlocal branches? You can find it in:\n\n tip/tip .tip/bin/tip-create-local-branches.sh\n\n(does/should the presence of local branches matter?)\n\n\tIngo\n"},{"id":"84729","messageId":"20080724152912.GB23585@elte.hu","threadId":"14617","inReplyTo":"7vy73seb2p.fsf@gitster.siamese.dyndns.org","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-24T15:29:12Z","receivedAt":"2008-07-24T15:29:12Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Junio C Hamano wrote:\n\n> (with patch)\n> 0.15user 0.03system 0:00.18elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n\n> (without patch)\n> 0.58user 0.03system 0:00.61elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n\ncool - a 3.3x speedup :-) Will check that out.\n\n\tIngo\n"},{"id":"84848","messageId":"7vej5iuz9j.fsf@gitster.siamese.dyndns.org","threadId":"14617","inReplyTo":"20080724152742.GA23585@elte.hu","subject":"Re: q: faster way to integrate/merge lots of topic branches?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-25T08:46:48Z","receivedAt":"2008-07-25T08:46:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ingo Molnar writes:\n\n> perhaps you need to run tip-create-local-branches.sh to create all the \n> local branches? You can find it in:\n>\n> tip/tip .tip/bin/tip-create-local-branches.sh\n>\n> (does/should the presence of local branches matter?)\n\nMy refs/remotes/mingo/ hierarchy has as many branches as you do in your\nrepository as local branches, and I presume you do not have these tracking\nbranches as I do because you are the upstream of this repository, so\noverall we have about the same number of refs. In the experiment, I did\n\"branch -a --no-merged\" (notice -a), so I do not think the difference\nshould have mattered.\n"}]}