Re: cherry-pick is slow

From: Jeff King <peff@peff.net>
Date: May 19, 2012, 00:54 UTC
Message-ID: <20120519005424.GF765@sigill.intra.peff.net>
In-Reply-To: <7vwr4dcg2b.fsf@alter.siamese.dyndns.org>

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

Show 7 quoted lines

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

Show 12 quoted lines

> 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