threads / patch / 18377

patch, 2 partsFix long running merge base computations

Subject: [JGIT PATCH 1/2] Fix long running merge base computations

## tl;dr

2 messages between Mar 18, 2009 and Mar 18, 2009. Diffs are folded; open one to read it.

replies: 1people: 1as markdown or json

Shawn O. Pearce· Mar 18, 2009, 18:01 UTC · lore

If a part of the project history is reachable by more than one path through the revision graph, we only need to traverse down it once through the first detected path when marking parents as reachable from an input branch.

Previously, JGit recomputed the entire project history for each path it was reachable through. On linux-2.6 based histories we got stuck for hours computing a merge base, as we kept passing back through the same sections of the revision graph.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../spearce/jgit/revwalk/MergeBaseGenerator.java   |    9 ++++++++-
 1 files changed, 8 insertions(+), 1 deletions(-)

Show changes to org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java +8 −1

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
index 1676caa..2eb9688 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
@@ -184,7 +184,9 @@ private void carryOntoHistory(RevCommit c, final int carry) {
 	}
 
 	private boolean carryOntoOne(final RevCommit p, final int carry) {
+		final boolean haveAll = (p.flags & carry) == carry;
 		p.flags |= carry;
+
 		if ((p.flags & POPPED) != 0 && (carry & MERGE_BASE) == 0
 				&& (p.flags & branchMask) == branchMask) {
 			// We were popped without being a merge base, but we just got
@@ -197,6 +199,11 @@ private boolean carryOntoOne(final RevCommit p, final int carry) {
 			carryOntoHistory(p, branchMask | MERGE_BASE);
 			return true;
 		}
-		return false;
+
+		// If we already had all carried flags, our parents do too.
+		// Return true to stop the caller from running down this leg
+		// of the revision graph any further.
+		//
+		return haveAll;
 	}
 }

-- 
1.6.2.1.337.g6270ba

Shawn O. Pearce· Mar 18, 2009, 18:01 UTC · re: Shawn O. Pearce · lore

[JGIT PATCH 2/2] Micro-optimize the merge base generator

Instead of doing 3 bit-wise and operations followed by 3 compares and two boolean and conditions on every commit we evaluate in the history, we can fold all of the tests into a pair of fields and do one bit mask and compare.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../spearce/jgit/revwalk/MergeBaseGenerator.java   |   13 +++++++++++--
 1 files changed, 11 insertions(+), 2 deletions(-)

Show changes to org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java +11 −2

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
index 2eb9688..8694e4c 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java
@@ -73,6 +73,10 @@
 
 	private int branchMask;
 
+	private int recarryTest;
+
+	private int recarryMask;
+
 	MergeBaseGenerator(final RevWalk w) {
 		walker = w;
 		pending = new DateRevQueue();
@@ -91,6 +95,12 @@ void init(final AbstractRevQueue p) {
 			// will be available for reuse when the walk resets.
 			//
 			walker.freeFlag(branchMask);
+
+			// Setup the condition used by carryOntoOne to detect a late
+			// merge base and produce it on the next round.
+			//
+			recarryTest = branchMask | POPPED;
+			recarryMask = branchMask | POPPED | MERGE_BASE;
 		}
 	}
 
@@ -187,8 +197,7 @@ private boolean carryOntoOne(final RevCommit p, final int carry) {
 		final boolean haveAll = (p.flags & carry) == carry;
 		p.flags |= carry;
 
-		if ((p.flags & POPPED) != 0 && (carry & MERGE_BASE) == 0
-				&& (p.flags & branchMask) == branchMask) {
+		if ((p.flags & recarryMask) == recarryTest) {
 			// We were popped without being a merge base, but we just got
 			// voted to be one. Inject ourselves back at the front of the
 			// pending queue and tell all of our ancestors they are within

-- 
1.6.2.1.337.g6270ba