2

I use git by creating a series of feature branches, and merging them to master when they're done with git merge --no-ff. This creates empty merge commits useful to identify start and end points of previous feature branches.

In order to handle multiple concurrent branches, or even nested branches, I use rebase. I never merge back, I always rebase my branches upon the latest commits, test and finally merge with --no-ff once everything is done. With nested branches, I do the same: multiple branches are merged sequentially onto the main branch, which is itself merged to master in the end.

In order to keep information about merges with nested branches, I often use git rebase --preserve-merges. This does exactly what I want and I have no problems with my workflow.

My main problem with git is that git rebase --preserve-merges is very slow (sometimes taking about 2 seconds per commit). After reading What exactly does git's "rebase --preserve-merges" do (and why?) I realize that git must perform a lot of work to preserve the merges, since git has to work on arbitrary graphs.

What I was wondering is this: since my workflow pretty much results in a graph equivalent to a linear history, is there a way to perform a git rebase --preserve-merge equivalent in a faster way, given that I guarantee "linearity" of history with only empty merge commits? I don't mind using scripts or weird commands, as long as the final result is correct.

     A-B-C
    /     \   
(1)--------D-- master
    \
     \---F-----I-- feature
      \ / \   /
       E   G-H

     A-B-C   E   G-H
    /     \ / \ /   \
(2)--------D---F-----I-feature
         master

tl; dr: How to transform (1) into (2) knowing that the underlying history is linear so git rebase --preserve-merges doesn't have to do as much work and does it fast?

Svalorzen
  • 5,353
  • 3
  • 30
  • 54

2 Answers2

2

You might be able to speed it all up a little bit by rewriting it from a bash script to something more clever (e.g., in Python, run git rev-list --parents with an appropriate set of revision delimiters, and collect up all the parent information before beginning the copy operations), but fundamentally it's just hard. As the answer in that other link notes in passing, git rebase -p also doesn't exactly preserve merges so much as re-create them. In the fully general case—which I know you're ignoring in favor of more limited special cases; I only mention this for completeness—git rebase -p fails completely on merges that have had special options or processing applied (--no-commit merges with manual modifications to produce an "evil merge", or merges run with -X rename-threshold or -X ours or similar), since the special-case information is, in effect, only stored in the resulting tree. The rebase code does not even look for it (this would take much longer: it would have to reproduce the original merge first just to see if a no-option merge would have re-created the original result).

All that aside, the speed (or lack of speed) of these options depends on the size of your repository and its files, and whether you use Windows (extremely slow) or a Unixish system (much faster). There is no reason I know of that Windows should be so terribly slow to run scripts, but clearly it is, because the Git folks keep rewriting things in C to make them perform acceptably on Windows because the scripts are so slow.

Hence, if you're doing this on Windows, one way to speed it up a lot is to stop using Windows. :-) (You could do this just for the duration of the rebase itself, using git push and git fetch to coordinate between Windows and Linux-or-whatever.)

torek
  • 448,244
  • 59
  • 642
  • 775
  • Unfortunately I'm on Ubuntu, so I don't think it depends on that. The repo where I last had this problem was used by many people with a messy history, so that could have been a factor in the slowness of the command. However, I disagree that in my special case it's difficult: a simple `git rebase` does it correctly very fast; my only difference would be that instead of skipping the merge commits it should copy/recreate them. Shouldn't be that hard, right? – Svalorzen Oct 02 '17 at 14:10
  • In a big repository, I have seen `git merge` itself take 30 minutes. Presumably yours is not *this* big, but repeating a merge could be the culprit. Since interactive rebase is (or was mostly, it's starting to change in Git) a shell script, you could find out by setting the `-x` flag and watching it operate, to see where the delays are. – torek Oct 02 '17 at 14:54
  • `git rev-list --parents` does not work saying `usage: git rev-list [OPTION] ... [ -- paths... ]` – alper Jul 03 '21 at 21:44
  • 1
    @alper: `git rev-list --parents HEAD` works fine for me. Did you forget to give `git rev-list` a starting point commit? I forgot to mention that this is required. :-) – torek Jul 04 '21 at 06:28
1

Reminder (2021)

IMPORTANT
Starting Git 2.22, Q2 2019, the old rebase script is no more

Original answer 2018:

My main problem with git is that git rebase --preserve-merges is very slow

That might not be so slow with Git 2.20+ (Q4 2018), considering it includes a rewrite of the "rebase" machinery in C.
No more shell script.

IMPORTANT
Again, let's be clear: starting Git 2.22, Q2 2019, the old rebase script is no more

See commit ac7f467, commit c7b64aa, commit 55071ea (06 Aug 2018) by Pratik Karki (prertik).
(Merged by Junio C Hamano -- gitster -- in commit 5ae5084, 02 Nov 2018)

