@@ -466,6 +466,19 @@ esac require_clean_work_tree"rebase""Please commit or stash them."+test-n"$upstream_name"&&forreflogin\+$(gitrev-list-g$upstream_name2>/dev/null)
Ugly.
test -n "$upstream_name" &&
for reflog in $(git rev-list ...)
do
...
done
Don't you need to make sure $upstream_name is a branch (or a ref in
general that can have a reflog), or does it not matter because the
"rev-list -g" will die without producing anything and you are discarding
the error message?
Now, a handful of random questions, none of them rhetorical, as I don't
know the answers to any of them.
Would it help if the code is made just as clever as the patch attempts to
be, when the user says
git rebase origin/next~4
IOW, use the reflog of origin/next even in such a case?
+do
+ if test $reflog = $(git merge-base $reflog $orig_head)
+ then
+ if test $reflog != $(git merge-base $onto $reflog)
+ then
+ upstream=$reflog
+ fi
+ break
+ fi
Do we always traverse down to the beginning of the reflog in the worst
case? Would bisection help to avoid the cost?
@@ -466,6 +466,19 @@ esac require_clean_work_tree"rebase""Please commit or stash them."+test-n"$upstream_name"&&forreflogin\+$(gitrev-list-g$upstream_name2>/dev/null)
Ugly.
Very. Fixed. Thanks.
test -n "$upstream_name" &&
for reflog in $(git rev-list ...)
do
...
done
Don't you need to make sure $upstream_name is a branch (or a ref in
general that can have a reflog), or does it not matter because the
"rev-list -g" will die without producing anything and you are discarding
the error message?
Exactly as you suspect. Is it too ugly?
Now, a handful of random questions, none of them rhetorical, as I don't
know the answers to any of them.
Would it help if the code is made just as clever as the patch attempts to
be, when the user says
git rebase origin/next~4
IOW, use the reflog of origin/next even in such a case?
Not sure. I think it seems too rare to worry about. In those cases,
one could still use the good old '--onto' option manually. Also, if we
don't handle the ref~4 case, the "cleverness" can be disabled by using
ref~0.
quoted
+do
+ if test $reflog = $(git merge-base $reflog $orig_head)
+ then
+ if test $reflog != $(git merge-base $onto $reflog)
+ then
+ upstream=$reflog
+ fi
+ break
+ fi
Do we always traverse down to the beginning of the reflog in the worst
case?
Yes.
Would bisection help to avoid the cost?
I don't think the straight-forward use of bisection would work. If the
history looks something like below, where 'b' is the branch to rebase
and 'u' is the upstream, we have to go through each entry in the
reflog to find u@{3}.
.-u@{0}
/
.---u@{1}
/
x---y-----u@{2}
\
.---u@{3}---b
\
.-u@{4}
I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:
Exponential stride phase:
1. candidates={ u@{0} }
merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
merge-base b $candidates -> u@{3}, in $candidates
Bisection phase:
1. candidates={ u@{3} u@{4} }
merge-base b $candidates -> u@{3}, in $candidates
2. candidates={ u@{3} }
merge-base b $candidates -> u@{3}, in $candidates, done
It works for the few cases I have thought of, but it may break in
other other cases. I just read about the virtual merge commits, so I'm
not sure I understand correctly how that works eiter.
Would it even perform better than searching linearly? I tried stepping
through it manually a few times and it seems faster.
Maybe something based on timestamps would be better?
/Martin
test -n "$upstream_name" &&
for reflog in $(git rev-list ...)
do
...
done
Don't you need to make sure $upstream_name is a branch (or a ref in
general that can have a reflog), or does it not matter because the
"rev-list -g" will die without producing anything and you are discarding
the error message?
Exactly as you suspect. Is it too ugly?
I also prefer Junio's version.
quoted
Now, a handful of random questions, none of them rhetorical, as I don't
know the answers to any of them.
Would it help if the code is made just as clever as the patch attempts to
be, when the user says
git rebase origin/next~4
IOW, use the reflog of origin/next even in such a case?
Not sure. I think it seems too rare to worry about. In those cases,
one could still use the good old '--onto' option manually. Also, if we
don't handle the ref~4 case, the "cleverness" can be disabled by using
ref~0.
With ref~4 you are specifying a commit, so I would expect to rebase to
use it as such, not also as a branch ref.
quoted
quoted
+do
+ if test $reflog = $(git merge-base $reflog $orig_head)
+ then
+ if test $reflog != $(git merge-base $onto $reflog)
+ then
+ upstream=$reflog
+ fi
+ break
+ fi
Do we always traverse down to the beginning of the reflog in the worst
case?
Yes.
quoted
Would bisection help to avoid the cost?
I don't think the straight-forward use of bisection would work. If the
history looks something like below, where 'b' is the branch to rebase
and 'u' is the upstream, we have to go through each entry in the
reflog to find u@{3}.
.-u@{0}
/
.---u@{1}
/
x---y-----u@{2}
\
.---u@{3}---b
\
.-u@{4}
I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:
Exponential stride phase:
1. candidates={ u@{0} }
merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
merge-base b $candidates -> u@{3}, in $candidates
Doesn't it indicate that u@{3} is the commit we are looking for? I
haven't found a counterexample...
If this is true the following patch can implement it for git-pull.sh and
git-rebase.sh (sorry if it is space damaged):
@@ -10,7 +10,12 @@ test_expect_success setup 'gitaddfile&&test_tick&&gitcommit-minitial&&+>elif&&+gitaddelif&&+test_tick&&+gitcommit-msecond&&+gitcheckout-bsideHEAD^echohello>file&&test_tick&&gitcommit-a-m"A sample commit log message that has a long
@@ -18,13 +23,7 @@ summary that spills over multiple lines. Butotherwisewithasanedescription." &&-gitbranchside&&--gitreset--hardHEAD^&&->elif&&-gitaddelif&&-test_tick&&-gitcommit-msecond+gitcheckoutmaster'
It passes the "git pull --rebase" test and the basic "git rebase branch"
tests, but it fails basically with two type of tests: 1) those involving "git
rebase -i" (I'll try to debug those but I find it difficult to debug all those
FAKE_LINES), and those with "bad" reflogs as shown in the above patch to
t3408 (see the next paragraph).
Trying to find the counterexample (and debugging the failing test
above) I've found one corner we don't handle (neither in git-pull.sh
nor in git-rebase.sh). It is the case when the upstream branch is
"fast-backwards" into an older commit without extra commits on top.
Something like this:
x---y----u@{1}---u@{2}---b
\
.---u@{0}
In this case the algorithm picks u@{1} instead of u@{2} (the
alternative algorithm has the same problem when u@{n} and u@{n+1} are
in different exponential phases.
Or the simple case in:
u@{2}---u@{0}
\
.---u@{1}=b
I think this is a very rare corner case as the upstream branch has to
be "fast-backward", and you have to fetch this state. So far nobody
has found it, at least.
Bisection phase:
1. candidates={ u@{3} u@{4} }
merge-base b $candidates -> u@{3}, in $candidates
2. candidates={ u@{3} }
merge-base b $candidates -> u@{3}, in $candidates, done
It works for the few cases I have thought of, but it may break in
other other cases. I just read about the virtual merge commits, so I'm
not sure I understand correctly how that works eiter.
On Wed, Feb 16, 2011 at 1:10 PM, Santi Béjar [off-list ref] wrote:
quoted hunk
On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk
[off-list ref] wrote:
quoted
On Tue, 15 Feb 2011, Junio C Hamano wrote:
quoted
Would bisection help to avoid the cost?
I don't think the straight-forward use of bisection would work. If the
history looks something like below, where 'b' is the branch to rebase
and 'u' is the upstream, we have to go through each entry in the
reflog to find u@{3}.
.-u@{0}
/
.---u@{1}
/
x---y-----u@{2}
\
.---u@{3}---b
\
.-u@{4}
I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:
Exponential stride phase:
1. candidates={ u@{0} }
merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
merge-base b $candidates -> u@{3}, in $candidates
Doesn't it indicate that u@{3} is the commit we are looking for? I
haven't found a counterexample...
If this is true the following patch can implement it for git-pull.sh and
git-rebase.sh (sorry if it is space damaged):
. git-parse-remote &&
remoteref="$(get_remote_merge_branch "$@" 2>/dev/null)" &&
oldremoteref="$(git rev-parse -q --verify "$remoteref")" &&
- for reflog in $(git rev-list -g $remoteref 2>/dev/null)
- do
- if test "$reflog" = "$(git merge-base $reflog $curr_branch)"
- then
- oldremoteref="$reflog"
- break
- fi
- done
+ oldremoteref=$(git merge-base $curr_branch $oldremoteref $(git
rev-list -g $remoteref 2>/dev/null))
One thing I forgot to say is that it seems to perform quite well:
Hot cache:
$ git rev-list -g origin/next | wc -l
36
$ git rev-list -g origin/master | wc -l
52
$ time git merge-base $(git rev-list -g origin/next)
3b781df0a25d5ba23bd2603b0e3e9bb4731369df
real 0m0.155s
user 0m0.064s
sys 0m0.044s
$ time git merge-base $(git rev-list -g origin/master)
7811d9600f02e70c9f835719c71156c967a684f7
real 0m0.161s
user 0m0.064s
sys 0m0.040s
$ time git merge-base $(git rev-list -g origin/master origin/master)
7811d9600f02e70c9f835719c71156c967a684f7
real 0m0.175s
user 0m0.076s
sys 0m0.036s
Cold-cache around 1 second. And it's not linear with the number of
reflog entries, but with the number of independent branches, I
suppose.
HTH,
Santi
P.D.: Attached is the patch, in case someone wants to try it.
test -n "$upstream_name" &&
for reflog in $(git rev-list ...)
do
...
done
Don't you need to make sure $upstream_name is a branch (or a ref in
general that can have a reflog), or does it not matter because the
"rev-list -g" will die without producing anything and you are discarding
the error message?
Exactly as you suspect. Is it too ugly?
I also prefer Junio's version.
I fixed the test + for loop, if that's what you mean by "Junio's
version". Or did you mean "make sure $upstream_name is a branch"? I
could do that as well if you like. I have no preference.
quoted
.-u@{0}
/
.---u@{1}
/
x---y-----u@{2}
\
.---u@{3}---b
\
.-u@{4}
I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:
Exponential stride phase:
1. candidates={ u@{0} }
merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
merge-base b $candidates -> u@{3}, in $candidates
Doesn't it indicate that u@{3} is the commit we are looking for? I
haven't found a counterexample...
Yes, of course. Stupid me ;-). Forget about the other half. (I think
that's what I did manually to match the sha1 back to the ref name, but
that is of course complete non-sense to do in the script.)
If this is true the following patch can implement it for git-pull.sh and
git-rebase.sh (sorry if it is space damaged):
Thanks! Will have a closer look at it later today. If I understand
correctly, you simply call merge-base with the _entire_ reflog. I
would have thought that would be slow, but it's great if that is fast
enough. The resulting code looks very nice and short. Thanks again.
/Martin
test -n "$upstream_name" &&
for reflog in $(git rev-list ...)
do
...
done
Don't you need to make sure $upstream_name is a branch (or a ref in
general that can have a reflog), or does it not matter because the
"rev-list -g" will die without producing anything and you are discarding
the error message?
Exactly as you suspect. Is it too ugly?
I also prefer Junio's version.
I fixed the test + for loop, if that's what you mean by "Junio's
version". Or did you mean "make sure $upstream_name is a branch"? I
could do that as well if you like. I have no preference.
I meant the test + loop, but I would also "make sure $upstream_name is
a branch", as done in git-pull.sh with:
git rev-parse -q --verify "$remoteref"
quoted
quoted
.-u@{0}
/
.---u@{1}
/
x---y-----u@{2}
\
.---u@{3}---b
\
.-u@{4}
I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:
Exponential stride phase:
1. candidates={ u@{0} }
merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
merge-base b $candidates -> u@{3}, in $candidates
Doesn't it indicate that u@{3} is the commit we are looking for? I
haven't found a counterexample...
Yes, of course. Stupid me ;-). Forget about the other half. (I think
that's what I did manually to match the sha1 back to the ref name, but
that is of course complete non-sense to do in the script.)
quoted
If this is true the following patch can implement it for git-pull.sh and
git-rebase.sh (sorry if it is space damaged):
Thanks! Will have a closer look at it later today. If I understand
correctly, you simply call merge-base with the _entire_ reflog. I
Yes, that is the idea (plus the old remote hash in case of git-pull)
would have thought that would be slow, but it's great if that is fast
enough.
Yes, I think it is fast enough in the normal case. Even feeding the
entire git.git's master, ~25000 revisions, it takes around 2-4 seconds
only:
$ git rev-list origin/master | wc -l
24380
$ time git merge-base $(git rev-list origin/master)
9971d6d52c5afeb8ba60ae6ddcffb34af23eeadd
real 0m4.014s
user 0m1.520s
sys 0m2.284s
(2.5GHz CPU)
But, as Junio showed, it has problems when the reflog lenght is too
large. Maybe git-merge-base can learn the --stdin flag, or we could
process the reflog in batches of 1000 (?) entries, ... but the nice
property of using the entire reflog is that the output is what you are
looking for, if you take the first 1000 entries you have to check if
the output is one of these entries.
The resulting code looks very nice and short. Thanks again.
From: Martin von Zweigbergk <hidden> Date: 2016-06-15 22:50:46
On Thu, 17 Feb 2011, Santi B?jar wrote:
On Wed, Feb 16, 2011 at 5:45 PM, Martin von Zweigbergk
[off-list ref] wrote:
quoted
On Wed, 16 Feb 2011, Santi B?jar wrote:
quoted
On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk
[off-list ref] wrote:
quoted
.-u@{0}
/
.---u@{1}
/
x---y-----u@{2}
\
.---u@{3}---b
\
.-u@{4}
I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:
Exponential stride phase:
1. candidates={ u@{0} }
merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
merge-base b $candidates -> u@{3}, in $candidates
Doesn't it indicate that u@{3} is the commit we are looking for? I
haven't found a counterexample...
Yes, of course. Stupid me ;-). Forget about the other half. (I think
that's what I did manually to match the sha1 back to the ref name, but
that is of course complete non-sense to do in the script.)
quoted
If this is true the following patch can implement it for git-pull.sh and
git-rebase.sh (sorry if it is space damaged):
Thanks! Will have a closer look at it later today. If I understand
correctly, you simply call merge-base with the _entire_ reflog. I
Yes, that is the idea (plus the old remote hash in case of git-pull)
quoted
would have thought that would be slow, but it's great if that is fast
enough.
Yes, I think it is fast enough in the normal case. Even feeding the
entire git.git's master, ~25000 revisions, it takes around 2-4 seconds
only:
$ git rev-list origin/master | wc -l
24380
$ time git merge-base $(git rev-list origin/master)
9971d6d52c5afeb8ba60ae6ddcffb34af23eeadd
real 0m4.014s
user 0m1.520s
sys 0m2.284s
(2.5GHz CPU)
I finally got around to doing some tests on this myself. I used
git.git as of mid Feb, which at that time had 10010 commits in master,
following only the first parent. I took the first 563 commits from the
todo branch and transplanted onto master~10000 (there were some
conflicts after about 563 commits and I figured that would be enough
anyway). I then rebased the resulting branch (let's call it 'u')
against master~9990, then against master~9980 and so on to get a
reflog with 1001 entries for u. I then created another branch 'b'
based on u@{10}, u@{100} and @{1000}, for different runs of the
tests. I created one additional commit on b in each case. I then
rebased b with master, using the following algorithms to find the base
to rebase from:
manual: simply calling 'git rebase --onto u b~1'
linear: same algorithm as in 'git pull', which linearly walks the
reflog until a commit that b contains is found
merge-base: the base will be calculated as 'git merge-base b $(git
ref-list -g u)'
exponential: like merge-base, but start with only u@{0}, then
{u@{1},u@{2}} and so on until a commit that b contains is found
These are the results:
u@{10} u@{100} u@{1000}
manual 0m0.535s 0m1.164s 0m1.415s
linear 0m1.245s 0m37.367s 5m10.068s
merge-base 0m14.490s 0m15.409s 0m15.508s
exponential 0m1.056s 0m6.175s 0m27.221s
(1.8 GHz Athlon 64).
This clearly shows that the linear algorithm from git pull is not good
enough when rebasing older branches (i.e. branches whose upstream has
many reflog entries created after the branch itself was created).
The time it takes the "merge-base" algorithm is quite independent on
how old the branch is, but with this quite long and branchy reflog
(but not too dissimilar from git.git's pu?), it takes quite a while to
calculate it. I think this is also too slow to be acceptable as a
default.
I would personnally be happy if the "exponential" algorithm was used
by git rebase default. I suppose not everyone would agree that the
convenience outweighs the performance cost, though. OTOH, a slower
algorithm has been used in git pull for a long time and it seems like
not many people have really been bothered by that. Also see the
following paragraphs.
I also ran the same tests with an upstream branch that was never
force-updated. For these test cases, I created a reflog such that
u@{$i} = master~$((10 * $i)). Since the upstream branch was know never
to have been force-updated in this case, the "manual" test case was
simply 'git rebase u'. These are the results:
u@{10} u@{100} u@{1000}
manual 0m0.885s 0m6.126s 0m52.248s
linear 0m1.349s 0m39.688s 5m28.753s
merge-base 0m1.160s 0m1.699s 0m1.901s
exponential 0m0.769s 0m4.342s 0m7.360s
Not surprisingly, the linear algorithm is slow in these cases as well.
What's more interesting here is that the last two algorithms are
actually faster than the plain 'git rebase u'. This is caused by
--ignore-if-in-upstream flag to format-patch. Since the other three
algorithms try to figure out what the base was and pass the range from
the guessed base to the branch (e.g. u@{100}..b) to format-patch, the
--ignore-if-in-upstream to that command effectively becomes a no-op.
Although this makes rebase faster in the case of a non-force-updated
upstream, it may also be a problem in some cases. This was something
that I had not thought about until I started timing the calls. One
reason I can think of when the --ignore-if-in-upstream is useful is
when the upstream branch has been rebased, but this is exactly the
case when guessing the old base is useful and solves the problem in a
better way anyway. However, if a commit on the upstream branch was
cherry-picked from some commit on the current branch above its base
(i.e. in u@{x}..b), then that would not be detected by
--ignore-if-in-upstream and could result in unnecessary merge
conflicts. I don't know how common this case is.
The above also applies to 'git pull', of course, but the ways of
getting identical patches in upstream are probably different (more
likely by 'git am' than 'git cherry-pick' perhaps).
I think this is a useful feature. I'm just not sure how to balance the
performance vs convenience. Worst case, this could probably become a
command line option and configuration. I guess 'git pull' should use
the same algorithm. If we decide to use configation, maybe git-pull's
default would need to be different to be backward compatible.
Any thoughts?
But, as Junio showed, it has problems when the reflog lenght is too
large. Maybe git-merge-base can learn the --stdin flag, or we could
process the reflog in batches of 1000 (?) entries, ... but the nice
property of using the entire reflog is that the output is what you are
looking for, if you take the first 1000 entries you have to check if
the output is one of these entries.
Since I think the exponential algorithm seems the best choice, we
could probably just limit it to a certain number of entries, but maybe
it's better to implement a --stdin flag to merge-base. It could be
useful for others too.
/Martin
Thanks for pushing this further.
I'll read it all carefully later, but let me just comment one thing.
On Sat, Mar 12, 2011 at 10:15 PM, Martin von Zweigbergk
[off-list ref] wrote:
On Thu, 17 Feb 2011, Santi B?jar wrote:
quoted
On Wed, Feb 16, 2011 at 5:45 PM, Martin von Zweigbergk
[off-list ref] wrote:
quoted
On Wed, 16 Feb 2011, Santi B?jar wrote:
quoted
On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk
[off-list ref] wrote:
quoted
.-u@{0}
/
.---u@{1}
/
x---y-----u@{2}
\
.---u@{3}---b
\
.-u@{4}
I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:
Exponential stride phase:
1. candidates={ u@{0} }
merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
merge-base b $candidates -> u@{3}, in $candidates
Doesn't it indicate that u@{3} is the commit we are looking for? I
haven't found a counterexample...
Yes, of course. Stupid me ;-). Forget about the other half. (I think
that's what I did manually to match the sha1 back to the ref name, but
that is of course complete non-sense to do in the script.)
quoted
If this is true the following patch can implement it for git-pull.sh and
git-rebase.sh (sorry if it is space damaged):
Thanks! Will have a closer look at it later today. If I understand
correctly, you simply call merge-base with the _entire_ reflog. I
Yes, that is the idea (plus the old remote hash in case of git-pull)
quoted
would have thought that would be slow, but it's great if that is fast
enough.
Yes, I think it is fast enough in the normal case. Even feeding the
entire git.git's master, ~25000 revisions, it takes around 2-4 seconds
only:
$ git rev-list origin/master | wc -l
24380
$ time git merge-base $(git rev-list origin/master)
9971d6d52c5afeb8ba60ae6ddcffb34af23eeadd
real 0m4.014s
user 0m1.520s
sys 0m2.284s
(2.5GHz CPU)
I finally got around to doing some tests on this myself. I used
git.git as of mid Feb, which at that time had 10010 commits in master,
following only the first parent. I took the first 563 commits from the
todo branch and transplanted onto master~10000 (there were some
conflicts after about 563 commits and I figured that would be enough
anyway). I then rebased the resulting branch (let's call it 'u')
against master~9990, then against master~9980 and so on to get a
reflog with 1001 entries for u. I then created another branch 'b'
based on u@{10}, u@{100} and @{1000}, for different runs of the
tests. I created one additional commit on b in each case. I then
rebased b with master, using the following algorithms to find the base
to rebase from:
manual: simply calling 'git rebase --onto u b~1'
linear: same algorithm as in 'git pull', which linearly walks the
reflog until a commit that b contains is found
merge-base: the base will be calculated as 'git merge-base b $(git
ref-list -g u)'
exponential: like merge-base, but start with only u@{0}, then
{u@{1},u@{2}} and so on until a commit that b contains is found
First, care to share the scripts/patches for the timings? Thanks.
Could you test also variants of the exponential strategy?
exponential(n,m): like merge-base, but start with n candidates {u@{0},
..., u@{n-1}}, then n*m candidates and so on until a commit that b
contains is found.
Your exponential would be exponential(1,2).
Timings for something like exponential(10,2) or exponential(10,10),
maybe others.
Thanks,
Santi
From: Martin von Zweigbergk <hidden> Date: 2016-06-15 22:50:46
On Sun, 13 Mar 2011, Santi B?jar wrote:
First, care to share the scripts/patches for the timings? Thanks.
Sure, see end of mail for the changes to git-rebase.sh. It applies on
top of the patch that started this thread. There are some minor
differences from what I used when I ran the tests, but nothing that
should impact the timings.
To run the tests, I just did modified versions of
git reset --hard u@{100}
touch foo && git add foo && git ci -m foo
time git rebase -n --guess-base=merge u
I don't have a script that creates the initial setup, but that should
be easy enough to do. I should warn you that it took 16 hours to run
it on my 6 year old computer :-).
Could you test also variants of the exponential strategy?
I guess I could :-). Will see if I get time for that later today.
exponential(n,m): like merge-base, but start with n candidates {u@{0},
..., u@{n-1}}, then n*m candidates and so on until a commit that b
contains is found.
Your exponential would be exponential(1,2).
Timings for something like exponential(10,2) or exponential(10,10),
maybe others.
Thanks,
Santi
@@ -87,6 +88,7 @@ git_am_opt=rebase_root=force_rebase=allow_rerere_autoupdate=+guess_base=# Non-empty if a rebase was in progress when 'git rebase' was invokedin_progress=# One of {am, merge, interactive}
@@ -459,19 +465,51 @@ esac require_clean_work_tree"rebase""Please commit or stash them."-upstream_ref=$(gitrev-parse-q--verify--symbolic-full-name\-"$upstream_name")&&test-n"$upstream_ref"&&-forreflogin$(gitrev-list-g$upstream_name2>/dev/null)-do-iftest$reflog=$(gitmerge-base$reflog$orig_head)-then-iftest$reflog!=$(gitmerge-base$onto$reflog)-then-upstream=$reflog-fi-break-fi-done+iftest-n"$guess_base"&&test-n"$(gitrev-parse-q--verify\+--symbolic-full-name"$upstream_name")"+then+case$guess_basein+linear)+forreflogin$(gitrev-list-g$upstream_name2>/dev/null)+do+iftest$reflog=$(gitmerge-base$reflog$orig_head)+then+iftest$reflog!=$(gitmerge-base$onto$reflog)+then+upstream=$reflog+fi+break+fi+done+;;+merge)+upstream=$(gitmerge-base$orig_head$(gitrev-list-g$upstream_name2>/dev/null))+;;+exponential)+reflogs=$(gitrev-list-g$upstream_name2>/dev/null)+limit=$(echo"$reflogs"|wc-l)+lo=0+hi=1+whiletrue+do+echo$lo-$hi+candidates=$(echo"$reflogs"|head-$hi|tail-$(($hi-$lo)))+reflog=$(gitmerge-base$orig_head$candidates)+iftest-n"$(echo$candidates|grep$reflog)"+then+upstream=$reflog+break+fi+iftest$hi-ge$limit+then+break+fi+lo=$hi+hi=$((2*$lo))+done+;;+esac+fi# Now we are rebasing commits $upstream..$orig_head (or with --root,# everything leading up to $orig_head) on top of $onto
From: Martin von Zweigbergk <hidden> Date: 2016-06-15 22:50:46
On Sat, 12 Mar 2011, Martin von Zweigbergk wrote:
On Sun, 13 Mar 2011, Santi B?jar wrote:
quoted
Could you test also variants of the exponential strategy?
I guess I could :-). Will see if I get time for that later today.
So here are the updated figures for the force-updated history
(pu-like):
u@{10} u@{100} u@{1000}
manual 0m0.535s 0m1.164s 0m1.415s
linear 0m1.245s 0m37.367s 5m10.068s
merge-base 0m14.490s 0m15.409s 0m15.508s
exp(1,2) 0m1.056s 0m6.175s 0m27.221s
exp(10,10) 0m1.950s 0m20.031s 0m18.215s
exp(7,7) 0m1.310s 0m6.851s 0m16.757s
and for the non-force-updated history (master-like):
u@{10} u@{100} u@{1000}
manual 0m0.885s 0m6.126s 0m52.248s
linear 0m1.349s 0m39.688s 5m28.753s
merge-base 0m1.160s 0m1.699s 0m1.901s
exp(1,2) 0m0.769s 0m4.342s 0m7.360s
exp(10,10) 0m0.700s 0m2.535s 0m3.110s
exp(7,7) 0m0.653s 0m2.332s 0m3.506s
exp(10,10) is worst possible for the test cases I picked, since the
wanted reflog entry is always the first one in an interval, so almost
10 times as many entries as necessary are considered. I therefore also
tried with exp(7,7) to get more fair figures.
/Martin
[Also quoted text from On Sun, Mar 13, 2011 at 4:14 AM, Martin von
Zweigbergk [off-list ref]]
On Sat, Mar 12, 2011 at 10:15 PM, Martin von Zweigbergk
[off-list ref] wrote:
On Thu, 17 Feb 2011, Santi B?jar wrote:
quoted
On Wed, Feb 16, 2011 at 5:45 PM, Martin von Zweigbergk
[off-list ref] wrote:
quoted
On Wed, 16 Feb 2011, Santi B?jar wrote:
quoted
On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk
[off-list ref] wrote:
quoted
.-u@{0}
/
.---u@{1}
/
x---y-----u@{2}
\
.---u@{3}---b
\
.-u@{4}
I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:
Exponential stride phase:
1. candidates={ u@{0} }
merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
merge-base b $candidates -> u@{3}, in $candidates
Doesn't it indicate that u@{3} is the commit we are looking for? I
haven't found a counterexample...
Yes, of course. Stupid me ;-). Forget about the other half. (I think
that's what I did manually to match the sha1 back to the ref name, but
that is of course complete non-sense to do in the script.)
quoted
If this is true the following patch can implement it for git-pull.sh and
git-rebase.sh (sorry if it is space damaged):
Thanks! Will have a closer look at it later today. If I understand
correctly, you simply call merge-base with the _entire_ reflog. I
Yes, that is the idea (plus the old remote hash in case of git-pull)
quoted
would have thought that would be slow, but it's great if that is fast
enough.
Yes, I think it is fast enough in the normal case. Even feeding the
entire git.git's master, ~25000 revisions, it takes around 2-4 seconds
only:
$ git rev-list origin/master | wc -l
24380
$ time git merge-base $(git rev-list origin/master)
9971d6d52c5afeb8ba60ae6ddcffb34af23eeadd
real 0m4.014s
user 0m1.520s
sys 0m2.284s
(2.5GHz CPU)
I finally got around to doing some tests on this myself. I used
git.git as of mid Feb, which at that time had 10010 commits in master,
following only the first parent. I took the first 563 commits from the
todo branch and transplanted onto master~10000 (there were some
conflicts after about 563 commits and I figured that would be enough
anyway). I then rebased the resulting branch (let's call it 'u')
against master~9990, then against master~9980 and so on to get a
reflog with 1001 entries for u. I then created another branch 'b'
based on u@{10}, u@{100} and @{1000}, for different runs of the
tests. I created one additional commit on b in each case. I then
rebased b with master, using the following algorithms to find the base
to rebase from:
manual: simply calling 'git rebase --onto u b~1'
linear: same algorithm as in 'git pull', which linearly walks the
reflog until a commit that b contains is found
merge-base: the base will be calculated as 'git merge-base b $(git
ref-list -g u)'
exponential: like merge-base, but start with only u@{0}, then
{u@{1},u@{2}} and so on until a commit that b contains is found
exp(n,m): like merge-base, but start with n candidates {u@{0},
..., u@{n-1}}, then n*m candidates and so on until a commit that b
contains is found.
These are the results:
These are best timing out of three runs, mean, only the first one? Hot-cache
for all tests?
u@{10} u@{100} u@{1000}
manual 0m0.535s 0m1.164s 0m1.415s
linear 0m1.245s 0m37.367s 5m10.068s
merge-base 0m14.490s 0m15.409s 0m15.508s
exp(1,2) 0m1.056s 0m6.175s 0m27.221s
exp(10,10) 0m1.950s 0m20.031s 0m18.215s
exp(7,7) 0m1.310s 0m6.851s 0m16.757s
(1.8 GHz Athlon 64).
This clearly shows that the linear algorithm from git pull is not good
enough when rebasing older branches (i.e. branches whose upstream has
many reflog entries created after the branch itself was created).
The time it takes the "merge-base" algorithm is quite independent on
how old the branch is, but with this quite long and branchy reflog
(but not too dissimilar from git.git's pu?), it takes quite a while to
calculate it. I think this is also too slow to be acceptable as a
default.
I would personnally be happy if the "exponential" algorithm was used
by git rebase default. I suppose not everyone would agree that the
convenience outweighs the performance cost, though.
I don't agree with this. For the normal case there is no performance cost
(manual 0.5s, exp(7,7) 1.3s). There is performance cost (manual 1.4s, exp(7,7)
16.7s) when you need it, when your upstream has been rebased a long ago (in
reflog entries).
OTOH, a slower
algorithm has been used in git pull for a long time and it seems like
not many people have really been bothered by that. Also see the
following paragraphs.
I also ran the same tests with an upstream branch that was never
force-updated. For these test cases, I created a reflog such that
u@{$i} = master~$((10 * $i)). Since the upstream branch was know never
to have been force-updated in this case, the "manual" test case was
simply 'git rebase u'. These are the results:
u@{10} u@{100} u@{1000}
manual 0m0.885s 0m6.126s 0m52.248s
linear 0m1.349s 0m39.688s 5m28.753s
merge-base 0m1.160s 0m1.699s 0m1.901s
exp(1,2) 0m0.769s 0m4.342s 0m7.360s
exp(10,10) 0m0.700s 0m2.535s 0m3.110s
exp(7,7) 0m0.653s 0m2.332s 0m3.506s
Not surprisingly, the linear algorithm is slow in these cases as well.
What's more interesting here is that the last two algorithms are
actually faster than the plain 'git rebase u'. This is caused by
--ignore-if-in-upstream flag to format-patch. Since the other three
algorithms try to figure out what the base was and pass the range from
the guessed base to the branch (e.g. u@{100}..b) to format-patch, the
--ignore-if-in-upstream to that command effectively becomes a no-op.
Although this makes rebase faster in the case of a non-force-updated
upstream, it may also be a problem in some cases. This was something
that I had not thought about until I started timing the calls. One
reason I can think of when the --ignore-if-in-upstream is useful is
when the upstream branch has been rebased, but this is exactly the
case when guessing the old base is useful and solves the problem in a
better way anyway. However, if a commit on the upstream branch was
cherry-picked from some commit on the current branch above its base
(i.e. in u@{x}..b), then that would not be detected by
--ignore-if-in-upstream and could result in unnecessary merge
conflicts. I don't know how common this case is.
The above also applies to 'git pull', of course, but the ways of
getting identical patches in upstream are probably different (more
likely by 'git am' than 'git cherry-pick' perhaps).
I think this is a useful feature. I'm just not sure how to balance the
performance vs convenience. Worst case, this could probably become a
command line option and configuration. I guess 'git pull' should use
the same algorithm. If we decide to use configation, maybe git-pull's
default would need to be different to be backward compatible.
Any thoughts?
I think it is worth, as it looks like it only affects those who need
the feature.
The exp(7,7) or similar seems a good candidate.
HTH,
Santi