[RFH] rebase -i optimization

[RFH] rebase -i optimization

[Sverre Rabbelier]

Heya,

I am currently working on a large set of patches for Melange, and as
such I'm using rebase -i a lot to polish things a bit. I do this
mainly by 'git rebase -i master' from my topic branch, then change on
of the 'pick' lines into an 'edit', and then fix up the commit and
'git rebase --continue'. Now I notice I'm waiting a lot for 'rebase
-i' to finish picking the first bunch of commits that I didn't change.
Now obviously I couldof done 'git rebase -i <foo>', but then I have
first figure out what the last commit I want to change is.
Would there be a reason to not reset to the last 'pick' commit instead
of to the 'based on' branch (as long as there history is linear)? If
so, what would be the best way to go around and implement this?

(to's based on who made the most changes to git-rebase--interactive.sh
and cc-ed those involved with git-sequencer)

-- 
Cheers,

Sverre Rabbelier

Re: [RFH] rebase -i optimization

[Johannes Schindelin]

Hi,

On Thu, 26 Feb 2009, Sverre Rabbelier wrote:

> I am currently working on a large set of patches for Melange, and as
> such I'm using rebase -i a lot to polish things a bit. I do this
> mainly by 'git rebase -i master' from my topic branch, then change on
> of the 'pick' lines into an 'edit', and then fix up the commit and
> 'git rebase --continue'. Now I notice I'm waiting a lot for 'rebase
> -i' to finish picking the first bunch of commits that I didn't change.
> Now obviously I couldof done 'git rebase -i <foo>', but then I have
> first figure out what the last commit I want to change is.
> Would there be a reason to not reset to the last 'pick' commit instead
> of to the 'based on' branch (as long as there history is linear)? If
> so, what would be the best way to go around and implement this?

This code is supposed to do exactly what you want:

http://repo.or.cz/w/git/dscho.git?a=blob;f=git-rebase--interactive.sh;h=532f161c1ddce351cf623b096899e0eb057180ca;hb=8394eb1ecee00c2aba9212f3445c42078b41614b#l198

Unfortunately, it seems to be quite broken by all the different directions 
rebase -i was pulled to, but maybe you see the bug right away.  Otherwise, 
I'll try to reschedule my Git time budget later tonight.

Ciao,
Dscho

Re: [RFH] rebase -i optimization

[Sverre Rabbelier]

Heya,

On Thu, Feb 26, 2009 at 15:59, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
> This code is supposed to do exactly what you want:

Hmmm, I can't say I understand it 100%, but what I can see from
reading the code and looking at the output of 'rebase -i -v' is that
it does a 'git reset --hard' on each commit if it was already applied,
instead of figuring out beforehand what to reset to? If that is the
case, it might still take a long time to do the rebase if it takes
long to do the 'reset --hard' between the patches (say, if a big
change is made).

> Unfortunately, it seems to be quite broken by all the different directions
> rebase -i was pulled to, but maybe you see the bug right away.  Otherwise,
> I'll try to reschedule my Git time budget later tonight.

After reading the code and trying with -v, I don't think the current
code is broken, just that it might be optimized to be even faster?

-- 
Cheers,

Sverre Rabbelier

Re: [RFH] rebase -i optimization

[Johannes Schindelin]

Hi,

On Thu, 26 Feb 2009, Sverre Rabbelier wrote:

> On Thu, Feb 26, 2009 at 15:59, Johannes Schindelin
> <Johannes.Schindelin@gmx.de> wrote:
> > This code is supposed to do exactly what you want:
> 
> Hmmm, I can't say I understand it 100%, but what I can see from
> reading the code and looking at the output of 'rebase -i -v' is that
> it does a 'git reset --hard' on each commit if it was already applied,
> instead of figuring out beforehand what to reset to? If that is the
> case, it might still take a long time to do the rebase if it takes
> long to do the 'reset --hard' between the patches (say, if a big
> change is made).

Right.

I am of two minds here:

On one hand, I could imagine that it is just a question of skipping those 
'pick' commands that do not contribute anything.  That would be a pretty 
simple function that would be called at the very beginning.

On the other hand, this very simple strategy would fail pretty quickly 
(and badly) with -i -p.  And that is the stuff I am mostly spending my Git 
time budget on these days.

Having said that, I think yours might be such a common case that it is 
worth optimizing for.

Ciao,
Dscho

Re: [RFH] rebase -i optimization