rebase: start implementing it as a builtin

This commit imitates the strategy that was used to convert the difftool to a builtin.
We start by renaming the shell script git-rebase.sh to git-legacy-rebase.sh and introduce a builtin/rebase.c that simply executes the shell script version, unless the config setting rebase.useBuiltin is set to true.

The motivation behind this is to rewrite all the functionality of the shell script version in the aforementioned rebase.c, one by one and be able to conveniently test new features by configuring rebase.useBuiltin.

In the original difftool conversion, if sane_execvp() that attempts to run the legacy scripted version returned with non-negative status, the command silently exited without doing anything with success, but sane_execvp() should not return with non-negative status in the first place, so we use die() to notice such an abnormal case.

We intentionally avoid reading the config directly to avoid messing up the GIT_* environment variables when we need to fall back to exec()ing the shell script.

See commit 62c2393, commit d8d0a54 (14 Nov 2018) by Ævar Arnfjörð Bjarmason (avar).
(Merged by Junio C Hamano -- gitster -- in commit 4520c23, 18 Nov 2018)

The documentation now states:

rebase.useBuiltin:

Set to false to use the legacy shellscript implementation if git rebase.
Is true by default, which means use the built-in rewrite of it in C.

The C rewrite is first included with Git version 2.20.
This option serves an an escape hatch to re-enable the legacy version in case any bugs are found in the rewrite.
This option and the shellscript version git-rebase will be removed in some future release.

If you find some reason to set this option to false other than one-off testing you should report the behavior difference as a bug in git.

With Git 2.21 (Feb. 2019), "git rebase --merge" as been reimplemented by reusing the internal machinery used for "git rebase -i".

See commit 68aa495, commit c91c944, commit 7b76ac6, commit 899b49c, commit 45339f7, commit 5400677, commit 72ee673, commit c913c59 (11 Dec 2018) by Elijah Newren (newren).
(Merged by Junio C Hamano -- gitster -- in commit 8fe9c3f, 07 Feb 2019)

rebase: implement --merge via the interactive machinery

As part of an ongoing effort to make rebase have more uniform behavior, modify the merge backend to behave like the interactive one, by re-implementing it on top of the latter.

Interactive rebases are implemented in terms of cherry-pick rather than the merge-recursive builtin, but cherry-pick also calls into the recursive merge machinery by default and can accept special merge strategies and/or special strategy options.
As such, there really is not any need for having both git-rebase--merge and git-rebase--interactive anymore.
Delete git-rebase--merge.sh and instead implement it in builtin/rebase.c.

rebase: define linearization ordering and enforce it

See commit c91c944 on performance.

Also, still Git 2.21 (Feb. 2019): "git rebase --merge" as been reimplemented by reusing the internal machinery used for "git rebase -i".

See commit 29d03f8 (14 Feb 2019) by Elijah Newren (newren).
(Merged by Junio C Hamano -- gitster -- in commit 6f07c7b, 14 Feb 2019)

rebase: implement --merge via the interactive machinery

As part of an ongoing effort to make rebase have more uniform behavior, modify the merge backend to behave like the interactive one, by re-implementing it on top of the latter.

Interactive rebases are implemented in terms of cherry-pick rather than the merge-recursive builtin, but cherry-pick also calls into the recursive merge machinery by default and can accept special merge strategies and/or special strategy options.
As such, there really is not any need for having both git-rebase--merge and git-rebase--interactive anymore.
Delete git-rebase--merge.sh and instead implement it in builtin/rebase.c.

This results in a few deliberate but small user-visible changes:

  • The progress output is modified (see t3406 and t3420 for examples)
  • A few known test failures are now fixed (see t3421)
  • bash-prompt during a rebase --merge is now REBASE-i instead of REBASE-m.
    Reason: The prompt is a reflection of the backend in use; this allows users to report an issue to the git mailing list with the appropriate backend information, and allows advanced users to know where to search for relevant control files. (see t9903)

Since "git rebase --preserve-merge" as been reimplemented by reusing the internal machinery used for "git rebase -i", this Git 2.22 (Q2 2019) patch is of interest:

See commit 460bc3c, commit 297b1e1, commit 0ea0847, commit 73fdc53, commit 3389853, commit 7d3488e, commit c44c246, commit 0609b74, commit 6023c92, commit 28dc09d, commit 146839c (17 Apr 2019), and commit fc4a673 (19 Mar 2019) by Phillip Wood (phillipwood).
(Merged by Junio C Hamano -- gitster -- in commit 7ba06bc, 13 May 2019)

rebase -i: run without forking rebase --interactive

