From: Junio C Hamano <hidden> Date: 2016-06-15 22:42:11
Linus Torvalds [off-list ref] writes:
It does:
struct commit *commit = pop_one_commit(list_p);
int still_interesting = !!interesting(*list_p);
in that order: it looks whether there are any interesting commits left
_after_ it has popped the top-of-stack.
Ahhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh. You are right.
The problem is most of the time hidden, because we usually do
one extra round (extra usually starts from 0 and we break out
after we say "not interesting anymore" and extra < 0).
Obviously, I was not thinking clearly.
From: Junio C Hamano <hidden> Date: 2016-06-15 22:42:11
Junio C Hamano [off-list ref] writes:
Linus Torvalds [off-list ref] writes:
quoted
It does:
struct commit *commit = pop_one_commit(list_p);
int still_interesting = !!interesting(*list_p);
in that order: it looks whether there are any interesting commits left
_after_ it has popped the top-of-stack.
The problem is most of the time hidden,...
As you pointed out, still_interesting means "after we are done
with this commit, do we still have something interesting to be
processed?", and the later "extra < 0" check compensates for
this. After I pop the last interesting commit, I still look at
its parents and push them back into the list.
It seems to be doing the right thing after all. I hate to admit
it, but I have been having hard time figuring out how this thing
works X-<. In the meantime, I've checked commits from linux-2.6
history that have more than one merge-base candidates.
"git-merge-base --all" and "git-show-branch --merge-base" give
the same answer to all of them [*1*].
I do not think "git-show-branch --merge-base" can be any more
efficient than "git-merge-base --all". It does _more_ things
(probably unnecessary things as well). Pasky's number could be
just an artifact of hot/cold cache difference.
[Footnote]
*1* Here are the commits I used from linux-2.6 repository that
have more than one commits:
ba9b543d5bec0a7605952e2ba501fb8b0f3b6407
84ffa747520edd4556b136bdfc9df9eb1673ce12
da28c12089dfcfb8695b6b555cdb8e03dda2b690
3190186362466658f01b2e354e639378ce07e1a9
0c168775709faa74c1b87f1e61046e0c51ade7f3
0e396ee43e445cb7c215a98da4e76d0ce354d9d7
467ca22d3371f132ee225a5591a1ed0cd518cb3d
From: Petr Baudis <hidden> Date: 2016-06-15 22:42:11
Dear diary, on Wed, Nov 09, 2005 at 11:20:22AM CET, I got a letter
where Junio C Hamano [off-list ref] said that...
I do not think "git-show-branch --merge-base" can be any more
efficient than "git-merge-base --all". It does _more_ things
(probably unnecessary things as well). Pasky's number could be
just an artifact of hot/cold cache difference.
Certainly not that. But I've fetched in the meantime and now show-branch
takes much longer - median 0.078s (git-merge-base's median still stays
around 0.128s). So possibly git-show-branch did some smart optimization
right away in the previous case. I can try to track down the particular
commits if there's any interest.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
VI has two modes: the one in which it beeps and the one in which
it doesn't.
As you pointed out, still_interesting means "after we are done
with this commit, do we still have something interesting to be
processed?", and the later "extra < 0" check compensates for
this. After I pop the last interesting commit, I still look at
its parents and push them back into the list.
That "extra" check only helps once. If we ever hit the "extra--", it's
gone.
In other words, follow this:
- we start out with "extra = 0" (default value)
- we've got one "interesting" commit left, and we just popped it.
- we now have "still_interesting = 0"
- the commit has just one parent, and it's not something we've seen
before, so we add it to the seen list and decrement "extra", which is
now -1. We then insert it back to the list.
- we go back up, pop the thing we just got, and now there are again no
interesting commits on the list any more, so "still_interesting = 0".
- now "extra" is -1, and we break out of the loop without ever
percolating the flags of this commit to its parents.
No?
It seems to be doing the right thing after all. I hate to admit it, but
I have been having hard time figuring out how this thing works X-<. In
the meantime, I've checked commits from linux-2.6 history that have more
than one merge-base candidates.
I'm not very impressed by "it works for the seven cases I tried".
It's entirely possible that there _is_ some reason it always works, but if
so, I'd like to understand it. More likely, it works in _practice_ because
the only way to trigger anything else is likely such a perverse commit
history that you'd never see it, but hey..
Also, I don't think this has necessarily anything to do with "multiple
merge bases". As far as I can tell, we can find a potential "merge base"
that starts the culling of uniniteresting things, but some other branch
(that we haven't followed yet - perhaps the one we just broke out of
early) may end up causing an _earlier_ commit to turn out to also be a
merge-base, and the merge-base we found originally turns out to be a
parent of the new one, and thus totally uninteresting.
See what I'm saying? Even with just _one_ well-defined merge base, we
might hit it.
It so happens that because we traverse the commit history in date order,
we almost never (but the keyword here is _almost_) hit the case where a
child of a commit ends up being parsed _after_ the commit that is its
parent. That only happens when there are non-synchronized clocks etc, and
there are very few cases of that in the kernel tree.
Just to see how rare that is, do this:
git-rev-list --pretty=raw HEAD |
grep '^committer' |
cut -d'>' -f2 |
cut -d' ' -f2 > date-list
which basically generates the list of dates of commits in the kernel tree,
sorted in the natural order that we always traverse the commits in.
Now, do
sort -nr date-list | diff -u date-list -
to see how often the dates are off. I'm seeing only _three_ commits that
have time-warps (ie they were "earlier" than one of their parents). Out of
13,000+.
So walking things in date order _almost_ always does the right thing just
by mistake (well, it's not "mistake", of course. It's by design: it's the
closest we can get to a nice balanced walk. But the point is that it's
still just a heuristic, not something we can absolutely depend on).
And THAT was the reason for the problem with the original git-merge-base
algorithm. Not multiple merge-bases (which was admittedly another
problem), but the fact that it didn't give the right merge-base at all due
to time warps.
(Again - it may be that there's something in show-branch that makes the
optimization valid, but I just don't understand it).
Linus
From: Junio C Hamano <hidden> Date: 2016-06-15 22:42:11
Linus Torvalds [off-list ref] writes:
That "extra" check only helps once. If we ever hit the "extra--", it's
gone.
I think you are right here, but while digging into this I found
an interesting case.
The current show-branch code does the same as merge-base in the
pathological example depicted in merge-base.c, but they seem to
do different things to this picture (commit grows from bottom to
top, time flows alphabetically; find base between G and H).
H
/ \
G A \
|\ / \
| B \
| \ \
\ C F
\ \ /
\ D /
\ | /
\| /
E
"git-merge-base --all" says the merge bases are B and E, while
"show-branch --merge-base" mentions only B. In this case the
latter is probably the better answer. Actually git-merge-base
without --all only mentions E. This is because we give up when
we find the list elements are all uninteresting. And this is
very expensive to fix (I recall mentioning "horizon effect" last
time we worked on this --- around August 12th).
G gets bit 1 and H gets bit 2. Here is what happens in each
iteration:
List A B C D E F G H Result
G1 H2 - - - - - - 1 2
H2 E1 B1 - 1 - - 1 - 1 2
F2 E1 B1 A2 2 1 - - 1 2 1 2
E3 B1 A2 2 1 - - 3 2 1 2 E3
B1 A2 2 1 - - 3 2 1 2 E3
C1 A2 2 1 1 - 3 2 1 2 E3
D1 A2 2 1 1 1 3 2 1 2 E3
A2 2 1 1 1 3 2 1 2 E3
B3 2 3 1 1 3 2 1 2 E3 B3
C7 2 3 7 1 3 2 1 2 E3 B3
We popped B with flag 3, and started contaminating the well by
reinjecting its parent C with flag 7. That is all good, but
"while (interesting(list))" check stops us from going further.
Ideally the following two steps would have found out that E is
also uninteresting.
D7 2 3 7 7 3 2 1 2
E7 2 3 7 7 7 2 1 2
But that is expensive -- we would not know when to stop.
A reproduction recipe is attached here, primarily so I do not
have to worry about losing it from /var/tmp/.
-- >8 -- cut here -- >8 --
#!/bin/sh
rm -fr .git && git-init-db
T=$(git-write-tree)
M=1130000000
Z=+0000
export GIT_COMMITTER_EMAIL=git@comm.iter.xz
export GIT_COMMITTER_NAME='C O Mmiter'
export GIT_AUTHOR_NAME='A U Thor'
export GIT_AUTHOR_EMAIL=git@au.thor.xz
doit() {
OFFSET=$1; shift
NAME=$1; shift
PARENTS=
for P
do
PARENTS="${PARENTS}-p $P "
done
GIT_COMMITTER_DATE="$(($M + $OFFSET)) $Z"
GIT_AUTHOR_DATE=$GIT_COMMITTER_DATE
export GIT_COMMITTER_DATE GIT_AUTHOR_DATE
commit=$(echo $NAME | git-commit-tree $T $PARENTS)
echo $commit >.git/refs/tags/$NAME
echo $commit
}
checkit() {
echo MB
git-merge-base --all "$@" | xargs git-name-rev
echo SB
git-show-branch --merge-base "$@" | xargs git-name-rev
git-show-branch --sha1-name --more=99 "$@"
}
E=$(doit 5 E)
D=$(doit 4 D $E)
F=$(doit 6 F $E)
C=$(doit 3 C $D)
B=$(doit 2 B $C)
A=$(doit 1 A $B)
G=$(doit 7 G $B $E)
H=$(doit 8 H $A $F)
checkit $G $H
exit
The current show-branch code does the same as merge-base in the
pathological example depicted in merge-base.c, but they seem to
do different things to this picture (commit grows from bottom to
top, time flows alphabetically; find base between G and H).
H
/ \
G A \
|\ / \
| B \
| \ \
\ C F
\ \ /
\ D /
\ | /
\| /
E
"git-merge-base --all" says the merge bases are B and E, while
"show-branch --merge-base" mentions only B. In this case the
latter is probably the better answer.
I don't agree.
Sure, B _may_ be the right answer for a particular merge strategt, but
there's no way of knowing. Maybe all the big changes came in through F,
and H is the merge that sorted that out, and E actually ends up being the
better base.
So I think from a correctness standpoint, the only thing that matters is
"git-merge-base --all", and anything that doesn't know to return both E
and B looks potentially buggy.
Actually git-merge-base without --all only mentions E.
Well, we should really consider anything that doesn't take them all into
account to be a bug waiting to happen (or rather, a merge waiting for a
disaster), but E is the right one, since it's the more recent one).
Now, this case obviously depends on history being almost maximally insane
(ie pretty much _all_ the dates are wrong). So in practice we probably
don't care.
So maybe "git-show-branch --merge-base" ends up acceptable as a faster way
to do the quick "let's see if we can find _some_ merge-base to do the
in-index merge with", but personally I'd much rather always do a
"git-merge-base --all", and only do the fast index merge if we only have
one potential parent.
That way there would never any question about what the "quick merge" does.
Linus