[Sverre Rabbelier]

Heya,

On Fri, Feb 27, 2009 at 11:50, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
> On one hand, I could imagine that it is just a question of skipping those
> 'pick' commands that do not contribute anything.  That would be a pretty
> simple function that would be called at the very beginning.

Exactly, that's what I had in mind.

> On the other hand, this very simple strategy would fail pretty quickly
> (and badly) with -i -p.  And that is the stuff I am mostly spending my Git
> time budget on these days.

I would be fine with making this optimization optional (with a config
option?), and barf if both the optimization and -p are supplied. We
could even automagically ignore the config option for -p, and only
barf if both -p and this option are specified explicitly?

> Having said that, I think yours might be such a common case that it is
> worth optimizing for.

Does this fit in your git time budget, or would you prefer I have a
stab at it? If the latter, any hints on where to put such a call?

-- 
Cheers,

Sverre Rabbelier

[PATCH] rebase -i: avoid 'git reset' when possible

[Johannes Schindelin]

When picking commits whose parents have not changed, we do not need to
rewrite the commit.  We do not need to reset the working directory to
the parent's state, either.

Requested by Sverre Rabbelier.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---

	On Fri, 27 Feb 2009, Johannes Schindelin wrote:

	> Having said that, I think yours might be such a common case that
	> it is worth optimizing for.

	And so I did.

 git-rebase--interactive.sh    |   23 +++++++++++++++++++++++
 t/t3404-rebase-interactive.sh |   11 +++++++++++
 2 files changed, 34 insertions(+), 0 deletions(-)

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index 3dc659d..a9617a2 100755
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh
@@ -442,6 +442,27 @@ do_rest () {
 	done
 }
 
+# skip picking commits whose parents are unchanged
+skip_unnecessary_picks () {
+	current=$ONTO
+	i=0
+	while read command sha1 rest
+	do
+		test pick = "$command" &&
+		test $current = "$(git rev-parse $sha1^)" ||
+		break
+		current=$(git rev-parse $sha1)
+		i=$(($i+1))
+	done < "$TODO"
+	test $i = 0 || {
+		sed -e "${i}q" < "$TODO" >> "$DONE" &&
+		sed -e "1,${i}d" < "$TODO" >> "$TODO".new &&
+		mv -f "$TODO".new "$TODO" &&
+		ONTO=$current ||
+		die "Could not skip $i pick commands"
+	}
+}
+
 # check if no other options are set
 is_standalone () {
 	test $# -eq 2 -a "$2" = '--' &&
@@ -746,6 +767,8 @@ EOF
 		has_action "$TODO" ||
 			die_abort "Nothing to do"
 
+		test -d "$REWRITTEN" || skip_unnecessary_picks
+
 		git update-ref ORIG_HEAD $HEAD
 		output git checkout $ONTO && do_rest
 		;;
diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
index 603b003..c32ff66 100755
--- a/t/t3404-rebase-interactive.sh
+++ b/t/t3404-rebase-interactive.sh
@@ -459,4 +459,15 @@ test_expect_success 'submodule rebase -i' '
 	FAKE_LINES="1 squash 2 3" git rebase -i A
 '
 
+test_expect_success 'avoid unnecessary reset' '
+	git checkout master &&
+	test-chmtime =123456789 file3 &&
+	git update-index --refresh &&
+	HEAD=$(git rev-parse HEAD) &&
+	git rebase -i HEAD~4 &&
+	test $HEAD = $(git rev-parse HEAD) &&
+	MTIME=$(test-chmtime -v +0 file3 | sed 's/[^0-9].*$//') &&
+	test 123456789 = $MTIME
+'
+
 test_done
-- 
1.6.2.rc1.350.g6caf6

Re: [PATCH] rebase -i: avoid 'git reset' when possible

[Sverre Rabbelier]

Heya,

On Fri, Feb 27, 2009 at 13:56, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
> When picking commits whose parents have not changed, we do not need to
> rewrite the commit.  We do not need to reset the working directory to
> the parent's state, either.

Awesome, I will give this a spin when I get home.

>> Having said that, I think yours might be such a common case that
>> it is worth optimizing for.
>
> And so I did.

Very nice, I don't think I couldof done it anywhere near as fast ;).

-- 
Cheers,

Sverre Rabbelier

Re: [PATCH] rebase -i: avoid 'git reset' when possible

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 436 bytes --]

Hi,

