[JGIT PATCH 08/14] Optimize path comparsion within subtrees during TreeWalk

From: Shawn O. Pearce <spearce@spearce.org>
Date: Aug 18, 2008, 23:53 UTC
Message-ID: <1219103602-32222-9-git-send-email-spearce@spearce.org>
In-Reply-To: <1219103602-32222-8-git-send-email-spearce@spearce.org>

If we are comparing two entries whose parents both match the same tree iterator we know the path up through pathOffset must all be identical, as the parents can only match if their paths up to pathOffset were equal and they were both trees.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/treewalk/AbstractTreeIterator.java        |   22 +++++++++++++++++++-
 1 files changed, 21 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index 31257b5..e6aa338 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -237,7 +237,13 @@ int pathCompare(final AbstractTreeIterator p, final int pMode) {
 		final int bLen = p.pathLen;
 		int cPos;
 
-		for (cPos = 0; cPos < aLen && cPos < bLen; cPos++) {
+		// Its common when we are a subtree for both parents to match;
+		// when this happens everything in path[0..cPos] is known to
+		// be equal and does not require evaluation again.
+		//
+		cPos = alreadyMatch(this, p);
+
+		for (; cPos < aLen && cPos < bLen; cPos++) {
 			final int cmp = (a[cPos] & 0xff) - (b[cPos] & 0xff);
 			if (cmp != 0)
 				return cmp;
@@ -250,6 +256,20 @@ int pathCompare(final AbstractTreeIterator p, final int pMode) {
 		return lastPathChar(mode) - lastPathChar(pMode);
 	}
 
+	private static int alreadyMatch(AbstractTreeIterator a,
+			AbstractTreeIterator b) {
+		for (;;) {
+			final AbstractTreeIterator ap = a.parent;
+			final AbstractTreeIterator bp = b.parent;
+			if (ap == null || bp == null)
+				return 0;
+			if (ap.matches == bp.matches)
+				return a.pathOffset;
+			a = ap;
+			b = bp;
+		}
+	}
+
 	private static int lastPathChar(final int mode) {
 		return FileMode.TREE.equals(mode) ? '/' : '\0';
 	}

-- 
1.6.0.87.g2858d