From 6de12836d72fe4cba9afc297c8988c6fff851fa9 Mon Sep 17 00:00:00 2001 From: Shawn Pearce Date: Thu, 17 Apr 2014 15:26:04 -0700 Subject: blame: Reduce running time ~4.5% by skipping common subtrees With this commit running blame on render_view_impl.cc[1] saves about 644 ms over prior versions, reducing the time about 4.5%. Large projects often contain strands of commits where no changes are made to a particular subtree. Blame used to dive recursively into these subtrees to look for the blob and check if its SHA-1 was changed. In chromium/src[1] only 20% of the commits modify the content/renderer subtree relevant for the file. The recursivePath is necessary to check for '/' and remember if common subtree elimination should be attempted. When a file lives within a subtree the extra cost to check for unmodified subtrees saves time. However for files in the root tree the extra work incurred by TreeWalk is not worthwhile and would significantly increase overall running time. Now typical running times from an otherwise idle desktop: real 0m13.387s 0m13.341s 0m13.443s user 0m15.410s 0m15.220s 0m15.350s previously: real 0m14.085s 0m14.049s 0m13.968s user 0m15.730s 0m15.820s 0m15.770s [1] https://chromium.googlesource.com/chromium/src/+show/34d6e5c5b4248b1b199405af7ad00f961921f347/content/renderer/render_view_impl.cc Change-Id: Ib16d684df7ffa034ee28def3fb22c797998d5b7b --- .../src/org/eclipse/jgit/blame/BlameGenerator.java | 70 ++++++++++++++++------ .../src/org/eclipse/jgit/blame/Candidate.java | 7 +++ 2 files changed, 60 insertions(+), 17 deletions(-) diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java index 34e15475c3..5b02ce6c92 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java @@ -73,6 +73,7 @@ import org.eclipse.jgit.revwalk.RevCommit; import org.eclipse.jgit.revwalk.RevFlag; import org.eclipse.jgit.revwalk.RevWalk; import org.eclipse.jgit.treewalk.TreeWalk; +import org.eclipse.jgit.treewalk.filter.AndTreeFilter; import org.eclipse.jgit.treewalk.filter.PathFilter; import org.eclipse.jgit.treewalk.filter.TreeFilter; @@ -599,19 +600,19 @@ public class BlameGenerator { return split(n.getNextCandidate(0), n); revPool.parseHeaders(parent); - if (find(parent, n.sourcePath)) { - if (idBuf.equals(n.sourceBlob)) { - // The common case of the file not being modified in - // a simple string-of-pearls history. Blame parent. - n.sourceCommit = parent; - push(n); - return false; + if (n.sourceCommit != null && n.recursivePath) { + treeWalk.setFilter(AndTreeFilter.create(n.sourcePath, ID_DIFF)); + treeWalk.reset(n.sourceCommit.getTree(), parent.getTree()); + if (!treeWalk.next()) + return blameEntireRegionOnParent(n, parent); + if (isFile(treeWalk.getRawMode(1))) { + treeWalk.getObjectId(idBuf, 1); + return splitBlameWithParent(n, parent); } - - Candidate next = n.create(parent, n.sourcePath); - next.sourceBlob = idBuf.toObjectId(); - next.loadText(reader); - return split(next, n); + } else if (find(parent, n.sourcePath)) { + if (idBuf.equals(n.sourceBlob)) + return blameEntireRegionOnParent(n, parent); + return splitBlameWithParent(n, parent); } if (n.sourceCommit == null) @@ -625,7 +626,7 @@ public class BlameGenerator { // A 100% rename without any content change can also // skip directly to the parent. n.sourceCommit = parent; - n.sourcePath = PathFilter.create(r.getOldPath()); + n.setSourcePath(PathFilter.create(r.getOldPath())); push(n); return false; } @@ -637,6 +638,21 @@ public class BlameGenerator { return split(next, n); } + private boolean blameEntireRegionOnParent(Candidate n, RevCommit parent) { + // File was not modified, blame parent. + n.sourceCommit = parent; + push(n); + return false; + } + + private boolean splitBlameWithParent(Candidate n, RevCommit parent) + throws IOException { + Candidate next = n.create(parent, n.sourcePath); + next.sourceBlob = idBuf.toObjectId(); + next.loadText(reader); + return split(next, n); + } + private boolean split(Candidate parent, Candidate source) throws IOException { EditList editList = diffAlgorithm.diff(textComparator, @@ -673,9 +689,7 @@ public class BlameGenerator { if (!find(parent, n.sourcePath)) continue; if (!(n instanceof ReverseCandidate) && idBuf.equals(n.sourceBlob)) { - n.sourceCommit = parent; - push(n); - return false; + return blameEntireRegionOnParent(n, parent); } if (ids == null) ids = new ObjectId[pCnt]; @@ -707,7 +721,7 @@ public class BlameGenerator { // we choose to follow the one parent over trying to do // possibly both parents. n.sourceCommit = parent; - n.sourcePath = PathFilter.create(r.getOldPath()); + n.setSourcePath(PathFilter.create(r.getOldPath())); push(n); return false; } @@ -974,4 +988,26 @@ public class BlameGenerator { return ent.getChangeType() == ChangeType.RENAME || ent.getChangeType() == ChangeType.COPY; } + + private static final TreeFilter ID_DIFF = new TreeFilter() { + @Override + public boolean include(TreeWalk tw) { + return !tw.idEqual(0, 1); + } + + @Override + public boolean shouldBeRecursive() { + return false; + } + + @Override + public TreeFilter clone() { + return this; + } + + @Override + public String toString() { + return "ID_DIFF"; //$NON-NLS-1$ + } + }; } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/blame/Candidate.java b/org.eclipse.jgit/src/org/eclipse/jgit/blame/Candidate.java index cbc5b43a6b..a652278d05 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/blame/Candidate.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/blame/Candidate.java @@ -80,6 +80,7 @@ class Candidate { /** Path of the candidate file in {@link #sourceCommit}. */ PathFilter sourcePath; + boolean recursivePath; /** Unique name of the candidate blob in {@link #sourceCommit}. */ ObjectId sourceBlob; @@ -110,6 +111,7 @@ class Candidate { Candidate(RevCommit commit, PathFilter path) { sourceCommit = commit; sourcePath = path; + recursivePath = path.shouldBeRecursive(); } int getParentCount() { @@ -144,6 +146,11 @@ class Candidate { return sourceCommit.getAuthorIdent(); } + void setSourcePath(PathFilter path) { + sourcePath = path; + recursivePath = path.shouldBeRecursive(); + } + Candidate create(RevCommit commit, PathFilter path) { return new Candidate(commit, path); } -- cgit v1.2.3