From: "Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: "Christian Couder" <chriscool@tuxfamily.org>,
"Derrick Stolee" <dstolee@microsoft.com>,
"Emily Shaffer" <emilyshaffer@google.com>,
"Eric Sunshine" <sunshine@sunshineco.com>,
"Jeff King" <peff@peff.net>,
"Johannes Schindelin" <Johannes.Schindelin@gmx.de>,
"Jonathan Nieder" <jrnieder@gmail.com>,
"Jonathan Tan" <jonathantanmy@google.com>,
"Junio C Hamano" <gitster@pobox.com>,
"Phillip Wood" <phillip.wood@dunelm.org.uk>,
"René Scharfe" <l.s.r@web.de>, "Taylor Blau" <me@ttaylorr.com>,
"Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
"Elijah Newren" <newren@gmail.com>,
"Elijah Newren" <newren@gmail.com>
Subject: [PATCH 1/2] Change default merge backend from recursive to ort
Date: Wed, 04 Aug 2021 05:38:01 +0000 [thread overview]
Message-ID: <4a0f088f3669a95c7f75e885d06c0a3bdaf31f42.1628055482.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.1011.git.1628055482.gitgitgadget@gmail.com>
From: Elijah Newren <newren@gmail.com>
There are a few reasons to switch the default:
* Correctness
* Extensibility
* Performance
I'll provide some summaries about each.
=== Correctness ===
The original impetus for a new merge backend was to fix issues that were
difficult to fix within recursive's design. The success with this goal
is perhaps most easily demonstrated by running the following:
$ git grep -2 KNOWN_FAILURE t/ | grep -A 4 GIT_TEST_MERGE_ALGORITHM
$ git grep test_expect_merge_algorithm.failure.success t/
$ git grep test_expect_merge_algorithm.success.failure t/
In order, these greps show:
* Seven sets of submodule tests (10 total tests) that fail with
recursive but succeed with ort
* 22 other tests that fail with recursive, but succeed with ort
* 0 tests that pass with recursive, but fail with ort
=== Extensibility ===
Being able to perform merges without touching the working tree or index
makes it possible to create new features that were difficult with the
old backend:
* Merging, cherry-picking, rebasing, reverting in bare repositories...
or just on branches that aren't checked out.
* `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)
* A --remerge-diff option for log/show, used to show diffs for merges
that display the difference between what an automatic merge would
have created and what was recorded in the merge. (This option will
often result in an empty diff because many merges are clean, but for
the non-clean ones it will show how conflicts were fixed including
the removal of conflict markers, and also show additional changes
made outside of conflict regions to e.g. fix semantic conflicts.)
* A --remerge-diff-only option for log/show, similar to --remerge-diff
but also showing how cherry-picks or reverts differed from what an
automatic cherry-pick or revert would provide.
The last three have been implemented already (though only one has been
submitted upstream so far; the others were waiting for performance work
to complete), and I still plan to implement the first one.
=== Performance ===
I'll quote from the summary of my final optimization for merge-ort
(while fixing the testcase name from 'no-renames' to 'few-renames'):
Timings
Infinite
merge- merge- Parallelism
recursive recursive of rename merge-ort
v2.30.0 current detection current
---------- --------- ----------- ---------
few-renames: 18.912 s 18.030 s 11.699 s 198.3 ms
mega-renames: 5964.031 s 361.281 s 203.886 s 661.8 ms
just-one-mega: 149.583 s 11.009 s 7.553 s 264.6 ms
Speedup factors
Infinite
merge- merge- Parallelism
recursive recursive of rename
v2.30.0 current detection merge-ort
---------- --------- ----------- ---------
few-renames: 1 1.05 1.6 95
mega-renames: 1 16.5 29 9012
just-one-mega: 1 13.6 20 565
And, for partial clone users:
Factor reduction in number of objects needed
Infinite
merge- merge- Parallelism
recursive recursive of rename
v2.30.0 current detection merge-ort
---------- --------- ----------- ---------
mega-renames: 1 1 1 181.3
Signed-off-by: Elijah Newren <newren@gmail.com>
---
builtin/merge.c | 10 ++++++++--
builtin/rebase.c | 2 +-
sequencer.c | 4 ++--
3 files changed, 11 insertions(+), 5 deletions(-)
diff --git a/builtin/merge.c b/builtin/merge.c
index d7b14bf4a7f..fbe21d413c1 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -88,9 +88,9 @@ static int autostash;
static int no_verify;
static struct strategy all_strategy[] = {
- { "recursive", DEFAULT_TWOHEAD | NO_TRIVIAL },
+ { "recursive", NO_TRIVIAL },
{ "octopus", DEFAULT_OCTOPUS },
- { "ort", NO_TRIVIAL },
+ { "ort", DEFAULT_TWOHEAD | NO_TRIVIAL },
{ "resolve", 0 },
{ "ours", NO_FAST_FORWARD | NO_TRIVIAL },
{ "subtree", NO_FAST_FORWARD | NO_TRIVIAL },
@@ -1484,6 +1484,12 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
fast_forward = FF_NO;
}
+ if (!use_strategies && !pull_twohead &&
+ remoteheads && !remoteheads->next) {
+ char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
+ if (default_strategy)
+ append_strategy(get_strategy(default_strategy));
+ }
if (!use_strategies) {
if (!remoteheads)
; /* already up-to-date */
diff --git a/builtin/rebase.c b/builtin/rebase.c
index 12f093121d9..587a2f1d299 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -1713,7 +1713,7 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
int i;
if (!options.strategy)
- options.strategy = "recursive";
+ options.strategy = "ort";
strbuf_reset(&buf);
for (i = 0; i < strategy_options.nr; i++)
diff --git a/sequencer.c b/sequencer.c
index a4e5c43fcf2..d08ddae52fa 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, "ort")) {
memset(&result, 0, sizeof(result));
merge_incore_nonrecursive(&o, base_tree, head_tree, next_tree,
&result);
@@ -3988,7 +3988,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, "ort")) {
/*
* TODO: Should use merge_incore_recursive() and
* merge_switch_to_result(), skipping the call to
--
gitgitgadget
next prev parent reply other threads:[~2021-08-04 5:38 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-04 5:38 [PATCH 0/2] Switch default merge backend from recursive to ort Elijah Newren via GitGitGadget
2021-08-04 5:38 ` Elijah Newren via GitGitGadget [this message]
2021-08-09 17:38 ` [PATCH 1/2] Change " Phillip Wood
2021-08-09 21:01 ` Elijah Newren
2021-08-04 5:38 ` [PATCH 2/2] Update docs for change of default merge backend Elijah Newren via GitGitGadget
2021-08-04 14:26 ` Derrick Stolee
2021-08-04 14:27 ` [PATCH 0/2] Switch default merge backend from recursive to ort Derrick Stolee
-- strict thread matches above, loose matches on Subject: below --
2021-08-01 0:07 [PATCH 0/2] [RFC] " Elijah Newren via GitGitGadget
2021-08-01 0:07 ` [PATCH 1/2] Change " Elijah Newren via GitGitGadget
2021-08-02 15:55 ` Ævar Arnfjörð Bjarmason
2021-08-02 16:33 ` Elijah Newren
2021-08-02 22:46 ` Johannes Schindelin
2021-08-03 1:04 ` Elijah Newren
2021-08-03 2:56 ` Philippe Blain
2021-08-03 3:39 ` Elijah Newren
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4a0f088f3669a95c7f75e885d06c0a3bdaf31f42.1628055482.git.gitgitgadget@gmail.com \
--to=gitgitgadget@gmail.com \
--cc=Johannes.Schindelin@gmx.de \
--cc=avarab@gmail.com \
--cc=chriscool@tuxfamily.org \
--cc=dstolee@microsoft.com \
--cc=emilyshaffer@google.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=jonathantanmy@google.com \
--cc=jrnieder@gmail.com \
--cc=l.s.r@web.de \
--cc=me@ttaylorr.com \
--cc=newren@gmail.com \
--cc=peff@peff.net \
--cc=phillip.wood@dunelm.org.uk \
--cc=sunshine@sunshineco.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.