Re: [PATCH] rebase: be cleverer with rebased upstream branches

[Martin von Zweigbergk <martin.von.zweigbergk@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.

> 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