# What's cooking in git.git (topics) 18 messages from 2007-01-10 to 2007-01-12. Participants: Junio C Hamano, Nicolas Pitre, Shawn O. Pearce, Johannes Schindelin, Andreas Ericsson, Jakub Narebski. Thread: https://gitlist.dev/t/6325 ## Junio C Hamano, 2007-01-10 08:23 Subject: What's cooking in git.git (topics) Message-ID: <7vr6u3cmsi.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vr6u3cmsi.fsf%40assigned-by-dhcp.cox.net ``` Here are the topics that have been cooking. Commits prefixed with '-' are only in 'pu' while commits prefixed with '+' are in 'next'. The topics list the commits in reverse chronological order. * jc/detached-head (Tue Jan 9 20:39:09 2007 -0800) 9 commits + git-checkout: handle local changes sanely when detaching HEAD + git-checkout: safety check for detached HEAD checks existing refs + git-checkout: fix branch name output from the command + git-checkout: safety when coming back from the detached HEAD state. + git-checkout: rewording comments regarding detached HEAD. + git-checkout: do not warn detaching HEAD when it is already detached. + Detached HEAD (experimental) + git-branch: show detached HEAD + git-status: show detached HEAD This is intended for v1.5.0; will merge to "master" by the weekend. * jc/merge-base (Tue Jan 9 02:23:42 2007 -0800) 6 commits - Teach "git-merge-base --check-ancestry" about refs. - git-merge-base: --check-ancestry option + in_merge_bases(): optimization + merge_base(): move traversal into a separate function. + Allow in_merge_bases() to take more than one reference commits. + Make merge-base a built-in. The early parts are just clean-up and optimization. It's not worth disrupt v1.5.0 process with potential bugs, so I would say this is on-hold. * js/reflog (Mon Jan 8 01:59:54 2007 +0100) 1 commit + Sanitize for_each_reflog_ent() I think this makes sense and is a good clean-up. * jc/bare (Sun Jan 7 02:17:52 2007 -0800) 3 commits + git-fetch: allow updating the current branch in a bare repository. + Introduce is_bare_repository() and core.bare configuration variable + Move initialization of log_all_ref_updates I'd like to take a serious look at Shawn's RFC patch to make Porcelain-ish commands that require working tree refuse to operate in a bare repository and rebuild it on top of these; intended for v1.5.0. * sp/merge (Sun Dec 31 00:02:13 2006 -0500) 3 commits - Refresh the index before starting merge-recursive. - Improve merge performance by avoiding in-index merges. - Avoid git-fetch in `git-pull .` when possible. * jc/diff (Mon Dec 25 01:08:50 2006 -0800) 2 commits - test-para: combined diff between HEAD, index and working tree. - para-walk: walk n trees, index and working tree in parallel * jc/explain (Mon Dec 4 19:35:04 2006 -0800) 1 commit - git-explain * jc/3way (Wed Nov 29 18:53:13 2006 -0800) 1 commit + git-merge: preserve and merge local changes when doing fast forward * jc/web (Wed Nov 8 14:54:09 2006 -0800) 1 commit - gitweb: steal loadavg throttle from kernel.org * jc/pickaxe (Sun Nov 5 11:52:43 2006 -0800) 1 commit - blame: --show-stats for easier optimization work. * jc/diff-apply-patch (Fri Sep 22 16:17:58 2006 -0700) 1 commit + git-diff/git-apply: make diff output a bit friendlier to GNU patch (part 2) ``` ## Junio C Hamano, 2007-01-11 00:48 Subject: What's cooking in git.git (topics) Message-ID: <7v3b6i75i5.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7v3b6i75i5.fsf%40assigned-by-dhcp.cox.net In-Reply-To: <7vr6u3cmsi.fsf@assigned-by-dhcp.cox.net> ``` Here are the topics that have been cooking. Commits prefixed with '-' are only in 'pu' while commits prefixed with '+' are in 'next'. The topics list the commits in reverse chronological order. * jc/detached-head (Tue Jan 9 20:39:09 2007 -0800) 9 commits + git-checkout: handle local changes sanely when detaching HEAD + git-checkout: safety check for detached HEAD checks existing refs + git-checkout: fix branch name output from the command + git-checkout: safety when coming back from the detached HEAD state. + git-checkout: rewording comments regarding detached HEAD. + git-checkout: do not warn detaching HEAD when it is already detached. + Detached HEAD (experimental) + git-branch: show detached HEAD + git-status: show detached HEAD Will be merged to 'master' in a few days for v1.5.0-rc1. * jc/bare (Sat Dec 30 23:32:38 2006 -0500) 4 commits + Disallow working directory commands in a bare repository. + git-fetch: allow updating the current branch in a bare repository. + Introduce is_bare_repository() and core.bare configuration variable + Move initialization of log_all_ref_updates I munged Shawn's RFC patch and placed on top of this series. Will be merged to 'master' in a few days for v1.5.0-rc1. * ar/merge-recursive (Wed Jan 10 11:20:58 2007 -0800) 2 commits + merge-recursive: do not use on-file index when not needed. + Speed-up recursive by flushing index only once for all entries I did not see much improvement (maybe a largish kernel merge going from 2.5 seconds to slightly less than one second) but this seems safe and the change removes a lot more code than it adds which must mean it is good. Perhaps in v1.5.0-rc1 but I do not think it is a must-have. Comments? * sp/merge (Thu Dec 28 02:35:17 2006 -0500) 2 commits - Avoid git-fetch in `git-pull .` when possible. + Improve merge performance by avoiding in-index merges. I fliped the patches around and the one that avoids the "read-tree then merge-recursive" sequence is now in 'next'. I haven't done any measurements yet. It looks obviously correct but I am not sure if it is a v1.5.0 material. Comments? * sp/describe (Wed Jan 10 06:39:47 2007 -0500) 1 commit - Chose better tag names in git-describe after merges. Slowing it down by 4x is very unfortunate. I think there is a better way to walk the ancestry than doing one at a time to count the commits, but I did not have enough time to look at this today. * jc/merge-base (Tue Jan 9 02:23:42 2007 -0800) 6 commits - Teach "git-merge-base --check-ancestry" about refs. - git-merge-base: --check-ancestry option + in_merge_bases(): optimization + merge_base(): move traversal into a separate function. + Allow in_merge_bases() to take more than one reference commits. + Make merge-base a built-in. * jc/diff (Mon Dec 25 01:08:50 2006 -0800) 2 commits - test-para: combined diff between HEAD, index and working tree. - para-walk: walk n trees, index and working tree in parallel * jc/explain (Mon Dec 4 19:35:04 2006 -0800) 1 commit - git-explain * jc/3way (Wed Nov 29 18:53:13 2006 -0800) 1 commit + git-merge: preserve and merge local changes when doing fast forward * jc/web (Wed Nov 8 14:54:09 2006 -0800) 1 commit - gitweb: steal loadavg throttle from kernel.org * jc/pickaxe (Sun Nov 5 11:52:43 2006 -0800) 1 commit - blame: --show-stats for easier optimization work. * jc/diff-apply-patch (Fri Sep 22 16:17:58 2006 -0700) 1 commit + git-diff/git-apply: make diff output a bit friendlier to GNU patch (part 2) These are on-hold. ``` ## Nicolas Pitre, 2007-01-11 03:50 Subject: Re: What's cooking in git.git (topics) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0701102241230.4964%40xanadu.home In-Reply-To: <7v3b6i75i5.fsf@assigned-by-dhcp.cox.net> ``` On Wed, 10 Jan 2007, Junio C Hamano wrote: > * jc/detached-head (Tue Jan 9 20:39:09 2007 -0800) 9 commits I want to say that this is really great and well done. > * sp/describe (Wed Jan 10 06:39:47 2007 -0500) 1 commit > - Chose better tag names in git-describe after merges. > > Slowing it down by 4x is very unfortunate. I think there is a > better way to walk the ancestry than doing one at a time to > count the commits, but I did not have enough time to look at > this today. However git-describe is certainly not a frequent and speed critical operation, and even if it cannot be sped up then waiting 300 ms more won't really affect one's workflow that badly. Nicolas ``` ## Shawn O. Pearce, 2007-01-11 08:00 Subject: Re: What's cooking in git.git (topics) Message-ID: <20070111080035.GA28222@spearce.org> URL: https://gitlist.dev/e/20070111080035.GA28222%40spearce.org In-Reply-To: ``` Nicolas Pitre wrote: > On Wed, 10 Jan 2007, Junio C Hamano wrote: > > * sp/describe (Wed Jan 10 06:39:47 2007 -0500) 1 commit > > - Chose better tag names in git-describe after merges. > > > > Slowing it down by 4x is very unfortunate. I think there is a > > better way to walk the ancestry than doing one at a time to > > count the commits, but I did not have enough time to look at > > this today. > > However git-describe is certainly not a frequent and speed critical > operation, and > even if it cannot be sped up then waiting 300 ms more won't really > affect one's workflow that badly. My thoughts exactly. I spent a few hours trying to determine an algorithm that produced the right answer and did not require generating the revlist between the tag and the requested commit for every possibly matching tag. I did not come up with one. If someone else does it would obviously be a welcome replacement to my own patch. :-) There is almost no additional penalty for a simple strand of pearls with the tag placed along that strand; only one possible tag will be found. But my code does an unnecessary revision list in this case. Where we really get hit is the large number of possible tags. The master branch is turning up 14 tags, some dating back to v1.4.1-rc1. I do try to abort the revision list as soon as one of those tags cannot give me a better selection than the one I have currently, but I still had to generate a revision list to reach that point. -- Shawn. ``` ## Johannes Schindelin, 2007-01-11 08:53 Subject: Re: What's cooking in git.git (topics) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0701110949421.22628%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <7v3b6i75i5.fsf@assigned-by-dhcp.cox.net> ``` Hi, On Wed, 10 Jan 2007, Junio C Hamano wrote: > * ar/merge-recursive (Wed Jan 10 11:20:58 2007 -0800) 2 commits > + merge-recursive: do not use on-file index when not needed. > + Speed-up recursive by flushing index only once for all entries > > I did not see much improvement (maybe a largish kernel merge > going from 2.5 seconds to slightly less than one second) That is a heck of an improvement. It is only uses 40% of the time it used before! On other machines, with other OSes, this makes the difference between 10 minutes and 4 minutes. BTW I am not quite sure if you missed this patch: http://thread.gmane.org/gmane.comp.version-control.git/36212/, or if you did not like it, want enhancements, ... Ciao, Dscho ``` ## Andreas Ericsson, 2007-01-11 09:20 Subject: Re: What's cooking in git.git (topics) Message-ID: <45A6016B.4030800@op5.se> URL: https://gitlist.dev/e/45A6016B.4030800%40op5.se In-Reply-To: <20070111080035.GA28222@spearce.org> ``` Shawn O. Pearce wrote: > Nicolas Pitre wrote: >> On Wed, 10 Jan 2007, Junio C Hamano wrote: >>> * sp/describe (Wed Jan 10 06:39:47 2007 -0500) 1 commit >>> - Chose better tag names in git-describe after merges. >>> >>> Slowing it down by 4x is very unfortunate. I think there is a >>> better way to walk the ancestry than doing one at a time to >>> count the commits, but I did not have enough time to look at >>> this today. >> However git-describe is certainly not a frequent and speed critical >> operation, and >> even if it cannot be sped up then waiting 300 ms more won't really >> affect one's workflow that badly. > > My thoughts exactly. I spent a few hours trying to determine > an algorithm that produced the right answer and did not require > generating the revlist between the tag and the requested commit > for every possibly matching tag. I did not come up with one. > If someone else does it would obviously be a welcome replacement > to my own patch. :-) > > There is almost no additional penalty for a simple strand of pearls > with the tag placed along that strand; only one possible tag will be > found. But my code does an unnecessary revision list in this case. > > Where we really get hit is the large number of possible tags. The > master branch is turning up 14 tags, some dating back to v1.4.1-rc1. > I do try to abort the revision list as soon as one of those tags > cannot give me a better selection than the one I have currently, > but I still had to generate a revision list to reach that point. > It could be worth skipping tags more than 6 months older than current branch-head. That would, at least for the git case, cut the number of tags down by a considerable amount. -- Andreas Ericsson andreas.ericsson@op5.se OP5 AB www.op5.se Tel: +46 8-230225 Fax: +46 8-230231 ``` ## Junio C Hamano, 2007-01-11 09:38 Subject: Re: What's cooking in git.git (topics) Message-ID: <7v1wm16gyd.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7v1wm16gyd.fsf%40assigned-by-dhcp.cox.net In-Reply-To: <20070111080035.GA28222@spearce.org> ``` "Shawn O. Pearce" writes: > There is almost no additional penalty for a simple strand of pearls > with the tag placed along that strand; only one possible tag will be > found. But my code does an unnecessary revision list in this case. > > Where we really get hit is the large number of possible tags. The > master branch is turning up 14 tags, some dating back to v1.4.1-rc1. > I do try to abort the revision list as soon as one of those tags > cannot give me a better selection than the one I have currently, > but I still had to generate a revision list to reach that point. I looked at the algorithm, and after scratching my head for a while, I finally found it sane (modulo leaks, which I think I fixed with the attached patch). One minor problem that you inherited from the original algorithm is the name priority. If you have an annotated tag A and a lightweight tag b, and ask "git describe --tags" in this graph: ---o---o---o---o---x A b you would still want to describe 'x' with A, not b. Unfortunately you don't (and the original doesn't either). I think this is probably easy to solve in the loop that finds "all_matches"; once you hit an annotated tag, your traversal should stop in any case. But if you were asked for --tags, and if your "initialized" piece did find both lightweight and annotated tags, you do not stop when you saw a lightweight one, but keep looking for an annotated one, ignoring any further lightweight ones. Another thought. I often do "git describe maint master next pu", and I see an opportunity for optimizing for such a multi-ref query. Once you traversed the commits in "all_matches" loop, you know which strands of pearls are reachable to what tags, so you could hang that information somewhere (perhaps ->utils) in each commit. But I think optimizing for a multi-ref query is probably not worth it. -- >8 -- [PATCH] plug a few leaks in revision walking used in describe. Signed-off-by: Junio C Hamano --- builtin-describe.c | 1 + revision.c | 8 +++++--- 2 files changed, 6 insertions(+), 3 deletions(-) diff --git a/builtin-describe.c b/builtin-describe.c index d65c7d2..a8c98ce 100644 --- a/builtin-describe.c +++ b/builtin-describe.c @@ -183,6 +183,7 @@ static void describe(const char *arg, int last_one) cur_match->depth++; if (!min_match || cur_match->depth < min_match->depth) min_match = cur_match; + free_commit_list(revs.commits); } printf("%s-g%s\n", min_match->name->path, find_unique_abbrev(cmit->object.sha1, abbrev)); diff --git a/revision.c b/revision.c index 1e3b29a..f2ddd95 100644 --- a/revision.c +++ b/revision.c @@ -1121,21 +1121,23 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch void prepare_revision_walk(struct rev_info *revs) { int nr = revs->pending.nr; - struct object_array_entry *list = revs->pending.objects; + struct object_array_entry *e, *list; + e = list = revs->pending.objects; revs->pending.nr = 0; revs->pending.alloc = 0; revs->pending.objects = NULL; while (--nr >= 0) { - struct commit *commit = handle_commit(revs, list->item, list->name); + struct commit *commit = handle_commit(revs, e->item, e->name); if (commit) { if (!(commit->object.flags & SEEN)) { commit->object.flags |= SEEN; insert_by_date(commit, &revs->commits); } } - list++; + e++; } + free(list); if (revs->no_walk) return; ``` ## Junio C Hamano, 2007-01-11 09:47 Subject: Re: What's cooking in git.git (topics) Message-ID: <7vsleh51zx.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vsleh51zx.fsf%40assigned-by-dhcp.cox.net In-Reply-To: ``` Johannes Schindelin writes: > BTW I am not quite sure if you missed this patch: > http://thread.gmane.org/gmane.comp.version-control.git/36212/, or if you > did not like it, want enhancements, ... It is still sitting in my in-box; I tend to agree with Shawn in that mixing the reflog sequence and true parenthood in the same traversal is kind of insane. I vaguely recall you thought dropping that would make the code simpler, and was kind of waiting for that to happen to review the results. Also I did not quite understand your comment about circular log entries. When you walk the reflog, the entries are by definition a single strand of pearls (reflog itself is a flat text file which you read linearly). The commits adjacent entries talk about may or may not be related at all, and two entries may happen to point at the same commit. But I do not think the appearance of another reflog entry in an earlier call to get_revision() should not cause a reflog entry to be dropped from the output only because it points at the same commit. ``` ## Johannes Schindelin, 2007-01-11 10:04 Subject: Re: What's cooking in git.git (topics) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.63.0701111103140.22628%40wbgn013.biozentrum.uni-wuerzburg.de In-Reply-To: <7vsleh51zx.fsf@assigned-by-dhcp.cox.net> ``` Hi, On Thu, 11 Jan 2007, Junio C Hamano wrote: > Johannes Schindelin writes: > > > BTW I am not quite sure if you missed this patch: > > http://thread.gmane.org/gmane.comp.version-control.git/36212/, or if you > > did not like it, want enhancements, ... > > It is still sitting in my in-box; I tend to agree with Shawn in > that mixing the reflog sequence and true parenthood in the same > traversal is kind of insane. Okay. > I vaguely recall you thought dropping that would make the code simpler, > and was kind of waiting for that to happen to review the results. I was kind of waiting if somebody actually cares. > Also I did not quite understand your comment about circular log > entries. But you did! My comment was only that I did not test if it actually works as expected. Ciao, Dscho ``` ## Shawn O. Pearce, 2007-01-11 10:08 Subject: Re: What's cooking in git.git (topics) Message-ID: <20070111100800.GB28309@spearce.org> URL: https://gitlist.dev/e/20070111100800.GB28309%40spearce.org In-Reply-To: <7v1wm16gyd.fsf@assigned-by-dhcp.cox.net> ``` Junio C Hamano wrote: > I looked at the algorithm, and after scratching my head for a > while, I finally found it sane (modulo leaks, which I think I > fixed with the attached patch). Thanks. I don't think it says much for the quality of my code if you had to scratch your head before you understood it. But at least you finally got it. :) > One minor problem that you inherited from the original algorithm > is the name priority. If you have an annotated tag A and a > lightweight tag b, and ask "git describe --tags" in this graph: > > ---o---o---o---o---x > A b > > you would still want to describe 'x' with A, not b. > Unfortunately you don't (and the original doesn't either). Actually I think you want to describe it with b. If you ask '--tags' then you want the lightweight ones too. In the case above the lightweight tag b better describes x as it has more in common with x than A has. > I think this is probably easy to solve in the loop that finds > "all_matches"; once you hit an annotated tag, your traversal > should stop in any case. But if you were asked for --tags, and > if your "initialized" piece did find both lightweight and > annotated tags, you do not stop when you saw a lightweight one, > but keep looking for an annotated one, ignoring any further > lightweight ones. I just implemented this in that loop, and then realized what I wrote above. The lower loop that performs the revision list traversal would have both A and b in all_matches and b would win, as its closer to x. So having the first loop abort when it does is the right thing to do, and so is describing x with b. > Another thought. I often do "git describe maint master next > pu", and I see an opportunity for optimizing for such a > multi-ref query. Once you traversed the commits in > "all_matches" loop, you know which strands of pearls are > reachable to what tags, so you could hang that information > somewhere (perhaps ->utils) in each commit. But I think > optimizing for a multi-ref query is probably not worth it. Without my patch its ~170ms; with my patch its ~1000ms. That is a huge difference for such a simple program. I'm not sure your optimization will make a big difference. The bulk of the cost appears to be in the later loop, not in the earlier one that produces all_matches. -- Shawn. ``` ## Nicolas Pitre, 2007-01-11 14:59 Subject: Re: What's cooking in git.git (topics) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0701110955100.4964%40xanadu.home In-Reply-To: <45A6016B.4030800@op5.se> ``` On Thu, 11 Jan 2007, Andreas Ericsson wrote: > Shawn O. Pearce wrote: > > Where we really get hit is the large number of possible tags. The > > master branch is turning up 14 tags, some dating back to v1.4.1-rc1. > > I do try to abort the revision list as soon as one of those tags > > cannot give me a better selection than the one I have currently, > > but I still had to generate a revision list to reach that point. > > > > It could be worth skipping tags more than 6 months older than current > branch-head. That would, at least for the git case, cut the number of tags > down by a considerable amount. This is bound to be wrong in some cases if a project is very active with many tags, or if there was a long period of inactivity. And what would be the benefit? Saving 250ms on git-describe output latency? Nicolas ``` ## Andreas Ericsson, 2007-01-11 16:00 Subject: Re: What's cooking in git.git (topics) Message-ID: <45A65F15.6040606@op5.se> URL: https://gitlist.dev/e/45A65F15.6040606%40op5.se In-Reply-To: ``` Nicolas Pitre wrote: > On Thu, 11 Jan 2007, Andreas Ericsson wrote: > >> Shawn O. Pearce wrote: >>> Where we really get hit is the large number of possible tags. The >>> master branch is turning up 14 tags, some dating back to v1.4.1-rc1. >>> I do try to abort the revision list as soon as one of those tags >>> cannot give me a better selection than the one I have currently, >>> but I still had to generate a revision list to reach that point. >>> >> It could be worth skipping tags more than 6 months older than current >> branch-head. That would, at least for the git case, cut the number of tags >> down by a considerable amount. > > This is bound to be wrong in some cases if a project is very active with > many tags, or if there was a long period of inactivity. And what would > be the benefit? Saving 250ms on git-describe output latency? > Output latency will grow with number of tags though, won't it? I was thinking of the repo which users had reported problems fetching tags from, as there was more than 2k tags. If my memory serves me correctly, this report led to the packed-refs stuff. Unless there's some bogosity going on that leads to it finding the 14 tags in the above case. -- Andreas Ericsson andreas.ericsson@op5.se OP5 AB www.op5.se Tel: +46 8-230225 Fax: +46 8-230231 ``` ## Junio C Hamano, 2007-01-11 23:55 Subject: Re: What's cooking in git.git (topics) Message-ID: <7v64bd15lg.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7v64bd15lg.fsf%40assigned-by-dhcp.cox.net In-Reply-To: <20070111100800.GB28309@spearce.org> ``` "Shawn O. Pearce" writes: >> One minor problem that you inherited from the original algorithm >> is the name priority. If you have an annotated tag A and a >> lightweight tag b, and ask "git describe --tags" in this graph: >> >> ---o---o---o---o---x >> A b >> >> you would still want to describe 'x' with A, not b. >> Unfortunately you don't (and the original doesn't either). > > Actually I think you want to describe it with b. If you ask > '--tags' then you want the lightweight ones too. In the case above > the lightweight tag b better describes x as it has more in common > with x than A has. The reason why I would run the command with --tags is to cope with this kind of graph. o---o---o---x / ---o---o---o---o---o---y b A in order to use lightweight ones as a back-up. Otherwise we would not have had the "prio" business there. And I would prefer if the presense of lightweight 'c' tag did not change how 'y' is described: o---o---o---x / ---o---o---o---o---o---y b A c ``` ## Shawn O. Pearce, 2007-01-12 00:49 Subject: Re: What's cooking in git.git (topics) Message-ID: <20070112004927.GB23864@spearce.org> URL: https://gitlist.dev/e/20070112004927.GB23864%40spearce.org In-Reply-To: <45A65F15.6040606@op5.se> ``` Andreas Ericsson wrote: > Output latency will grow with number of tags though, won't it? I was > thinking of the repo which users had reported problems fetching tags > from, as there was more than 2k tags. If my memory serves me correctly, > this report led to the packed-refs stuff. Only on tags which are considered possible matches. What we do now is we walk back along the commit history until we find a commit which has a tag pointing at it. As soon as we find that commit we enqueue its corresponding tag into a list and completely ignore its parents, aborting listing any further back. So we really only pay the bare minimum price here. Unfortunately the tag matching is O(n*m*q) where: n == number of tags, m == number of commits we have to walk back before we find a tag, q == number of possible tags that will match for this lineage. Storing the tags in a hash structure would accelerate this matching, especially for high values of n. m and q we cannot do anything about, except to recommend to projects that they tag more than often then never. > Unless there's some bogosity going on that leads to it finding the 14 > tags in the above case. Yea, its a bogosity in the way the branches are merged together. I haven't dug into what is causing this specifically in git.git but I know the code is doing the best it can to select the smallest set of possible matches. There is however a better algorithm for the revision list generation; I think I can fold it into the main walkback loop and still get the right result. I have to read a stack of papers tonight but I'll see if I can try to code up the algorithm. It would accelerate git-describe right back to where it was before my change. -- Shawn. ``` ## Shawn O. Pearce, 2007-01-12 01:01 Subject: Re: What's cooking in git.git (topics) Message-ID: <20070112010126.GF23864@spearce.org> URL: https://gitlist.dev/e/20070112010126.GF23864%40spearce.org In-Reply-To: <7v64bd15lg.fsf@assigned-by-dhcp.cox.net> ``` Junio C Hamano wrote: > The reason why I would run the command with --tags is to cope > with this kind of graph. > > o---o---o---x > / > ---o---o---o---o---o---y > b A Why isn't that the default? > in order to use lightweight ones as a back-up. Otherwise we > would not have had the "prio" business there. > > And I would prefer if the presense of lightweight 'c' tag did > not change how 'y' is described: > > > o---o---o---x > / > ---o---o---o---o---o---y > b A c If we just make '--tags' the default and fix the priority to always pick an annotated tag over a lightweight one then things make sense. We'd automatically pickup b above for x but always A for y. -- Shawn. ``` ## Junio C Hamano, 2007-01-12 06:15 Subject: Re: What's cooking in git.git (topics) Message-ID: <7vr6u0wz2s.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vr6u0wz2s.fsf%40assigned-by-dhcp.cox.net In-Reply-To: <20070112004927.GB23864@spearce.org> ``` "Shawn O. Pearce" writes: > Only on tags which are considered possible matches. What we do > now is we walk back along the commit history until we find a commit > which has a tag pointing at it. As soon as we find that commit we > enqueue its corresponding tag into a list and completely ignore its > parents, aborting listing any further back. So we really only pay > the bare minimum price here. This actually is QUITE bad. With the tip of linux-2.6 repository, v1.4.4 series takes 0.03s while v1.5.0-rc1 takes about 3.6s. That is 100x fold, not just 4x. It turns out that to describe 0404f87f (tip of linux-2.6) the new one picks up 61 tags in the posible-tag loop. Since this loop uses the usual date-order, we can limit the number of candidate tags without losing too much precision. When limiting the candidates to only 6 (attached patch), the time drops to 0.25s. --- diff --git a/builtin-describe.c b/builtin-describe.c index a8c98ce..a1ecec2 100644 --- a/builtin-describe.c +++ b/builtin-describe.c @@ -12,6 +12,7 @@ static const char describe_usage[] = static int all; /* Default to annotated tags only */ static int tags; /* But allow any tags if --tags is specified */ +static int debug; static int abbrev = DEFAULT_ABBREV; @@ -113,6 +114,7 @@ static void describe(const char *arg, int last_one) static int initialized = 0; struct commit_name *n; struct possible_tag *all_matches, *min_match, *cur_match; + int cnt; if (get_sha1(arg, sha1)) die("Not a valid object name %s", arg); @@ -136,6 +138,7 @@ static void describe(const char *arg, int last_one) all_matches = NULL; cur_match = NULL; commit_list_insert(cmit, &list); + cnt = 6; while (list) { struct commit *c = pop_commit(&list); n = match(c); @@ -148,6 +151,8 @@ static void describe(const char *arg, int last_one) else all_matches = p; cur_match = p; + if (--cnt <= 0) + break; } else { struct commit_list *parents = c->parents; while (parents) { @@ -161,6 +166,18 @@ static void describe(const char *arg, int last_one) } } } + if (list) + free_commit_list(list); + + if (debug) { + int cnt = 0; + for (cur_match = all_matches; + cur_match; + cur_match = cur_match->next) + cnt++; + fprintf(stderr, "%d candidates for %s\n", cnt, + sha1_to_hex(cmit->object.sha1)); + } if (!all_matches) die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1)); @@ -210,6 +227,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix) all = 1; else if (!strcmp(arg, "--tags")) tags = 1; + else if (!strcmp(arg, "--debug")) + debug = 1; else if (!strncmp(arg, "--abbrev=", 9)) { abbrev = strtoul(arg + 9, NULL, 10); if (abbrev < MINIMUM_ABBREV || 40 < abbrev) ``` ## Shawn O. Pearce, 2007-01-12 06:26 Subject: Re: What's cooking in git.git (topics) Message-ID: <20070112062644.GC24195@spearce.org> URL: https://gitlist.dev/e/20070112062644.GC24195%40spearce.org In-Reply-To: <7vr6u0wz2s.fsf@assigned-by-dhcp.cox.net> ``` Junio C Hamano wrote: > With the tip of linux-2.6 repository, v1.4.4 series takes 0.03s > while v1.5.0-rc1 takes about 3.6s. That is 100x fold, not just > 4x. > > It turns out that to describe 0404f87f (tip of linux-2.6) the > new one picks up 61 tags in the posible-tag loop. > > Since this loop uses the usual date-order, we can limit the > number of candidate tags without losing too much precision. > When limiting the candidates to only 6 (attached patch), the > time drops to 0.25s. OK. Apply your patch to master. 3.6s is insane, even for git-describe. I think your guess of 6 is reasonable, but I'd obviously like to remove the need for it entirely. I think I have a sketch in my head for an algorithm that can compute the revision counts while in the possible-tag loop, which would completely remove the huge cost of the per-tag revision list later on. I can't work on it right now (need to get other stuff done before 1 pm Friday) but I will try to code and test it tomorrow afternoon. If I'm right I'll send a patch. -- Shawn. ``` ## Jakub Narebski, 2007-01-12 18:16 Subject: Re: What's cooking in git.git (topics) Message-ID: URL: https://gitlist.dev/e/eo8j8o%24ahq%241%40sea.gmane.org In-Reply-To: <20070111100800.GB28309@spearce.org> ``` Shawn O. Pearce wrote: >> One minor problem that you inherited from the original algorithm >> is the name priority.  If you have an annotated tag A and a >> lightweight tag b, and ask "git describe --tags" in this graph: >> >>     ---o---o---o---o---x >>            A   b >> >> you would still want to describe 'x' with A, not b. >> Unfortunately you don't (and the original doesn't either). > > Actually I think you want to describe it with b.  If you ask > '--tags' then you want the lightweight ones too.  In the case above > the lightweight tag b better describes x as it has more in common > with x than A has. Actually I very often want to describe with _annotated_ tags only. I have few lightweight tags which are former heads (former branches), few lightweight tags which are branch points or before-merge points, and are _not_ version tags. Although perhaps command line switch (to prefer annotated tags to lightweight tags) would be better... -- Jakub Narebski Warsaw, Poland ShadeHawk on #git ```