What's cooking in git.git (topics)

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)

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.

On Wed, 10 Jan 2007, Junio C Hamano wrote:

I want to say that this is really great and well done.

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

Nicolas Pitre <nico@cam.org> wrote:

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 O. Pearce wrote:

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.

On Thu, 11 Jan 2007, Andreas Ericsson wrote:

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

Nicolas Pitre 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.

Unless there's some bogosity going on that leads to it finding the 14 tags in the above case.

Andreas Ericsson <ae@op5.se> wrote:

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.

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 O. Pearce" <spearce@spearce.org> writes:

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.

--- 

Junio C Hamano <junkio@cox.net> wrote:

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 O. Pearce" <spearce@spearce.org> writes:

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 <junkio@cox.net>
---
 builtin-describe.c |    1 +
 revision.c         |    8 +++++---
 2 files changed, 6 insertions(+), 3 deletions(-)

Junio C Hamano <junkio@cox.net> wrote:

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.  :)
 

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 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.

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 O. Pearce" <spearce@spearce.org> writes:

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

Junio C Hamano <junkio@cox.net> wrote:

Why isn't that the default?
 

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 O. Pearce wrote:

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...

Hi,

On Wed, 10 Jan 2007, Junio C Hamano wrote:

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

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

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.

Hi,

On Thu, 11 Jan 2007, Junio C Hamano wrote:

Okay.

I was kind of waiting if somebody actually cares.

But you did! My comment was only that I did not test if it actually works as expected.

Ciao, Dscho