Re: [PATCH] rebase: be cleverer with rebased upstream branches
From: Martin von Zweigbergk <hidden>
Date: 2016-06-15 22:50:46
Subsystem:
the rest · Maintainer:
Linus Torvalds
Possibly related (same subject, not in this thread)
- 2016-06-15 · Re: [PATCH] rebase: be cleverer with rebased upstream branches · Junio C Hamano <hidden>
- 2016-06-15 · Re: [PATCH] rebase: be cleverer with rebased upstream branches · Santi Béjar <hidden>
- 2016-06-15 · Re: [PATCH] rebase: be cleverer with rebased upstream branches · Santi Béjar <hidden>
- 2016-06-15 · Re: [PATCH] rebase: be cleverer with rebased upstream branches · Martin von Zweigbergk <hidden>
- 2016-06-15 · Re: [PATCH] rebase: be cleverer with rebased upstream branches · Santi Béjar <hidden>
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.
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