When the builtin rebase starts an interactive rebase it parses the options and then repackages them and forks rebase--interactive.
Separate the option parsing in cmd_rebase__interactive() from the business logic to allow interactive rebases can be run without forking rebase__interactive by calling run_rebase_interactive() directly.

Starting interactive rebases without forking makes it easy to debug the sequencer without worrying about attaching to child processes.
Ævar has also reported that some of the rebase perf tests are 30% faster.

This patch also makes it easy to remove cmd_rebase__interactive() in the future when git-legacy-rebase.sh and git-rebase--preserve-merges.sh are retired.

"git rebase -i" (and friends) used to unnecessarily check out the tip of the branch to be rebased, which has been corrected with Git 2.26 (Q1 2020),

See commit 767a9c4 (24 Jan 2020) by Alban Gruin (``).
(Merged by Junio C Hamano -- gitster -- in commit d8b8d59, 14 Feb 2020)

rebase -i: stop checking out the tip of the branch to rebase

Reported-by: SZEDER Gábor
Signed-off-by: Alban Gruin

One of the first things done when using a sequencer-based rebase (ie. rebase -i, rebase -r, or rebase -m) is to make a todo list.

This requires knowledge of the commit range to rebase.

To get the oid of the last commit of the range, the tip of the branch to rebase is checked out with prepare_branch_to_be_rebased(), then the oid of the head is read.

After this, the tip of the branch is not even modified. The `am' backend, on the other hand, does not check out the branch.

On big repositories, it's a performance penalty: with rebase -i', the user may have to wait before editing the todo list while git is extracting the branch silently, and "quiet" rebases will be slower than am'.

Since we already have the oid of the tip of the branch in opts->orig_head, it's useless to switch to this commit.

This removes the call to prepare_branch_to_be_rebased() in do_interactive_rebase(), and adds a orig_head' parameter to get_revision_ranges()`.

prepare_branch_to_be_rebased() is removed as it is no longer used.

This introduces a visible change: as we do not switch on the tip of the branch to rebase, no reflog entry is created at the beginning of the rebase for it.

Unscientific performance measurements, performed on linux.git, are as follow:

Before this patch:

$ time git rebase -m --onto v4.18 463fa44eec2fef50~ 463fa44eec2fef50

real    0m8,940s
user    0m6,830s
sys     0m2,121s

After this patch:

$ time git rebase -m --onto v4.18 463fa44eec2fef50~ 463fa44eec2fef50

real    0m1,834s
user    0m0,916s
sys     0m0,206s

As notes with Git 2.26 (Q1 2020), "git rebase" has learned to use the merge backend (i.e. the machinery that drives "rebase -i") by default, while allowing "--apply" option to use the "apply" backend (e.g. the moral equivalent of "format-patch piped to am").

The rebase.backend configuration variable can be set to customize.

See commit 10cdb9f, commit 2ac0d62, commit 8295ed6, commit 76340c8, commit 980b482, commit c2417d3, commit 6d04ce7, commit 52eb738, commit 8af14f0, commit be50c93, commit befb89c, commit 9a70f3d, commit 93122c9, commit 55d2b6d, commit 8a997ed, commit 7db00f0, commit e98c426, commit d48e5e2 (15 Feb 2020), and commit a9ae8fd, commit 22a69fd (16 Jan 2020) by Elijah Newren (newren).
(Merged by Junio C Hamano -- gitster -- in commit 8c22bd9, 02 Mar 2020)

rebase: rename the two primary rebase backends

Signed-off-by: Elijah Newren

Rename the 'interactive' backend to 'merge' because:

  • 'interactive' as a name caused confusion; this backend has been used for many kinds of non-interactive rebases, and will probably be used in the future for more non-interactive rebases than interactive ones given that we are making it the default.
  • 'interactive' is not the underlying strategy; merging is.
  • the directory where state is stored is not called .git/rebase-interactive but .git/rebase-merge.

With Git 2.27 (Q2 2020), you can also allow "git rebase" to reapply all local commits, even if the may be already in the upstream, without checking first.

git rebase --reapply-cherry-picks

That would accelerate the rebase process.

See commit 0fcb4f6 (11 Apr 2020) by Jonathan Tan (jhowtan).
(Merged by Junio C Hamano -- gitster -- in commit d6d561d, 22 Apr 2020)

rebase --merge: optionally skip upstreamed commits

Signed-off-by: Jonathan Tan
Signed-off-by: Elijah Newren

When rebasing against an upstream that has had many commits since the original branch was created:

O -- O -- ... -- O -- O (upstream)
 \
  -- O (my-dev-branch)

it must read the contents of every novel upstream commit, in addition to the tip of the upstream and the merge base, because "git rebase" attempts to exclude commits that are duplicates of upstream ones.

This can be a significant performance hit, especially in a partial clone, wherein a read of an object may end up being a fetch.

