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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html