Optimize RevWalk.getMergedInto()
Transitive Relation Definition:
On the DAG of commit history, if A can reach B, C can reach A, then C
can reach B.
Example:
As is shown in the graph below:
1 - 2 - 3 - 4 (side)
\
5 - 6^ (master) - 7 (topic)
Find out which branches is 2 merged into:
After we calculated that master contains 2, we can mark 6 as TEMP_MARK
to avoid unwanted walks.
When we want to figure out if 2 is merge into the topic, the traversal
path would be [7, 6] instead of [7, 6, 5, 3, 2].
Test:
This change can significantly improve performance for tags.
On a copy of the Linux repository, the command 'git tag --contains
<commit>' had the following performance improvement:
commit | Before | After | Rel %
47a44d27ca | 29251ms | 6687ms | -77%
90327e7dff | 21388ms | 6256ms | -70%
f85fac0efa | 11150ms | 7338ms | -34%
The current version ignores tags, even though the tag is a type of
the ref.
Follow-up commits I'll fix it.
Change-Id: Ie6295ca4d16070499912af462239e679a97cce47
Signed-off-by: kylezhao <kylezhao@tencent.com>
Reviewed-by: Christian Halstrick <christian.halstrick@sap.com>
Reviewed-by: Martin Fick <mfick@codeaurora.org>
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java
index 200cb6a..0a045c9 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java
@@ -82,20 +82,33 @@ public void findBranchesReachableManyTimes() throws Exception {
* a b
* | |
* c d
+ * | \
+ * f e
+ * | /
+ * g
*/
RevCommit a = commit();
RevCommit b = commit();
RevCommit c = commit(a);
RevCommit d = commit(b);
+ RevCommit f = commit(d);
+ RevCommit e = commit(d);
+ RevCommit g = commit(f, e);
Ref branchA = branch("a", a);
Ref branchB = branch("b", b);
Ref branchC = branch("c", c);
Ref branchD = branch("d", d);
+ Ref branchE = branch("e", e);
+ Ref branchF = branch("f", f);
+ Ref branchG = branch("g", g);
assertContains(a, asList(branchA, branchC));
- assertContains(b, asList(branchB, branchD));
+ assertContains(b, asList(branchB, branchD, branchE, branchF, branchG));
assertContains(c, asList(branchC));
- assertContains(d, asList(branchD));
+ assertContains(d, asList(branchD, branchE, branchF, branchG));
+ assertContains(e, asList(branchE, branchG));
+ assertContains(f, asList(branchF, branchG));
+ assertContains(g, asList(branchG));
}
private Ref branch(String name, RevCommit dst) throws Exception {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
index d5b3643..d2ab4a1 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -528,6 +528,7 @@ private List<Ref> getMergedInto(RevCommit needle, Collection<Ref> haystacks,
Enum returnStrategy, ProgressMonitor monitor) throws IOException {
List<Ref> result = new ArrayList<>();
List<RevCommit> uninteresting = new ArrayList<>();
+ List<RevCommit> marked = new ArrayList<>();
RevFilter oldRF = filter;
TreeFilter oldTF = treeFilter;
try {
@@ -545,17 +546,20 @@ private List<Ref> getMergedInto(RevCommit needle, Collection<Ref> haystacks,
continue;
}
RevCommit c = (RevCommit) o;
- resetRetain(RevFlag.UNINTERESTING);
+ reset(UNINTERESTING | TEMP_MARK);
markStart(c);
boolean commitFound = false;
RevCommit next;
while ((next = next()) != null) {
- if (References.isSameObject(next, needle)) {
+ if (References.isSameObject(next, needle)
+ || (next.flags & TEMP_MARK) != 0) {
result.add(r);
if (returnStrategy == GetMergedIntoStrategy.RETURN_ON_FIRST_FOUND) {
return result;
}
commitFound = true;
+ c.flags |= TEMP_MARK;
+ marked.add(c);
break;
}
}
@@ -571,6 +575,9 @@ private List<Ref> getMergedInto(RevCommit needle, Collection<Ref> haystacks,
roots.addAll(uninteresting);
filter = oldRF;
treeFilter = oldTF;
+ for (RevCommit c : marked) {
+ c.flags &= ~TEMP_MARK;
+ }
}
return result;
}
