patch, 2 parts[RFC] Switch default merge backend from recursive to ort

> From: Elijah Newren <newren@gmail.com>
> [...]
> @@ -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

>
> On Sun, Aug 01 2021, Elijah Newren via GitGitGadget wrote:
>
> > From: Elijah Newren <newren@gmail.com>
> > [...]
> > @@ -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.

> diff --git a/sequencer.c b/sequencer.c
> index 0bec01cf38e..a98de9a8d15 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -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")) {

>  		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")) {

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

>
> Hi Elijah,
>
> On Sun, 1 Aug 2021, Elijah Newren via GitGitGadget wrote:
>
> > From: Elijah Newren <newren@gmail.com>
> >
> > 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`:
>
> > diff --git a/sequencer.c b/sequencer.c
> > index 0bec01cf38e..a98de9a8d15 100644
> > --- a/sequencer.c
> > +++ b/sequencer.c
> > @@ -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:
>
> -       if (opts->strategy && !strcmp(opts->strategy, "ort")) {
> +       if (!opts->strategy || !strcmp(opts->strategy, "ort")) {
>
> >               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:
>
> -       if (opts->strategy && !strcmp(opts->strategy, "ort")) {
> +       if (!opts->strategy || !strcmp(opts->strategy, "ort")) {
>
> Thank you,
> Dscho
>
> >               /*
> >                * TODO: Should use merge_incore_recursive() and
> >                * merge_switch_to_result(), skipping the call to
> > --
> > gitgitgadget

> From: Elijah Newren <newren@gmail.com>
> 
> 
>    * `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,
>
> Le 2021-07-31 à 20:07, Elijah Newren via GitGitGadget a écrit :
> > From: Elijah Newren <newren@gmail.com>
> >
> >
> >    * `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 ?

> diff --git a/Documentation/gitfaq.txt b/Documentation/gitfaq.txt
> index afdaeab8503..072bf84fa8a 100644
> --- a/Documentation/gitfaq.txt
> +++ b/Documentation/gitfaq.txt
> @@ -275,7 +275,7 @@ best to always use a regular merge commit.
>  
>  [[merge-two-revert-one]]
>  If I make a change on two branches but revert it on one, why does the merge of those branches include the change?::
> -	By default, when Git does a merge, it uses a strategy called the recursive
> +	By default, when Git does a merge, it uses a strategy called the ort
>  	strategy, which does a fancy three-way merge.  In such a case, when Git

>  	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
> diff --git a/Documentation/merge-options.txt b/Documentation/merge-options.txt
> index eb0aabd396f..72b53188504 100644
> --- a/Documentation/merge-options.txt
> +++ b/Documentation/merge-options.txt
> @@ -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>::
> diff --git a/Documentation/merge-strategies.txt b/Documentation/merge-strategies.txt
> index 2912de706bf..6caf3fd6486 100644
> --- a/Documentation/merge-strategies.txt
> +++ b/Documentation/merge-strategies.txt
> @@ -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
> +	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 strategy can detect
> +	and handle merges involving renames.  It does not make use of
> +	detected copies.  The name for this algorithm is an acronym
> +	("Ostensibly Recursive's Twin") and came from the fact that it
> +	was written as a replacement for the previous default
> +	algorithm, recursive.

>
> From: Elijah Newren <newren@gmail.com>
>
> 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?

>
> On 7/31/2021 8:07 PM, Elijah Newren via GitGitGadget wrote:
> > 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?
>
> 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.

> On Mon, Aug 2, 2021 at 9:05 AM Derrick Stolee <stolee@gmail.com> wrote:
>> 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?

>
> On Sun, Aug 01, 2021 at 12:07:39AM +0000, Elijah Newren via GitGitGadget wrote:
>
> > 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?

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

> Jeff King <peff@peff.net> writes:
> 
> > 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.

>
> On Tue, Aug 03, 2021 at 03:08:53PM -0700, Junio C Hamano wrote:
>
> > Jeff King <peff@peff.net> writes:
> >
> > > 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.
>
> 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).

>
> Jeff King <peff@peff.net> writes:
>
> > 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.