Fix built-in rebase perf regression

builtin/rebase.c +0 -0

index 0ee06aa363..6f6d7de156 100644

builtin/rebase.c +1 -2

@@ -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");

Quoted 5 lines · Johannes Schindelin via GitGitGadget

builtin/rebase.c +0 -0

index 0ee06aa363..6f6d7de156 100644

builtin/rebase.c static int reset_head(struct object_id *oid, const char *action, · line 574

Quoted 10 lines

builtin/rebase.c +2 -4

@@ -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.

There are a few earlier conditionals in reset_head() that do only rollback_lock_file() that could similarly be converted to use the goto. But they would need desc.buffer to be initialized to NULL. I could go either way on converting them or not.

Quoted 16 lines

builtin/rebase.c +1 -2

@@ -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);
 	}
 

builtin/rebase.c static int reset_head(struct object_id *oid, const char *action, · line 625

Quoted 5 lines

builtin/rebase.c +3 -0

+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.

So overall looks good to me.

From: Johannes Schindelin <[email protected]>

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.

Quoted 10 lines · Johannes Schindelin via GitGitGadget

From: Johannes Schindelin <[email protected]>

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.

Quoted 1 line

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.

builtin/rebase.c finished_rebase: · line 527

Quoted 11 lines

builtin/rebase.c +2 -1

index 6f6d7de156..c1cc50f3f8 100644
@@ -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:

builtin/rebase.c int cmd_rebase(int argc, const char **argv, const char *prefix) · line 1510

Quoted 3 lines

builtin/rebase.c +1 -1

-	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).

builtin/rebase.c static int reset_head(struct object_id *oid, const char *action, · line 551

Quoted 10 lines

builtin/rebase.c +3 -6

-	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).

Take all my comments as observations, not objections. This looks OK to me either way.

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.

Quoted 11 lines · Johannes Schindelin

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. :)

Quoted 8 lines

builtin/rebase.c finished_rebase: · line 527

Quoted 4 lines

static int reset_head(struct object_id *oid, const char *action,

builtin/rebase.c +2 -1

-		      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:

Quoted 5 lines

builtin/rebase.c int cmd_rebase(int argc, const char **argv, const char *prefix) · line 1510

Quoted 3 lines

builtin/rebase.c +1 -1

-	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 ;-)

Quoted 5 lines

This one could actually turn into:

  ret = error(...);
  goto leave_reset_head;

Quoted 5 lines

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.

Quoted 8 lines · Johannes Schindelin

Quoted 8 lines

builtin/rebase.c finished_rebase: · line 527

Quoted 4 lines

static int reset_head(struct object_id *oid, const char *action,

builtin/rebase.c +2 -1

-		      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:

Quoted 8 lines

Quoted 5 lines

builtin/rebase.c int cmd_rebase(int argc, const char **argv, const char *prefix) · line 1510

Quoted 3 lines

builtin/rebase.c +1 -1

-	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.

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.

So I am OK either way, slightly in favor of fixing it while we remember.

Quoted 5 lines

Quoted 5 lines

This one could actually turn into:

  ret = error(...);
  goto leave_reset_head;

Quoted 7 lines

Quoted 5 lines

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.

Quoted 2 lines

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.

Quoted 11 lines · Johannes Schindelin

Quoted 2 lines

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);

Signature · 1 line

gitgitgadget