Switch default merge backend from recursive to ort

sequencer.c static int do_merge(struct repository *r, · line 3974

Quoted 11 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>
[...]

sequencer.c +1 -1

@@ -3968,7 +3968,7 @@ static int do_merge(struct repository *r,
      o.branch2 = ref_name.buf;
      o.buffer_output = 2;
 
-     if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+     if (!opts->strategy || strcmp(opts->strategy, "recursive")) {
              /*
               * TODO: Should use merge_incore_recursive() and
               * merge_switch_to_result(), skipping the call to

I might spot more tiny issues, but it looks like our error messaging needs updating for 14c4586c2df (merge,rebase,revert: select ort or recursive by config or environment, 2020-11-02).

I.e. we die on "Unknown option for merge-recursive", presumably that should be updated to indicate that we might call one of merge_recursive() or merge_ort_recursive() now.

And perhaps this in sequencer.c:

that represents the "current" state for merge-recursive[...]

From: Elijah Newren <[email protected]>

There are a few reasons to switch the default:
[...]

sequencer.c +0 -1

 		/*
 		 * TODO: Should use merge_incore_recursive() and
 		 * merge_switch_to_result(), skipping the call to
--

gitgitgadget

Hi Elijah,

Quoted 4 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

There are a few reasons to switch the default:
[...]

I think it would be really fantastic to change to the new default right after v2.33.0.

As to the patch, I only struggled slightly with the changes to sequencer.c:

sequencer.c static int do_recursive_merge(struct repository *r, · line 639

Quoted 10 lines

sequencer.c +1 -1

index 0bec01cf38e..a98de9a8d15 100644
@@ -636,7 +636,7 @@ static int do_recursive_merge(struct repository *r,
      for (i = 0; i < opts->xopts_nr; i++)
              parse_merge_opt(&o, opts->xopts[i]);
 
-     if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+     if (!opts->strategy || strcmp(opts->strategy, "recursive")) {

At this stage, we're in do_recursive_merge(), and there is only one caller, do_pick_commit(), and the caller is guarded by the following condition:

        else if (!opts->strategy ||
                 !strcmp(opts->strategy, "recursive") ||
                 !strcmp(opts->strategy, "ort") ||
                 command == TODO_REVERT) {

The issue I see is with git revert allowing custom merge strategies. I _think_ we need a slightly different patch here, something like this:

(quoted diff) +1 -1

-       if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+       if (!opts->strategy || !strcmp(opts->strategy, "ort")) {

sequencer.c static int do_merge(struct repository *r, · line 3971

Quoted 10 lines

sequencer.c +1 -1

              memset(&result, 0, sizeof(result));
              merge_incore_nonrecursive(&o, base_tree, head_tree, next_tree,
                                          &result);

@@ -3968,7 +3968,7 @@ static int do_merge(struct repository *r,
      o.branch2 = ref_name.buf;
      o.buffer_output = 2;
 
-     if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+     if (!opts->strategy || strcmp(opts->strategy, "recursive")) {

It took me a while to convince myself that this is correct. At least now I _think_ it is correct: do_merge() defines:

        const char *strategy = !opts->xopts_nr &&
                (!opts->strategy ||
                 !strcmp(opts->strategy, "recursive") ||
                 !strcmp(opts->strategy, "ort")) ?
                NULL : opts->strategy;

and then hands off to git merge -s <strategy> if strategy is set, _before_ this hunk. Therefore we can be pretty certain that opts->strategy is either not set, or "ort", or "recursive" at that stage.

However, I think we could use the same idea I outlined in the previous hunk, to make things more obvious:

(quoted diff) +1 -1

-       if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+       if (!opts->strategy || !strcmp(opts->strategy, "ort")) {

Thank you,
Dscho

Quoted 5 lines

sequencer.c +0 -1

              /*
               * TODO: Should use merge_incore_recursive() and
               * merge_switch_to_result(), skipping the call to
--

gitgitgadget

From: Elijah Newren <[email protected]>

* git diff AUTO_MERGE -- ability to see what changes the user has made to resolve conflicts so far (see commit 5291828df8 ("merge-ort:
write $GIT_DIR/AUTO_MERGE whenever we hit a conflict", 2021-03-20)

The last three have been implemented already (though only one has been submitted upstream so far;

Hi Elijah,

Quoted 10 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

* git diff AUTO_MERGE -- ability to see what changes the user has made to resolve conflicts so far (see commit 5291828df8 ("merge-ort:
write $GIT_DIR/AUTO_MERGE whenever we hit a conflict", 2021-03-20)

The last three have been implemented already (though only one has been submitted upstream so far;

From what I could find this indeed only refers to your 5291828df8 (merge-ort:
write $GIT_DIR/AUTO_MERGE whenever we hit a conflict, 2021-03-20). This is a very nice improvement, but I noticed it is not mentioned in the doc. Do you plan to update the 'git diff' doc to mention that special ref ? (And maybe also gitrevisions(5), where most of the special refs are listed ?)

Do you plan to implement a new '--auto-merge' option to 'git diff' as a shortcut to 'git diff AUTO_MERGE', in order to hide a bit the special ref from users ?

From: Elijah Newren <[email protected]>

Documentation/gitfaq.txt +0 -0

 	performs the merge, it considers exactly three points: the two heads and a
 	third point, called the _merge base_, which is usually the common ancestor of

Documentation/merge-options.txt +2 -2

index eb0aabd396f..72b53188504 100644
@@ -112,8 +112,8 @@ With --squash, --commit is not allowed, and will fail.
 	Use the given merge strategy; can be supplied more than
 	once to specify them in the order they should be tried.
 	If there is no `-s` option, a built-in list of strategies
-	is used instead ('git merge-recursive' when merging a single
-	head, 'git merge-octopus' otherwise).
+	is used instead (`ort` when merging a single head,
+	`octopus` otherwise).
 
 -X <option>::
 --strategy-option=<option>::

Documentation/merge-strategies.txt +5 -20

index 2912de706bf..6caf3fd6486 100644
@@ -6,28 +6,23 @@ backend 'merge strategies' to be chosen with `-s` option.  Some strategies
 can also take their own options, which can be passed by giving `-X<option>`
 arguments to `git merge` and/or `git pull`.
 
-resolve::
-	This can only resolve two heads (i.e. the current branch
-	and another branch you pulled from) using a 3-way merge
-	algorithm.  It tries to carefully detect criss-cross
-	merge ambiguities and is considered generally safe and
-	fast.
-
-recursive::
-	This can only resolve two heads using a 3-way merge
-	algorithm.  When there is more than one common
-	ancestor that can be used for 3-way merge, it creates a
-	merged tree of the common ancestors and uses that as
-	the reference tree for the 3-way merge.  This has been
-	reported to result in fewer merge conflicts without
-	causing mismerges by tests done on actual merge commits
-	taken from Linux 2.6 kernel development history.
-	Additionally this can detect and handle merges involving
-	renames, but currently cannot make use of detected
-	copies.  This is the default merge strategy when pulling
-	or merging one branch.
+ort::
+	This is the default merge strategy when pulling or merging one
+	branch.  This strategy can only resolve two heads using a
+	3-way merge algorithm.  When there is more than one common
+	ancestor that can be used for 3-way merge, it creates a merged

From: Elijah Newren <[email protected]>

Make multiple documentation updates to bring things up to date as we change the default merge backend...

This is an RFC series designed to spur feedback about switching the default merge backend (reviewing the patches is of secondary importance at this point). Some questions:

* Are there things others want before this series is considered for inclusion?
* What kind of timeline do others think is reasonable?
* Would it be beneficial to let this series sit in 'next' for an extended duration to gain more feedback?

Some potentially useful context in relation to the above:

* I've personally used the ort backend for well over a year
* I have ~50 testers using ort as the default merge backend since Nov. 2020.
* ort fixes known bugs in recursive, and there are no known regressions (more testers may change that)
* ort is significantly faster than recursive
* ort provides one new feature already, and enables more that are on the way
* The commit message of patch 1 has more details about the last three items above

So...thoughts?

Quoted 23 lines · Elijah Newren via GitGitGadget

This is an RFC series designed to spur feedback about switching the default merge backend (reviewing the patches is of secondary importance at this point). Some questions:

* Are there things others want before this series is considered for inclusion?
* What kind of timeline do others think is reasonable?
* Would it be beneficial to let this series sit in 'next' for an extended duration to gain more feedback?

Some potentially useful context in relation to the above:

* I've personally used the ort backend for well over a year
* I have ~50 testers using ort as the default merge backend since Nov. 2020.
* ort fixes known bugs in recursive, and there are no known regressions (more testers may change that)
* ort is significantly faster than recursive
* ort provides one new feature already, and enables more that are on the way
* The commit message of patch 1 has more details about the last three items above

Quoted 1 line

So...thoughts?

I fully endorse this change as soon as possible. I've applied the patches you supplied here and submitted a PR to microsoft/git [1] to take them.

[1] https://github.com/microsoft/git/pull/404

I've done my own share of testing on some of our private monorepos to see how ORT compares to the recursive algorithm. My data is not perhaps as rigorous as yours, but I did notice that the ORT algorithm was consistently within the 5-6 second range while the recursive algorithm would vary within the 7-20 second range (and some outliers near 30s).

Of course, I'm particularly excited about the benefits to the sparse index work. I also have a prototype of a 'git merge' integration with sparse index which was not very hard because the ORT strategy does not use the index as a data structure. With that change, my tests dropped to between 0.5s and 1.5 seconds. (This shows just how much my earlier timings were stuck on index reads and writes.) Now, the largest indicator of time is how long it takes to resolve text conflicts.

Thanks! What a monumental effort.

Quoted 5 lines · Derrick Stolee

I've done my own share of testing on some of our private monorepos to see how ORT compares to the recursive algorithm. My data is not perhaps as rigorous as yours, but I did notice that the ORT algorithm was consistently within the 5-6 second range while the recursive algorithm would vary within the 7-20 second range (and some outliers near 30s).

One quick question on your timings here, though: in the past, when you compared timings, you compared merge-recursive *without* rename detection to merge-ort *with* rename detection. Are you doing the same here (just so others have a better sense of what is being compared)?

This is an RFC series designed to spur feedback about switching the default merge backend (reviewing the patches is of secondary importance at this point). Some questions:

* Are there things others want before this series is considered for inclusion?
* What kind of timeline do others think is reasonable?
* Would it be beneficial to let this series sit in 'next' for an extended duration to gain more feedback?

Quoted 9 lines · Elijah Newren via GitGitGadget

This is an RFC series designed to spur feedback about switching the default merge backend (reviewing the patches is of secondary importance at this point). Some questions:

* Are there things others want before this series is considered for inclusion?
* What kind of timeline do others think is reasonable?
* Would it be beneficial to let this series sit in 'next' for an extended duration to gain more feedback?

It looks like others gave some more specific review on the patches, but on the meta-topic of "do we switch, and when", my response is: yes, and soon. :)

Having watched the development of merge-ort, plus all of the weird corner cases in merge-recursive we've seen over the years (many of which you found and added tests for while working on merge-ort!), my gut feeling is that the switch is _much_ more likely to fix problems people might see in the wild rather than cause them.

It would make sense to me to do the switch in 'next' early in the post-v2.33 cycle. It can cook there for a bit, but I think we have found that it's much more likely to see actual use once it hits 'master'. So I don't see a particular reason to have it sit in 'next' for a long time. We should get as much exposure in 'master' during the v2.34 cycle as possible.

The nice thing is that the two strategies can co-exist. So if it does turn out to have any regressions, it's an easy revert to switch back, and even post-release users can switch at runtime. We have pull.twohead, but I don't think we have an equivalent that would impact a bare "git merge" or "git rebase -m". Maybe it would be worth adding those as an escape hatch?

Quoted 6 lines

The nice thing is that the two strategies can co-exist. So if it does turn out to have any regressions, it's an easy revert to switch back, and even post-release users can switch at runtime. We have pull.twohead, but I don't think we have an equivalent that would impact a bare "git merge" or "git rebase -m". Maybe it would be worth adding those as an escape hatch?

Actually, pull.twohead is not pull specific; it already affects merge, rebase (-m is the default for rebase, btw), cherry-pick, and revert. pull.twohead has affected a bare "git merge" since 1c7b76be7d ("Build in merge", 2008-07-07). I thought it was weird that "merge strategy" for the merge command was specified via a config option under "pull", and included my misgivings about it in the commit message of 14c4586c2d ("merge,rebase,revert: select ort or recursive by config or environment", 2020-11-02) when I made sequencer.c pay attention to that config option as well:

"""
Also, allow folks to pick the new algorithm via config setting. It turns out builtin/merge.c already had a way to allow users to specify a different default merge algorithm: pull.twohead. Rather odd configuration name (especially to be in the 'pull' namespace rather than 'merge') but it's there. Add that same configuration to rebase, cherry-pick, and revert.
"""

But no one had an alternate suggestion or opinion on attempting to migrate the configuration to a different name, so it has just stuck. Anyway, if folks want to try out 'ort' with the 2.32 or 2.33 releases, they can set pull.twohead=ort. Once we switch the default, they can set pull.twohead=recursive to get the old default.

It would make sense to me to do the switch in 'next' early in the post-v2.33 cycle. It can cook there for a bit, but I think we have found that it's much more likely to see actual use once it hits 'master'. So I don't see a particular reason to have it sit in 'next' for a long time. We should get as much exposure in 'master' during the v2.34 cycle as possible.

The nice thing is that the two strategies can co-exist. So if it does turn out to have any regressions, it's an easy revert to switch back, and even post-release users can switch at runtime. We have pull.twohead, but I don't think we have an equivalent that would impact a bare "git merge" or "git rebase -m". Maybe it would be worth adding those as an escape hatch?

Quoted 6 lines · Jeff King

It would make sense to me to do the switch in 'next' early in the post-v2.33 cycle. It can cook there for a bit, but I think we have found that it's much more likely to see actual use once it hits 'master'. So I don't see a particular reason to have it sit in 'next' for a long time. We should get as much exposure in 'master' during the v2.34 cycle as possible.

I do not mind queuing what is available today to 'next' to gain 2 more weeks of dogfood time during the pre-release freeze. If an simple escape hatch that lets us say "anytime we ask ort, use recursive instead as an emergency measure" can be added with a trivially obvious small patch, that would be a plus.

Quoted 9 lines · Junio C Hamano

Quoted 6 lines · Jeff King

It would make sense to me to do the switch in 'next' early in the post-v2.33 cycle. It can cook there for a bit, but I think we have found that it's much more likely to see actual use once it hits 'master'. So I don't see a particular reason to have it sit in 'next' for a long time. We should get as much exposure in 'master' during the v2.34 cycle as possible.

Quoted 5 lines

I do not mind queuing what is available today to 'next' to gain 2 more weeks of dogfood time during the pre-release freeze. If an simple escape hatch that lets us say "anytime we ask ort, use recursive instead as an emergency measure" can be added with a trivially obvious small patch, that would be a plus.

Yeah, I am happy even starting the 'next' portion sooner than the release. :) As Elijah explained, we already have that emergency measure in place (pull.merge).

Quoted 6 lines · Jeff King

It would make sense to me to do the switch in 'next' early in the post-v2.33 cycle. It can cook there for a bit, but I think we have found that it's much more likely to see actual use once it hits 'master'. So I don't see a particular reason to have it sit in 'next' for a long time. We should get as much exposure in 'master' during the v2.34 cycle as possible.

I do not mind queuing what is available today to 'next' to gain 2 more weeks of dogfood time during the pre-release freeze.

If an
simple escape hatch that lets us say "anytime we ask ort, use recursive instead as an emergency measure" can be added with a trivially obvious small patch, that would be a plus.