Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> writes:
> 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.
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
