RevWalk: use generation number to optimize getMergedInto()

A commit A can reach a commit B only if the generation number of A is
strictly larger than the generation number of B. This condition allows
significantly short-circuiting commit-graph walks.

On a copy of the Linux repository where HEAD is contained in v6.3-rc4
but no earlier tag, the command 'git tag --contains HEAD' of
ListTagCommand#call() had the following peformance improvement:
(excluded the startup time of the repo)

Before: 2649ms    (core.commitgraph=true)
        11909ms   (core.commitgraph=false)
After:  91ms     (core.commitgraph=true)
        11934ms   (core.commitgraph=false)

Bug: 574368
Change-Id: Ia2efaa4e9ae598266f72e70eb7e3b27655cbf85b
Signed-off-by: kylezhao <kylezhao@tencent.com>

1 files changed, 10 insertions, 0 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
index 9da7105566..3737c6b67b 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -550,6 +550,12 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 			reset(~freeFlags & APP_FLAGS);
 			filter = RevFilter.ALL;
 			treeFilter = TreeFilter.ALL;
+
+			// Make sure commit is parsed from commit-graph
+			if ((needle.flags & PARSED) == 0) {
+				needle.parseHeaders(this);
+			}
+			int cutoff = needle.getGeneration();
 			for (Ref r : haystacks) {
 				if (monitor.isCancelled()) {
 					return result;
@@ -565,6 +571,10 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 				boolean commitFound = false;
 				RevCommit next;
 				while ((next = next()) != null) {
+					if (next.getGeneration() < cutoff) {
+						markUninteresting(next);
+						uninteresting.add(next);
+					}
 					if (References.isSameObject(next, needle)
 							|| (next.flags & TEMP_MARK) != 0) {
 						result.add(r);