threads / discuss / 9886

rename detection limit checking, cherry picking, and git am -3

Subject: rename detection limit checking, cherry picking, and git am -3

## tl;dr

5 messages between Sep 17, 2007 and Sep 18, 2007.

replies: 4people: 4as markdown or json

Mark Levedahl· Sep 17, 2007, 03:32 UTC · lore

Linus' recent patch to invoke limiting on rename detection broke my ability to use cherry-picking on one project. This project has about 4300 files on one branch (a), 2500 on a later branch (b), 226 commits in total between the two branches, and a convoluted history of how branch a morphed into branch b. About 50 files were renamed in the transition, and we need to migrate patches from the still maintained branch a onto the new branch b.

Prior to Linus' recent patch to limit rename detection (0024a549), cherry picking a patch from a to b, where the patch affected just one file, often took about 45 seconds on a 3 GHz pentium 4 with the CPU pegged at 100% for the duration. The cherry picking always succeeded and correctly followed renames, but was very slow.

Following Linus' patch, the cherry picking fails with a merge conflict (almost instantly), complaining the file has been deleted on b but modified on a, i.e., the rename detection does not work. I tried raising diff.renameLimit to 100000, that seems to have no effect whatsoever on cherry-pick (the process aborts with a conflict almost immediately).

Curiously, using "git format-patch x..y --stdout | git am -3" succeeds in this case, and runs in well less than a second. This performance seems unchanged by the rename detection limit patch.

So, the rename limit patch "broke" git for this usage, though one could reasonably argue the previous code was so slow as to be broken anyway.

The curious thing to me is the vast superiority of whatever git-format-patch|git-am -3 does, and I wonder if that isn't a fundementally better design for cherry picking than git-cherry-pick implements (it obviously is for this case).

Mark

Shawn O. Pearce· Sep 17, 2007, 03:47 UTC · re: Mark Levedahl · lore

Re: rename detection limit checking, cherry picking, and git am -3

Mark Levedahl <mlevedahl@gmail.com> wrote:

> The curious thing to me is the vast superiority of whatever 
> git-format-patch|git-am -3 does, and I wonder if that isn't a 
> fundementally better design for cherry picking than git-cherry-pick 
> implements (it obviously is for this case).

In this case `git am -3` creates a tree object containing only the files modified by the patch and then feeds that tree into git-merge-recursive. Now if you go study git-revert's code you'll see it actually just calls git-merge-recursive on three trees, but these are three complete trees.

So what's probably happening here is there's less candidates on one side in the `am -3` case, so we spend a lot less time generating the rename matrix, searching for a match, and we get better changes of finding a match.

I actually don't see why cherry-pick can't be defined in terms of `format-patch|am -3`. It probably would be faster in almost all cases.

-- 
Shawn.

Junio C Hamano· Sep 17, 2007, 04:27 UTC · re: Shawn O. Pearce · lore

Re: rename detection limit checking, cherry picking, and git am -3

"Shawn O. Pearce" <spearce@spearce.org> writes:

> I actually don't see why cherry-pick can't be defined in terms
> of `format-patch|am -3`.  It probably would be faster in almost
> all cases.

Heh, people often suggested that rebase should get --merge as default, and I resisted that.

I think it would make sense to do the consolidated backend for rebase, revert, cherry-pick and am (I have been tentatively calling this "git replay") primarily based on the "patch with fallback to 3-way" like format-patch piped to "am -3", with an option to do merge-recursive.

Karl Hasselström· Sep 17, 2007, 09:58 UTC · re: Junio C Hamano · lore

Re: rename detection limit checking, cherry picking, and git am -3

On 2007-09-16 21:27:46 -0700, Junio C Hamano wrote:

Show 5 quoted lines

> I think it would make sense to do the consolidated backend for
> rebase, revert, cherry-pick and am (I have been tentatively calling
> this "git replay") primarily based on the "patch with fallback to
> 3-way" like format-patch piped to "am -3", with an option to do
> merge-recursive.

I guess such a backend would be useful for StGit as well.

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

Mark Levedahl· Sep 18, 2007, 00:18 UTC · re: Shawn O. Pearce · lore

Re: rename detection limit checking, cherry picking, and git am -3

Shawn O. Pearce wrote:

Show 12 quoted lines

> In this case `git am -3` creates a tree object containing only
> the files modified by the patch and then feeds that tree into
> git-merge-recursive.  Now if you go study git-revert's code you'll
> see it actually just calls git-merge-recursive on three trees,
> but these are three complete trees.
>
> So what's probably happening here is there's less candidates on one
> side in the `am -3` case, so we spend a lot less time generating
> the rename matrix, searching for a match, and we get better changes
> of finding a match.
>
>

Thanks for the explanation. For my case, there are < 500 files (including renamed files) in common between the two branches, giving ~2000*4000 files that have no correspondence for which git can try to find renames. Clearly, reducing the one side from 4000 files to 1 file has an enormous payoff.

Mark