git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[EGIT PATCH 04/10] Speed up history by comparing tree hashes.

From
Robin Rosenberg <robin.rosenberg@dewire.com>
Date
Mar 11, 2007, 18:15 UTC
Message-ID
<20070311181537.18012.48173.stgit@lathund.dewire.com>
In-Reply-To
<20070311180608.18012.13767.stgit@lathund.dewire.com>

Instead of looking up full path name all the time we split the path name of the resource we are looking at and compare hashed at each level.

The performance improvement isn't huge since most of the work is reading commits.

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../egit/core/internal/mapping/GitFileHistory.java |   79 +++++++++++++++--------
 .../src/org/spearce/jgit/lib/ObjectId.java         |    6 ++
 2 files changed, 58 insertions(+), 27 deletions(-)
diff --git a/org.spearce.egit.core/src/org/spearce/egit/core/internal/mapping/GitFileHistory.java b/org.spearce.egit.core/src/org/spearce/egit/core/internal/mapping/GitFileHistory.java
index 163278d..6c40bb0 100644
--- a/org.spearce.egit.core/src/org/spearce/egit/core/internal/mapping/GitFileHistory.java
+++ b/org.spearce.egit.core/src/org/spearce/egit/core/internal/mapping/GitFileHistory.java
@@ -18,6 +18,7 @@ package org.spearce.egit.core.internal.mapping;
 
 import java.io.IOException;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Date;
@@ -34,13 +35,14 @@ import org.spearce.egit.core.project.RepositoryMapping;
 import org.spearce.jgit.lib.Commit;
 import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.lib.Repository;
