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

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

[Mark Levedahl]

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

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

[Shawn O. Pearce]

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.

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

[Junio C Hamano]

"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.

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

[Karl Hasselström]

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

> 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

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

[Mark Levedahl]

Shawn O. Pearce wrote:
> 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