Re: [PATCH] rebase: be cleverer with rebased upstream branches
- From
Martin von Zweigbergk <martin.von.zweigbergk@gmail.com>
- Date
- Mar 13, 2011, 01:32 UTC
- Message-ID
- <alpine.DEB.2.00.1103122005490.15442@debian>
- In-Reply-To
- <AANLkTikrYbY6r5hYnhWCB1GVKbPgounxdvAGeejsUKoC@mail.gmail.com>
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.
Show 12 quoted lines
> 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
> -- 8< --
diff --git a/git-rebase.sh b/git-rebase.sh index b50c91e..8a4efab 100755 --- a/git-rebase.sh +++ b/git-rebase.sh @@ -56,6 +56,7 @@ ignore-date! passed to 'git am' whitespace=! passed to 'git apply' ignore-whitespace! passed to 'git apply' C=! passed to 'git apply' +guess-base=! to guess the base Actions: continue! continue rebasing process abort! abort rebasing process and restore original branch @@ -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 invoked in_progress= # One of {am, merge, interactive} @@ -228,6 +230,10 @@ do --no-autosquash) autosquash= ;; + --guess-base) + shift + guess_base=$1 + ;; -M|-m) do_merge=t ;; @@ -459,19 +465,51 @@ esac require_clean_work_tree "rebase" "Please commit or stash them." -upstream_ref=$(git rev-parse -q --verify --symbolic-full-name \ - "$upstream_name") && test -n "$upstream_ref" && -for reflog in $(git rev-list -g $upstream_name 2>/dev/null) -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 -done +if test -n "$guess_base" && test -n "$(git rev-parse -q --verify \ + --symbolic-full-name "$upstream_name")" +then + case $guess_base in + linear) + for reflog in $(git rev-list -g $upstream_name 2>/dev/null) + 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 + done + ;; + merge) + upstream=$(git merge-base $orig_head $(git rev-list -g $upstream_name 2>/dev/null)) + ;; + exponential) + reflogs=$(git rev-list -g $upstream_name 2>/dev/null) + limit=$(echo "$reflogs" | wc -l) + lo=0 + hi=1 + while true + do + echo $lo - $hi + candidates=$(echo "$reflogs" | head -$hi | tail -$(($hi - $lo))) + reflog=$(git merge-base $orig_head $candidates) + if test -n "$(echo $candidates | grep $reflog)" + then + upstream=$reflog + break + fi + if test $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