Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 11, 2007, 09:17 UTC
Message-ID: <7vtzr6mnvw.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <alpine.LFD.0.999.0708101240200.30176@woody.linux-foundation.org>

Linus Torvalds <torvalds@linux-foundation.org> writes:

Show 10 quoted lines

> And as mentioned, the three-way case *should* be as trivial as the 
> following. It passes all the tests, and I verified that a conflicting 
> merge in the 100,000 file horror-case merged correctly (with the conflict 
> markers) in 0.687 seconds with this, so it works, but I'm lazy and 
> somebody else should double-check it.
>
> (Again - *without* this patch, the merge took 8.355 seconds, so this patch 
> really does make a huge difference for merge performance with lots and 
> lots of files, and we're not talking percentages, we're talking 
> orders-of-magnitude differences!)

Hmph, this might make what I was hoping to find time to do more or less unnecessary.

But here it is anyway.

I wanted to speed up the three-way merges. The assumption is that when you do a merge, you are not in the middle of your own messy work. It is either while you are in a merge binge, pulling from one subsystem lieutenant after another, or perhaps applying patchbombs from people. In either case, you would start your merge with a clean index that >99% matches the HEAD, after writing your index out as a tree.

Then, the new 3-way read-tree (or unpack_trees) would go like this.

First, we scan the index and find locally modified paths; invalidate cache-tree by calling cache_tree_invalidate_path() for such paths. The expectation is that you will still have largely usable cache-tree after this step.

The main part of the merge will be done by using tree_desc based traversal that walks over three (ancestor, mine and theirs) trees, instead of the current unpack_trees() that iterates mainly over the index entries.

(A) The three trees all may have a subtree at the same path, or
    the one that does not have a tree where others have does not
    have a blob at the path either (i.e. the subtree is missing
    from the tree without a D/F conflict).  If the usual 3-way
    tree level merge rule (one side changes while the other side
    does not do anything, or both sides change to the same) can
    be applied, and if the cache tree entry for that subtree is
    valid and matches our tree, then...

    - we know the working tree for that entire subdirectory is
      also clean because of the earlier invalidation;

    - we can simply follow the tree level merge without ever
      looking at individual paths contained in the subtree.

(B) If the precondition of (A) does not hold, we recurse into
    the subtree, and perform per-path 3-way merge, like the
    current unpack_trees() does.

If your merge does not involve anything in large subdirectories, e.g., include/, arch/, or drivers/, this would allow you to skip quite a lot of per-path merge computation by doing comparison of four (tree entries and cache-tree) tree object names (the three subdirectories have about 6k paths each, so this could be a huge win).

Another optimization I was hoping to do was "git diff --cached", which is unrelated to the recent change to use read_tree(). Instead of reading the tree into the stage #1 of the same index, we could walk the tree and skip the subtree whose cache-tree matches the entry from the tree. This would have the same scale of performance improvement opportunity.