On Fri, 27 Feb 2009, Sverre Rabbelier wrote:

> On Fri, Feb 27, 2009 at 13:56, Johannes Schindelin
> <Johannes.Schindelin@gmx.de> wrote:
> 
> >> Having said that, I think yours might be such a common case that it 
> >> is worth optimizing for.
> >
> > And so I did.
> 
> Very nice, I don't think I couldof done it anywhere near as fast ;).

Heh, the time I save now that I read less mails... :-)  It's more fun, 
too.

Ciao,
Dscho

Re: [PATCH] rebase -i: avoid 'git reset' when possible

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
> index 3dc659d..a9617a2 100755
> --- a/git-rebase--interactive.sh
> +++ b/git-rebase--interactive.sh
> @@ -442,6 +442,27 @@ do_rest () {
>  	done
>  }
>  
> +# skip picking commits whose parents are unchanged
> +skip_unnecessary_picks () {
> +	current=$ONTO
> +	i=0
> +	while read command sha1 rest
> +	do
> +		test pick = "$command" &&
> +		test $current = "$(git rev-parse $sha1^)" ||
> +		break
> +		current=$(git rev-parse $sha1)
> +		i=$(($i+1))
> +	done < "$TODO"
> +	test $i = 0 || {
> +		sed -e "${i}q" < "$TODO" >> "$DONE" &&
> +		sed -e "1,${i}d" < "$TODO" >> "$TODO".new &&
> +		mv -f "$TODO".new "$TODO" &&
> +		ONTO=$current ||
> +		die "Could not skip $i pick commands"
> +	}
> +}

I do not think you have to count and then run two sed.

	this=$ONTO
	skip_pick=t
	while read command sha1 rest
	do
		sha1=$(git rev-parse "$sha1")
        	case "$skip_pick,$command" in
                t,pick | t,p)
			if test "$this" = "$sha1"
                        then
				echo >&3 "$command $sha1 $rest"
                        	this="$sha1"
				continue
			fi
		esac                        
		skip_pick=f
                echo "$command $sha1 $rest"
	done <"$TODO" >"$TODO.new" 3>>"$DONE" &&
	...

Re: [PATCH] rebase -i: avoid 'git reset' when possible

[Johannes Schindelin]

Hi,

On Sun, 1 Mar 2009, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
> > index 3dc659d..a9617a2 100755
> > --- a/git-rebase--interactive.sh
> > +++ b/git-rebase--interactive.sh
> > @@ -442,6 +442,27 @@ do_rest () {
> >  	done
> >  }
> >  
> > +# skip picking commits whose parents are unchanged
> > +skip_unnecessary_picks () {
> > +	current=$ONTO
> > +	i=0
> > +	while read command sha1 rest
> > +	do
> > +		test pick = "$command" &&
> > +		test $current = "$(git rev-parse $sha1^)" ||
> > +		break
> > +		current=$(git rev-parse $sha1)
> > +		i=$(($i+1))
> > +	done < "$TODO"
> > +	test $i = 0 || {
> > +		sed -e "${i}q" < "$TODO" >> "$DONE" &&
> > +		sed -e "1,${i}d" < "$TODO" >> "$TODO".new &&
> > +		mv -f "$TODO".new "$TODO" &&
> > +		ONTO=$current ||
> > +		die "Could not skip $i pick commands"
> > +	}
> > +}
> 
> I do not think you have to count and then run two sed.
> 
> 	this=$ONTO
> 	skip_pick=t
> 	while read command sha1 rest
> 	do
> 		sha1=$(git rev-parse "$sha1")
>         	case "$skip_pick,$command" in
>                 t,pick | t,p)
> 			if test "$this" = "$sha1"
>                         then
> 				echo >&3 "$command $sha1 $rest"
>                         	this="$sha1"
> 				continue
> 			fi
> 		esac                        
> 		skip_pick=f
>                 echo "$command $sha1 $rest"
> 	done <"$TODO" >"$TODO.new" 3>>"$DONE" &&
> 	...

Or even

	current=$ONTO
	fd=3
	while read command sha1 rest
	do
		case "$fd,$command,$current" in
		3,pick,"$sha1"*|t,p,"$sha1"*)
			current=$sha1
			;;
		*)
			fd=1
			;;
		esac
		echo "$command $sha1 $rest" >&$fd
	done < "$TODO" > "$TODO.new" 3>> "$DONE" &&
	mv "$TODO.new" "$TODO"

