{"thread":{"id":"6325","subject":"What's cooking in git.git (topics)","startedAt":"2007-01-10T08:23:57Z","lastAt":"2007-01-12T18:16:14Z","messageCount":18,"participants":["Junio C Hamano","Nicolas Pitre","Shawn O. Pearce","Johannes Schindelin","Andreas Ericsson","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"31369","messageId":"7vr6u3cmsi.fsf@assigned-by-dhcp.cox.net","threadId":"6325","inReplyTo":null,"subject":"What's cooking in git.git (topics)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-10T08:23:57Z","receivedAt":"2007-01-10T08:23:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Here are the topics that have been cooking.  Commits prefixed\nwith '-' are only in 'pu' while commits prefixed with '+' are\nin 'next'.  The topics list the commits in reverse chronological\norder.\n\n* jc/detached-head (Tue Jan 9 20:39:09 2007 -0800) 9 commits\n + git-checkout: handle local changes sanely when detaching HEAD\n + git-checkout: safety check for detached HEAD checks existing refs\n + git-checkout: fix branch name output from the command\n + git-checkout: safety when coming back from the detached HEAD\n   state.\n + git-checkout: rewording comments regarding detached HEAD.\n + git-checkout: do not warn detaching HEAD when it is already\n   detached.\n + Detached HEAD (experimental)\n + git-branch: show detached HEAD\n + git-status: show detached HEAD\n\nThis is intended for v1.5.0; will merge to \"master\" by the weekend.\n\n* jc/merge-base (Tue Jan 9 02:23:42 2007 -0800) 6 commits\n - Teach \"git-merge-base --check-ancestry\" about refs.\n - git-merge-base: --check-ancestry option\n + in_merge_bases(): optimization\n + merge_base(): move traversal into a separate function.\n + Allow in_merge_bases() to take more than one reference commits.\n + Make merge-base a built-in.\n\nThe early parts are just clean-up and optimization.  It's not\nworth disrupt v1.5.0 process with potential bugs, so I would say\nthis is on-hold. \n\n* js/reflog (Mon Jan 8 01:59:54 2007 +0100) 1 commit\n + Sanitize for_each_reflog_ent()\n\nI think this makes sense and is a good clean-up.\n\n* jc/bare (Sun Jan 7 02:17:52 2007 -0800) 3 commits\n + git-fetch: allow updating the current branch in a bare repository.\n + Introduce is_bare_repository() and core.bare configuration\n   variable\n + Move initialization of log_all_ref_updates\n\nI'd like to take a serious look at Shawn's RFC patch to make\nPorcelain-ish commands that require working tree refuse to\noperate in a bare repository and rebuild it on top of these;\nintended for v1.5.0.\n\n* sp/merge (Sun Dec 31 00:02:13 2006 -0500) 3 commits\n - Refresh the index before starting merge-recursive.\n - Improve merge performance by avoiding in-index merges.\n - Avoid git-fetch in `git-pull .` when possible.\n* jc/diff (Mon Dec 25 01:08:50 2006 -0800) 2 commits\n - test-para: combined diff between HEAD, index and working tree.\n - para-walk: walk n trees, index and working tree in parallel\n* jc/explain (Mon Dec 4 19:35:04 2006 -0800) 1 commit\n - git-explain\n* jc/3way (Wed Nov 29 18:53:13 2006 -0800) 1 commit\n + git-merge: preserve and merge local changes when doing fast\n   forward\n* jc/web (Wed Nov 8 14:54:09 2006 -0800) 1 commit\n - gitweb: steal loadavg throttle from kernel.org\n* jc/pickaxe (Sun Nov 5 11:52:43 2006 -0800) 1 commit\n - blame: --show-stats for easier optimization work.\n* jc/diff-apply-patch (Fri Sep 22 16:17:58 2006 -0700) 1 commit\n + git-diff/git-apply: make diff output a bit friendlier to GNU patch\n   (part 2)\n"},{"id":"31427","messageId":"7v3b6i75i5.fsf@assigned-by-dhcp.cox.net","threadId":"6325","inReplyTo":"7vr6u3cmsi.fsf@assigned-by-dhcp.cox.net","subject":"What's cooking in git.git (topics)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-11T00:48:34Z","receivedAt":"2007-01-11T00:48:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Here are the topics that have been cooking.  Commits prefixed\nwith '-' are only in 'pu' while commits prefixed with '+' are\nin 'next'.  The topics list the commits in reverse chronological\norder.\n\n* jc/detached-head (Tue Jan 9 20:39:09 2007 -0800) 9 commits\n + git-checkout: handle local changes sanely when detaching HEAD\n + git-checkout: safety check for detached HEAD checks existing refs\n + git-checkout: fix branch name output from the command\n + git-checkout: safety when coming back from the detached HEAD\n   state.\n + git-checkout: rewording comments regarding detached HEAD.\n + git-checkout: do not warn detaching HEAD when it is already\n   detached.\n + Detached HEAD (experimental)\n + git-branch: show detached HEAD\n + git-status: show detached HEAD\n\nWill be merged to 'master' in a few days for v1.5.0-rc1.\n\n* jc/bare (Sat Dec 30 23:32:38 2006 -0500) 4 commits\n + Disallow working directory commands in a bare repository.\n + git-fetch: allow updating the current branch in a bare repository.\n + Introduce is_bare_repository() and core.bare configuration\n   variable\n + Move initialization of log_all_ref_updates\n\nI munged Shawn's RFC patch and placed on top of this series.\nWill be merged to 'master' in a few days for v1.5.0-rc1.\n\n* ar/merge-recursive (Wed Jan 10 11:20:58 2007 -0800) 2 commits\n + merge-recursive: do not use on-file index when not needed.\n + Speed-up recursive by flushing index only once for all entries\n\nI did not see much improvement (maybe a largish kernel merge\ngoing from 2.5 seconds to slightly less than one second) but\nthis seems safe and the change removes a lot more code than it\nadds which must mean it is good.  Perhaps in v1.5.0-rc1 but I do\nnot think it is a must-have.  Comments?\n\n\n* sp/merge (Thu Dec 28 02:35:17 2006 -0500) 2 commits\n - Avoid git-fetch in `git-pull .` when possible.\n + Improve merge performance by avoiding in-index merges.\n\nI fliped the patches around and the one that avoids the\n\"read-tree then merge-recursive\" sequence is now in 'next'.  I\nhaven't done any measurements yet.  It looks obviously correct\nbut I am not sure if it is a v1.5.0 material.  Comments?\n\n\n* sp/describe (Wed Jan 10 06:39:47 2007 -0500) 1 commit\n - Chose better tag names in git-describe after merges.\n\nSlowing it down by 4x is very unfortunate.  I think there is a\nbetter way to walk the ancestry than doing one at a time to\ncount the commits, but I did not have enough time to look at\nthis today.\n\n* jc/merge-base (Tue Jan 9 02:23:42 2007 -0800) 6 commits\n - Teach \"git-merge-base --check-ancestry\" about refs.\n - git-merge-base: --check-ancestry option\n + in_merge_bases(): optimization\n + merge_base(): move traversal into a separate function.\n + Allow in_merge_bases() to take more than one reference commits.\n + Make merge-base a built-in.\n\n* jc/diff (Mon Dec 25 01:08:50 2006 -0800) 2 commits\n - test-para: combined diff between HEAD, index and working tree.\n - para-walk: walk n trees, index and working tree in parallel\n* jc/explain (Mon Dec 4 19:35:04 2006 -0800) 1 commit\n - git-explain\n* jc/3way (Wed Nov 29 18:53:13 2006 -0800) 1 commit\n + git-merge: preserve and merge local changes when doing fast\n   forward\n* jc/web (Wed Nov 8 14:54:09 2006 -0800) 1 commit\n - gitweb: steal loadavg throttle from kernel.org\n* jc/pickaxe (Sun Nov 5 11:52:43 2006 -0800) 1 commit\n - blame: --show-stats for easier optimization work.\n* jc/diff-apply-patch (Fri Sep 22 16:17:58 2006 -0700) 1 commit\n + git-diff/git-apply: make diff output a bit friendlier to GNU patch\n   (part 2)\n\nThese are on-hold.\n"},{"id":"31428","messageId":"Pine.LNX.4.64.0701102241230.4964@xanadu.home","threadId":"6325","inReplyTo":"7v3b6i75i5.fsf@assigned-by-dhcp.cox.net","subject":"Re: What's cooking in git.git (topics)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-01-11T03:50:00Z","receivedAt":"2007-01-11T03:50:00Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 10 Jan 2007, Junio C Hamano wrote:\n\n> * jc/detached-head (Tue Jan 9 20:39:09 2007 -0800) 9 commits\n\nI want to say that this is really great and well done.\n\n> * sp/describe (Wed Jan 10 06:39:47 2007 -0500) 1 commit\n>  - Chose better tag names in git-describe after merges.\n> \n> Slowing it down by 4x is very unfortunate.  I think there is a\n> better way to walk the ancestry than doing one at a time to\n> count the commits, but I did not have enough time to look at\n> this today.\n\nHowever git-describe is certainly not a frequent and speed critical \noperation, and \neven if it cannot be sped up then waiting 300 ms more won't really \naffect one's workflow that badly.\n\n\nNicolas\n"},{"id":"31434","messageId":"20070111080035.GA28222@spearce.org","threadId":"6325","inReplyTo":"Pine.LNX.4.64.0701102241230.4964@xanadu.home","subject":"Re: What's cooking in git.git (topics)","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-11T08:00:36Z","receivedAt":"2007-01-11T08:00:36Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre <nico@cam.org> wrote:\n> On Wed, 10 Jan 2007, Junio C Hamano wrote:\n> > * sp/describe (Wed Jan 10 06:39:47 2007 -0500) 1 commit\n> >  - Chose better tag names in git-describe after merges.\n> > \n> > Slowing it down by 4x is very unfortunate.  I think there is a\n> > better way to walk the ancestry than doing one at a time to\n> > count the commits, but I did not have enough time to look at\n> > this today.\n> \n> However git-describe is certainly not a frequent and speed critical \n> operation, and \n> even if it cannot be sped up then waiting 300 ms more won't really \n> affect one's workflow that badly.\n\nMy thoughts exactly.  I spent a few hours trying to determine\nan algorithm that produced the right answer and did not require\ngenerating the revlist between the tag and the requested commit\nfor every possibly matching tag.  I did not come up with one.\nIf someone else does it would obviously be a welcome replacement\nto my own patch.  :-)\n\nThere is almost no additional penalty for a simple strand of pearls\nwith the tag placed along that strand; only one possible tag will be\nfound.  But my code does an unnecessary revision list in this case.\n\nWhere we really get hit is the large number of possible tags.  The\nmaster branch is turning up 14 tags, some dating back to v1.4.1-rc1.\nI do try to abort the revision list as soon as one of those tags\ncannot give me a better selection than the one I have currently,\nbut I still had to generate a revision list to reach that point.\n\n-- \nShawn.\n"},{"id":"31441","messageId":"Pine.LNX.4.63.0701110949421.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6325","inReplyTo":"7v3b6i75i5.fsf@assigned-by-dhcp.cox.net","subject":"Re: What's cooking in git.git (topics)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-01-11T08:53:34Z","receivedAt":"2007-01-11T08:53:34Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 10 Jan 2007, Junio C Hamano wrote:\n\n> * ar/merge-recursive (Wed Jan 10 11:20:58 2007 -0800) 2 commits\n>  + merge-recursive: do not use on-file index when not needed.\n>  + Speed-up recursive by flushing index only once for all entries\n> \n> I did not see much improvement (maybe a largish kernel merge\n> going from 2.5 seconds to slightly less than one second)\n\nThat is a heck of an improvement. It is only uses 40% of the time it used \nbefore! On other machines, with other OSes, this makes the difference \nbetween 10 minutes and 4 minutes.\n\nBTW I am not quite sure if you missed this patch: \nhttp://thread.gmane.org/gmane.comp.version-control.git/36212/, or if you \ndid not like it, want enhancements, ...\n\nCiao,\nDscho\n"},{"id":"31444","messageId":"45A6016B.4030800@op5.se","threadId":"6325","inReplyTo":"20070111080035.GA28222@spearce.org","subject":"Re: What's cooking in git.git (topics)","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-01-11T09:20:43Z","receivedAt":"2007-01-11T09:20:43Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Shawn O. Pearce wrote:\n> Nicolas Pitre <nico@cam.org> wrote:\n>> On Wed, 10 Jan 2007, Junio C Hamano wrote:\n>>> * sp/describe (Wed Jan 10 06:39:47 2007 -0500) 1 commit\n>>>  - Chose better tag names in git-describe after merges.\n>>>\n>>> Slowing it down by 4x is very unfortunate.  I think there is a\n>>> better way to walk the ancestry than doing one at a time to\n>>> count the commits, but I did not have enough time to look at\n>>> this today.\n>> However git-describe is certainly not a frequent and speed critical \n>> operation, and \n>> even if it cannot be sped up then waiting 300 ms more won't really \n>> affect one's workflow that badly.\n> \n> My thoughts exactly.  I spent a few hours trying to determine\n> an algorithm that produced the right answer and did not require\n> generating the revlist between the tag and the requested commit\n> for every possibly matching tag.  I did not come up with one.\n> If someone else does it would obviously be a welcome replacement\n> to my own patch.  :-)\n> \n> There is almost no additional penalty for a simple strand of pearls\n> with the tag placed along that strand; only one possible tag will be\n> found.  But my code does an unnecessary revision list in this case.\n> \n> Where we really get hit is the large number of possible tags.  The\n> master branch is turning up 14 tags, some dating back to v1.4.1-rc1.\n> I do try to abort the revision list as soon as one of those tags\n> cannot give me a better selection than the one I have currently,\n> but I still had to generate a revision list to reach that point.\n> \n\nIt could be worth skipping tags more than 6 months older than current \nbranch-head. That would, at least for the git case, cut the number of \ntags down by a considerable amount.\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n"},{"id":"31446","messageId":"7v1wm16gyd.fsf@assigned-by-dhcp.cox.net","threadId":"6325","inReplyTo":"20070111080035.GA28222@spearce.org","subject":"Re: What's cooking in git.git (topics)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-11T09:38:50Z","receivedAt":"2007-01-11T09:38:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> There is almost no additional penalty for a simple strand of pearls\n> with the tag placed along that strand; only one possible tag will be\n> found.  But my code does an unnecessary revision list in this case.\n>\n> Where we really get hit is the large number of possible tags.  The\n> master branch is turning up 14 tags, some dating back to v1.4.1-rc1.\n> I do try to abort the revision list as soon as one of those tags\n> cannot give me a better selection than the one I have currently,\n> but I still had to generate a revision list to reach that point.\n\nI looked at the algorithm, and after scratching my head for a\nwhile, I finally found it sane (modulo leaks, which I think I\nfixed with the attached patch).\n\nOne minor problem that you inherited from the original algorithm\nis the name priority.  If you have an annotated tag A and a\nlightweight tag b, and ask \"git describe --tags\" in this graph:\n\n    ---o---o---o---o---x\n           A   b\n\nyou would still want to describe 'x' with A, not b.\nUnfortunately you don't (and the original doesn't either).\n\nI think this is probably easy to solve in the loop that finds\n\"all_matches\"; once you hit an annotated tag, your traversal\nshould stop in any case.  But if you were asked for --tags, and\nif your \"initialized\" piece did find both lightweight and\nannotated tags, you do not stop when you saw a lightweight one,\nbut keep looking for an annotated one, ignoring any further\nlightweight ones.\n\nAnother thought.  I often do \"git describe maint master next\npu\", and I see an opportunity for optimizing for such a\nmulti-ref query.  Once you traversed the commits in\n\"all_matches\" loop, you know which strands of pearls are\nreachable to what tags, so you could hang that information\nsomewhere (perhaps ->utils) in each commit.  But I think\noptimizing for a multi-ref query is probably not worth it.\n\n\n-- >8 --\n[PATCH] plug a few leaks in revision walking used in describe.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n builtin-describe.c |    1 +\n revision.c         |    8 +++++---\n 2 files changed, 6 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin-describe.c b/builtin-describe.c\nindex d65c7d2..a8c98ce 100644\n--- a/builtin-describe.c\n+++ b/builtin-describe.c\n@@ -183,6 +183,7 @@ static void describe(const char *arg, int last_one)\n \t\t\tcur_match->depth++;\n \t\tif (!min_match || cur_match->depth < min_match->depth)\n \t\t\tmin_match = cur_match;\n+\t\tfree_commit_list(revs.commits);\n \t}\n \tprintf(\"%s-g%s\\n\", min_match->name->path,\n \t\t   find_unique_abbrev(cmit->object.sha1, abbrev));\ndiff --git a/revision.c b/revision.c\nindex 1e3b29a..f2ddd95 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1121,21 +1121,23 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch\n void prepare_revision_walk(struct rev_info *revs)\n {\n \tint nr = revs->pending.nr;\n-\tstruct object_array_entry *list = revs->pending.objects;\n+\tstruct object_array_entry *e, *list;\n \n+\te = list = revs->pending.objects;\n \trevs->pending.nr = 0;\n \trevs->pending.alloc = 0;\n \trevs->pending.objects = NULL;\n \twhile (--nr >= 0) {\n-\t\tstruct commit *commit = handle_commit(revs, list->item, list->name);\n+\t\tstruct commit *commit = handle_commit(revs, e->item, e->name);\n \t\tif (commit) {\n \t\t\tif (!(commit->object.flags & SEEN)) {\n \t\t\t\tcommit->object.flags |= SEEN;\n \t\t\t\tinsert_by_date(commit, &revs->commits);\n \t\t\t}\n \t\t}\n-\t\tlist++;\n+\t\te++;\n \t}\n+\tfree(list);\n \n \tif (revs->no_walk)\n \t\treturn;\n"},{"id":"31451","messageId":"7vsleh51zx.fsf@assigned-by-dhcp.cox.net","threadId":"6325","inReplyTo":"Pine.LNX.4.63.0701110949421.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: What's cooking in git.git (topics)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-11T09:47:14Z","receivedAt":"2007-01-11T09:47:14Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> BTW I am not quite sure if you missed this patch: \n> http://thread.gmane.org/gmane.comp.version-control.git/36212/, or if you \n> did not like it, want enhancements, ...\n\nIt is still sitting in my in-box; I tend to agree with Shawn in\nthat mixing the reflog sequence and true parenthood in the same\ntraversal is kind of insane.  I vaguely recall you thought\ndropping that would make the code simpler, and was kind of\nwaiting for that to happen to review the results.\n\nAlso I did not quite understand your comment about circular log\nentries.\n\nWhen you walk the reflog, the entries are by definition a single\nstrand of pearls (reflog itself is a flat text file which you\nread linearly).  The commits adjacent entries talk about may or\nmay not be related at all, and two entries may happen to point\nat the same commit.  But I do not think the appearance of\nanother reflog entry in an earlier call to get_revision() should\nnot cause a reflog entry to be dropped from the output only\nbecause it points at the same commit.\n"},{"id":"31455","messageId":"Pine.LNX.4.63.0701111103140.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6325","inReplyTo":"7vsleh51zx.fsf@assigned-by-dhcp.cox.net","subject":"Re: What's cooking in git.git (topics)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-01-11T10:04:28Z","receivedAt":"2007-01-11T10:04:28Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 11 Jan 2007, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > BTW I am not quite sure if you missed this patch: \n> > http://thread.gmane.org/gmane.comp.version-control.git/36212/, or if you \n> > did not like it, want enhancements, ...\n> \n> It is still sitting in my in-box; I tend to agree with Shawn in\n> that mixing the reflog sequence and true parenthood in the same\n> traversal is kind of insane.\n\nOkay.\n\n> I vaguely recall you thought dropping that would make the code simpler, \n> and was kind of waiting for that to happen to review the results.\n\nI was kind of waiting if somebody actually cares.\n\n> Also I did not quite understand your comment about circular log\n> entries.\n\nBut you did! My comment was only that I did not test if it actually works \nas expected.\n\nCiao,\nDscho\n"},{"id":"31456","messageId":"20070111100800.GB28309@spearce.org","threadId":"6325","inReplyTo":"7v1wm16gyd.fsf@assigned-by-dhcp.cox.net","subject":"Re: What's cooking in git.git (topics)","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-11T10:08:00Z","receivedAt":"2007-01-11T10:08:00Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> I looked at the algorithm, and after scratching my head for a\n> while, I finally found it sane (modulo leaks, which I think I\n> fixed with the attached patch).\n\nThanks.  I don't think it says much for the quality of my code\nif you had to scratch your head before you understood it.  But\nat least you finally got it.  :)\n \n> One minor problem that you inherited from the original algorithm\n> is the name priority.  If you have an annotated tag A and a\n> lightweight tag b, and ask \"git describe --tags\" in this graph:\n> \n>     ---o---o---o---o---x\n>            A   b\n> \n> you would still want to describe 'x' with A, not b.\n> Unfortunately you don't (and the original doesn't either).\n\nActually I think you want to describe it with b.  If you ask\n'--tags' then you want the lightweight ones too.  In the case above\nthe lightweight tag b better describes x as it has more in common\nwith x than A has.\n\n> I think this is probably easy to solve in the loop that finds\n> \"all_matches\"; once you hit an annotated tag, your traversal\n> should stop in any case.  But if you were asked for --tags, and\n> if your \"initialized\" piece did find both lightweight and\n> annotated tags, you do not stop when you saw a lightweight one,\n> but keep looking for an annotated one, ignoring any further\n> lightweight ones.\n\nI just implemented this in that loop, and then realized what\nI wrote above.  The lower loop that performs the revision list\ntraversal would have both A and b in all_matches and b would win,\nas its closer to x.  So having the first loop abort when it does\nis the right thing to do, and so is describing x with b.\n\n> Another thought.  I often do \"git describe maint master next\n> pu\", and I see an opportunity for optimizing for such a\n> multi-ref query.  Once you traversed the commits in\n> \"all_matches\" loop, you know which strands of pearls are\n> reachable to what tags, so you could hang that information\n> somewhere (perhaps ->utils) in each commit.  But I think\n> optimizing for a multi-ref query is probably not worth it.\n\nWithout my patch its ~170ms; with my patch its ~1000ms.  That is\na huge difference for such a simple program.  I'm not sure your\noptimization will make a big difference.  The bulk of the cost\nappears to be in the later loop, not in the earlier one that\nproduces all_matches.\n\n-- \nShawn.\n"},{"id":"31477","messageId":"Pine.LNX.4.64.0701110955100.4964@xanadu.home","threadId":"6325","inReplyTo":"45A6016B.4030800@op5.se","subject":"Re: What's cooking in git.git (topics)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-01-11T14:59:40Z","receivedAt":"2007-01-11T14:59:40Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 11 Jan 2007, Andreas Ericsson wrote:\n\n> Shawn O. Pearce wrote:\n> > Where we really get hit is the large number of possible tags.  The\n> > master branch is turning up 14 tags, some dating back to v1.4.1-rc1.\n> > I do try to abort the revision list as soon as one of those tags\n> > cannot give me a better selection than the one I have currently,\n> > but I still had to generate a revision list to reach that point.\n> > \n> \n> It could be worth skipping tags more than 6 months older than current\n> branch-head. That would, at least for the git case, cut the number of tags\n> down by a considerable amount.\n\nThis is bound to be wrong in some cases if a project is very active with \nmany tags, or if there was a long period of inactivity. And what would \nbe the benefit?  Saving 250ms on git-describe output latency?\n\n\nNicolas\n"},{"id":"31478","messageId":"45A65F15.6040606@op5.se","threadId":"6325","inReplyTo":"Pine.LNX.4.64.0701110955100.4964@xanadu.home","subject":"Re: What's cooking in git.git (topics)","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-01-11T16:00:21Z","receivedAt":"2007-01-11T16:00:21Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Nicolas Pitre wrote:\n> On Thu, 11 Jan 2007, Andreas Ericsson wrote:\n> \n>> Shawn O. Pearce wrote:\n>>> Where we really get hit is the large number of possible tags.  The\n>>> master branch is turning up 14 tags, some dating back to v1.4.1-rc1.\n>>> I do try to abort the revision list as soon as one of those tags\n>>> cannot give me a better selection than the one I have currently,\n>>> but I still had to generate a revision list to reach that point.\n>>>\n>> It could be worth skipping tags more than 6 months older than current\n>> branch-head. That would, at least for the git case, cut the number of tags\n>> down by a considerable amount.\n> \n> This is bound to be wrong in some cases if a project is very active with \n> many tags, or if there was a long period of inactivity. And what would \n> be the benefit?  Saving 250ms on git-describe output latency?\n> \n\nOutput latency will grow with number of tags though, won't it? I was \nthinking of the repo which users had reported problems fetching tags \nfrom, as there was more than 2k tags. If my memory serves me correctly, \nthis report led to the packed-refs stuff.\n\nUnless there's some bogosity going on that leads to it finding the 14 \ntags in the above case.\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n"},{"id":"31519","messageId":"7v64bd15lg.fsf@assigned-by-dhcp.cox.net","threadId":"6325","inReplyTo":"20070111100800.GB28309@spearce.org","subject":"Re: What's cooking in git.git (topics)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-11T23:55:23Z","receivedAt":"2007-01-11T23:55:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n>> One minor problem that you inherited from the original algorithm\n>> is the name priority.  If you have an annotated tag A and a\n>> lightweight tag b, and ask \"git describe --tags\" in this graph:\n>> \n>>     ---o---o---o---o---x\n>>            A   b\n>> \n>> you would still want to describe 'x' with A, not b.\n>> Unfortunately you don't (and the original doesn't either).\n>\n> Actually I think you want to describe it with b.  If you ask\n> '--tags' then you want the lightweight ones too.  In the case above\n> the lightweight tag b better describes x as it has more in common\n> with x than A has.\n\nThe reason why I would run the command with --tags is to cope\nwith this kind of graph.\n\n             o---o---o---x\n            /\n    ---o---o---o---o---o---y\n       b       A\n\nin order to use lightweight ones as a back-up.  Otherwise we\nwould not have had the \"prio\" business there.\n\nAnd I would prefer if the presense of lightweight 'c' tag did\nnot change how 'y' is described:\n\n\n             o---o---o---x\n            /\n    ---o---o---o---o---o---y\n       b       A       c\n"},{"id":"31527","messageId":"20070112004927.GB23864@spearce.org","threadId":"6325","inReplyTo":"45A65F15.6040606@op5.se","subject":"Re: What's cooking in git.git (topics)","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-12T00:49:27Z","receivedAt":"2007-01-12T00:49:27Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Andreas Ericsson <ae@op5.se> wrote:\n> Output latency will grow with number of tags though, won't it? I was \n> thinking of the repo which users had reported problems fetching tags \n> from, as there was more than 2k tags. If my memory serves me correctly, \n> this report led to the packed-refs stuff.\n\nOnly on tags which are considered possible matches.  What we do\nnow is we walk back along the commit history until we find a commit\nwhich has a tag pointing at it.  As soon as we find that commit we\nenqueue its corresponding tag into a list and completely ignore its\nparents, aborting listing any further back.  So we really only pay\nthe bare minimum price here.\n\nUnfortunately the tag matching is O(n*m*q) where:\n\n  n == number of tags,\n  m == number of commits we have to walk back before we find a tag,\n  q == number of possible tags that will match for this lineage.\n\nStoring the tags in a hash structure would accelerate this matching,\nespecially for high values of n.  m and q we cannot do anything\nabout, except to recommend to projects that they tag more than\noften then never.\n\n> Unless there's some bogosity going on that leads to it finding the 14 \n> tags in the above case.\n\nYea, its a bogosity in the way the branches are merged together.\nI haven't dug into what is causing this specifically in git.git\nbut I know the code is doing the best it can to select the smallest\nset of possible matches.\n\nThere is however a better algorithm for the revision list generation;\nI think I can fold it into the main walkback loop and still get the\nright result.  I have to read a stack of papers tonight but I'll\nsee if I can try to code up the algorithm.  It would accelerate\ngit-describe right back to where it was before my change.\n\n-- \nShawn.\n"},{"id":"31531","messageId":"20070112010126.GF23864@spearce.org","threadId":"6325","inReplyTo":"7v64bd15lg.fsf@assigned-by-dhcp.cox.net","subject":"Re: What's cooking in git.git (topics)","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-12T01:01:26Z","receivedAt":"2007-01-12T01:01:26Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> The reason why I would run the command with --tags is to cope\n> with this kind of graph.\n> \n>              o---o---o---x\n>             /\n>     ---o---o---o---o---o---y\n>        b       A\n\nWhy isn't that the default?\n \n> in order to use lightweight ones as a back-up.  Otherwise we\n> would not have had the \"prio\" business there.\n> \n> And I would prefer if the presense of lightweight 'c' tag did\n> not change how 'y' is described:\n> \n> \n>              o---o---o---x\n>             /\n>     ---o---o---o---o---o---y\n>        b       A       c\n\nIf we just make '--tags' the default and fix the priority to always\npick an annotated tag over a lightweight one then things make sense.\nWe'd automatically pickup b above for x but always A for y.\n\n-- \nShawn.\n"},{"id":"31544","messageId":"7vr6u0wz2s.fsf@assigned-by-dhcp.cox.net","threadId":"6325","inReplyTo":"20070112004927.GB23864@spearce.org","subject":"Re: What's cooking in git.git (topics)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-12T06:15:07Z","receivedAt":"2007-01-12T06:15:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> Only on tags which are considered possible matches.  What we do\n> now is we walk back along the commit history until we find a commit\n> which has a tag pointing at it.  As soon as we find that commit we\n> enqueue its corresponding tag into a list and completely ignore its\n> parents, aborting listing any further back.  So we really only pay\n> the bare minimum price here.\n\nThis actually is QUITE bad.\n\nWith the tip of linux-2.6 repository, v1.4.4 series takes 0.03s\nwhile v1.5.0-rc1 takes about 3.6s.  That is 100x fold, not just\n4x.\n\nIt turns out that to describe 0404f87f (tip of linux-2.6) the\nnew one picks up 61 tags in the posible-tag loop.\n\nSince this loop uses the usual date-order, we can limit the\nnumber of candidate tags without losing too much precision.\nWhen limiting the candidates to only 6 (attached patch), the\ntime drops to 0.25s.\n\n--- \ndiff --git a/builtin-describe.c b/builtin-describe.c\nindex a8c98ce..a1ecec2 100644\n--- a/builtin-describe.c\n+++ b/builtin-describe.c\n@@ -12,6 +12,7 @@ static const char describe_usage[] =\n \n static int all;\t/* Default to annotated tags only */\n static int tags;\t/* But allow any tags if --tags is specified */\n+static int debug;\n \n static int abbrev = DEFAULT_ABBREV;\n \n@@ -113,6 +114,7 @@ static void describe(const char *arg, int last_one)\n \tstatic int initialized = 0;\n \tstruct commit_name *n;\n \tstruct possible_tag *all_matches, *min_match, *cur_match;\n+\tint cnt;\n \n \tif (get_sha1(arg, sha1))\n \t\tdie(\"Not a valid object name %s\", arg);\n@@ -136,6 +138,7 @@ static void describe(const char *arg, int last_one)\n \tall_matches = NULL;\n \tcur_match = NULL;\n \tcommit_list_insert(cmit, &list);\n+\tcnt = 6;\n \twhile (list) {\n \t\tstruct commit *c = pop_commit(&list);\n \t\tn = match(c);\n@@ -148,6 +151,8 @@ static void describe(const char *arg, int last_one)\n \t\t\telse\n \t\t\t\tall_matches = p;\n \t\t\tcur_match = p;\n+\t\t\tif (--cnt <= 0)\n+\t\t\t\tbreak;\n \t\t} else {\n \t\t\tstruct commit_list *parents = c->parents;\n \t\t\twhile (parents) {\n@@ -161,6 +166,18 @@ static void describe(const char *arg, int last_one)\n \t\t\t}\n \t\t}\n \t}\n+\tif (list)\n+\t\tfree_commit_list(list);\n+\n+\tif (debug) {\n+\t\tint cnt = 0;\n+\t\tfor (cur_match = all_matches;\n+\t\t     cur_match;\n+\t\t     cur_match = cur_match->next)\n+\t\t\tcnt++;\n+\t\tfprintf(stderr, \"%d candidates for %s\\n\", cnt,\n+\t\t\tsha1_to_hex(cmit->object.sha1));\n+\t}\n \n \tif (!all_matches)\n \t\tdie(\"cannot describe '%s'\", sha1_to_hex(cmit->object.sha1));\n@@ -210,6 +227,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\t\tall = 1;\n \t\telse if (!strcmp(arg, \"--tags\"))\n \t\t\ttags = 1;\n+\t\telse if (!strcmp(arg, \"--debug\"))\n+\t\t\tdebug = 1;\n \t\telse if (!strncmp(arg, \"--abbrev=\", 9)) {\n \t\t\tabbrev = strtoul(arg + 9, NULL, 10);\n \t\t\tif (abbrev < MINIMUM_ABBREV || 40 < abbrev)\n"},{"id":"31545","messageId":"20070112062644.GC24195@spearce.org","threadId":"6325","inReplyTo":"7vr6u0wz2s.fsf@assigned-by-dhcp.cox.net","subject":"Re: What's cooking in git.git (topics)","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-12T06:26:44Z","receivedAt":"2007-01-12T06:26:44Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> With the tip of linux-2.6 repository, v1.4.4 series takes 0.03s\n> while v1.5.0-rc1 takes about 3.6s.  That is 100x fold, not just\n> 4x.\n> \n> It turns out that to describe 0404f87f (tip of linux-2.6) the\n> new one picks up 61 tags in the posible-tag loop.\n> \n> Since this loop uses the usual date-order, we can limit the\n> number of candidate tags without losing too much precision.\n> When limiting the candidates to only 6 (attached patch), the\n> time drops to 0.25s.\n\nOK.  Apply your patch to master.  3.6s is insane, even for\ngit-describe. I think your guess of 6 is reasonable, but I'd\nobviously like to remove the need for it entirely.\n\nI think I have a sketch in my head for an algorithm that can\ncompute the revision counts while in the possible-tag loop, which\nwould completely remove the huge cost of the per-tag revision\nlist later on.  I can't work on it right now (need to get other\nstuff done before 1 pm Friday) but I will try to code and test it\ntomorrow afternoon.  If I'm right I'll send a patch.\n\n-- \nShawn.\n"},{"id":"31569","messageId":"eo8j8o$ahq$1@sea.gmane.org","threadId":"6325","inReplyTo":"20070111100800.GB28309@spearce.org","subject":"Re: What's cooking in git.git (topics)","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2007-01-12T18:16:14Z","receivedAt":"2007-01-12T18:16:14Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Shawn O. Pearce wrote:\n\n>> One minor problem that you inherited from the original algorithm\n>> is the name priority.  If you have an annotated tag A and a\n>> lightweight tag b, and ask \"git describe --tags\" in this graph:\n>> \n>>     ---o---o---o---o---x\n>>            A   b\n>> \n>> you would still want to describe 'x' with A, not b.\n>> Unfortunately you don't (and the original doesn't either).\n> \n> Actually I think you want to describe it with b.  If you ask\n> '--tags' then you want the lightweight ones too.  In the case above\n> the lightweight tag b better describes x as it has more in common\n> with x than A has.\n\nActually I very often want to describe with _annotated_ tags only.\nI have few lightweight tags which are former heads (former branches),\nfew lightweight tags which are branch points or before-merge points,\nand are _not_ version tags.\n\nAlthough perhaps command line switch (to prefer annotated tags to\nlightweight tags) would be better...\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"}]}