{"thread":{"id":"26495","subject":"[PATCH] rebase: be cleverer with rebased upstream branches","startedAt":"2011-02-14T13:51:21Z","lastAt":"2011-03-13T23:42:12Z","messageCount":19,"participants":["Martin von Zweigbergk","Santi Béjar","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"161046","messageId":"1297691481-3308-1-git-send-email-martin.von.zweigbergk@gmail.com","threadId":"26495","inReplyTo":null,"subject":"[PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2011-02-14T13:51:21Z","receivedAt":"2011-02-14T13:51:21Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"Since c85c792 (pull --rebase: be cleverer with rebased upstream\nbranches, 2008-01-26), 'git pull --rebase' has used the reflog to try\nto rebase from the old upstream onto the new upstream.\n\nHowever, if, instead of 'git pull --rebase', the user were to do 'git\nfetch' followed by 'git rebase', the reflog would not be walked. This\npatch teaches \"git rebase\" the same reflog-walking tricks that 'git\npull --rebase' already knows.\n\nThis may be useful for rebasing one branch against another local\nbranch that has been rebased. Currently, you would have to do that\nusing 'git rebase --onto' or by configuring it on the branch.\n\nIt might seem like most of the related code in git-pull.sh can be\nremoved once git-rebase.sh supports reflog walking. Unfortunately, not\nmuch of it can be removed, though. The reason is that git-pull.sh\nsimulates one step of \"reflog walking\" by keeping track of the\nposition of the remote-tracking branch before and after the fetch\noperation. This does not rely on reflogs. There are at least two cases\nwhere the reflog is not used: a) when it is disabled, b) when the\nremote branch was specified on the command line (as in 'git pull\n--rebase origin master').  In both of these cases, git-pull.sh\nremembers the position of the reference before the fetch and uses that\nas a kind of '$upstream@{1}'.\n\nSigned-off-by: Martin von Zweigbergk <martin.von.zweigbergk@gmail.com>\n---\n    This applies on top of mz/rebase.\n\n    I have been using this in combination with the patch for defaulting\n    rebase to @{upstream} for a few months now. I find it very convenient\n    e.g. when Junio has published some changes and I want to rebase my\n    branches. Then I just go to each of my branches and run 'git rebase'\n    without any arguments, and they get rebased correctly, whether they\n    are based on origin/master, origin/pu (they shouldn't be, but let's\n    say they are anyway), or on a local branch that is in turn based on\n    e.g. origin/master.\n\n    HOWEVER, this causes a very noticable delay in some cases. With this\n    patch, 'git rebase' walks the reflog of the upstream ref until it\n    finds a commit that the branch-to-rebase contains. If the upstream ref\n    has moved a lot since the branch was last rebased, there may be quite\n    a few commits to test before the old upstream commit is found.\n\n    The same thing can already occur with 'git pull --rebase' for exactly\n    the same reasons. For example, assume that your upstream remote branch\n    changes quite frequently and that you often fetch from the remote so\n    that your origin/master gets a long reflog. If you then checkout some\n    branch you had not been working on for a while, and run 'git pull',\n    you get into the same situation. The delay is probably less likely to\n    be noticed in the case of 'git pull --rebase', however, since most\n    users will probably assume it is a problem with the network or the\n    server.\n\n    Of course, 'git pull --rebase' can also be used with a local branch\n    configured as upstream. In this case, the behavior today is just like\n    what this patch introduces for 'git rebase'.\n\n    What do you think? I think it's a useful feature, but how do we handle\n    the delay problem? Maybe simply by making it configurable?\n\n    Should such a configuration variable apply to 'git pull --rebase' as\n    well? It would seem inconsistent otherwise, but maybe that's ok since\n    'git pull --rebase' is usually used with remote-tracking branches,\n    which probably change less frequently. Btw, is this a correct\n    assumption? It is definitely true for my own work on git, but I\n    actually think it's the other way around for my work at $dayjob. Am I\n    missing some part to the puzzle that explains why I had not noticed\n    the delay until I started using this patch?\n\n\n Documentation/git-rebase.txt |    7 ++++++-\n git-rebase.sh                |   13 +++++++++++++\n t/t3400-rebase.sh            |   26 ++++++++++++++++++++++++++\n 3 files changed, 45 insertions(+), 1 deletions(-)\n\ndiff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt\nindex 095a67f..d4dbe28 100644\n--- a/Documentation/git-rebase.txt\n+++ b/Documentation/git-rebase.txt\n@@ -24,7 +24,12 @@ it remains on the current branch.\n All changes made by commits in the current branch but that are not\n in <upstream> are saved to a temporary area.  This is the same set\n of commits that would be shown by `git log <upstream>..HEAD` (or\n-`git log HEAD`, if --root is specified).\n+`git log HEAD`, if --root is specified). If, however, there is a ref\n+for the upstream branch, and this branch was rebased since the\n+current branch was last rebased, the rebase uses that information to\n+avoid rebasing changes done on the upstream branch. If you do not want\n+'git rebase' to use this intelligence, refer to the upstream without\n+using a reference (e.g. 'master~0').\n \n The current branch is reset to <upstream>, or <newbase> if the\n --onto option was supplied.  This has the exact same effect as\ndiff --git a/git-rebase.sh b/git-rebase.sh\nindex 5abfeac..1bc0c29 100755\n--- a/git-rebase.sh\n+++ b/git-rebase.sh\n@@ -466,6 +466,19 @@ esac\n \n require_clean_work_tree \"rebase\" \"Please commit or stash them.\"\n \n+test -n \"$upstream_name\" && for reflog in \\\n+\t$(git rev-list -g $upstream_name 2>/dev/null)\n+do\n+\tif test $reflog = $(git merge-base $reflog $orig_head)\n+\tthen\n+\t\tif test $reflog != $(git merge-base $onto $reflog)\n+\t\tthen\n+\t\t\tupstream=$reflog\n+\t\tfi\n+\t\tbreak\n+\tfi\n+done\n+\n # Now we are rebasing commits $upstream..$orig_head (or with --root,\n # everything leading up to $orig_head) on top of $onto\n \ndiff --git a/t/t3400-rebase.sh b/t/t3400-rebase.sh\nindex 349eebd..b64df31 100755\n--- a/t/t3400-rebase.sh\n+++ b/t/t3400-rebase.sh\n@@ -209,4 +209,30 @@ test_expect_success 'rebase -m can copy notes' '\n \ttest \"a note\" = \"$(git notes show HEAD)\"\n '\n \n+test_expect_success 'rebase against rebased upstream uses reflog' '\n+\tgit checkout my-topic-branch &&\n+\techo \"Conflicting modification\" > B &&\n+\tgit add B &&\n+\tgit commit -m \"Modify B\" &&\n+\tgit reset --hard nonlinear &&\n+\tgit checkout -b old-topic my-topic-branch@{1} &&\n+\techo def > D &&\n+\tgit add D &&\n+\tgit commit -m \"Add D\" &&\n+\tgit rebase my-topic-branch &&\n+\ttest $(git rev-parse HEAD^) = $(git rev-parse my-topic-branch)\n+'\n+\n+test_expect_success 'rebase against forwarded upstream does not reapply patches' '\n+\tgit checkout my-topic-branch &&\n+\techo abc > B &&\n+\tgit add B &&\n+\tgit commit -m \"Conficting B\" &&\n+\tgit reset HEAD~2 &&\n+\tgit reset HEAD@{1} &&\n+\tgit checkout old-topic &&\n+\tgit rebase my-topic-branch &&\n+\ttest $(git rev-parse HEAD^) = $(git rev-parse my-topic-branch)\n+'\n+\n test_done\n-- \n1.7.4.rc2.33.g8a14f\n"},{"id":"161175","messageId":"AANLkTi=1WkZXBtQu71mELTBc6F7XrfBi+NWNWy-AxS79@mail.gmail.com","threadId":"26495","inReplyTo":"1297691481-3308-1-git-send-email-martin.von.zweigbergk@gmail.com","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-02-15T11:28:09Z","receivedAt":"2011-02-15T11:28:09Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Mon, Feb 14, 2011 at 1:51 PM, Martin von Zweigbergk\n<martin.von.zweigbergk@gmail.com> wrote:\n> Since c85c792 (pull --rebase: be cleverer with rebased upstream\n> branches, 2008-01-26), 'git pull --rebase' has used the reflog to try\n> to rebase from the old upstream onto the new upstream.\n>\n> However, if, instead of 'git pull --rebase', the user were to do 'git\n> fetch' followed by 'git rebase', the reflog would not be walked. This\n> patch teaches \"git rebase\" the same reflog-walking tricks that 'git\n> pull --rebase' already knows.\n>\n> This may be useful for rebasing one branch against another local\n> branch that has been rebased. Currently, you would have to do that\n> using 'git rebase --onto' or by configuring it on the branch.\n\nIt make sense.\n\n>\n> It might seem like most of the related code in git-pull.sh can be\n> removed once git-rebase.sh supports reflog walking. Unfortunately, not\n> much of it can be removed, though. The reason is that git-pull.sh\n> simulates one step of \"reflog walking\" by keeping track of the\n> position of the remote-tracking branch before and after the fetch\n> operation. This does not rely on reflogs. There are at least two cases\n> where the reflog is not used: a) when it is disabled, b) when the\n> remote branch was specified on the command line (as in 'git pull\n> --rebase origin master').  In both of these cases, git-pull.sh\n> remembers the position of the reference before the fetch and uses that\n> as a kind of '$upstream@{1}'.\n\nI don't agree with point b). In line 190:\n\n\tremoteref=\"$(get_remote_merge_branch \"$@\" 2>/dev/null)\" &&\n\nIt returns the local tracking branch for repo=origin and branch=master\nand uses its reflog.\n\nThe end result is the same, there is one case where you need the old\nvalue of the tracking branch, so it should be done in git-pull.\n\nBut I wonder if it is possible to write a function shared by\ngit-pull.sh and git-rebase.sh that computes the branch forking points,\nthe number of arguments could detect if it has the old-remote-hash or\nnot.\n\n>\n> Signed-off-by: Martin von Zweigbergk <martin.von.zweigbergk@gmail.com>\n> ---\n\n[...]\n\n>\n>    HOWEVER, this causes a very noticable delay in some cases. With this\n>    patch, 'git rebase' walks the reflog of the upstream ref until it\n>    finds a commit that the branch-to-rebase contains. If the upstream ref\n>    has moved a lot since the branch was last rebased, there may be quite\n>    a few commits to test before the old upstream commit is found.\n>\n>    The same thing can already occur with 'git pull --rebase' for exactly\n>    the same reasons. For example, assume that your upstream remote branch\n>    changes quite frequently and that you often fetch from the remote so\n>    that your origin/master gets a long reflog. If you then checkout some\n>    branch you had not been working on for a while, and run 'git pull',\n>    you get into the same situation. The delay is probably less likely to\n>    be noticed in the case of 'git pull --rebase', however, since most\n>    users will probably assume it is a problem with the network or the\n>    server.\n>\n>    Of course, 'git pull --rebase' can also be used with a local branch\n>    configured as upstream. In this case, the behavior today is just like\n>    what this patch introduces for 'git rebase'.\n>\n>    What do you think? I think it's a useful feature, but how do we handle\n>    the delay problem? Maybe simply by making it configurable?\n>\n>    Should such a configuration variable apply to 'git pull --rebase' as\n>    well? It would seem inconsistent otherwise, but maybe that's ok since\n>    'git pull --rebase' is usually used with remote-tracking branches,\n>    which probably change less frequently. Btw, is this a correct\n>    assumption? It is definitely true for my own work on git, but I\n>    actually think it's the other way around for my work at $dayjob. Am I\n>    missing some part to the puzzle that explains why I had not noticed\n>    the delay until I started using this patch?\n\nI agree with you that it may add a long delay in some cases. I\nnormally rebase branches based on an upstream branch and this may\nexplain why I haven't seen the delay (or maybe I thought it was a\nnetwork delay).\n\nI think the delay could be much shorter if the computation was not in\nshell, but in C. Or maybe change the algorithm. So I don't think a\nconfiguration item is the answer here.\n\nOther than that I think the change make sense it include docs and\ntests and works, thanks.\n\nSanti\n"},{"id":"161211","messageId":"7vzkpxm45e.fsf@alter.siamese.dyndns.org","threadId":"26495","inReplyTo":"1297691481-3308-1-git-send-email-martin.von.zweigbergk@gmail.com","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-02-15T20:30:53Z","receivedAt":"2011-02-15T20:30:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:\n\n> diff --git a/git-rebase.sh b/git-rebase.sh\n> index 5abfeac..1bc0c29 100755\n> --- a/git-rebase.sh\n> +++ b/git-rebase.sh\n> @@ -466,6 +466,19 @@ esac\n>  \n>  require_clean_work_tree \"rebase\" \"Please commit or stash them.\"\n>  \n> +test -n \"$upstream_name\" && for reflog in \\\n> +\t$(git rev-list -g $upstream_name 2>/dev/null)\n\nUgly.\n\n\ttest -n \"$upstream_name\" &&\n        for reflog in $(git rev-list ...)\n        do\n        \t...\n\tdone\n\nDon't you need to make sure $upstream_name is a branch (or a ref in\ngeneral that can have a reflog), or does it not matter because the\n\"rev-list -g\" will die without producing anything and you are discarding\nthe error message?\n\nNow, a handful of random questions, none of them rhetorical, as I don't\nknow the answers to any of them.\n\nWould it help if the code is made just as clever as the patch attempts to\nbe, when the user says\n\n\tgit rebase origin/next~4\n\nIOW, use the reflog of origin/next even in such a case?\n\n> +do\n> +\tif test $reflog = $(git merge-base $reflog $orig_head)\n> +\tthen\n> +\t\tif test $reflog != $(git merge-base $onto $reflog)\n> +\t\tthen\n> +\t\t\tupstream=$reflog\n> +\t\tfi\n> +\t\tbreak\n> +\tfi\n\nDo we always traverse down to the beginning of the reflog in the worst\ncase?  Would bisection help to avoid the cost?\n"},{"id":"161247","messageId":"alpine.DEB.2.00.1102151940140.7843@debian","threadId":"26495","inReplyTo":"AANLkTi=1WkZXBtQu71mELTBc6F7XrfBi+NWNWy-AxS79@mail.gmail.com","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2011-02-16T01:37:47Z","receivedAt":"2011-02-16T01:37:47Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Tue, 15 Feb 2011, Santi B?jar wrote:\n\n> On Mon, Feb 14, 2011 at 1:51 PM, Martin von Zweigbergk\n> <martin.von.zweigbergk@gmail.com> wrote:\n> > It might seem like most of the related code in git-pull.sh can be\n> > removed once git-rebase.sh supports reflog walking. Unfortunately, not\n> > much of it can be removed, though. The reason is that git-pull.sh\n> > simulates one step of \"reflog walking\" by keeping track of the\n> > position of the remote-tracking branch before and after the fetch\n> > operation. This does not rely on reflogs. There are at least two cases\n> > where the reflog is not used: a) when it is disabled, b) when the\n> > remote branch was specified on the command line (as in 'git pull\n> > --rebase origin master').  In both of these cases, git-pull.sh\n> > remembers the position of the reference before the fetch and uses that\n> > as a kind of '$upstream@{1}'.\n> \n> I don't agree with point b). In line 190:\n> \n> \tremoteref=\"$(get_remote_merge_branch \"$@\" 2>/dev/null)\" &&\n> \n> It returns the local tracking branch for repo=origin and branch=master\n> and uses its reflog.\n\nYes, but the local tracking branch is not updated when the\ntwo-argument version of 'git pull' is used [1].\n \n> The end result is the same, there is one case where you need the old\n> value of the tracking branch, so it should be done in git-pull.\n\nTrue, case a) is still there. I was just trying to explain why I\ndidn't just move the code from git-pull.sh to git-rebase.sh, but maybe\nit confused more than it clarified...\n\n> But I wonder if it is possible to write a function shared by\n> git-pull.sh and git-rebase.sh that computes the branch forking points,\n> the number of arguments could detect if it has the old-remote-hash or\n> not.\n\nMakes sense. I will have a look at it.\n\n> I think the delay could be much shorter if the computation was not in\n> shell, but in C. Or maybe change the algorithm. So I don't think a\n> configuration item is the answer here.\n\nIt would definitely be nice if we can make it fast enough so we don't\nhave to make it configurable.\n\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/165758\n"},{"id":"161254","messageId":"alpine.DEB.2.00.1102152040370.14950@debian","threadId":"26495","inReplyTo":"7vzkpxm45e.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2011-02-16T03:03:23Z","receivedAt":"2011-02-16T03:03:23Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Tue, 15 Feb 2011, Junio C Hamano wrote:\n\n> Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:\n> \n> > diff --git a/git-rebase.sh b/git-rebase.sh\n> > index 5abfeac..1bc0c29 100755\n> > --- a/git-rebase.sh\n> > +++ b/git-rebase.sh\n> > @@ -466,6 +466,19 @@ esac\n> >  \n> >  require_clean_work_tree \"rebase\" \"Please commit or stash them.\"\n> >  \n> > +test -n \"$upstream_name\" && for reflog in \\\n> > +\t$(git rev-list -g $upstream_name 2>/dev/null)\n> \n> Ugly.\n\nVery. Fixed. Thanks.\n\n> \ttest -n \"$upstream_name\" &&\n>         for reflog in $(git rev-list ...)\n>         do\n>         \t...\n> \tdone\n> \n> Don't you need to make sure $upstream_name is a branch (or a ref in\n> general that can have a reflog), or does it not matter because the\n> \"rev-list -g\" will die without producing anything and you are discarding\n> the error message?\n\nExactly as you suspect. Is it too ugly?\n\n> Now, a handful of random questions, none of them rhetorical, as I don't\n> know the answers to any of them.\n> \n> Would it help if the code is made just as clever as the patch attempts to\n> be, when the user says\n> \n> \tgit rebase origin/next~4\n> \n> IOW, use the reflog of origin/next even in such a case?\n\nNot sure. I think it seems too rare to worry about. In those cases,\none could still use the good old '--onto' option manually. Also, if we\ndon't handle the ref~4 case, the \"cleverness\" can be disabled by using\nref~0.\n\n> > +do\n> > +\tif test $reflog = $(git merge-base $reflog $orig_head)\n> > +\tthen\n> > +\t\tif test $reflog != $(git merge-base $onto $reflog)\n> > +\t\tthen\n> > +\t\t\tupstream=$reflog\n> > +\t\tfi\n> > +\t\tbreak\n> > +\tfi\n> \n> Do we always traverse down to the beginning of the reflog in the worst\n> case?\n\nYes.\n\n> Would bisection help to avoid the cost?\n\nI don't think the straight-forward use of bisection would work. If the\nhistory looks something like below, where 'b' is the branch to rebase\nand 'u' is the upstream, we have to go through each entry in the\nreflog to find u@{3}.\n\n\n        .-u@{0}\n       /\n      .---u@{1}\n     /\nx---y-----u@{2}\n     \\\n      .---u@{3}---b\n       \\\n        .-u@{4}\n\n\nI have an idea inspired by bisection, Thomas's exponential stride, and\nwhat someone (you?) mentioned the other day about virtual merge\ncommits. I haven't tried it out, but let me know what you think. I'll\ntry to explain it using an example only:\n\nExponential stride phase:\n1. candidates={ u@{0} }\n   merge-base b $candidates -> y, _not_ in $candidates\n2. candidates={ u@{1} u@{2} }\n   merge-base b $candidates -> y, _not_ in $candidates\n3. candidates={ u@{3} u@{4} u@{5} u@{6} }\n   merge-base b $candidates -> u@{3}, in $candidates\nBisection phase:\n1. candidates={ u@{3} u@{4} }\n   merge-base b $candidates -> u@{3}, in $candidates\n2. candidates={ u@{3} }\n   merge-base b $candidates -> u@{3}, in $candidates, done\n\n\nIt works for the few cases I have thought of, but it may break in\nother other cases. I just read about the virtual merge commits, so I'm\nnot sure I understand correctly how that works eiter.\n\nWould it even perform better than searching linearly? I tried stepping\nthrough it manually a few times and it seems faster.\n\nMaybe something based on timestamps would be better?\n\n\n/Martin\n"},{"id":"161272","messageId":"AANLkTim_0omhFW-jVRqC8TgrG7vux2-X3k1o6RFaRf0b@mail.gmail.com","threadId":"26495","inReplyTo":"alpine.DEB.2.00.1102151940140.7843@debian","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-02-16T09:26:17Z","receivedAt":"2011-02-16T09:26:17Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Wed, Feb 16, 2011 at 1:37 AM, Martin von Zweigbergk\n<martin.von.zweigbergk@gmail.com> wrote:\n> On Tue, 15 Feb 2011, Santi B?jar wrote:\n>\n>> On Mon, Feb 14, 2011 at 1:51 PM, Martin von Zweigbergk\n>> <martin.von.zweigbergk@gmail.com> wrote:\n>> > It might seem like most of the related code in git-pull.sh can be\n>> > removed once git-rebase.sh supports reflog walking. Unfortunately, not\n>> > much of it can be removed, though. The reason is that git-pull.sh\n>> > simulates one step of \"reflog walking\" by keeping track of the\n>> > position of the remote-tracking branch before and after the fetch\n>> > operation. This does not rely on reflogs. There are at least two cases\n>> > where the reflog is not used: a) when it is disabled, b) when the\n>> > remote branch was specified on the command line (as in 'git pull\n>> > --rebase origin master').  In both of these cases, git-pull.sh\n>> > remembers the position of the reference before the fetch and uses that\n>> > as a kind of '$upstream@{1}'.\n>>\n>> I don't agree with point b). In line 190:\n>>\n>>       remoteref=\"$(get_remote_merge_branch \"$@\" 2>/dev/null)\" &&\n>>\n>> It returns the local tracking branch for repo=origin and branch=master\n>> and uses its reflog.\n>\n> Yes, but the local tracking branch is not updated when the\n> two-argument version of 'git pull' is used [1].\n\nYes, but the reflog is used nevertheless and it can use the local\ntracking branch as the old-remote-hash.\n\n>\n>> The end result is the same, there is one case where you need the old\n>> value of the tracking branch, so it should be done in git-pull.\n>\n> True, case a) is still there. I was just trying to explain why I\n> didn't just move the code from git-pull.sh to git-rebase.sh, but maybe\n> it confused more than it clarified...\n\nYes, with only case a) is sufficient (and complete).\n\nHTH,\nSanti\n"},{"id":"161298","messageId":"AANLkTinmxbYLB-K+VzY50NtOAPwd-q3WwAosAHqKRq_0@mail.gmail.com","threadId":"26495","inReplyTo":"alpine.DEB.2.00.1102152040370.14950@debian","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-02-16T12:10:28Z","receivedAt":"2011-02-16T12:10:28Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk\n<martin.von.zweigbergk@gmail.com> wrote:\n> On Tue, 15 Feb 2011, Junio C Hamano wrote:\n>\n>> Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:\n>>\n>> > diff --git a/git-rebase.sh b/git-rebase.sh\n>> > index 5abfeac..1bc0c29 100755\n>> > --- a/git-rebase.sh\n>> > +++ b/git-rebase.sh\n>>       test -n \"$upstream_name\" &&\n>>         for reflog in $(git rev-list ...)\n>>         do\n>>               ...\n>>       done\n>>\n>> Don't you need to make sure $upstream_name is a branch (or a ref in\n>> general that can have a reflog), or does it not matter because the\n>> \"rev-list -g\" will die without producing anything and you are discarding\n>> the error message?\n>\n> Exactly as you suspect. Is it too ugly?\n\nI also prefer Junio's version.\n\n>\n>> Now, a handful of random questions, none of them rhetorical, as I don't\n>> know the answers to any of them.\n>>\n>> Would it help if the code is made just as clever as the patch attempts to\n>> be, when the user says\n>>\n>>       git rebase origin/next~4\n>>\n>> IOW, use the reflog of origin/next even in such a case?\n>\n> Not sure. I think it seems too rare to worry about. In those cases,\n> one could still use the good old '--onto' option manually. Also, if we\n> don't handle the ref~4 case, the \"cleverness\" can be disabled by using\n> ref~0.\n\nWith ref~4 you are specifying a commit, so I would expect to rebase to\nuse it as such, not also as a branch ref.\n\n>\n>> > +do\n>> > +   if test $reflog = $(git merge-base $reflog $orig_head)\n>> > +   then\n>> > +           if test $reflog != $(git merge-base $onto $reflog)\n>> > +           then\n>> > +                   upstream=$reflog\n>> > +           fi\n>> > +           break\n>> > +   fi\n>>\n>> Do we always traverse down to the beginning of the reflog in the worst\n>> case?\n>\n> Yes.\n>\n>> Would bisection help to avoid the cost?\n>\n> I don't think the straight-forward use of bisection would work. If the\n> history looks something like below, where 'b' is the branch to rebase\n> and 'u' is the upstream, we have to go through each entry in the\n> reflog to find u@{3}.\n>\n>\n>        .-u@{0}\n>       /\n>      .---u@{1}\n>     /\n> x---y-----u@{2}\n>     \\\n>      .---u@{3}---b\n>       \\\n>        .-u@{4}\n>\n>\n> I have an idea inspired by bisection, Thomas's exponential stride, and\n> what someone (you?) mentioned the other day about virtual merge\n> commits. I haven't tried it out, but let me know what you think. I'll\n> try to explain it using an example only:\n>\n> Exponential stride phase:\n> 1. candidates={ u@{0} }\n>   merge-base b $candidates -> y, _not_ in $candidates\n> 2. candidates={ u@{1} u@{2} }\n>   merge-base b $candidates -> y, _not_ in $candidates\n> 3. candidates={ u@{3} u@{4} u@{5} u@{6} }\n>   merge-base b $candidates -> u@{3}, in $candidates\n\nDoesn't it indicate that u@{3} is the commit we are looking for? I\nhaven't found a counterexample...\n\nIf this is true the following patch can implement it for git-pull.sh and\ngit-rebase.sh (sorry if it is space damaged):\n\ndiff --git i/git-pull.sh w/git-pull.sh\nindex 2cdea26..09ef0a9 100755\n--- i/git-pull.sh\n+++ w/git-pull.sh\n@@ -189,14 +189,7 @@ test true = \"$rebase\" && {\n \t. git-parse-remote &&\n \tremoteref=\"$(get_remote_merge_branch \"$@\" 2>/dev/null)\" &&\n \toldremoteref=\"$(git rev-parse -q --verify \"$remoteref\")\" &&\n-\tfor reflog in $(git rev-list -g $remoteref 2>/dev/null)\n-\tdo\n-\t\tif test \"$reflog\" = \"$(git merge-base $reflog $curr_branch)\"\n-\t\tthen\n-\t\t\toldremoteref=\"$reflog\"\n-\t\t\tbreak\n-\t\tfi\n-\tdone\n+\toldremoteref=$(git merge-base $curr_branch $oldremoteref $(git\nrev-list -g $remoteref 2>/dev/null))\n }\n orig_head=$(git rev-parse -q --verify HEAD)\n git fetch $verbosity $progress $dry_run $recurse_submodules\n--update-head-ok \"$@\" || exit 1\ndiff --git i/git-rebase.sh w/git-rebase.sh\nindex 0d245fe..4b3e131 100755\n--- i/git-rebase.sh\n+++ w/git-rebase.sh\n@@ -448,18 +448,8 @@ esac\n\n require_clean_work_tree \"rebase\" \"Please commit or stash them.\"\n\n-test -n \"$upstream_name\" && for reflog in \\\n-\t$(git rev-list -g $upstream_name 2>/dev/null)\n-do\n-\tif test $reflog = $(git merge-base $reflog $orig_head)\n-\tthen\n-\t\tif test $reflog != $(git merge-base $onto $reflog)\n-\t\tthen\n-\t\t\tupstream=$reflog\n-\t\tfi\n-\t\tbreak\n-\tfi\n-done\n+test -n \"$upstream_name\" &&\n+upstream=$(git merge-base $orig_head $(git rev-list -g $upstream_name\n2>/dev/null))\n\n # Now we are rebasing commits $upstream..$orig_head (or with --root,\n # everything leading up to $orig_head) on top of $onto\ndiff --git i/t/t3408-rebase-multi-line.sh w/t/t3408-rebase-multi-line.sh\nindex 6b84e60..bee4494 100755\n--- i/t/t3408-rebase-multi-line.sh\n+++ w/t/t3408-rebase-multi-line.sh\n@@ -10,7 +10,12 @@ test_expect_success setup '\n \tgit add file &&\n \ttest_tick &&\n \tgit commit -m initial &&\n+\t>elif &&\n+\tgit add elif &&\n+\ttest_tick &&\n+\tgit commit -m second &&\n\n+\tgit checkout -b side HEAD^\n \techo hello >file &&\n \ttest_tick &&\n \tgit commit -a -m \"A sample commit log message that has a long\n@@ -18,13 +23,7 @@ summary that spills over multiple lines.\n\n But otherwise with a sane description.\" &&\n\n-\tgit branch side &&\n-\n-\tgit reset --hard HEAD^ &&\n-\t>elif &&\n-\tgit add elif &&\n-\ttest_tick &&\n-\tgit commit -m second\n+\tgit checkout master\n\n '\n\n\nIt passes the \"git pull --rebase\" test and the basic \"git rebase branch\"\ntests, but it fails basically with two type of tests: 1) those involving \"git\nrebase -i\" (I'll try to debug those but I find it difficult to debug all those\nFAKE_LINES), and those with \"bad\" reflogs as shown in the above patch to\nt3408 (see the next paragraph).\n\nTrying to find the counterexample (and debugging the failing test\nabove) I've found one corner we don't handle (neither in git-pull.sh\nnor in git-rebase.sh). It is the case when the upstream branch is\n\"fast-backwards\" into an older commit without extra commits on top.\nSomething like this:\n\nx---y----u@{1}---u@{2}---b\n          \\\n           .---u@{0}\n\nIn this case the algorithm picks u@{1} instead of u@{2} (the\nalternative algorithm has the same problem when u@{n} and u@{n+1} are\nin different exponential phases.\n\nOr the simple case in:\n\nu@{2}---u@{0}\n \\\n  .---u@{1}=b\n\nI think this is a very rare corner case as the upstream branch has to\nbe \"fast-backward\",  and you have to fetch this state. So far nobody\nhas found it, at least.\n\n> Bisection phase:\n> 1. candidates={ u@{3} u@{4} }\n>   merge-base b $candidates -> u@{3}, in $candidates\n> 2. candidates={ u@{3} }\n>   merge-base b $candidates -> u@{3}, in $candidates, done\n>\n>\n> It works for the few cases I have thought of, but it may break in\n> other other cases. I just read about the virtual merge commits, so I'm\n> not sure I understand correctly how that works eiter.\n\nMe too.\n\nHTH,\nSanti\n"},{"id":"161301","messageId":"AANLkTinsvfXjVhJfLDeZ+g4skev6bBmJgByyxXW7eO39@mail.gmail.com","threadId":"26495","inReplyTo":"AANLkTinmxbYLB-K+VzY50NtOAPwd-q3WwAosAHqKRq_0@mail.gmail.com","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-02-16T13:22:04Z","receivedAt":"2011-02-16T13:22:04Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Wed, Feb 16, 2011 at 1:10 PM, Santi Béjar <santi@agolina.net> wrote:\n> On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk\n> <martin.von.zweigbergk@gmail.com> wrote:\n>> On Tue, 15 Feb 2011, Junio C Hamano wrote:\n>>\n>>> Would bisection help to avoid the cost?\n>>\n>> I don't think the straight-forward use of bisection would work. If the\n>> history looks something like below, where 'b' is the branch to rebase\n>> and 'u' is the upstream, we have to go through each entry in the\n>> reflog to find u@{3}.\n>>\n>>\n>>        .-u@{0}\n>>       /\n>>      .---u@{1}\n>>     /\n>> x---y-----u@{2}\n>>     \\\n>>      .---u@{3}---b\n>>       \\\n>>        .-u@{4}\n>>\n>>\n>> I have an idea inspired by bisection, Thomas's exponential stride, and\n>> what someone (you?) mentioned the other day about virtual merge\n>> commits. I haven't tried it out, but let me know what you think. I'll\n>> try to explain it using an example only:\n>>\n>> Exponential stride phase:\n>> 1. candidates={ u@{0} }\n>>   merge-base b $candidates -> y, _not_ in $candidates\n>> 2. candidates={ u@{1} u@{2} }\n>>   merge-base b $candidates -> y, _not_ in $candidates\n>> 3. candidates={ u@{3} u@{4} u@{5} u@{6} }\n>>   merge-base b $candidates -> u@{3}, in $candidates\n>\n> Doesn't it indicate that u@{3} is the commit we are looking for? I\n> haven't found a counterexample...\n>\n> If this is true the following patch can implement it for git-pull.sh and\n> git-rebase.sh (sorry if it is space damaged):\n>\n> diff --git i/git-pull.sh w/git-pull.sh\n> index 2cdea26..09ef0a9 100755\n> --- i/git-pull.sh\n> +++ w/git-pull.sh\n> @@ -189,14 +189,7 @@ test true = \"$rebase\" && {\n>        . git-parse-remote &&\n>        remoteref=\"$(get_remote_merge_branch \"$@\" 2>/dev/null)\" &&\n>        oldremoteref=\"$(git rev-parse -q --verify \"$remoteref\")\" &&\n> -       for reflog in $(git rev-list -g $remoteref 2>/dev/null)\n> -       do\n> -               if test \"$reflog\" = \"$(git merge-base $reflog $curr_branch)\"\n> -               then\n> -                       oldremoteref=\"$reflog\"\n> -                       break\n> -               fi\n> -       done\n> +       oldremoteref=$(git merge-base $curr_branch $oldremoteref $(git\n> rev-list -g $remoteref 2>/dev/null))\n\nOne thing I forgot to say is that it seems to perform quite well:\n\nHot cache:\n\n$ git rev-list -g origin/next | wc -l\n36\n$ git rev-list -g origin/master | wc -l\n52\n$ time git merge-base $(git rev-list -g origin/next)\n3b781df0a25d5ba23bd2603b0e3e9bb4731369df\n\nreal\t0m0.155s\nuser\t0m0.064s\nsys\t0m0.044s\n$ time git merge-base $(git rev-list -g origin/master)\n7811d9600f02e70c9f835719c71156c967a684f7\n\nreal\t0m0.161s\nuser\t0m0.064s\nsys\t0m0.040s\n$ time git merge-base $(git rev-list -g origin/master origin/master)\n7811d9600f02e70c9f835719c71156c967a684f7\n\nreal\t0m0.175s\nuser\t0m0.076s\nsys\t0m0.036s\n\nCold-cache around 1 second. And it's not linear with the number of\nreflog entries, but with the number of independent branches, I\nsuppose.\n\nHTH,\nSanti\n\nP.D.: Attached is the patch, in case someone wants to try it.\n"},{"id":"161310","messageId":"alpine.DEB.2.00.1102161122350.14950@debian","threadId":"26495","inReplyTo":"AANLkTinmxbYLB-K+VzY50NtOAPwd-q3WwAosAHqKRq_0@mail.gmail.com","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2011-02-16T16:45:49Z","receivedAt":"2011-02-16T16:45:49Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Wed, 16 Feb 2011, Santi B?jar wrote:\n\n> On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk\n> <martin.von.zweigbergk@gmail.com> wrote:\n> > On Tue, 15 Feb 2011, Junio C Hamano wrote:\n> >\n> >> Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:\n> >>\n> >> > diff --git a/git-rebase.sh b/git-rebase.sh\n> >> > index 5abfeac..1bc0c29 100755\n> >> > --- a/git-rebase.sh\n> >> > +++ b/git-rebase.sh\n> >>       test -n \"$upstream_name\" &&\n> >>         for reflog in $(git rev-list ...)\n> >>         do\n> >>               ...\n> >>       done\n> >>\n> >> Don't you need to make sure $upstream_name is a branch (or a ref in\n> >> general that can have a reflog), or does it not matter because the\n> >> \"rev-list -g\" will die without producing anything and you are discarding\n> >> the error message?\n> >\n> > Exactly as you suspect. Is it too ugly?\n> \n> I also prefer Junio's version.\n\nI fixed the test + for loop, if that's what you mean by \"Junio's\nversion\". Or did you mean \"make sure $upstream_name is a branch\"? I\ncould do that as well if you like. I have no preference.\n\n> >        .-u@{0}\n> >       /\n> >      .---u@{1}\n> >     /\n> > x---y-----u@{2}\n> >     \\\n> >      .---u@{3}---b\n> >       \\\n> >        .-u@{4}\n> >\n> >\n> > I have an idea inspired by bisection, Thomas's exponential stride, and\n> > what someone (you?) mentioned the other day about virtual merge\n> > commits. I haven't tried it out, but let me know what you think. I'll\n> > try to explain it using an example only:\n> >\n> > Exponential stride phase:\n> > 1. candidates={ u@{0} }\n> >   merge-base b $candidates -> y, _not_ in $candidates\n> > 2. candidates={ u@{1} u@{2} }\n> >   merge-base b $candidates -> y, _not_ in $candidates\n> > 3. candidates={ u@{3} u@{4} u@{5} u@{6} }\n> >   merge-base b $candidates -> u@{3}, in $candidates\n> \n> Doesn't it indicate that u@{3} is the commit we are looking for? I\n> haven't found a counterexample...\n\nYes, of course. Stupid me ;-). Forget about the other half. (I think\nthat's what I did manually to match the sha1 back to the ref name, but\nthat is of course complete non-sense to do in the script.)\n\n> If this is true the following patch can implement it for git-pull.sh and\n> git-rebase.sh (sorry if it is space damaged):\n\nThanks! Will have a closer look at it later today. If I understand\ncorrectly, you simply call merge-base with the _entire_ reflog. I\nwould have thought that would be slow, but it's great if that is fast\nenough. The resulting code looks very nice and short. Thanks again.\n\n\n/Martin\n"},{"id":"161324","messageId":"7vei77kdce.fsf@alter.siamese.dyndns.org","threadId":"26495","inReplyTo":"AANLkTinsvfXjVhJfLDeZ+g4skev6bBmJgByyxXW7eO39@mail.gmail.com","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-02-16T19:07:29Z","receivedAt":"2011-02-16T19:07:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Santi Béjar <santi@agolina.net> writes:\n\n>> +    oldremoteref=$(git merge-base $curr_branch $oldremoteref $(git\n>> rev-list -g $remoteref 2>/dev/null))\n\nYuck; the entire set of commits that appear in reflog can be quite long.\nWhat will happen when this exceeds the shell command line limit or when\nyou get E2BIG from execve(2)?\n"},{"id":"161338","messageId":"AANLkTi=e+T2V+cnVYKziU7ezQdMpbBcxke4vj0AH7DZc@mail.gmail.com","threadId":"26495","inReplyTo":"7vei77kdce.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-02-16T21:16:11Z","receivedAt":"2011-02-16T21:16:11Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Wed, Feb 16, 2011 at 8:07 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Santi Béjar <santi@agolina.net> writes:\n>\n>>> +    oldremoteref=$(git merge-base $curr_branch $oldremoteref $(git\n>>> rev-list -g $remoteref 2>/dev/null))\n>\n> Yuck; the entire set of commits that appear in reflog can be quite long.\n> What will happen when this exceeds the shell command line limit or when\n> you get E2BIG from execve(2)?\n>\n\nSure, but it was just a proof of concept to test the algorithm.\n\nSanti\n"},{"id":"161399","messageId":"AANLkTik-JGZFCE+m7g__mwfQhRReOM=Qe_EO3otw50XC@mail.gmail.com","threadId":"26495","inReplyTo":"alpine.DEB.2.00.1102161122350.14950@debian","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-02-17T10:24:11Z","receivedAt":"2011-02-17T10:24:11Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Wed, Feb 16, 2011 at 5:45 PM, Martin von Zweigbergk\n<martin.von.zweigbergk@gmail.com> wrote:\n> On Wed, 16 Feb 2011, Santi B?jar wrote:\n>\n>> On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk\n>> <martin.von.zweigbergk@gmail.com> wrote:\n>> > On Tue, 15 Feb 2011, Junio C Hamano wrote:\n>> >\n>> >> Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:\n>> >>\n>> >> > diff --git a/git-rebase.sh b/git-rebase.sh\n>> >> > index 5abfeac..1bc0c29 100755\n>> >> > --- a/git-rebase.sh\n>> >> > +++ b/git-rebase.sh\n>> >>       test -n \"$upstream_name\" &&\n>> >>         for reflog in $(git rev-list ...)\n>> >>         do\n>> >>               ...\n>> >>       done\n>> >>\n>> >> Don't you need to make sure $upstream_name is a branch (or a ref in\n>> >> general that can have a reflog), or does it not matter because the\n>> >> \"rev-list -g\" will die without producing anything and you are discarding\n>> >> the error message?\n>> >\n>> > Exactly as you suspect. Is it too ugly?\n>>\n>> I also prefer Junio's version.\n>\n> I fixed the test + for loop, if that's what you mean by \"Junio's\n> version\". Or did you mean \"make sure $upstream_name is a branch\"? I\n> could do that as well if you like. I have no preference.\n\nI meant the test + loop, but I would also \"make sure $upstream_name is\na branch\", as done in git-pull.sh with:\n\ngit rev-parse -q --verify \"$remoteref\"\n\n>\n>> >        .-u@{0}\n>> >       /\n>> >      .---u@{1}\n>> >     /\n>> > x---y-----u@{2}\n>> >     \\\n>> >      .---u@{3}---b\n>> >       \\\n>> >        .-u@{4}\n>> >\n>> >\n>> > I have an idea inspired by bisection, Thomas's exponential stride, and\n>> > what someone (you?) mentioned the other day about virtual merge\n>> > commits. I haven't tried it out, but let me know what you think. I'll\n>> > try to explain it using an example only:\n>> >\n>> > Exponential stride phase:\n>> > 1. candidates={ u@{0} }\n>> >   merge-base b $candidates -> y, _not_ in $candidates\n>> > 2. candidates={ u@{1} u@{2} }\n>> >   merge-base b $candidates -> y, _not_ in $candidates\n>> > 3. candidates={ u@{3} u@{4} u@{5} u@{6} }\n>> >   merge-base b $candidates -> u@{3}, in $candidates\n>>\n>> Doesn't it indicate that u@{3} is the commit we are looking for? I\n>> haven't found a counterexample...\n>\n> Yes, of course. Stupid me ;-). Forget about the other half. (I think\n> that's what I did manually to match the sha1 back to the ref name, but\n> that is of course complete non-sense to do in the script.)\n>\n>> If this is true the following patch can implement it for git-pull.sh and\n>> git-rebase.sh (sorry if it is space damaged):\n>\n> Thanks! Will have a closer look at it later today. If I understand\n> correctly, you simply call merge-base with the _entire_ reflog. I\n\nYes, that is the idea (plus the old remote hash in case of git-pull)\n\n> would have thought that would be slow, but it's great if that is fast\n> enough.\n\nYes, I think it is fast enough in the normal case. Even feeding the\nentire git.git's master, ~25000 revisions, it takes around 2-4 seconds\nonly:\n\n$ git rev-list origin/master | wc -l\n24380\n$ time git merge-base $(git rev-list origin/master)\n9971d6d52c5afeb8ba60ae6ddcffb34af23eeadd\n\nreal\t0m4.014s\nuser\t0m1.520s\nsys\t0m2.284s\n\n(2.5GHz CPU)\n\nBut, as Junio showed, it has problems when the reflog lenght is too\nlarge. Maybe git-merge-base can learn the --stdin flag, or we could\nprocess the reflog in batches of 1000 (?) entries, ... but the nice\nproperty of using the entire reflog is that the output is what you are\nlooking for, if you take the first 1000 entries you have to check if\nthe output is one of these entries.\n\n> The resulting code looks very nice and short. Thanks again.\n\nNo, thanks to you for the nice idea!\n\nHTH,\nSanti\n"},{"id":"163269","messageId":"alpine.DEB.2.00.1103120930250.15442@debian","threadId":"26495","inReplyTo":"AANLkTik-JGZFCE+m7g__mwfQhRReOM=Qe_EO3otw50XC@mail.gmail.com","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2011-03-12T21:15:22Z","receivedAt":"2011-03-12T21:15:22Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Thu, 17 Feb 2011, Santi B?jar wrote:\n\n> On Wed, Feb 16, 2011 at 5:45 PM, Martin von Zweigbergk\n> <martin.von.zweigbergk@gmail.com> wrote:\n> > On Wed, 16 Feb 2011, Santi B?jar wrote:\n> >\n> >> On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk\n> >> <martin.von.zweigbergk@gmail.com> wrote:\n> >> >\n> >> >        .-u@{0}\n> >> >       /\n> >> >      .---u@{1}\n> >> >     /\n> >> > x---y-----u@{2}\n> >> >     \\\n> >> >      .---u@{3}---b\n> >> >       \\\n> >> >        .-u@{4}\n> >> >\n> >> >\n> >> > I have an idea inspired by bisection, Thomas's exponential stride, and\n> >> > what someone (you?) mentioned the other day about virtual merge\n> >> > commits. I haven't tried it out, but let me know what you think. I'll\n> >> > try to explain it using an example only:\n> >> >\n> >> > Exponential stride phase:\n> >> > 1. candidates={ u@{0} }\n> >> >   merge-base b $candidates -> y, _not_ in $candidates\n> >> > 2. candidates={ u@{1} u@{2} }\n> >> >   merge-base b $candidates -> y, _not_ in $candidates\n> >> > 3. candidates={ u@{3} u@{4} u@{5} u@{6} }\n> >> >   merge-base b $candidates -> u@{3}, in $candidates\n> >>\n> >> Doesn't it indicate that u@{3} is the commit we are looking for? I\n> >> haven't found a counterexample...\n> >\n> > Yes, of course. Stupid me ;-). Forget about the other half. (I think\n> > that's what I did manually to match the sha1 back to the ref name, but\n> > that is of course complete non-sense to do in the script.)\n> >\n> >> If this is true the following patch can implement it for git-pull.sh and\n> >> git-rebase.sh (sorry if it is space damaged):\n> >\n> > Thanks! Will have a closer look at it later today. If I understand\n> > correctly, you simply call merge-base with the _entire_ reflog. I\n> \n> Yes, that is the idea (plus the old remote hash in case of git-pull)\n> \n> > would have thought that would be slow, but it's great if that is fast\n> > enough.\n> \n> Yes, I think it is fast enough in the normal case. Even feeding the\n> entire git.git's master, ~25000 revisions, it takes around 2-4 seconds\n> only:\n> \n> $ git rev-list origin/master | wc -l\n> 24380\n> $ time git merge-base $(git rev-list origin/master)\n> 9971d6d52c5afeb8ba60ae6ddcffb34af23eeadd\n> \n> real\t0m4.014s\n> user\t0m1.520s\n> sys\t0m2.284s\n> \n> (2.5GHz CPU)\n\n\nI finally got around to doing some tests on this myself. I used\ngit.git as of mid Feb, which at that time had 10010 commits in master,\nfollowing only the first parent. I took the first 563 commits from the\ntodo branch and transplanted onto master~10000 (there were some\nconflicts after about 563 commits and I figured that would be enough\nanyway). I then rebased the resulting branch (let's call it 'u')\nagainst master~9990, then against master~9980 and so on to get a\nreflog with 1001 entries for u. I then created another branch 'b'\nbased on u@{10}, u@{100} and @{1000}, for different runs of the\ntests. I created one additional commit on b in each case. I then\nrebased b with master, using the following algorithms to find the base\nto rebase from:\n\n manual: simply calling 'git rebase --onto u b~1'\n\n linear: same algorithm as in 'git pull', which linearly walks the\n reflog until a commit that b contains is found\n\n merge-base: the base will be calculated as 'git merge-base b $(git\n ref-list -g u)'\n\n exponential: like merge-base, but start with only u@{0}, then\n {u@{1},u@{2}} and so on until a commit that b contains is found\n\nThese are the results:\n\n                 u@{10}     u@{100}    u@{1000}\nmanual         0m0.535s    0m1.164s    0m1.415s\nlinear         0m1.245s   0m37.367s   5m10.068s\nmerge-base    0m14.490s   0m15.409s   0m15.508s\nexponential    0m1.056s    0m6.175s   0m27.221s\n\n(1.8 GHz Athlon 64).\n\nThis clearly shows that the linear algorithm from git pull is not good\nenough when rebasing older branches (i.e. branches whose upstream has\nmany reflog entries created after the branch itself was created).\n\nThe time it takes the \"merge-base\" algorithm is quite independent on\nhow old the branch is, but with this quite long and branchy reflog\n(but not too dissimilar from git.git's pu?), it takes quite a while to\ncalculate it. I think this is also too slow to be acceptable as a\ndefault.\n\nI would personnally be happy if the \"exponential\" algorithm was used\nby git rebase default. I suppose not everyone would agree that the\nconvenience outweighs the performance cost, though. OTOH, a slower\nalgorithm has been used in git pull for a long time and it seems like\nnot many people have really been bothered by that. Also see the\nfollowing paragraphs.\n\nI also ran the same tests with an upstream branch that was never\nforce-updated. For these test cases, I created a reflog such that\nu@{$i} = master~$((10 * $i)). Since the upstream branch was know never\nto have been force-updated in this case, the \"manual\" test case was\nsimply 'git rebase u'. These are the results:\n\n                 u@{10}     u@{100}    u@{1000}\nmanual         0m0.885s    0m6.126s   0m52.248s\nlinear         0m1.349s   0m39.688s   5m28.753s\nmerge-base     0m1.160s    0m1.699s    0m1.901s\nexponential    0m0.769s    0m4.342s    0m7.360s\n\nNot surprisingly, the linear algorithm is slow in these cases as well.\n\nWhat's more interesting here is that the last two algorithms are\nactually faster than the plain 'git rebase u'. This is caused by\n--ignore-if-in-upstream flag to format-patch. Since the other three\nalgorithms try to figure out what the base was and pass the range from\nthe guessed base to the branch (e.g. u@{100}..b) to format-patch, the\n--ignore-if-in-upstream to that command effectively becomes a no-op.\n\nAlthough this makes rebase faster in the case of a non-force-updated\nupstream, it may also be a problem in some cases. This was something\nthat I had not thought about until I started timing the calls. One\nreason I can think of when the --ignore-if-in-upstream is useful is\nwhen the upstream branch has been rebased, but this is exactly the\ncase when guessing the old base is useful and solves the problem in a\nbetter way anyway. However, if a commit on the upstream branch was\ncherry-picked from some commit on the current branch above its base\n(i.e. in u@{x}..b), then that would not be detected by\n--ignore-if-in-upstream and could result in unnecessary merge\nconflicts. I don't know how common this case is.\n\nThe above also applies to 'git pull', of course, but the ways of\ngetting identical patches in upstream are probably different (more\nlikely by 'git am' than 'git cherry-pick' perhaps).\n\nI think this is a useful feature. I'm just not sure how to balance the\nperformance vs convenience. Worst case, this could probably become a\ncommand line option and configuration. I guess 'git pull' should use\nthe same algorithm. If we decide to use configation, maybe git-pull's\ndefault would need to be different to be backward compatible.\n\nAny thoughts?\n\n> But, as Junio showed, it has problems when the reflog lenght is too\n> large. Maybe git-merge-base can learn the --stdin flag, or we could\n> process the reflog in batches of 1000 (?) entries, ... but the nice\n> property of using the entire reflog is that the output is what you are\n> looking for, if you take the first 1000 entries you have to check if\n> the output is one of these entries.\n\nSince I think the exponential algorithm seems the best choice, we\ncould probably just limit it to a certain number of entries, but maybe\nit's better to implement a --stdin flag to merge-base. It could be\nuseful for others too.\n\n\n/Martin\n"},{"id":"163271","messageId":"AANLkTikrYbY6r5hYnhWCB1GVKbPgounxdvAGeejsUKoC@mail.gmail.com","threadId":"26495","inReplyTo":"alpine.DEB.2.00.1103120930250.15442@debian","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-03-12T23:51:30Z","receivedAt":"2011-03-12T23:51:30Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"Thanks for pushing this further.\n\nI'll read it all carefully later, but let me just comment one thing.\n\nOn Sat, Mar 12, 2011 at 10:15 PM, Martin von Zweigbergk\n<martin.von.zweigbergk@gmail.com> wrote:\n> On Thu, 17 Feb 2011, Santi B?jar wrote:\n>\n>> On Wed, Feb 16, 2011 at 5:45 PM, Martin von Zweigbergk\n>> <martin.von.zweigbergk@gmail.com> wrote:\n>> > On Wed, 16 Feb 2011, Santi B?jar wrote:\n>> >\n>> >> On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk\n>> >> <martin.von.zweigbergk@gmail.com> wrote:\n>> >> >\n>> >> >        .-u@{0}\n>> >> >       /\n>> >> >      .---u@{1}\n>> >> >     /\n>> >> > x---y-----u@{2}\n>> >> >     \\\n>> >> >      .---u@{3}---b\n>> >> >       \\\n>> >> >        .-u@{4}\n>> >> >\n>> >> >\n>> >> > I have an idea inspired by bisection, Thomas's exponential stride, and\n>> >> > what someone (you?) mentioned the other day about virtual merge\n>> >> > commits. I haven't tried it out, but let me know what you think. I'll\n>> >> > try to explain it using an example only:\n>> >> >\n>> >> > Exponential stride phase:\n>> >> > 1. candidates={ u@{0} }\n>> >> >   merge-base b $candidates -> y, _not_ in $candidates\n>> >> > 2. candidates={ u@{1} u@{2} }\n>> >> >   merge-base b $candidates -> y, _not_ in $candidates\n>> >> > 3. candidates={ u@{3} u@{4} u@{5} u@{6} }\n>> >> >   merge-base b $candidates -> u@{3}, in $candidates\n>> >>\n>> >> Doesn't it indicate that u@{3} is the commit we are looking for? I\n>> >> haven't found a counterexample...\n>> >\n>> > Yes, of course. Stupid me ;-). Forget about the other half. (I think\n>> > that's what I did manually to match the sha1 back to the ref name, but\n>> > that is of course complete non-sense to do in the script.)\n>> >\n>> >> If this is true the following patch can implement it for git-pull.sh and\n>> >> git-rebase.sh (sorry if it is space damaged):\n>> >\n>> > Thanks! Will have a closer look at it later today. If I understand\n>> > correctly, you simply call merge-base with the _entire_ reflog. I\n>>\n>> Yes, that is the idea (plus the old remote hash in case of git-pull)\n>>\n>> > would have thought that would be slow, but it's great if that is fast\n>> > enough.\n>>\n>> Yes, I think it is fast enough in the normal case. Even feeding the\n>> entire git.git's master, ~25000 revisions, it takes around 2-4 seconds\n>> only:\n>>\n>> $ git rev-list origin/master | wc -l\n>> 24380\n>> $ time git merge-base $(git rev-list origin/master)\n>> 9971d6d52c5afeb8ba60ae6ddcffb34af23eeadd\n>>\n>> real  0m4.014s\n>> user  0m1.520s\n>> sys   0m2.284s\n>>\n>> (2.5GHz CPU)\n>\n>\n> I finally got around to doing some tests on this myself. I used\n> git.git as of mid Feb, which at that time had 10010 commits in master,\n> following only the first parent. I took the first 563 commits from the\n> todo branch and transplanted onto master~10000 (there were some\n> conflicts after about 563 commits and I figured that would be enough\n> anyway). I then rebased the resulting branch (let's call it 'u')\n> against master~9990, then against master~9980 and so on to get a\n> reflog with 1001 entries for u. I then created another branch 'b'\n> based on u@{10}, u@{100} and @{1000}, for different runs of the\n> tests. I created one additional commit on b in each case. I then\n> rebased b with master, using the following algorithms to find the base\n> to rebase from:\n>\n>  manual: simply calling 'git rebase --onto u b~1'\n>\n>  linear: same algorithm as in 'git pull', which linearly walks the\n>  reflog until a commit that b contains is found\n>\n>  merge-base: the base will be calculated as 'git merge-base b $(git\n>  ref-list -g u)'\n>\n>  exponential: like merge-base, but start with only u@{0}, then\n>  {u@{1},u@{2}} and so on until a commit that b contains is found\n>\n\nFirst, care to share the scripts/patches for the timings? Thanks.\n\nCould you test also variants of the exponential strategy?\n\nexponential(n,m): like merge-base, but start with n candidates {u@{0},\n..., u@{n-1}}, then n*m candidates and so on until a commit that b\ncontains is found.\n\nYour exponential would be exponential(1,2).\n\nTimings for something like exponential(10,2) or exponential(10,10),\nmaybe others.\n\nThanks,\nSanti\n"},{"id":"163273","messageId":"alpine.DEB.2.00.1103122005490.15442@debian","threadId":"26495","inReplyTo":"AANLkTikrYbY6r5hYnhWCB1GVKbPgounxdvAGeejsUKoC@mail.gmail.com","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2011-03-13T01:32:39Z","receivedAt":"2011-03-13T01:32:39Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Sun, 13 Mar 2011, Santi B?jar wrote:\n\n> First, care to share the scripts/patches for the timings? Thanks.\n\nSure, see end of mail for the changes to git-rebase.sh. It applies on\ntop of the patch that started this thread. There are some minor\ndifferences from what I used when I ran the tests, but nothing that\nshould impact the timings.\n\nTo run the tests, I just did modified versions of\n\ngit reset --hard u@{100}\ntouch foo && git add foo && git ci -m foo\ntime git rebase -n --guess-base=merge u\n\nI don't have a script that creates the initial setup, but that should\nbe easy enough to do. I should warn you that it took 16 hours to run\nit on my 6 year old computer :-).\n\n\n> Could you test also variants of the exponential strategy?\n\nI guess I could :-). Will see if I get time for that later today.\n\n> exponential(n,m): like merge-base, but start with n candidates {u@{0},\n> ..., u@{n-1}}, then n*m candidates and so on until a commit that b\n> contains is found.\n> \n> Your exponential would be exponential(1,2).\n> \n> Timings for something like exponential(10,2) or exponential(10,10),\n> maybe others.\n> \n> Thanks,\n> Santi\n> \n\n\n-- 8< --\n\ndiff --git a/git-rebase.sh b/git-rebase.sh\nindex b50c91e..8a4efab 100755\n--- a/git-rebase.sh\n+++ b/git-rebase.sh\n@@ -56,6 +56,7 @@ ignore-date!       passed to 'git am'\n whitespace=!       passed to 'git apply'\n ignore-whitespace! passed to 'git apply'\n C=!                passed to 'git apply'\n+guess-base=!       to guess the base\n  Actions:\n continue!          continue rebasing process\n abort!             abort rebasing process and restore original branch\n@@ -87,6 +88,7 @@ git_am_opt=\n rebase_root=\n force_rebase=\n allow_rerere_autoupdate=\n+guess_base=\n # Non-empty if a rebase was in progress when 'git rebase' was invoked\n in_progress=\n # One of {am, merge, interactive}\n@@ -228,6 +230,10 @@ do\n \t--no-autosquash)\n \t\tautosquash=\n \t\t;;\n+\t--guess-base)\n+\t\tshift\n+\t\tguess_base=$1\n+\t\t;;\n \t-M|-m)\n \t\tdo_merge=t\n \t\t;;\n@@ -459,19 +465,51 @@ esac\n \n require_clean_work_tree \"rebase\" \"Please commit or stash them.\"\n \n-upstream_ref=$(git rev-parse -q --verify --symbolic-full-name \\\n-\t\"$upstream_name\") && test -n \"$upstream_ref\" &&\n-for reflog in $(git rev-list -g $upstream_name 2>/dev/null)\n-do\n-\tif test $reflog = $(git merge-base $reflog $orig_head)\n-\tthen\n-\t\tif test $reflog != $(git merge-base $onto $reflog)\n-\t\tthen\n-\t\t\tupstream=$reflog\n-\t\tfi\n-\t\tbreak\n-\tfi\n-done\n+if test -n \"$guess_base\" && test -n \"$(git rev-parse -q --verify \\\n+\t--symbolic-full-name \"$upstream_name\")\"\n+then\n+\tcase $guess_base in\n+\tlinear)\n+\t\tfor reflog in $(git rev-list -g $upstream_name 2>/dev/null)\n+\t\tdo\n+\t\t\tif test $reflog = $(git merge-base $reflog $orig_head)\n+\t\t\tthen\n+\t\t\t\tif test $reflog != $(git merge-base $onto $reflog)\n+\t\t\t\tthen\n+\t\t\t\t\tupstream=$reflog\n+\t\t\t\tfi\n+\t\t\t\tbreak\n+\t\t\tfi\n+\t\tdone\n+\t\t;;\n+\tmerge)\n+\t\tupstream=$(git merge-base $orig_head $(git rev-list -g $upstream_name 2>/dev/null))\n+\t\t;;\n+\texponential)\n+\t\treflogs=$(git rev-list -g $upstream_name 2>/dev/null)\n+\t\tlimit=$(echo \"$reflogs\" | wc -l)\n+\t\tlo=0\n+\t\thi=1\n+\t\twhile true\n+\t\tdo\n+\t\t\techo $lo - $hi\n+\t\t\tcandidates=$(echo \"$reflogs\" | head -$hi | tail -$(($hi - $lo)))\n+\t\t\treflog=$(git merge-base $orig_head $candidates)\n+\t\t\tif test -n \"$(echo $candidates | grep $reflog)\"\n+\t\t\tthen\n+\t\t\t\tupstream=$reflog\n+\t\t\t\tbreak\n+\t\t\tfi\n+\t\t\tif test $hi -ge $limit\n+\t\t\tthen\n+\t\t\t\tbreak\n+\t\t\tfi\n+\t\t\tlo=$hi\n+\t\t\thi=$((2 * $lo))\n+\t\tdone\n+\t\t;;\n+\tesac\n+fi\n \n # Now we are rebasing commits $upstream..$orig_head (or with --root,\n # everything leading up to $orig_head) on top of $onto\n"},{"id":"163277","messageId":"alpine.DEB.2.00.1103122159300.15442@debian","threadId":"26495","inReplyTo":"alpine.DEB.2.00.1103122005490.15442@debian","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Martin von Zweigbergk","fromEmail":"martin.von.zweigbergk@gmail.com","sentAt":"2011-03-13T03:14:04Z","receivedAt":"2011-03-13T03:14:04Z","isPatch":true,"sender":{"key":"martinvonz@gmail.com","avatar":"https://avatars.githubusercontent.com/u/891642?v=4"},"body":"On Sat, 12 Mar 2011, Martin von Zweigbergk wrote:\n\n> On Sun, 13 Mar 2011, Santi B?jar wrote:\n> \n> > Could you test also variants of the exponential strategy?\n> \n> I guess I could :-). Will see if I get time for that later today.\n\nSo here are the updated figures for the force-updated history\n(pu-like):\n\n                 u@{10}     u@{100}    u@{1000}\nmanual         0m0.535s    0m1.164s    0m1.415s\nlinear         0m1.245s   0m37.367s   5m10.068s\nmerge-base    0m14.490s   0m15.409s   0m15.508s\nexp(1,2)       0m1.056s    0m6.175s   0m27.221s\nexp(10,10)     0m1.950s   0m20.031s   0m18.215s\nexp(7,7)       0m1.310s    0m6.851s   0m16.757s\n\nand for the non-force-updated history (master-like):\n\n                 u@{10}     u@{100}    u@{1000}\nmanual         0m0.885s    0m6.126s   0m52.248s\nlinear         0m1.349s   0m39.688s   5m28.753s\nmerge-base     0m1.160s    0m1.699s    0m1.901s\nexp(1,2)       0m0.769s    0m4.342s    0m7.360s\nexp(10,10)     0m0.700s    0m2.535s    0m3.110s\nexp(7,7)       0m0.653s    0m2.332s    0m3.506s\n\n\nexp(10,10) is worst possible for the test cases I picked, since the\nwanted reflog entry is always the first one in an interval, so almost\n10 times as many entries as necessary are considered. I therefore also\ntried with exp(7,7) to get more fair figures.\n\n\n/Martin\n"},{"id":"163299","messageId":"7vd3luhbmt.fsf@alter.siamese.dyndns.org","threadId":"26495","inReplyTo":"alpine.DEB.2.00.1103122159300.15442@debian","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-13T22:57:30Z","receivedAt":"2011-03-13T22:57:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:\n\n> So here are the updated figures for the force-updated history\n> (pu-like):\n>\n>                  u@{10}     u@{100}    u@{1000}\n> manual         0m0.535s    0m1.164s    0m1.415s\n> linear         0m1.245s   0m37.367s   5m10.068s\n> merge-base    0m14.490s   0m15.409s   0m15.508s\n> exp(1,2)       0m1.056s    0m6.175s   0m27.221s\n> exp(10,10)     0m1.950s   0m20.031s   0m18.215s\n> exp(7,7)       0m1.310s    0m6.851s   0m16.757s\n>\n> and for the non-force-updated history (master-like):\n>\n>                  u@{10}     u@{100}    u@{1000}\n> manual         0m0.885s    0m6.126s   0m52.248s\n> linear         0m1.349s   0m39.688s   5m28.753s\n> merge-base     0m1.160s    0m1.699s    0m1.901s\n> exp(1,2)       0m0.769s    0m4.342s    0m7.360s\n> exp(10,10)     0m0.700s    0m2.535s    0m3.110s\n> exp(7,7)       0m0.653s    0m2.332s    0m3.506s\n\nI have a suspicion that merge-base shouldn't be taken as \"one of the\ncandidates among others\".\n\nIt is merely a technique to check multiple heads simultaneously and\ncheaply, instead of checking things one by one, and should be applicable\nregardless of these \"multiple heads\" come from.  It may come from a linear\nwalk of reflog, or it may come from a leaky exponential or fibonacci walk.\n\nInstead of \"linear\" that checks \"Is the tip good?  Is the tip@{1} good?\nIs the tip@{2} good? How about tip@{3}?\" repeatedly, we can check \"is the\ntip through tip@{N} good?\" with a single invocation using the merge-base\ntechnique.\n\nSimilarly if your exp(i,j) checks \"Is the tip good? tip@{1}? tip@{2}?\ntip@{4}?  tip@{8}? ...\"  iteratively, you can grab these commit object\nnames out of reflog and still use the merge-base optimization, effectively\nmaking \"one at a time\" check into \"N at a time\" check (perhaps checking a\ndozen or two at a time).\n\nIf you generate list of reglog entries way beyond what matters to the end\nresult, and feed all of them to the machinery, it is not surprising that\nit would spend more time than linear that can stop early upon the first\nsuccess.\n\nWe should optimize for common case by picking the default that performs\nwell for history that is never rewound.  If the the default algorithm on\npathological histories performs badly, it is Ok to have an alternative\nheuristics that is only triggered on such a history, but if we are going\nto do so, we need to make sure that we can cheaply detect if we need to\nuse the alternative heuristics in the first place.\n\nIs it easy to tell in an earlier phase if the history is \"force-updated\"\nor not?\n"},{"id":"163301","messageId":"AANLkTinQU8=-thBQxKJFvsUQ=C+FiBohk+PrJtnHWYG7@mail.gmail.com","threadId":"26495","inReplyTo":"alpine.DEB.2.00.1103120930250.15442@debian","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-03-13T23:09:01Z","receivedAt":"2011-03-13T23:09:01Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"[Also quoted text from On Sun, Mar 13, 2011 at 4:14 AM, Martin von\nZweigbergk <martin.von.zweigbergk@gmail.com>]\n\nOn Sat, Mar 12, 2011 at 10:15 PM, Martin von Zweigbergk\n<martin.von.zweigbergk@gmail.com> wrote:\n> On Thu, 17 Feb 2011, Santi B?jar wrote:\n>\n>> On Wed, Feb 16, 2011 at 5:45 PM, Martin von Zweigbergk\n>> <martin.von.zweigbergk@gmail.com> wrote:\n>> > On Wed, 16 Feb 2011, Santi B?jar wrote:\n>> >\n>> >> On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk\n>> >> <martin.von.zweigbergk@gmail.com> wrote:\n>> >> >\n>> >> >        .-u@{0}\n>> >> >       /\n>> >> >      .---u@{1}\n>> >> >     /\n>> >> > x---y-----u@{2}\n>> >> >     \\\n>> >> >      .---u@{3}---b\n>> >> >       \\\n>> >> >        .-u@{4}\n>> >> >\n>> >> >\n>> >> > I have an idea inspired by bisection, Thomas's exponential stride, and\n>> >> > what someone (you?) mentioned the other day about virtual merge\n>> >> > commits. I haven't tried it out, but let me know what you think. I'll\n>> >> > try to explain it using an example only:\n>> >> >\n>> >> > Exponential stride phase:\n>> >> > 1. candidates={ u@{0} }\n>> >> >   merge-base b $candidates -> y, _not_ in $candidates\n>> >> > 2. candidates={ u@{1} u@{2} }\n>> >> >   merge-base b $candidates -> y, _not_ in $candidates\n>> >> > 3. candidates={ u@{3} u@{4} u@{5} u@{6} }\n>> >> >   merge-base b $candidates -> u@{3}, in $candidates\n>> >>\n>> >> Doesn't it indicate that u@{3} is the commit we are looking for? I\n>> >> haven't found a counterexample...\n>> >\n>> > Yes, of course. Stupid me ;-). Forget about the other half. (I think\n>> > that's what I did manually to match the sha1 back to the ref name, but\n>> > that is of course complete non-sense to do in the script.)\n>> >\n>> >> If this is true the following patch can implement it for git-pull.sh and\n>> >> git-rebase.sh (sorry if it is space damaged):\n>> >\n>> > Thanks! Will have a closer look at it later today. If I understand\n>> > correctly, you simply call merge-base with the _entire_ reflog. I\n>>\n>> Yes, that is the idea (plus the old remote hash in case of git-pull)\n>>\n>> > would have thought that would be slow, but it's great if that is fast\n>> > enough.\n>>\n>> Yes, I think it is fast enough in the normal case. Even feeding the\n>> entire git.git's master, ~25000 revisions, it takes around 2-4 seconds\n>> only:\n>>\n>> $ git rev-list origin/master | wc -l\n>> 24380\n>> $ time git merge-base $(git rev-list origin/master)\n>> 9971d6d52c5afeb8ba60ae6ddcffb34af23eeadd\n>>\n>> real  0m4.014s\n>> user  0m1.520s\n>> sys   0m2.284s\n>>\n>> (2.5GHz CPU)\n>\n>\n> I finally got around to doing some tests on this myself. I used\n> git.git as of mid Feb, which at that time had 10010 commits in master,\n> following only the first parent. I took the first 563 commits from the\n> todo branch and transplanted onto master~10000 (there were some\n> conflicts after about 563 commits and I figured that would be enough\n> anyway). I then rebased the resulting branch (let's call it 'u')\n> against master~9990, then against master~9980 and so on to get a\n> reflog with 1001 entries for u. I then created another branch 'b'\n> based on u@{10}, u@{100} and @{1000}, for different runs of the\n> tests. I created one additional commit on b in each case. I then\n> rebased b with master, using the following algorithms to find the base\n> to rebase from:\n>\n>  manual: simply calling 'git rebase --onto u b~1'\n>\n>  linear: same algorithm as in 'git pull', which linearly walks the\n>  reflog until a commit that b contains is found\n>\n>  merge-base: the base will be calculated as 'git merge-base b $(git\n>  ref-list -g u)'\n>\n>  exponential: like merge-base, but start with only u@{0}, then\n>  {u@{1},u@{2}} and so on until a commit that b contains is found\n\nexp(n,m): like merge-base, but start with n candidates {u@{0},\n..., u@{n-1}}, then n*m candidates and so on until a commit that b\ncontains is found.\n\n>\n> These are the results:\n\nThese are best timing out of three runs, mean, only the first one? Hot-cache\nfor all tests?\n\n>\n>                 u@{10}     u@{100}    u@{1000}\n> manual         0m0.535s    0m1.164s    0m1.415s\n> linear         0m1.245s   0m37.367s   5m10.068s\n> merge-base    0m14.490s   0m15.409s   0m15.508s\n> exp(1,2)       0m1.056s    0m6.175s   0m27.221s\n> exp(10,10)     0m1.950s   0m20.031s   0m18.215s\n> exp(7,7)       0m1.310s    0m6.851s   0m16.757s\n>\n> (1.8 GHz Athlon 64).\n>\n> This clearly shows that the linear algorithm from git pull is not good\n> enough when rebasing older branches (i.e. branches whose upstream has\n> many reflog entries created after the branch itself was created).\n>\n> The time it takes the \"merge-base\" algorithm is quite independent on\n> how old the branch is, but with this quite long and branchy reflog\n> (but not too dissimilar from git.git's pu?), it takes quite a while to\n> calculate it. I think this is also too slow to be acceptable as a\n> default.\n>\n> I would personnally be happy if the \"exponential\" algorithm was used\n> by git rebase default. I suppose not everyone would agree that the\n> convenience outweighs the performance cost, though.\n\nI don't agree with this. For the normal case there is no performance cost\n(manual 0.5s, exp(7,7) 1.3s). There is performance cost (manual 1.4s, exp(7,7)\n16.7s) when you need it, when your upstream has been rebased a long ago (in\nreflog entries).\n\n> OTOH, a slower\n> algorithm has been used in git pull for a long time and it seems like\n> not many people have really been bothered by that. Also see the\n> following paragraphs.\n>\n> I also ran the same tests with an upstream branch that was never\n> force-updated. For these test cases, I created a reflog such that\n> u@{$i} = master~$((10 * $i)). Since the upstream branch was know never\n> to have been force-updated in this case, the \"manual\" test case was\n> simply 'git rebase u'. These are the results:\n>\n>                 u@{10}     u@{100}    u@{1000}\n> manual         0m0.885s    0m6.126s   0m52.248s\n> linear         0m1.349s   0m39.688s   5m28.753s\n> merge-base     0m1.160s    0m1.699s    0m1.901s\n> exp(1,2)       0m0.769s    0m4.342s    0m7.360s\n> exp(10,10)     0m0.700s    0m2.535s    0m3.110s\n> exp(7,7)       0m0.653s    0m2.332s    0m3.506s\n>\n> Not surprisingly, the linear algorithm is slow in these cases as well.\n>\n> What's more interesting here is that the last two algorithms are\n> actually faster than the plain 'git rebase u'. This is caused by\n> --ignore-if-in-upstream flag to format-patch. Since the other three\n> algorithms try to figure out what the base was and pass the range from\n> the guessed base to the branch (e.g. u@{100}..b) to format-patch, the\n> --ignore-if-in-upstream to that command effectively becomes a no-op.\n>\n> Although this makes rebase faster in the case of a non-force-updated\n> upstream, it may also be a problem in some cases. This was something\n> that I had not thought about until I started timing the calls. One\n> reason I can think of when the --ignore-if-in-upstream is useful is\n> when the upstream branch has been rebased, but this is exactly the\n> case when guessing the old base is useful and solves the problem in a\n> better way anyway. However, if a commit on the upstream branch was\n> cherry-picked from some commit on the current branch above its base\n> (i.e. in u@{x}..b), then that would not be detected by\n> --ignore-if-in-upstream and could result in unnecessary merge\n> conflicts. I don't know how common this case is.\n>\n> The above also applies to 'git pull', of course, but the ways of\n> getting identical patches in upstream are probably different (more\n> likely by 'git am' than 'git cherry-pick' perhaps).\n>\n> I think this is a useful feature. I'm just not sure how to balance the\n> performance vs convenience. Worst case, this could probably become a\n> command line option and configuration. I guess 'git pull' should use\n> the same algorithm. If we decide to use configation, maybe git-pull's\n> default would need to be different to be backward compatible.\n>\n> Any thoughts?\n\nI think it is worth, as it looks like it only affects those who need\nthe feature.\nThe exp(7,7) or similar seems a good candidate.\n\nHTH,\nSanti\n"},{"id":"163302","messageId":"AANLkTi=8m+nypebRXOBHYthmRpidqPnAB3iWRKVPvcTN@mail.gmail.com","threadId":"26495","inReplyTo":"7vd3luhbmt.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] rebase: be cleverer with rebased upstream branches","fromName":"Santi Béjar","fromEmail":"santi@agolina.net","sentAt":"2011-03-13T23:42:12Z","receivedAt":"2011-03-13T23:42:12Z","isPatch":true,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Sun, Mar 13, 2011 at 11:57 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> writes:\n>\n>> So here are the updated figures for the force-updated history\n>> (pu-like):\n>>\n>>                  u@{10}     u@{100}    u@{1000}\n>> manual         0m0.535s    0m1.164s    0m1.415s\n>> linear         0m1.245s   0m37.367s   5m10.068s\n>> merge-base    0m14.490s   0m15.409s   0m15.508s\n>> exp(1,2)       0m1.056s    0m6.175s   0m27.221s\n>> exp(10,10)     0m1.950s   0m20.031s   0m18.215s\n>> exp(7,7)       0m1.310s    0m6.851s   0m16.757s\n>>\n>> and for the non-force-updated history (master-like):\n>>\n>>                  u@{10}     u@{100}    u@{1000}\n>> manual         0m0.885s    0m6.126s   0m52.248s\n>> linear         0m1.349s   0m39.688s   5m28.753s\n>> merge-base     0m1.160s    0m1.699s    0m1.901s\n>> exp(1,2)       0m0.769s    0m4.342s    0m7.360s\n>> exp(10,10)     0m0.700s    0m2.535s    0m3.110s\n>> exp(7,7)       0m0.653s    0m2.332s    0m3.506s\n>\n> I have a suspicion that merge-base shouldn't be taken as \"one of the\n> candidates among others\".\n>\n> It is merely a technique to check multiple heads simultaneously and\n> cheaply, instead of checking things one by one, and should be applicable\n> regardless of these \"multiple heads\" come from.  It may come from a linear\n> walk of reflog, or it may come from a leaky exponential or fibonacci walk.\n\nHere the merge-base strategy mean take all the reflog at once. And in this\ncase the reflog is 1000 entries long, it is only relevant to the u@{1000}\ncase. For me it is more like: take the solution and check that indeed it is\nthe solution. In this sense it is the \"minimum\" time required to find the\nsolution.\n\n>\n> Instead of \"linear\" that checks \"Is the tip good?  Is the tip@{1} good?\n> Is the tip@{2} good? How about tip@{3}?\" repeatedly, we can check \"is the\n> tip through tip@{N} good?\" with a single invocation using the merge-base\n> technique.\n\nexp(n,m) is similar to this. But, yes, we could have a merge-base(N)\nstrategy which checks using the merge-base technique the first N reflog\nentries, then the next N entries, and so on. But I think it would scale worst\nthen the exponential strategy.\n\n>\n> Similarly if your exp(i,j) checks \"Is the tip good? tip@{1}? tip@{2}?\n> tip@{4}?  tip@{8}? ...\"  iteratively, you can grab these commit object\n> names out of reflog and still use the merge-base optimization, effectively\n> making \"one at a time\" check into \"N at a time\" check (perhaps checking a\n> dozen or two at a time).\n\nIndeed it is \"Is the tip good? tip@{1},tip@{2}? tip@{4},tip{5},...,tip@{8}?\n... and the merge-base techinque is used to answer each question.\n\n>\n> If you generate list of reglog entries way beyond what matters to the end\n> result, and feed all of them to the machinery, it is not surprising that\n> it would spend more time than linear that can stop early upon the first\n> success.\n\nBut if the answer is the last entry in the reflog (as in the u@{1000} case) it\nis a lower limit, see above.\n\n>\n> We should optimize for common case by picking the default that performs\n> well for history that is never rewound.  If the the default algorithm on\n> pathological histories performs badly, it is Ok to have an alternative\n> heuristics that is only triggered on such a history, but if we are going\n> to do so, we need to make sure that we can cheaply detect if we need to\n> use the alternative heuristics in the first place.\n\nMaybe I'm wrong, but from the number I see that the exp strategy this\n\"optimize for the common case and works reasonably work for pathological\nhistories\".\n\n>\n> Is it easy to tell in an earlier phase if the history is \"force-updated\"\n> or not?\n>\n\nI'm afraid this is a similar question.\n\nHTH,\nSanti\n"}]}