Re: cherry-pick is slow

[Jeff King <peff@peff.net>]

On Tue, May 15, 2012 at 02:03:40PM -0700, Junio C Hamano wrote:

> > 	git format-patch -1 --stdout $commit | git apply --index --3way
> [...]
> An unscientific datapoint shows that with a project as small as the kernel,
> the difference is noticeable.
>
> For example, v3.4-rc7-22-g3911ff3 (random tip of the day) touches two
> paths, and cherry-picking it on top of v3.3 goes like this:

Yeah that's what I would expect. And that's not even that far away.
Cherry-picking the same commit onto v3.0 should be even more noticeable.

> I _think_ most of the overhead comes from having to match the large trees
> in unpack_trees() even though none of the changes between the base
> versions matters for this" cherry-pick".
> 
> Both reads the flat index into the core in its entirety and futzing with
> the index file format would not affect this comparison, even though it
> could improve the performance of "am", if done right, as it could limit
> its updates to only two paths.  In the merge case, we pretty much rebuild
> the resulting index from scratch by walking the entire tree in
> unpack_trees(), so there won't be much benefit.
> 
> Perhaps we might want to rethink the way we run merges?

For merge-recursive, we would always want to compute the pair-wise
renames between each side and the ancestor. So that diff to the
cherry-pick destination is always going to be an expensive O(# of
changes between source and dest) operation.

Without renames, you could do better on the actual merge with a
three-way tree walk. E.g., you see that some sub-tree is at tree A in
the "ours" and "ancestor" trees, but at tree B in "theirs". So you don't
have to descend further, and can just say "take theirs" (well, you have
to descend "theirs" to get the values). But I expect it gets more
complicated with the interactions with the index (and is probably not
worth spending much effort on because of the rename issue, anyway).

-Peff