threads / discuss / 18032

[RFH] rebase -i optimization

Subject: [RFH] rebase -i optimization

## tl;dr

16 messages between Feb 26, 2009 and Mar 3, 2009.

replies: 15people: 5as markdown or json

Sverre Rabbelier· Feb 26, 2009, 14:55 UTC · lore
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
Johannes Schindelin· Feb 26, 2009, 14:59 UTC · re: Sverre Rabbelier · lore

Re: [RFH] rebase -i optimization

Hi,
On Thu, 26 Feb 2009, Sverre Rabbelier wrote:
Show 11 quoted lines
> 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

Sverre Rabbelier· Feb 26, 2009, 15:33 UTC · re: Johannes Schindelin · lore

Re: [RFH] rebase -i optimization

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
Johannes Schindelin· Feb 27, 2009, 10:50 UTC · re: Sverre Rabbelier · lore

Re: [RFH] rebase -i optimization

Hi,
On Thu, 26 Feb 2009, Sverre Rabbelier wrote:
Show 11 quoted lines
> 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

Sverre Rabbelier· Feb 27, 2009, 12:29 UTC · re: Johannes Schindelin · lore

Re: [RFH] rebase -i optimization

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
Johannes Schindelin· Feb 27, 2009, 12:56 UTC · re: Johannes Schindelin · lore

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

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
Sverre Rabbelier· Feb 27, 2009, 13:03 UTC · re: Johannes Schindelin · lore

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

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
Johannes Schindelin· Feb 27, 2009, 13:33 UTC · re: Sverre Rabbelier · lore

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

Hi,
On Fri, 27 Feb 2009, Sverre Rabbelier wrote:
Show 9 quoted lines
> 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

Junio C Hamano· Mar 1, 2009, 08:38 UTC · re: Johannes Schindelin · lore

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

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
Show 28 quoted lines
> 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" &&
	...
Johannes Schindelin· Mar 1, 2009, 21:57 UTC · re: Junio C Hamano · lore

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

Hi,
On Sun, 1 Mar 2009, Junio C Hamano wrote:
Show 51 quoted lines
> 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

Junio C Hamano· Mar 3, 2009, 00:57 UTC · re: Johannes Schindelin · lore

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

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
Show 19 quoted lines
> 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.

Johannes Schindelin· Mar 3, 2009, 09:24 UTC · re: Junio C Hamano · lore

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

Hi,
On Mon, 2 Mar 2009, Junio C Hamano wrote:
Show 27 quoted lines
> 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

Johannes Schindelin· Mar 3, 2009, 09:55 UTC · re: Johannes Schindelin · lore

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

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
Johannes Sixt· Mar 3, 2009, 11:19 UTC · re: Johannes Schindelin · lore

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

Johannes Schindelin schrieb:
Show 8 quoted lines
> +# 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,/
Show 15 quoted lines
> +			# 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
Johannes Schindelin· Mar 3, 2009, 11:21 UTC · re: Johannes Sixt · lore

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

Hi,
On Tue, 3 Mar 2009, Johannes Sixt wrote:
Show 11 quoted lines
> 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

Sitaram Chamarty· Feb 27, 2009, 01:10 UTC · re: Sverre Rabbelier · lore

Re: [RFH] rebase -i optimization

On 2009-02-26, Sverre Rabbelier <srabbelier@gmail.com> wrote:
Show 8 quoted lines
> 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 :-)

← back to recent threads