+import org.spearce.jgit.lib.Tree;
 import org.spearce.jgit.lib.TreeEntry;
 
 public class GitFileHistory extends FileHistory {
 
 	private final IResource resource;
 
-	private final String relativeResourceName;
+	private final String[] relativeResourceName;
 
 	private final int flags;
 
@@ -50,12 +52,11 @@ public class GitFileHistory extends FileHistory {
 		this.resource = resource;
 		this.flags = flags;
 		String prefix = getRepositoryMapping().getSubset();
-		if (prefix != null)
-			prefix = prefix + "/";
-		else
-			prefix = "";
-		relativeResourceName = prefix
-				+ resource.getProjectRelativePath().toString();
+		String[] prefixSegments = prefix!=null ? prefix.split("/") : new String[0];
+		String[] resourceSegments = resource.getProjectRelativePath().segments(); 
+		relativeResourceName = new String[prefixSegments.length + resourceSegments.length];
+		System.arraycopy(prefixSegments, 0, relativeResourceName, 0, prefixSegments.length);
+		System.arraycopy(resourceSegments, 0, relativeResourceName, prefixSegments.length, resourceSegments.length);
 	}
 
 	public IFileRevision[] getContributors(IFileRevision revision) {
@@ -105,7 +106,9 @@ public class GitFileHistory extends FileHistory {
 		try {
 			ObjectId id = repository.resolve("HEAD");
 			Commit commit = repository.mapCommit(id);
-			return collectHistory(new ObjectId(ObjectId.toString(null)),
+			ObjectId[] initialResourceHash = new ObjectId[relativeResourceName.length];
+			Arrays.fill(initialResourceHash, ObjectId.zeroId());
+			return collectHistory(initialResourceHash, null,
 					repository, commit);
 		} catch (IOException e) {
 			e.printStackTrace();
@@ -113,29 +116,49 @@ public class GitFileHistory extends FileHistory {
 		}
 	}
 
-	private Collection collectHistory(ObjectId lastResourceHash,
-			Repository repository, Commit top) {
+	private Collection collectHistory(ObjectId[] lastResourceHash, TreeEntry lastEntry,
+			Repository repository, Commit top) throws IOException {
 		if (top == null)
 			return Collections.EMPTY_LIST;
 		Collection ret = new ArrayList(10000);
 		Commit current = top;
 		Commit previous = top;
+
 		do {
-			TreeEntry currentEntry;
-			try {
-				currentEntry = current.getTree().findMember(
-						relativeResourceName);
-			} catch (IOException e1) {
-				e1.printStackTrace();
-				return ret;
+			TreeEntry currentEntry = lastEntry;
+			ObjectId[] currentResourceHash = new ObjectId[lastResourceHash.length];
+			Tree t = current.getTree();
+			for (int i = 0; i < currentResourceHash.length; ++i) {
+				TreeEntry m = t.findMember(relativeResourceName[i]);
+				if (m != null) {
+					ObjectId id = m.getId();
+					currentResourceHash[i] = id;
+					if (id.equals(lastResourceHash[i])) {
+						while (++i < currentResourceHash.length) {
+							currentResourceHash[i] = lastResourceHash[i];
+						}
+					} else {
+						if (m instanceof Tree) {
+							t = (Tree)m;
+						} else {
+							if (i == currentResourceHash.length - 1) {
+								currentEntry = m;
+							} else {
+								currentEntry = null;
+								while (++i < currentResourceHash.length) {
+									currentResourceHash[i] = ObjectId.zeroId();
+								}
+							}
+						}
+					}
+				} else {
+					for (; i < currentResourceHash.length; ++i) {
+						currentResourceHash[i] = ObjectId.zeroId();
+					}
+				}
 			}
-			ObjectId currentResourceHash;
-			if (currentEntry == null)
-				currentResourceHash = new ObjectId(ObjectId.toString(null));
-			else
-				currentResourceHash = currentEntry.getId();
-
-			if (!currentResourceHash.equals(lastResourceHash))
+			
+			if (!currentResourceHash[currentResourceHash.length-1].equals(lastResourceHash[currentResourceHash.length-1]))
 				ret.add(new GitFileRevision(previous, resource));
 
 			lastResourceHash = currentResourceHash;
@@ -150,7 +173,7 @@ public class GitFileHistory extends FileHistory {
 					Commit mergeParent;
 					try {
 						mergeParent = repository.mapCommit(mergeParentId);
-						ret.addAll(collectHistory(lastResourceHash, repository,
+						ret.addAll(collectHistory(lastResourceHash, currentEntry, repository, 
 								mergeParent));
 						// TODO: this gets us a lot of duplicates that we need
 						// to filter out
@@ -208,8 +231,10 @@ public class GitFileHistory extends FileHistory {
 					return;
 				}
 			}
-			TreeEntry currentEntry = current.getTree().findMember(
-					relativeResourceName);
+			TreeEntry currentEntry = current.getTree();
+			for (int i=0; i < relativeResourceName.length && currentEntry != null; ++i) {
+				((Tree)currentEntry).findMember(relativeResourceName[i]);
+			}
 			if (currentEntry != null)
 				revisions = new IFileRevision[] { new GitFileRevision(current,
 						resource) };
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectId.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectId.java
index 38fefe2..9e62424 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectId.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectId.java
@@ -30,6 +30,10 @@ public class ObjectId implements Comparable {
 		ZEROID_STR = ZEROID.toString();
 	}
 
+	public static ObjectId zeroId() {
+		return ZEROID;
+	}
+	
 	public static final boolean isId(final String id) {
 		if (id.length() != (2 * Constants.OBJECT_ID_LENGTH)) {
 			return false;
@@ -80,6 +84,8 @@ public class ObjectId implements Comparable {
 	}
 
 	private static int compare(final byte[] a, final byte[] b) {
+		if (a==b)
+			return 0;
 		for (int k = 0; k < a.length && k < b.length; k++) {
 			final int ak = a[k] & 0xff;
 			final int bk = b[k] & 0xff;
Previous: Robin RosenbergNext: Robin Rosenberg
Message 5 of 16 in “Fixes and improvement on Eclipse plugin”
  1. 00/10 Fixes and improvement on Eclipse pluginRobin Rosenberg, Mar 11, 2007
  2. 01/10 Git history refresh problemRobin Rosenberg, Mar 11, 2007
  3. 02/10 Support commit encoding headerRobin Rosenberg, Mar 11, 2007
  4. 03/10 Avoid a nullpointerexception on shutdownRobin Rosenberg, Mar 11, 2007
  5. 04/10 Speed up history by comparing tree hashes.Robin Rosenberg, Mar 11, 2007
  6. 05/10 Cache commitsRobin Rosenberg, Mar 11, 2007
  7. 06/10 Allow history listing on folders and projects.Robin Rosenberg, Mar 11, 2007
  8. 07/10 Return nothing if no version exists for a commit.Robin Rosenberg, Mar 11, 2007
  9. 08/10 Show only commits that represent changes in the history viewRobin Rosenberg, Mar 11, 2007
  10. 09/10 Hash ObjectId faster.Robin Rosenberg, Mar 11, 2007
  11. 10/10 Display distance to head in history pageRobin Rosenberg, Mar 11, 2007
  12. 0/2 Series short descriptionRobin Rosenberg, Mar 11, 2007
  13. Shawn O. PearceMar 11, 2007
  14. Robin RosenbergMar 11, 2007
  15. 1/2 Tag version 0.2.1Robin Rosenberg, Mar 11, 2007
  16. 2/2 Re-add qualfiier for development versionRobin Rosenberg, Mar 11, 2007

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.