Hmm?

Ciao,
Dscho

Re: [PATCH] rebase -i: avoid 'git reset' when possible

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> Or even
>
> 	current=$ONTO
> 	fd=3
> 	while read command sha1 rest
> 	do
> 		case "$fd,$command,$current" in
> 		3,pick,"$sha1"*|t,p,"$sha1"*)
> 			current=$sha1
> 			;;
> 		*)
> 			fd=1
> 			;;
> 		esac
> 		echo "$command $sha1 $rest" >&$fd
> 	done < "$TODO" > "$TODO.new" 3>> "$DONE" &&
> 	mv "$TODO.new" "$TODO"
>
> Hmm?

Certainly.

Even though "3 means we haven't found a non-pick yet" feels slightly
hacky, the logic is contained in this small loop and I do not see it as a
problem.  As long as you are sure $ONTO and all sha1 can be compared
without running them through rev-parse, avoiding rev-parse per iteration
is a very attractive optimization.

Re: [PATCH] rebase -i: avoid 'git reset' when possible

[Johannes Schindelin]

Hi,

On Mon, 2 Mar 2009, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > Or even
> >
> > 	current=$ONTO
> > 	fd=3
> > 	while read command sha1 rest
> > 	do
> > 		case "$fd,$command,$current" in
> > 		3,pick,"$sha1"*|t,p,"$sha1"*)
> > 			current=$sha1
> > 			;;
> > 		*)
> > 			fd=1
> > 			;;
> > 		esac
> > 		echo "$command $sha1 $rest" >&$fd
> > 	done < "$TODO" > "$TODO.new" 3>> "$DONE" &&
> > 	mv "$TODO.new" "$TODO"
> >
> > Hmm?
> 
> Certainly.
> 
> Even though "3 means we haven't found a non-pick yet" feels slightly
> hacky, the logic is contained in this small loop and I do not see it as a
> problem.

I'll add a one line comment.

> As long as you are sure $ONTO and all sha1 can be compared without 
> running them through rev-parse, avoiding rev-parse per iteration is a 
> very attractive optimization.

Yes, that is the beauty of abbreviated commit names: they are guaranteed 
to be unique, unless other objects were added since, which is not the case 
at this point.

Ciao,
Dscho

[PATCH v2] rebase -i: avoid 'git reset' when possible

[Johannes Schindelin]

When picking commits whose parents have not changed, we do not need to
rewrite the commit.  We do not need to reset the working directory to
the parent's state, either.

Requested by Sverre Rabbelier.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---

	Actually, I did not think things through.  Of _course_ we need
	that rev-parse, to determine the parent of the to-be-picked
	commit.

	Changes since v1: use only one loop instead of counting the number 
	of skipped commits first, and then actually skipping them.

 git-rebase--interactive.sh    |   26 ++++++++++++++++++++++++++
 t/t3404-rebase-interactive.sh |   11 +++++++++++
 2 files changed, 37 insertions(+), 0 deletions(-)

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index 3dc659d..72f7fc7 100755
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh
@@ -442,6 +442,30 @@ do_rest () {
 	done
 }
 
