git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Elijah Newren <newren@gmail.com>
To: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Cc: Git Mailing List <git@vger.kernel.org>,
	Junio C Hamano <gitster@pobox.com>,
	Alban Gruin <alban.gruin@gmail.com>
Subject: Re: [RFC PATCH 3/3] git-rebase.sh: make git-rebase--interactive the default
Date: Wed, 20 Jun 2018 09:27:54 -0700	[thread overview]
Message-ID: <CABPp-BEnJ4q9WGi4BgikpLJ9Aty5-3MR4VozjBk7ie4rGMc-ng@mail.gmail.com> (raw)
In-Reply-To: <nycvar.QRO.7.76.6.1806172337340.77@tvgsbejvaqbjf.bet>

Hi Dscho,

On Sun, Jun 17, 2018 at 2:44 PM, Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:

> I was really referring to speed. But I have to admit that I do not have
> any current numbers.
>
> Another issue just hit me, though: rebase --am does not need to look at as
> many Git objects as rebase --merge or rebase -i. Therefore, GVFS users
> will still want to use --am wherever possible, to avoid "hydrating"
> many objects during their rebase.

What is it that makes rebase --am need fewer Git objects than rebase
--merge or rebase -i?  I have one idea which isn't intrinsic to the
algorithm, so I'm curious if there's something else I'm unaware of.

My guess at what objects are needed by each type:

At a high level, rebase --am for each commit will need to compare the
commit to its parent to generate a diff (which thus involves walking
over the objects in both the commit and its parent, though it should
be able to skip over subtrees that are equal), and then will need to
look at all the objects in the target commit on which it needs to
apply the patch (in order to properly fill the index for a starting
point, and used later when creating a new commit).  If the application
of the diff fails, it falls back to a three-way merge, though the
three-way merge shouldn't need any additional objects.  So, to
summarize, rebase--am needs objects from the commit being rebased, its
parent, and the target commit onto which it is applying, though it can
short circuit some objects when the commit and its parent have
matching subtree(s).

rebase -i, if I understand correctly, does a three-way merge between
the commit, its parent, and the target commit.  Thus, we again walk
over objects in those three commits; I think unpack_trees() does not
take advantage of matching trees to avoid descending into subtrees,
but if so that's an optimization that we may be able to implement
(though it would require diving into unpack_trees() code, which is
never easy...).

