From: Santi Béjar <santi@agolina.net>
Date: Sat, 12 Mar 2011 23:51:30 GMT
Subject: Re: [PATCH] rebase: be cleverer with rebased upstream branches
Message-ID: <AANLkTikrYbY6r5hYnhWCB1GVKbPgounxdvAGeejsUKoC@mail.gmail.com>
In-Reply-To: <alpine.DEB.2.00.1103120930250.15442@debian>

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
<martin.von.zweigbergk@gmail.com> wrote:
> On Thu, 17 Feb 2011, Santi B?jar wrote:
>
>> On Wed, Feb 16, 2011 at 5:45 PM, Martin von Zweigbergk
>> <martin.von.zweigbergk@gmail.com> wrote:
>> > On Wed, 16 Feb 2011, Santi B?jar wrote:
>> >
>> >> On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk
>> >> <martin.von.zweigbergk@gmail.com> wrote:
>> >> >
>> >> >        .-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
>>
>> 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)
>
>
> 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