On Wed, Feb 16, 2011 at 1:10 PM, Santi Béjar <santi@xxxxxxxxxxx> wrote:
> On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk
> <martin.von.zweigbergk@xxxxxxxxx> wrote:
>> On Tue, 15 Feb 2011, Junio C Hamano wrote:
>>
>>> 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):
>
> diff --git i/git-pull.sh w/git-pull.sh
> index 2cdea26..09ef0a9 100755
> --- i/git-pull.sh
> +++ w/git-pull.sh
> @@ -189,14 +189,7 @@ test true = "$rebase" && {
> . 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.
Attachment:
patch
Description: Binary data