+# skip picking commits whose parents are unchanged
+skip_unnecessary_picks () {
+	fd=3
+	while read command sha1 rest
+	do
+		# fd=3 means we skip the command
+		case "$fd,$command,$(git rev-parse --verify --quiet $sha1^)" in
+		3,pick,"$ONTO"*|t,p,"$ONTO"*)
+			# pick a commit whose parent is current $ONTO -> skip
+			ONTO=$sha1
+			;;
+		3,#*|3,,*)
+			# copy comments
+			;;
+		*)
+			fd=1
+			;;
+		esac
+		echo "$command${sha1:+ }$sha1${rest:+ }$rest" >&$fd
+	done < "$TODO" > "$TODO.new" 3>> "$DONE" &&
+	mv -f "$TODO".new "$TODO" ||
+	die "Could not skip unnecessary pick commands"
+}
+
 # check if no other options are set
 is_standalone () {
 	test $# -eq 2 -a "$2" = '--' &&
@@ -746,6 +770,8 @@ EOF
 		has_action "$TODO" ||
 			die_abort "Nothing to do"
 
+		test -d "$REWRITTEN" || skip_unnecessary_picks
+
 		git update-ref ORIG_HEAD $HEAD
 		output git checkout $ONTO && do_rest
 		;;
diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
index 603b003..c32ff66 100755
--- a/t/t3404-rebase-interactive.sh
+++ b/t/t3404-rebase-interactive.sh
@@ -459,4 +459,15 @@ test_expect_success 'submodule rebase -i' '
 	FAKE_LINES="1 squash 2 3" git rebase -i A
 '
 
+test_expect_success 'avoid unnecessary reset' '
+	git checkout master &&
+	test-chmtime =123456789 file3 &&
+	git update-index --refresh &&
+	HEAD=$(git rev-parse HEAD) &&
+	git rebase -i HEAD~4 &&
+	test $HEAD = $(git rev-parse HEAD) &&
+	MTIME=$(test-chmtime -v +0 file3 | sed 's/[^0-9].*$//') &&
+	test 123456789 = $MTIME
+'
+
 test_done
-- 
1.6.2.rc1.456.g3dbe7

Re: [PATCH v2] rebase -i: avoid 'git reset' when possible

[Johannes Sixt]

Johannes Schindelin schrieb:
> +# skip picking commits whose parents are unchanged
> +skip_unnecessary_picks () {
> +	fd=3
> +	while read command sha1 rest
> +	do
> +		# fd=3 means we skip the command
> +		case "$fd,$command,$(git rev-parse --verify --quiet $sha1^)" in
> +		3,pick,"$ONTO"*|t,p,"$ONTO"*)

s/t,/3,/

> +			# pick a commit whose parent is current $ONTO -> skip
> +			ONTO=$sha1
> +			;;
> +		3,#*|3,,*)
> +			# copy comments
> +			;;
> +		*)
> +			fd=1
> +			;;
> +		esac
> +		echo "$command${sha1:+ }$sha1${rest:+ }$rest" >&$fd
> +	done < "$TODO" > "$TODO.new" 3>> "$DONE" &&
> +	mv -f "$TODO".new "$TODO" ||
> +	die "Could not skip unnecessary pick commands"
> +}

-- Hannes

Re: [PATCH v2] rebase -i: avoid 'git reset' when possible

[Johannes Schindelin]

Hi,

On Tue, 3 Mar 2009, Johannes Sixt wrote:

> Johannes Schindelin schrieb:
> > +# skip picking commits whose parents are unchanged
> > +skip_unnecessary_picks () {
> > +	fd=3
> > +	while read command sha1 rest
> > +	do
> > +		# fd=3 means we skip the command
> > +		case "$fd,$command,$(git rev-parse --verify --quiet $sha1^)" in
> > +		3,pick,"$ONTO"*|t,p,"$ONTO"*)
> 
> s/t,/3,/

Bah!  Of course, I had to insert a typo there!

Thanks!
Dscho

Re: [RFH] rebase -i optimization

[Sitaram Chamarty]

On 2009-02-26, Sverre Rabbelier <srabbelier@gmail.com> wrote:

> I am currently working on a large set of patches for Melange, and as
> such I'm using rebase -i a lot to polish things a bit. I do this
> mainly by 'git rebase -i master' from my topic branch, then change on
> of the 'pick' lines into an 'edit', and then fix up the commit and
> 'git rebase --continue'. Now I notice I'm waiting a lot for 'rebase
> -i' to finish picking the first bunch of commits that I didn't change.
> Now obviously I couldof done 'git rebase -i <foo>', but then I have
> first figure out what the last commit I want to change is.

you could, in theory, do it with a custom "EDITOR" variable
that actually points to a script you write.  This script
will invoke the normal editor just as now, but if it finds
that the resulting file has pick line(s) before the first
edit line, it aborts the rebase by sending back an empty
file, and print out a suitable rebase command that you just
click-and-paste :-)

Any other combination it just sends through as normal (like
if the first non-pick line was a 'squash', for instance).

Yes this is a kludge but it gets your job done with a
minimum of fuss asap.

Regards,

Sitaram

PS: Even more fun...

I tested a script that looks like this:

    #!/bin/bash

    vim "$@"
    # -- parse $1 (which will be # .git/rebase-merge/rebase-todo
    # really) to pick the correct SHA you need --
    unset EDITOR
    git rebase --abort
    git rebase -i the-SHA-you-picked

When it finishes the inner rebase it does protest mildly
(something about grep not finding that same file), a remnant
of the outer rebase... but it seems to work fine.

This removes even the extra step of having the outer rebase
print something that you have to then copy/paste :-)