BlameGenerator: introduce Commit Graph based performance boosts BlameGenerator inflates the body all returning commits with its result() method, so there's no need to parse the body in majority of the iterating commits. Since the RevWalk is self-contained within the BlameGenerator and no customization to it can be done, we don't have to worry about a filter that might require commit bodies. By turning off the retainBody flag, all commits will be prioritized to be loaded from Commit Graph first. Additionally, we can take advantage of ChangedPathFilter within PathAnyDiffFilter to quickly skip commits that did not modify the file. If useCommitGraphOptimizations is true, disable RetainBody and use ChangedPathFilter. Added a blameGeneratorStats class to track the numbers of object parsing done within BlameGenerator and its ChangedPathFilter usage. Signed-off-by: Xing Huang <xingkhuang@google.com> Change-Id: I2c3bbd632cdc2d2d7ad011a4994ff7c9b6f73608
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 979c8ce..c3653dc 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java
@@ -58,6 +58,7 @@ import org.eclipse.jgit.treewalk.FileTreeIterator; import org.eclipse.jgit.treewalk.TreeWalk; import org.eclipse.jgit.treewalk.TreeWalk.OperationType; +import org.eclipse.jgit.treewalk.filter.ChangedPathTreeFilter; import org.eclipse.jgit.treewalk.filter.PathFilter; import org.eclipse.jgit.treewalk.filter.TreeFilter; import org.eclipse.jgit.util.IO; @@ -144,6 +145,12 @@ public class BlameGenerator implements AutoCloseable { private final Stats stats = new Stats(); + private boolean useCommitGraphOptimizations; + + private ChangedPathTreeFilter changedPathTreeFilter; + + private final TreeFilter.MutableBoolean changedPathFilterUsed = new TreeFilter.MutableBoolean(); + /** * Create a blame generator for the repository and path (relative to * repository) @@ -268,6 +275,27 @@ public BlameGenerator setFollowFileRenames(boolean follow) { } /** + * Enable Commit Graph related optimizations. + * <p> + * If true, all commits will be parsed from Commit Graph if Commit Graph is + * available. Use ChangedPathFilter if available. + * + * @param useCommitGraph + * set useCommitGraphOptimizations. + * @return {@code this} + * + * @since 7.8 + */ + public BlameGenerator setUseCommitGraphOptimizations( + boolean useCommitGraph) { + useCommitGraphOptimizations = useCommitGraph; + changedPathTreeFilter = ChangedPathTreeFilter + .create(resultPath.getPath()); + revPool.setRetainBody(!useCommitGraph); + return this; + } + + /** * Obtain the RenameDetector, allowing the application to configure its * settings for rename score and breaking behavior. * @@ -481,6 +509,7 @@ public BlameGenerator push(String description, AnyObjectId id) resultPath); c.sourceBlob = id.toObjectId(); c.sourceText = new RawText(ldr.getCachedBytes(Integer.MAX_VALUE)); + stats.blobsParsed++; c.regionList = new Region(0, 0, c.sourceText.size()); remaining = c.sourceText.size(); push(c); @@ -494,6 +523,7 @@ public BlameGenerator push(String description, AnyObjectId id) Candidate c = new Candidate(getRepository(), commit, resultPath); c.sourceBlob = idBuf.toObjectId(); c.loadText(reader); + stats.blobsParsed++; c.regionList = new Region(0, 0, c.sourceText.size()); remaining = c.sourceText.size(); push(c); @@ -579,6 +609,7 @@ public BlameGenerator reverse(AnyObjectId start, resultPath); c.sourceBlob = idBuf.toObjectId(); c.loadText(reader); + stats.blobsParsed++; c.regionList = new Region(0, 0, c.sourceText.size()); remaining = c.sourceText.size(); push(c); @@ -652,7 +683,6 @@ public boolean next() throws IOException { if (n == null) return done(); stats.candidatesVisited += 1; - int pCnt = n.getParentCount(); if (pCnt == 1) { if (processOne(n)) @@ -783,9 +813,33 @@ private boolean processOne(Candidate n) throws IOException { return split(n.getNextCandidate(0), n); revPool.parseHeaders(parent); - if (find(parent, n.sourcePath)) { - if (idBuf.equals(n.sourceBlob)) + if (useCommitGraphOptimizations) { + RevCommit c = n.sourceCommit; + String path = n.sourcePath.getPath(); + if (!changedPathTreeFilter.getPaths().contains(path)) { + changedPathTreeFilter.setPaths(path); + } + changedPathFilterUsed.reset(); + boolean mightHaveChangedFile = changedPathTreeFilter + .shouldTreeWalk(c, revPool, changedPathFilterUsed); + if (!mightHaveChangedFile) { + // commit didn't change the file or renamed the file. + stats.changedPathFilterNegative++; return blameEntireRegionOnParent(n, parent); + } + } + + // parent has access to the same file + if (find(parent, n.sourcePath)) { + if (idBuf.equals(n.sourceBlob)) { + if (changedPathFilterUsed.get()) { + stats.changedPathFilterFalsePositive++; + } + return blameEntireRegionOnParent(n, parent); + } + if (changedPathFilterUsed.get()) { + stats.changedPathFilterTruePositive++; + } return splitBlameWithParent(n, parent); } @@ -793,10 +847,17 @@ private boolean processOne(Candidate n) throws IOException { return result(n); DiffEntry r = findRename(parent, n.sourceCommit, n.sourcePath); - if (r == null) + if (r == null) { + if (changedPathFilterUsed.get()) { + stats.changedPathFilterTruePositive++; + } return result(n); + } if (0 == r.getOldId().prefixCompare(n.sourceBlob)) { + if (changedPathFilterUsed.get()) { + stats.changedPathFilterTruePositive++; + } // A 100% rename without any content change can also // skip directly to the parent. Candidate cached = blameFromCache(n); @@ -809,12 +870,17 @@ private boolean processOne(Candidate n) throws IOException { return false; } + // commit renamed the file and made content change + if (changedPathFilterUsed.get()) { + stats.changedPathFilterTruePositive++; + } Candidate next = n.create(getRepository(), parent, PathFilter.create(r.getOldPath())); next.sourceBlob = r.getOldId().toObjectId(); next.renameScore = r.getScore(); next.loadText(reader); + stats.blobsParsed++; return split(next, n); } @@ -830,6 +896,7 @@ private boolean splitBlameWithParent(Candidate n, RevCommit parent) Candidate next = n.create(getRepository(), parent, n.sourcePath); next.sourceBlob = idBuf.toObjectId(); next.loadText(reader); + stats.blobsParsed++; return split(next, n); } @@ -938,6 +1005,7 @@ private boolean processMerge(Candidate n) throws IOException { editList = new EditList(0); } else { p.loadText(reader); + stats.blobsParsed++; editList = diffAlgorithm.diff(textComparator, p.sourceText, n.sourceText); } @@ -1192,6 +1260,7 @@ public void close() { private boolean find(RevCommit commit, PathFilter path) throws IOException { treeWalk.setFilter(path); treeWalk.reset(commit.getTree()); + stats.treesParsed++; if (treeWalk.next() && isFile(treeWalk.getRawMode(0))) { treeWalk.getObjectId(idBuf, 0); return true; @@ -1210,6 +1279,7 @@ private DiffEntry findRename(RevCommit parent, RevCommit commit, treeWalk.setFilter(TreeFilter.ANY_DIFF); treeWalk.reset(parent.getTree(), commit.getTree()); + stats.treesParsed += 2; List<DiffEntry> diffs = DiffEntry.scan(treeWalk); FilteredRenameDetector filteredRenameDetector = new FilteredRenameDetector( renameDetector); @@ -1237,6 +1307,16 @@ public static class Stats { private boolean cacheHit; + private int blobsParsed; + + private int treesParsed; + + private int changedPathFilterNegative; + + private int changedPathFilterTruePositive; + + private int changedPathFilterFalsePositive; + /** * Number of candidates taken from the queue * <p> @@ -1258,5 +1338,64 @@ public int getCandidatesVisited() { public boolean isCacheHit() { return cacheHit; } + + /** + * Number of blobs parsed + * + * @return number of blobs parsed + * + * @since 7.8 + */ + public int getBlobsParsed() { + return blobsParsed; + } + + /** + * Number of trees parsed + * + * @return number of trees parsed + * + * @since 7.8 + */ + public int getTreesParsed() { + return treesParsed; + } + + /** + * Times the changedPathFilter said the commit does not touch a path + * + * @return count of times the changed path filter returned false + * + * @since 7.8 + */ + public int getChangedPathFilterNegative() { + return changedPathFilterNegative; + } + + /** + * Times the changedPathFilter said the commit does contain a path, and + * it was true. + * + * @return count of times the changed path filter returned true and + * later it was right. + * + * @since 7.8 + */ + public int getChangedPathFilterTruePositive() { + return changedPathFilterTruePositive; + } + + /** + * Times the changedPathFilter said the commit does contains a path, and + * later it was not true. + * + * @return count of times the changed path filter returned true and + * later was wrong. + * + * @since 7.8 + */ + public int getChangedPathFilterFalsePositive() { + return changedPathFilterFalsePositive; + } } }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/filter/ChangedPathTreeFilter.java b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/filter/ChangedPathTreeFilter.java index 6371d2a..5405216 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/filter/ChangedPathTreeFilter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/filter/ChangedPathTreeFilter.java
@@ -10,6 +10,11 @@ package org.eclipse.jgit.treewalk.filter; +import java.io.IOException; +import java.util.Arrays; +import java.util.List; +import java.util.stream.Collectors; + import org.eclipse.jgit.internal.JGitText; import org.eclipse.jgit.internal.storage.commitgraph.ChangedPathFilter; import org.eclipse.jgit.lib.Constants; @@ -19,11 +24,6 @@ import org.eclipse.jgit.treewalk.TreeWalk; import org.eclipse.jgit.util.StringUtils; -import java.io.IOException; -import java.util.Arrays; -import java.util.List; -import java.util.stream.Collectors; - /** * Filter tree entries that modified the contents of particular file paths. * <p> @@ -64,28 +64,7 @@ public static ChangedPathTreeFilter create(String... paths) { } private ChangedPathTreeFilter(String... paths) { - List<String> filtered = Arrays.stream(paths) - .map(s -> StringUtils.trim(s, '/')) - .collect(Collectors.toList()); - - if (filtered.size() == 0) - throw new IllegalArgumentException( - JGitText.get().atLeastOnePathIsRequired); - - if (filtered.stream().anyMatch(s -> s.isEmpty() || s.isBlank())) { - throw new IllegalArgumentException( - JGitText.get().emptyPathNotPermitted); - } - - this.paths = filtered; - this.rawPaths = this.paths.stream().map(Constants::encode) - .collect(Collectors.toList()); - if (filtered.size() == 1) { - this.pathFilter = PathFilter.create(paths[0]); - } else { - this.pathFilter = OrTreeFilter.create(Arrays.stream(paths) - .map(PathFilter::create).collect(Collectors.toList())); - } + setPaths(paths); } @Override @@ -147,6 +126,38 @@ public List<String> getPaths() { return paths; } + /** + * Reset the paths this filter matches to a new array of paths. + * + * @param paths + * new paths that this filter matches with. + * @since 7.8 + */ + public void setPaths(String... paths) { + List<String> filtered = Arrays.stream(paths) + .map(s -> StringUtils.trim(s, '/')) + .collect(Collectors.toList()); + + if (filtered.size() == 0) + throw new IllegalArgumentException( + JGitText.get().atLeastOnePathIsRequired); + + if (filtered.stream().anyMatch(s -> s.isEmpty() || s.isBlank())) { + throw new IllegalArgumentException( + JGitText.get().emptyPathNotPermitted); + } + + this.paths = filtered; + this.rawPaths = this.paths.stream().map(Constants::encode) + .collect(Collectors.toList()); + if (filtered.size() == 1) { + this.pathFilter = PathFilter.create(paths[0]); + } else { + this.pathFilter = OrTreeFilter.create(Arrays.stream(paths) + .map(PathFilter::create).collect(Collectors.toList())); + } + } + @SuppressWarnings("nls") @Override public String toString() {