Re: [PATCH] rebase: be cleverer with rebased upstream branches

On Thu, 17 Feb 2011, Santi B?jar wrote:

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?

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