patch, 2 partsFix built-in rebase perf regression

> diff --git a/builtin/rebase.c b/builtin/rebase.c
> index 0ee06aa363..6f6d7de156 100644
> --- a/builtin/rebase.c
> +++ b/builtin/rebase.c
> @@ -569,16 +569,13 @@ static int reset_head(struct object_id *oid, const char *action,
>  	}
>  
>  	if (!fill_tree_descriptor(&desc, oid)) {
> -		error(_("failed to find tree of %s"), oid_to_hex(oid));
> -		rollback_lock_file(&lock);
> -		free((void *)desc.buffer);
> -		return -1;
> +		ret = error(_("failed to find tree of %s"), oid_to_hex(oid));
> +		goto leave_reset_head;
>  	}

> @@ -586,10 +583,9 @@ static int reset_head(struct object_id *oid, const char *action,
>  
>  	if (write_locked_index(the_repository->index, &lock, COMMIT_LOCK) < 0)
>  		ret = error(_("could not write index"));
> -	free((void *)desc.buffer);
>  
>  	if (ret)
> -		return ret;
> +		goto leave_reset_head;
>  
>  	reflog_action = getenv(GIT_REFLOG_ACTION_ENVIRONMENT);
>  	strbuf_addf(&msg, "%s: ", reflog_action ? reflog_action : "rebase");
> @@ -622,7 +618,10 @@ static int reset_head(struct object_id *oid, const char *action,
>  					 UPDATE_REFS_MSG_ON_ERR);
>  	}
>  
> +leave_reset_head:
>  	strbuf_release(&msg);
> +	rollback_lock_file(&lock);
> +	free((void *)desc.buffer);
>  	return ret;

> On Fri, Nov 09, 2018 at 01:34:17AM -0800, Johannes Schindelin via GitGitGadget wrote:
> 
> > diff --git a/builtin/rebase.c b/builtin/rebase.c
> > index 0ee06aa363..6f6d7de156 100644
> > --- a/builtin/rebase.c
> > +++ b/builtin/rebase.c
> > @@ -569,16 +569,13 @@ static int reset_head(struct object_id *oid, const char *action,
> >  	}
> >  
> >  	if (!fill_tree_descriptor(&desc, oid)) {
> > -		error(_("failed to find tree of %s"), oid_to_hex(oid));
> > -		rollback_lock_file(&lock);
> > -		free((void *)desc.buffer);
> > -		return -1;
> > +		ret = error(_("failed to find tree of %s"), oid_to_hex(oid));
> > +		goto leave_reset_head;
> >  	}
> 
> If fill_tree_descriptor() fails, what is left in desc.buffer? Looking at
> the implementation, I think it's always NULL or a valid buffer. But I
> think all code paths actually die() unless we pass a NULL oid (and in
> that case desc.buffer would be NULL, too).
> 
> So I think the original here that calls free() doesn't ever do anything
> but it did not hurt. After your patch, the leave_reset_head code would
> continue to call free(), and that's OK.

> > @@ -586,10 +583,9 @@ static int reset_head(struct object_id *oid, const char *action,
> >  
> >  	if (write_locked_index(the_repository->index, &lock, COMMIT_LOCK) < 0)
> >  		ret = error(_("could not write index"));
> > -	free((void *)desc.buffer);
> >  
> >  	if (ret)
> > -		return ret;
> > +		goto leave_reset_head;
> >  
> >  	reflog_action = getenv(GIT_REFLOG_ACTION_ENVIRONMENT);
> >  	strbuf_addf(&msg, "%s: ", reflog_action ? reflog_action : "rebase");
> > @@ -622,7 +618,10 @@ static int reset_head(struct object_id *oid, const char *action,
> >  					 UPDATE_REFS_MSG_ON_ERR);
> >  	}
> >  
> > +leave_reset_head:
> >  	strbuf_release(&msg);
> > +	rollback_lock_file(&lock);
> > +	free((void *)desc.buffer);
> >  	return ret;
> 
> We get here on success, too. So we may call rollback_lock_file() on an
> already-committed lock. This is explicitly documented as a no-op by the
> lock code, so that's OK.