Add a flag --reapply-cherry-picks to "git rebase" to allow suppression of this feature.
This flag only works when using the "merge" backend.

This flag changes the behavior of sequencer_make_script(), called from do_interactive_rebase() <- run_rebase_interactive() <- run_specific_rebase() <- cmd_rebase(). With this flag, limit_list() (indirectly called from sequencer_make_script() through prepare_revision_walk()) will no longer call cherry_pick_list(), and thus PATCHSAME is no longer set.
Refraining from setting PATCHSAME both means that the intermediate commits in upstream are no longer read (as shown by the test) and means that no PATCHSAME-caused skipping of commits is done by sequencer_make_script(), either directly or through make_script_with_merges().

With Git 2.30 (Q1 2021), "git-parse-remote" shell script library outlived its usefulness.

See commit 66d36b9 (24 Nov 2020) by Jeff King (peff).
See commit a89a2fb, commit e63f7b0, commit 1c15180 (14 Nov 2020) by Ævar Arnfjörð Bjarmason (avar).
(Merged by Junio C Hamano -- gitster -- in commit e89ecfb, 03 Dec 2020)

parse-remote: remove this now-unused library

Signed-off-by: Ævar Arnfjörð Bjarmason

The previous two commits removed the last use of a function in this library, but most of it had been dead code for a while.
Only the "get_default_remote" function was still being used.

Even though we had a manual page for this library it was never intended (or I expect, actually) used outside of git.git. Let's just remove it, if anyone still cares about a function here they can pull them into their own project.

  1. Last use of error_on_missing_default_upstream(): d03ebd411c ("rebase: remove the rebase.useBuiltin setting", 2019-03-18)

  2. Last use of get_remote_merge_branch(): 49eb8d39c7 ("Remove> contrib/examples/*", 2018-03-25)

  3. https://lore.kernel.org/git/87a6vmhdka.fsf@evledraar.gmail.com/

With Git 2.32 (Q2 2021), the final hint that used to have a scripted git rebase is removed.

See commit 9bcde4d (23 Mar 2021) by Ævar Arnfjörð Bjarmason (avar).
(Merged by Junio C Hamano -- gitster -- in commit dc2a073, 30 Mar 2021)

rebase: remove transitory rebase.useBuiltin setting & env

Signed-off-by: Ævar Arnfjörð Bjarmason
Acked-by: Johannes Schindelin

Remove the rebase.useBuiltin setting and the now-obsolete GIT_TEST_REBASE_USE_BUILTIN test flag.

This was left in place after my d03ebd4 ("rebase: remove the rebase.useBuiltin setting", 2019-03-18, Git v2.22.0-rc0 -- merge listed in batch #5) to help anyone who'd used the experimental flag and wanted to know that it was the default, or that they should transition their test environment to use the builtin rebase unconditionally.

It's been more than long enough for those users to get a headsup about this.
So remove all the scaffolding that was left in-place after d03ebd4.
I'm also removing the documentation entry, if anyone still has this left in their configuration they can do some source archaeology to figure out what it used to do, which makes more sense than exposing every Git user reading the documentation to this legacy configuration switch.

With Git 2.36 (Q2 2022), git rebase -m is safer:

See commit 38c541c, commit cd1528e, commit 7700ab0, commit 6ae8086, commit ee464c4, commit b7de153, commit 1526d0f, commit d6a9f5e, commit 1946d45, commit 4840002, commit ab2fba0, commit 69f4c23, commit bd55eee, commit ae42fa4 (26 Jan 2022) by Phillip Wood (phillipwood).
(Merged by Junio C Hamano -- gitster -- in commit bcd020f, 18 Feb 2022)

rebase -m: don't fork git checkout

Signed-off-by: Phillip Wood

Now that reset_head() can handle the initial checkout of onto correctly use it in the "merge" backend instead of forking git checkout".
This opens the way for us to stop calling the post-checkout hook in the future.
Not running "git checkout"(man) means that rebase -i/m no longer recurse submodules when checking out onto (thanks to Philippe Blain for pointing this out).
As the rest of rebase does not know what to do with submodules this is probably a good thing.
When using merge-ort rebase ought be able to handle submodules correctly if it parsed the submodule config, such a change is left for a future patch series.

The "apply" based rebase has avoided forking git checkout since ac7f467 (builtin/rebase: support running , 2018-08-07, Git v2.20.0-rc0 -- merge listed in batch #8) ("builtin/rebase: support running "git rebase"(man) <upstream>, 2018-08-07).
The code that handles the checkout was moved into libgit by b309a97 ("reset: extract reset_head() from rebase", 2020-04-07, Git v2.27.0-rc0 -- merge listed in batch #5).

VonC
  • 1,262,500
  • 529
  • 4,410
  • 5,250