(Side notes: (1) rebase --merge is basically the same as rebase -i
here; it's path to reaching the recursive merge machinery is a bit
different but the resulting arguments are the same; (2) a real merge
between branches would require more objects because it would have to
do some revision walking to find a merge base, and a real merge base
is likely to differ more than just the parent commit.  But finding
merge bases isn't relevant to rebase -m or rebase -i)

Is there something else I'm missing that fundamentally makes rebase -i
need more objects?

> As to speed: that might be harder. But then, the performance might already
> be good enough. I do not have numbers (nor the time to generate them) to
> back up my hunch that --am is substantially faster than --merge.

I too have a hunch that --am is faster than --merge, on big enough
repos or repos with enough renames.  I can partially back it up with
an indirect number: at [1], it was reported that cherry-picks could be
sped up by a factor of 20-30 on some repos with lots of renames.  I
believe there are other performance improvements possible too, for the
--merge or -i cases.

I'm also curious now whether your comment on hydrating objects might
uncover additional areas where performance improvements could be made
for non-am-based rebases of large-enough repos.

Elijah

[1] https://public-inbox.org/git/CABPp-BH4LLzeJjE5cvwWQJ8xTj3m9oC-41Tu8BM8c7R0gQTjWw@mail.gmail.com/
(see also Peter's last reply in that thread, and compare to his first
post)

  reply	other threads:[~2018-06-20 16:27 UTC|newest]

Thread overview: 130+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-06-07  4:58 RFC: rebase inconsistency in 2.18 -- course of action? Elijah Newren
2018-06-07  5:04 ` [PATCH] t3401: add directory rename testcases for rebase and am Elijah Newren
2018-06-25 16:17   ` Elijah Newren
2018-06-07  5:05 ` [PATCH] apply: fix grammar error in comment Elijah Newren
2018-06-07  5:05 ` [PATCH] t5407: fix test to cover intended arguments Elijah Newren
2018-06-07  5:06 ` [PATCH] git-rebase--merge: modernize "git-$cmd" to "git $cmd" Elijah Newren
2018-06-07  5:24   ` Elijah Newren
2018-06-27  7:46   ` [PATCH v2] " Elijah Newren
2018-07-12 15:49     ` Johannes Schindelin
2018-07-13 16:13       ` Elijah Newren
2018-07-14 22:20         ` Johannes Schindelin
2018-06-07  5:06 ` [PATCH 1/2] t3422: new testcases for checking when incompatible options passed Elijah Newren
2018-06-07  5:06   ` [PATCH 2/2] git-rebase: error out " Elijah Newren
2018-06-10 19:40     ` Phillip Wood
2018-06-11 15:19       ` Elijah Newren
2018-06-11 15:59         ` Phillip Wood
2018-06-11 15:49       ` Elijah Newren
2018-06-12  9:45         ` Phillip Wood
2018-06-17  5:58   ` [RFC PATCH v2 0/7] Document/fix/warn about rebase incompatibilities and inconsistences Elijah Newren
2018-06-17  5:58     ` [RFC PATCH v2 1/7] git-rebase.txt: document incompatible options Elijah Newren
2018-06-17 15:38       ` Phillip Wood
2018-06-20 17:09         ` Elijah Newren
2018-06-17 17:15       ` Eric Sunshine
2018-06-20 17:10         ` Elijah Newren
2018-06-17  5:58     ` [RFC PATCH v2 2/7] git-rebase.sh: update help messages a bit Elijah Newren
2018-06-17  5:58     ` [RFC PATCH v2 3/7] t3422: new testcases for checking when incompatible options passed Elijah Newren
2018-06-17  5:58     ` [RFC PATCH v2 4/7] git-rebase: error out " Elijah Newren
2018-06-17  5:58     ` [RFC PATCH v2 5/7] git-rebase.txt: document behavioral inconsistencies between modes Elijah Newren
2018-06-17  5:58     ` [RFC PATCH v2 6/7] git-rebase.txt: address confusion between --no-ff vs --force-rebase Elijah Newren
2018-06-17  5:58     ` [RFC PATCH v2 7/7] git-rebase: make --allow-empty-message the default Elijah Newren
2018-06-17 15:30       ` Phillip Wood
2018-06-20 16:47         ` Elijah Newren
2018-06-17 15:41     ` [RFC PATCH v2 0/7] Document/fix/warn about rebase incompatibilities and inconsistences Phillip Wood
2018-06-21 15:00     ` [PATCH v3 0/7] Document/fix/warn about rebase incompatibilities and inconsistencies Elijah Newren
2018-06-21 15:00       ` [PATCH v3 1/7] git-rebase.txt: document incompatible options Elijah Newren
2018-06-21 19:47         ` Junio C Hamano
2018-06-21 20:33           ` Elijah Newren
2018-06-22  8:32         ` SZEDER Gábor
2018-06-21 15:00       ` [PATCH v3 2/7] git-rebase.sh: update help messages a bit Elijah Newren
2018-06-21 19:58         ` Junio C Hamano
2018-06-21 20:34           ` Elijah Newren
2018-06-21 15:00       ` [PATCH v3 3/7] t3422: new testcases for checking when incompatible options passed Elijah Newren
2018-06-21 20:04         ` Junio C Hamano
2018-06-21 20:37           ` Elijah Newren
2018-06-21 21:18           ` Eric Sunshine
2018-06-21 15:00       ` [PATCH v3 4/7] git-rebase: error out " Elijah Newren
2018-06-21 20:29         ` Junio C Hamano
2018-06-21 20:41           ` Elijah Newren
2018-06-21 15:00       ` [PATCH v3 5/7] git-rebase.txt: document behavioral inconsistencies between modes Elijah Newren
2018-06-21 20:44         ` Junio C Hamano
2018-06-21 21:25           ` Elijah Newren
2018-06-21 15:00       ` [PATCH v3 6/7] git-rebase.txt: address confusion between --no-ff vs --force-rebase Elijah Newren
2018-06-21 20:46         ` Junio C Hamano
2018-06-21 21:22           ` Elijah Newren
2018-06-21 15:00       ` [RFC PATCH v3 7/7] git-rebase: make --allow-empty-message the default Elijah Newren
2018-06-25 16:12       ` [PATCH v4 0/9] Document/fix/warn about rebase incompatibilities and inconsistencies Elijah Newren
2018-06-25 16:12         ` [PATCH v4 1/9] git-rebase.txt: document incompatible options Elijah Newren
2018-06-25 16:12         ` [PATCH v4 2/9] git-rebase.sh: update help messages a bit Elijah Newren
2018-06-25 16:12         ` [PATCH v4 3/9] t3422: new testcases for checking when incompatible options passed Elijah Newren
2018-06-26 18:17           ` Junio C Hamano
2018-06-27  6:50             ` Elijah Newren
2018-06-25 16:12         ` [PATCH v4 4/9] git-rebase: error out " Elijah Newren
2018-06-25 16:12         ` [PATCH v4 5/9] git-rebase.txt: address confusion between --no-ff vs --force-rebase Elijah Newren
2018-06-25 16:12         ` [PATCH v4 6/9] directory-rename-detection.txt: technical docs on abilities and limitations Elijah Newren
2018-06-25 16:12         ` [PATCH v4 7/9] git-rebase.txt: document behavioral differences between modes Elijah Newren
2018-06-25 16:12         ` [PATCH v4 8/9] t3401: add directory rename testcases for rebase and am Elijah Newren
2018-06-25 16:13         ` [RFC PATCH v4 9/9] git-rebase: make --allow-empty-message the default Elijah Newren
2018-06-27  7:23         ` [PATCH v5 0/9] Document/fix/warn about rebase incompatibilities and inconsistencies Elijah Newren
2018-06-27  7:23           ` [PATCH v5 1/9] git-rebase.txt: document incompatible options Elijah Newren
2018-06-27  7:23           ` [PATCH v5 2/9] git-rebase.sh: update help messages a bit Elijah Newren
2018-06-27  7:23           ` [PATCH v5 3/9] t3422: new testcases for checking when incompatible options passed Elijah Newren
2018-06-27  7:23           ` [PATCH v5 4/9] git-rebase: error out " Elijah Newren
2018-06-27  7:23           ` [PATCH v5 5/9] git-rebase.txt: address confusion between --no-ff vs --force-rebase Elijah Newren
2018-06-27  7:23           ` [PATCH v5 6/9] directory-rename-detection.txt: technical docs on abilities and limitations Elijah Newren
2018-06-27  7:23           ` [PATCH v5 7/9] git-rebase.txt: document behavioral differences between modes Elijah Newren
2018-06-27  7:23           ` [PATCH v5 8/9] t3401: add directory rename testcases for rebase and am Elijah Newren
2018-06-27  7:23           ` [RFC PATCH v5 9/9] git-rebase: make --allow-empty-message the default Elijah Newren
2018-09-12  2:42             ` 2.19.0 regression: leaving editor with empty commit message doesn't stop rebase [was: Re: [RFC PATCH v5 9/9] git-rebase: make --allow-empty-message the default] SZEDER Gábor
2018-09-12  6:21               ` Elijah Newren
2018-09-12 21:18               ` [PATCH] sequencer: fix --allow-empty-message behavior, make it smarter Elijah Newren
2018-09-13 20:24                 ` Junio C Hamano
2018-06-29 13:20           ` [PATCH v5 0/9] Document/fix/warn about rebase incompatibilities and inconsistencies Phillip Wood
2018-06-07  5:07 ` [PATCH] git-rebase.sh: handle keep-empty like all other options Elijah Newren
2018-06-10 19:26   ` Phillip Wood
2018-06-11 14:42     ` Elijah Newren
2018-06-11 15:16       ` Phillip Wood
2018-06-11 16:08         ` Elijah Newren
2018-06-12  9:53           ` Phillip Wood
2018-06-07  5:08 ` [PATCH 1/2] t3418: add testcase showing problems with rebase -i and strategy options Elijah Newren
2018-06-07  5:08   ` [PATCH 2/2] Fix use of strategy options with interactive rebases Elijah Newren
2018-06-27  7:36   ` [PATCH v2 0/2] " Elijah Newren
2018-06-27  7:36     ` [PATCH v2 1/2] t3418: add testcase showing problems with rebase -i and strategy options Elijah Newren
2018-06-27  7:45       ` Eric Sunshine
2018-06-27  7:49         ` Elijah Newren
2018-06-27 16:54           ` Junio C Hamano
2018-06-27 17:27             ` Elijah Newren
2018-06-27 18:17               ` Johannes Sixt
2018-06-27 18:24                 ` Eric Sunshine
2018-06-27 18:34                 ` [PATCH v2 1/2] t3418: add testcase showing problems with rebase SZEDER Gábor
2018-06-27 19:20                 ` [PATCH v2 1/2] t3418: add testcase showing problems with rebase -i and strategy options Junio C Hamano
2018-06-27 19:23               ` Junio C Hamano
2018-06-27  7:36     ` [PATCH v2 2/2] Fix use of strategy options with interactive rebases Elijah Newren
2018-06-27 15:48     ` [PATCH v3 0/2] " Elijah Newren
2018-06-27 15:48       ` [PATCH v3 1/2] t3418: add testcase showing problems with rebase -i and strategy options Elijah Newren
2018-06-27 18:28         ` SZEDER Gábor
2018-07-11 10:56           ` SZEDER Gábor
2018-07-11 19:12             ` Elijah Newren
2018-06-27 15:48       ` [PATCH v3 2/2] Fix use of strategy options with interactive rebases Elijah Newren
2018-07-12 15:41         ` Johannes Schindelin
2018-07-13 15:51           ` Elijah Newren
2018-06-07 17:13 ` [RFC PATCH 0/3] Send more rebases through interactive machinery Elijah Newren
2018-06-07 17:13   ` [RFC PATCH 1/3] git-rebase, sequencer: add a --quiet option for the " Elijah Newren
2018-06-09 21:45     ` Johannes Schindelin
2018-06-09 23:05       ` Elijah Newren
2018-06-07 17:13   ` [RFC PATCH 2/3] rebase: Implement --merge via git-rebase--interactive Elijah Newren
2018-06-09 22:04     ` Johannes Schindelin
2018-06-10  1:14       ` Elijah Newren
2018-06-11  9:54         ` Phillip Wood
2018-06-07 17:13   ` [RFC PATCH 3/3] git-rebase.sh: make git-rebase--interactive the default Elijah Newren
2018-06-09 22:11     ` Johannes Schindelin
2018-06-10  1:31       ` Elijah Newren
2018-06-17 21:44         ` Johannes Schindelin
2018-06-20 16:27           ` Elijah Newren [this message]
2018-06-21 10:57             ` Johannes Schindelin
2018-06-21 15:36               ` Elijah Newren
2019-01-21 15:55                 ` Johannes Schindelin
2019-01-21 19:02                   ` Elijah Newren
2019-01-22 15:37                     ` Johannes Schindelin
2018-06-11 17:44 ` RFC: rebase inconsistency in 2.18 -- course of action? Junio C Hamano
2018-06-11 20:17   ` 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

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CABPp-BEnJ4q9WGi4BgikpLJ9Aty5-3MR4VozjBk7ie4rGMc-ng@mail.gmail.com \
    --to=newren@gmail.com \
    --cc=Johannes.Schindelin@gmx.de \
    --cc=alban.gruin@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.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.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).