> From: Johannes Schindelin <johannes.schindelin@gmx.de>
> 
> When we converted a `git checkout -q $onto^0` call to use
> `reset_head()`, we inadvertently incurred a change from a twoway_merge
> to a oneway_merge, as if we wanted a `git reset --hard` instead.
> 
> This has performance ramifications under certain, though, as the
> oneway_merge needs to lstat() every single index entry whereas
> twoway_merge does not.
> 
> So let's go back to the old behavior.

> diff --git a/builtin/rebase.c b/builtin/rebase.c
> index 6f6d7de156..c1cc50f3f8 100644
> --- a/builtin/rebase.c
> +++ b/builtin/rebase.c
> @@ -523,11 +523,12 @@ finished_rebase:
>  #define GIT_REFLOG_ACTION_ENVIRONMENT "GIT_REFLOG_ACTION"
>  
>  static int reset_head(struct object_id *oid, const char *action,
> -		      const char *switch_to_branch, int detach_head,
> +		      const char *switch_to_branch,
> +		      int detach_head, int reset_hard,

> -	if (!oid) {
> -		if (get_oid("HEAD", &head_oid)) {
> -			rollback_lock_file(&lock);
> -			return error(_("could not determine HEAD revision"));
> -		}
> -		oid = &head_oid;
> +	if (get_oid("HEAD", &head_oid)) {
> +		rollback_lock_file(&lock);
> +		return error(_("could not determine HEAD revision"));
>  	}

> On Fri, Nov 09, 2018 at 01:34:19AM -0800, Johannes Schindelin via GitGitGadget wrote:
> 
> > From: Johannes Schindelin <johannes.schindelin@gmx.de>
> > 
> > When we converted a `git checkout -q $onto^0` call to use
> > `reset_head()`, we inadvertently incurred a change from a twoway_merge
> > to a oneway_merge, as if we wanted a `git reset --hard` instead.
> > 
> > This has performance ramifications under certain, though, as the
> > oneway_merge needs to lstat() every single index entry whereas
> > twoway_merge does not.
> > 
> > So let's go back to the old behavior.
> 
> Makes sense. I didn't think too hard about any possible gotchas with the
> twoway/oneway switch, but if that's what git-checkout was doing before,
> it seems obviously safe.

> > diff --git a/builtin/rebase.c b/builtin/rebase.c
> > index 6f6d7de156..c1cc50f3f8 100644
> > --- a/builtin/rebase.c
> > +++ b/builtin/rebase.c
> > @@ -523,11 +523,12 @@ finished_rebase:
> >  #define GIT_REFLOG_ACTION_ENVIRONMENT "GIT_REFLOG_ACTION"
> >  
> >  static int reset_head(struct object_id *oid, const char *action,
> > -		      const char *switch_to_branch, int detach_head,
> > +		      const char *switch_to_branch,
> > +		      int detach_head, int reset_hard,
> 
> It might be worth switching to a single flag variable here. It would
> make calls like this:
> 
> > -	if (reset_head(&options.onto->object.oid, "checkout", NULL, 1,
> > +	if (reset_head(&options.onto->object.oid, "checkout", NULL, 1, 0,
> >  	    NULL, msg.buf))
> 
> a little more self-documenting (if a little more verbose).

> > -	if (!oid) {
> > -		if (get_oid("HEAD", &head_oid)) {
> > -			rollback_lock_file(&lock);
> > -			return error(_("could not determine HEAD revision"));
> > -		}
> > -		oid = &head_oid;
> > +	if (get_oid("HEAD", &head_oid)) {
> > +		rollback_lock_file(&lock);
> > +		return error(_("could not determine HEAD revision"));
> >  	}
> 
> This one could actually turn into:
> 
>   ret = error(...);
>   goto leave_reset_head;
> 
> now. We don't have to worry about an uninitialized desc.buffer anymore
> (as I mentioned in the previous email), because "nr" would be 0.
> 
> It doesn't save any lines, though (but maybe having a single
> cleanup/exit point would make things easier to read; I dunno).

> Actually, you got me thinking about the desc.buffer. And I think there is
> one corner case where it could cause a problem: `struct tree_desc desc[2]`
> does not initialize the buffers to NULL. And what if
> fill_tree_descriptor() function returns NULL? Then the buffer is still
> uninitialized.
> 
> In practice, our *current* version of fill_tree_descriptor() never returns
> NULL if the oid parameter is non-NULL. It would die() in the error case
> instead (bad!). So to prepare for a less bad version, I'd rather
> initialize the `desc` array and be on the safe (and easier to reason
> about) side.

> On Fri, Nov 09, 2018 at 06:21:41PM +0100, Johannes Schindelin wrote:
> 
> > Actually, you got me thinking about the desc.buffer. And I think there is
> > one corner case where it could cause a problem: `struct tree_desc desc[2]`
> > does not initialize the buffers to NULL. And what if
> > fill_tree_descriptor() function returns NULL? Then the buffer is still
> > uninitialized.
> > 
> > In practice, our *current* version of fill_tree_descriptor() never returns
> > NULL if the oid parameter is non-NULL. It would die() in the error case
> > instead (bad!). So to prepare for a less bad version, I'd rather
> > initialize the `desc` array and be on the safe (and easier to reason
> > about) side.
> 
> Yeah, I agree with all of that.
> 
> One solution would just be to increment only after success:
> 
>   if (fill_tree_descriptor(&desc[nr], ..) < 0)
> 	goto error;
>   nr++; /* now we know it's valid! */
> 
> But there are lots of alternatives.  :)

>> >  static int reset_head(struct object_id *oid, const char *action,
>> > -		      const char *switch_to_branch, int detach_head,
>> > +		      const char *switch_to_branch,
>> > +		      int detach_head, int reset_hard,
>> 
>> It might be worth switching to a single flag variable here. It would
>> make calls like this:
>> 
>> > -	if (reset_head(&options.onto->object.oid, "checkout", NULL, 1,
>> > +	if (reset_head(&options.onto->object.oid, "checkout", NULL, 1, 0,
>> >  	    NULL, msg.buf))
>> 
>> a little more self-documenting (if a little more verbose).
>
> I thought about that, but for just two flags? Well, let me try it and see
> whether I like the result ;-)

>> This one could actually turn into:
>> 
>>   ret = error(...);
>>   goto leave_reset_head;
>> 
>> now. We don't have to worry about an uninitialized desc.buffer anymore
>> (as I mentioned in the previous email), because "nr" would be 0.
>> 
>> It doesn't save any lines, though (but maybe having a single
>> cleanup/exit point would make things easier to read; I dunno).
>
> But you're right, of course. Consistency makes for easier-to-read code.

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> >> >  static int reset_head(struct object_id *oid, const char *action,
> >> > -		      const char *switch_to_branch, int detach_head,
> >> > +		      const char *switch_to_branch,
> >> > +		      int detach_head, int reset_hard,
> >> 
> >> It might be worth switching to a single flag variable here. It would
> >> make calls like this:
> >> 
> >> > -	if (reset_head(&options.onto->object.oid, "checkout", NULL, 1,
> >> > +	if (reset_head(&options.onto->object.oid, "checkout", NULL, 1, 0,
> >> >  	    NULL, msg.buf))
> >> 
> >> a little more self-documenting (if a little more verbose).
> >
> > I thought about that, but for just two flags? Well, let me try it and see
> > whether I like the result ;-)
> 
> My rule of thumb is that repeating three times is definitely when we
> should consolidate separate ones into a single flag word, and twice
> is a borderline.
> 
> For two-time repetition, it is often worth fixing when somebody
> notices it during the review, as that is a sign that repetition,
> even a minor one, disturbed a reader enough to point out.

> So I am OK either way, slightly in favor of fixing it while we
> remember.
> 
> 
> >> This one could actually turn into:
> >> 
> >>   ret = error(...);
> >>   goto leave_reset_head;
> >> 
> >> now. We don't have to worry about an uninitialized desc.buffer anymore
> >> (as I mentioned in the previous email), because "nr" would be 0.
> >> 
> >> It doesn't save any lines, though (but maybe having a single
> >> cleanup/exit point would make things easier to read; I dunno).
> >
> > But you're right, of course. Consistency makes for easier-to-read code.
> 
> Yup, that does sound good.
> 
> Thanks.
> 

>> On the other hand, for a file-scope static that is likely to stay as a
>> non-API function but a local helper, it may not be worth it.
>
> Oh, do you think that `reset_head()` is likely to stay as non-API
> function? I found myself in the need of repeating this tedious
> unpack_trees() dance quite a few times over the past two years, and it is
> *always* daunting because the API is *that* unintuitive.
>
> So I *do* hope that `reset_head()` will actually be moved to reset.[ch]
> eventually, and callsites e.g. in `sequencer.c` will be converted from
> calling `unpack_trees()` to calling `reset_head()` instead.

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
>
>>> On the other hand, for a file-scope static that is likely to stay as a
>>> non-API function but a local helper, it may not be worth it.
>>
>> Oh, do you think that `reset_head()` is likely to stay as non-API
>> function? I found myself in the need of repeating this tedious
>> unpack_trees() dance quite a few times over the past two years, and it is
>> *always* daunting because the API is *that* unintuitive.
>>
>> So I *do* hope that `reset_head()` will actually be moved to reset.[ch]
>> eventually, and callsites e.g. in `sequencer.c` will be converted from
>> calling `unpack_trees()` to calling `reset_head()` instead.
>
> As long as the public API function is well thought out, of course it
> is OK.  Ideally, builtin/reset.c can detect when it is making a hard
> reset to HEAD and call that same function.  Which may or may not
> mean you would also want to tell it to record ORIG_HEAD and remove
> MERGE_HEAD and others), perhaps with another bit in that flag word.

> In our tests with large repositories, we noticed a serious regression of the
> performance of git rebase when using the built-in vs the shell script
> version. It boils down to an incorrect conversion of a git checkout -q:
> instead of using a twoway_merge as git checkout does, we used a oneway_merge 
> as git reset does. The latter, however, calls lstat() on all files listed in
> the index, while the former essentially looks only at the files that are
> different between the given two revisions.
> 
> Let's reinstate the original behavior by introducing a flag to the 
> reset_head() function to indicate whether we want to emulate reset --hard 
> (in which case we use the oneway_merge, otherwise we use twoway_merge).
> 
> Johannes Schindelin (3):
>   rebase: consolidate clean-up code before leaving reset_head()
>   rebase: prepare reset_head() for more flags
>   built-in rebase: reinstate `checkout -q` behavior where appropriate
> 
>  builtin/rebase.c | 79 ++++++++++++++++++++++++++++--------------------
>  1 file changed, 46 insertions(+), 33 deletions(-)

> 
> 
> base-commit: 8858448bb49332d353febc078ce4a3abcc962efe
> Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-72%2Fdscho%2Fbuiltin-rebase-perf-regression-v2
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-72/dscho/builtin-rebase-perf-regression-v2
> Pull-Request: https://github.com/gitgitgadget/git/pull/72
> 
> Range-diff vs v1:
> 
>  1:  64597fe827 ! 1:  28e24d98ab rebase: consolidate clean-up code before leaving reset_head()
>      @@ -11,6 +11,33 @@
>       --- a/builtin/rebase.c
>       +++ b/builtin/rebase.c
>       @@
>      + 	if (switch_to_branch && !starts_with(switch_to_branch, "refs/"))
>      + 		BUG("Not a fully qualified branch: '%s'", switch_to_branch);
>      + 
>      +-	if (hold_locked_index(&lock, LOCK_REPORT_ON_ERROR) < 0)
>      +-		return -1;
>      ++	if (hold_locked_index(&lock, LOCK_REPORT_ON_ERROR) < 0) {
>      ++		ret = -1;
>      ++		goto leave_reset_head;
>      ++	}
>      + 
>      + 	if (!oid) {
>      + 		if (get_oid("HEAD", &head_oid)) {
>      +-			rollback_lock_file(&lock);
>      +-			return error(_("could not determine HEAD revision"));
>      ++			ret = error(_("could not determine HEAD revision"));
>      ++			goto leave_reset_head;
>      + 		}
>      + 		oid = &head_oid;
>      + 	}
>      +@@
>      + 		unpack_tree_opts.reset = 1;
>      + 
>      + 	if (read_index_unmerged(the_repository->index) < 0) {
>      +-		rollback_lock_file(&lock);
>      +-		return error(_("could not read index"));
>      ++		ret = error(_("could not read index"));
>      ++		goto leave_reset_head;
>        	}
>        
>        	if (!fill_tree_descriptor(&desc, oid)) {
>      @@ -31,15 +58,17 @@
>        	}
>        
>        	tree = parse_tree_indirect(oid);
>      -@@
>      + 	prime_cache_tree(the_repository->index, tree);
>        
>      - 	if (write_locked_index(the_repository->index, &lock, COMMIT_LOCK) < 0)
>      +-	if (write_locked_index(the_repository->index, &lock, COMMIT_LOCK) < 0)
>      ++	if (write_locked_index(the_repository->index, &lock, COMMIT_LOCK) < 0) {
>        		ret = error(_("could not write index"));
>       -	free((void *)desc.buffer);
>      - 
>      - 	if (ret)
>      +-
>      +-	if (ret)
>       -		return ret;
>       +		goto leave_reset_head;
>      ++	}
>        
>        	reflog_action = getenv(GIT_REFLOG_ACTION_ENVIRONMENT);
>        	strbuf_addf(&msg, "%s: ", reflog_action ? reflog_action : "rebase");
>  -:  ---------- > 2:  db963b2094 rebase: prepare reset_head() for more flags
>  2:  070092b430 ! 3:  a7360b856f built-in rebase: reinstate `checkout -q` behavior where appropriate
>      @@ -20,15 +20,18 @@
>       @@
>        #define GIT_REFLOG_ACTION_ENVIRONMENT "GIT_REFLOG_ACTION"
>        
>      + #define RESET_HEAD_DETACH (1<<0)
>      ++#define RESET_HEAD_HARD (1<<1)
>      + 
>        static int reset_head(struct object_id *oid, const char *action,
>      --		      const char *switch_to_branch, int detach_head,
>      -+		      const char *switch_to_branch,
>      -+		      int detach_head, int reset_hard,
>      + 		      const char *switch_to_branch, unsigned flags,
>        		      const char *reflog_orig_head, const char *reflog_head)
>        {
>      + 	unsigned detach_head = flags & RESET_HEAD_DETACH;
>      ++	unsigned reset_hard = flags & RESET_HEAD_HARD;
>        	struct object_id head_oid;
>       -	struct tree_desc desc;
>      -+	struct tree_desc desc[2];
>      ++	struct tree_desc desc[2] = { { NULL }, { NULL } };
>        	struct lock_file lock = LOCK_INIT;
>        	struct unpack_trees_options unpack_tree_opts;
>        	struct tree *tree;
>      @@ -42,18 +45,18 @@
>        	if (switch_to_branch && !starts_with(switch_to_branch, "refs/"))
>        		BUG("Not a fully qualified branch: '%s'", switch_to_branch);
>       @@
>      - 	if (hold_locked_index(&lock, LOCK_REPORT_ON_ERROR) < 0)
>      - 		return -1;
>      + 		goto leave_reset_head;
>      + 	}
>        
>       -	if (!oid) {
>       -		if (get_oid("HEAD", &head_oid)) {
>      --			rollback_lock_file(&lock);
>      --			return error(_("could not determine HEAD revision"));
>      +-			ret = error(_("could not determine HEAD revision"));
>      +-			goto leave_reset_head;
>       -		}
>       -		oid = &head_oid;
>      -+	if (get_oid("HEAD", &head_oid)) {
>      -+		rollback_lock_file(&lock);
>      -+		return error(_("could not determine HEAD revision"));
>      ++	if ((!oid || !reset_hard) && get_oid("HEAD", &head_oid)) {
>      ++		ret = error(_("could not determine HEAD revision"));
>      ++		goto leave_reset_head;
>        	}
>        
>       +	if (!oid)
>      @@ -70,7 +73,7 @@
>        	unpack_tree_opts.merge = 1;
>        	if (!detach_head)
>       @@
>      - 		return error(_("could not read index"));
>      + 		goto leave_reset_head;
>        	}
>        
>       -	if (!fill_tree_descriptor(&desc, oid)) {
>      @@ -104,7 +107,8 @@
>        		string_list_clear(&merge_rr, 1);
>        
>       -		if (reset_head(NULL, "reset", NULL, 0, NULL, NULL) < 0)
>      -+		if (reset_head(NULL, "reset", NULL, 0, 1, NULL, NULL) < 0)
>      ++		if (reset_head(NULL, "reset", NULL, RESET_HEAD_HARD,
>      ++			       NULL, NULL) < 0)
>        			die(_("could not discard worktree changes"));
>        		if (read_basic_state(&options))
>        			exit(1);
>      @@ -113,7 +117,8 @@
>        			exit(1);
>        		if (reset_head(&options.orig_head, "reset",
>       -			       options.head_name, 0, NULL, NULL) < 0)
>      -+			       options.head_name, 0, 1, NULL, NULL) < 0)
>      ++			       options.head_name, RESET_HEAD_HARD,
>      ++			       NULL, NULL) < 0)
>        			die(_("could not move back to %s"),
>        			    oid_to_hex(&options.orig_head));
>        		ret = finish_rebase(&options);
>      @@ -122,34 +127,7 @@
>        			printf(_("Created autostash: %s\n"), buf.buf);
>        			if (reset_head(&head->object.oid, "reset --hard",
>       -				       NULL, 0, NULL, NULL) < 0)
>      -+				       NULL, 0, 1, NULL, NULL) < 0)
>      ++				       NULL, RESET_HEAD_HARD, NULL, NULL) < 0)
>        				die(_("could not reset --hard"));
>        			printf(_("HEAD is now at %s"),
>        			       find_unique_abbrev(&head->object.oid,
>      -@@
>      - 				strbuf_addf(&buf, "rebase: checkout %s",
>      - 					    options.switch_to);
>      - 				if (reset_head(&oid, "checkout",
>      --					       options.head_name, 0,
>      -+					       options.head_name, 0, 0,
>      - 					       NULL, NULL) < 0) {
>      - 					ret = !!error(_("could not switch to "
>      - 							"%s"),
>      -@@
>      - 			 "it...\n"));
>      - 
>      - 	strbuf_addf(&msg, "rebase: checkout %s", options.onto_name);
>      --	if (reset_head(&options.onto->object.oid, "checkout", NULL, 1,
>      -+	if (reset_head(&options.onto->object.oid, "checkout", NULL, 1, 0,
>      - 	    NULL, msg.buf))
>      - 		die(_("Could not detach HEAD"));
>      - 	strbuf_release(&msg);
>      -@@
>      - 		strbuf_addf(&msg, "rebase finished: %s onto %s",
>      - 			options.head_name ? options.head_name : "detached HEAD",
>      - 			oid_to_hex(&options.onto->object.oid));
>      --		reset_head(NULL, "Fast-forwarded", options.head_name, 0,
>      -+		reset_head(NULL, "Fast-forwarded", options.head_name, 0, 0,
>      - 			   "HEAD", msg.buf);
>      - 		strbuf_release(&msg);
>      - 		ret = !!finish_rebase(&options);
> 
> -- 
> gitgitgadget
>