Merge branch 'stable-6.7' into stable-6.8

* stable-6.7:
  Introduce a PriorityQueue sorting RevCommits by commit timestamp
  Remove org.eclipse.jgit.benchmark/.factorypath
  Update jmh to 1.37 for org.eclipse.jgit.benchmark

Change-Id: I5d49a9dc7da17b83243229d4d8d3b9ee0a063e65

11 files changed, 449 insertions, 41 deletions

diff --git a/Documentation/config-options.md b/Documentation/config-options.md
index 84c4f5a664..ec9d86bd8d 100644
--- a/Documentation/config-options.md
+++ b/Documentation/config-options.md
@@ -134,6 +134,13 @@ Proxy configuration uses the standard Java mechanisms via class `java.net.ProxyS
 |---------|---------|------------|-------------|
 | `repack.packKeptObjects` | `true` when `pack.buildBitmaps` is set, `false` otherwise | ✅ | Include objects in packs locked by a `.keep` file when repacking. |
 
+
+## Java System Properties
+
+| system property | default | description |
+|-----------------|---------|-------------|
+| `REVWALK_USE_PRIORITY_QUEUE` | `false` | If set to `true` `RevWalk` uses `DateRevPriorityQueue` which is faster, otherwise it uses the old `DateRevQueue`. |
+
 ## Tracing
 
 **GIT_TRACE_PERFORMANCE**: set this to `true` as a Java system property or environment variable to trace timings from the progress monitor. The system property takes
diff --git a/org.eclipse.jgit.benchmarks/.factorypath b/org.eclipse.jgit.benchmarks/.factorypath
deleted file mode 100644
index c631d4ac84..0000000000
--- a/org.eclipse.jgit.benchmarks/.factorypath
+++ /dev/null
@@ -1,29 +0,0 @@
-<factorypath>
-    <factorypathentry kind="VARJAR" id="M2_REPO/org/openjdk/jmh/jmh-generator-annprocess/1.32/jmh-generator-annprocess-1.32.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/org/openjdk/jmh/jmh-core/1.32/jmh-core-1.32.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/net/sf/jopt-simple/jopt-simple/4.6/jopt-simple-4.6.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/org/apache/commons/commons-math3/3.2/commons-math3-3.2.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/errorprone/error_prone_core/2.9.0/error_prone_core-2.9.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/errorprone/error_prone_annotation/2.9.0/error_prone_annotation-2.9.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/errorprone/error_prone_type_annotations/2.9.0/error_prone_type_annotations-2.9.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/errorprone/error_prone_check_api/2.9.0/error_prone_check_api-2.9.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/io/github/java-diff-utils/java-diff-utils/4.0/java-diff-utils-4.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/org/eclipse/jgit/org.eclipse.jgit/4.4.1.201607150455-r/org.eclipse.jgit-4.4.1.201607150455-r.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/github/kevinstern/software-and-algorithms/1.0/software-and-algorithms-1.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/github/ben-manes/caffeine/caffeine/2.8.8/caffeine-2.8.8.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/org/pcollections/pcollections/2.1.2/pcollections-2.1.2.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/guava/guava/30.1-jre/guava-30.1-jre.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/guava/failureaccess/1.0.1/failureaccess-1.0.1.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/guava/listenablefuture/9999.0-empty-to-avoid-conflict-with-guava/listenablefuture-9999.0-empty-to-avoid-conflict-with-guava.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/org/checkerframework/checker-qual/3.5.0/checker-qual-3.5.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/j2objc/j2objc-annotations/1.3/j2objc-annotations-1.3.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/auto/auto-common/1.1.2/auto-common-1.1.2.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/code/findbugs/jFormatString/3.0.0/jFormatString-3.0.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/code/findbugs/jsr305/3.0.0/jsr305-3.0.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/org/checkerframework/dataflow-errorprone/3.15.0/dataflow-errorprone-3.15.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/errorprone/javac/9+181-r4173-1/javac-9+181-r4173-1.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/auto/value/auto-value-annotations/1.7/auto-value-annotations-1.7.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/errorprone/error_prone_annotations/2.9.0/error_prone_annotations-2.9.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/protobuf/protobuf-java/3.4.0/protobuf-java-3.4.0.jar" enabled="true" runInBatchMode="false"/>
-    <factorypathentry kind="VARJAR" id="M2_REPO/com/google/auto/service/auto-service-annotations/1.0-rc6/auto-service-annotations-1.0-rc6.jar" enabled="true" runInBatchMode="false"/>
-</factorypath>
diff --git a/org.eclipse.jgit.benchmarks/src/org/eclipse/jgit/revwalk/DateRevQueueBenchmark.java b/org.eclipse.jgit.benchmarks/src/org/eclipse/jgit/revwalk/DateRevQueueBenchmark.java
new file mode 100644
index 0000000000..71075a8b4c
--- /dev/null
+++ b/org.eclipse.jgit.benchmarks/src/org/eclipse/jgit/revwalk/DateRevQueueBenchmark.java
@@ -0,0 +1,137 @@
+/*
+ * Copyright (C) 2023, GerritForge Ltd
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.revwalk;
+
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.TimeUnit;
+
+import org.eclipse.jgit.api.Git;
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.util.FileUtils;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.TearDown;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.runner.Runner;
+import org.openjdk.jmh.runner.RunnerException;
+import org.openjdk.jmh.runner.options.Options;
+import org.openjdk.jmh.runner.options.OptionsBuilder;
+
+@State(Scope.Thread)
+public class DateRevQueueBenchmark {
+
+	ThreadLocalRandom commitsIndex = ThreadLocalRandom.current();
+
+	@State(Scope.Benchmark)
+	public static class BenchmarkState {
+
+		@Param({ "5", "10", "50", "100", "500", "1000", "5000", "10000",
+				"50000", "100000", "500000" })
+		int numCommits;
+
+		@Param({ "true", "false" })
+		boolean usePriorityQueue;
+
+		int low, count;
+
+		RevCommit[] commits = new RevCommit[numCommits];
+
+		private Path testDir;
+
+		private TestRepository<Repository> repoUtil;
+
+		DateRevQueue queue;
+
+		@Setup
+		public void setupBenchmark() throws Exception {
+			testDir = Files.createTempDirectory("testrepos");
+			String repoName = "commits-" + numCommits + "-usePriorityQueue-"
+					+ usePriorityQueue;
+			Path workDir = testDir.resolve(repoName);
+			Git git = Git.init().setDirectory(workDir.toFile()).call();
+			repoUtil = new TestRepository<>(git.getRepository());
+
+			RevCommit parent = repoUtil.commit().create();
+			commits = new RevCommit[numCommits];
+			commits[0] = parent;
+			for (int i = 1; i < numCommits; i++) {
+				parent = repoUtil.parseBody(repoUtil.commit(i, parent));
+				commits[i] = parent;
+				if (i % 10000 == 0) {
+					System.out.println(" " + i + " done");
+				}
+			}
+
+			if (usePriorityQueue) {
+				queue = new DateRevPriorityQueue(false);
+			} else {
+				queue = new DateRevQueue(false);
+			}
+
+			low = 9 * numCommits / 10;
+			ThreadLocalRandom random = ThreadLocalRandom.current();
+			// add 90% * numCommits commits, benchmark adding commits from
+			// 90-100%
+			for (int i = 0; i < low; i++) {
+				RevCommit commit = commits[random.nextInt(numCommits)];
+				queue.add(commit);
+				++count;
+			}
+		}
+
+		@TearDown(Level.Invocation)
+		public void check() {
+			// if queue is full remove 10% of its entries
+			if (++count == numCommits) {
+				do {
+					queue.next();
+				} while (--count > low);
+			}
+		}
+
+		@TearDown
+		public void teardown() throws IOException {
+			repoUtil.close();
+			FileUtils.delete(testDir.toFile(),
+					FileUtils.RECURSIVE | FileUtils.RETRY);
+		}
+	}
+
+	@Benchmark
+	@BenchmarkMode({ Mode.AverageTime })
+	@OutputTimeUnit(TimeUnit.NANOSECONDS)
+	@Warmup(iterations = 2, time = 100, timeUnit = TimeUnit.MILLISECONDS)
+	@Measurement(iterations = 10, time = 10, timeUnit = TimeUnit.SECONDS)
+	public void testDataRevQueue(BenchmarkState state) throws Exception {
+		RevCommit commit = state.commits[commitsIndex
+				.nextInt(state.numCommits)];
+		state.queue.add(commit);
+	}
+
+	public static void main(String[] args) throws RunnerException {
+		Options opt = new OptionsBuilder()
+				.include(DateRevQueueBenchmark.class.getSimpleName()).forks(1)
+				.jvmArgs("-ea").build();
+		new Runner(opt).run();
+	}
+
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/DateRevPriorityQueueTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/DateRevPriorityQueueTest.java
new file mode 100644
index 0000000000..369e2fae72
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/DateRevPriorityQueueTest.java
@@ -0,0 +1,109 @@
+/*
+ * Copyright (C) 2023, GerritForge Inc. and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.revwalk;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+
+import org.junit.Test;
+
+public class DateRevPriorityQueueTest extends RevQueueTestCase<DateRevPriorityQueue> {
+	@Override
+	protected DateRevPriorityQueue create() {
+		return new DateRevPriorityQueue();
+	}
+
+	@Override
+	@Test
+	public void testEmpty() throws Exception {
+		super.testEmpty();
+		assertNull(q.peek());
+		assertEquals(Generator.SORT_COMMIT_TIME_DESC, q.outputType());
+	}
+
+	@Test
+	public void testCloneEmpty() throws Exception {
+		q = new DateRevPriorityQueue(AbstractRevQueue.EMPTY_QUEUE);
+		assertNull(q.next());
+	}
+
+	@Test
+	public void testInsertOutOfOrder() throws Exception {
+		final RevCommit a = parseBody(commit());
+		final RevCommit b = parseBody(commit(10, a));
+		final RevCommit c1 = parseBody(commit(5, b));
+		final RevCommit c2 = parseBody(commit(-50, b));
+
+		q.add(c2);
+		q.add(a);
+		q.add(b);
+		q.add(c1);
+
+		assertCommit(c1, q.next());
+		assertCommit(b, q.next());
+		assertCommit(a, q.next());
+		assertCommit(c2, q.next());
+		assertNull(q.next());
+	}
+
+	@Test
+	public void testInsertTie() throws Exception {
+		final RevCommit a = parseBody(commit());
+		final RevCommit b = parseBody(commit(0, a));
+		final RevCommit c = parseBody(commit(0, b));
+
+		{
+			q = create();
+			q.add(a);
+			q.add(b);
+			q.add(c);
+
+			assertCommit(a, q.next());
+			assertCommit(b, q.next());
+			assertCommit(c, q.next());
+			assertNull(q.next());
+		}
+		{
+			q = create();
+			q.add(c);
+			q.add(b);
+			q.add(a);
+
+			assertCommit(c, q.next());
+			assertCommit(b, q.next());
+			assertCommit(a, q.next());
+			assertNull(q.next());
+		}
+	}
+
+	@Test
+	public void testCloneFIFO() throws Exception {
+		final RevCommit a = parseBody(commit());
+		final RevCommit b = parseBody(commit(200, a));
+		final RevCommit c = parseBody(commit(200, b));
+
+		final FIFORevQueue src = new FIFORevQueue();
+		src.add(a);
+		src.add(b);
+		src.add(c);
+
+		q = new DateRevPriorityQueue(src);
+		assertFalse(q.everbodyHasFlag(RevWalk.UNINTERESTING));
+		assertFalse(q.anybodyHasFlag(RevWalk.UNINTERESTING));
+		assertCommit(c, q.peek());
+		assertCommit(c, q.peek());
+
+		assertCommit(c, q.next());
+		assertCommit(b, q.next());
+		assertCommit(a, q.next());
+		assertNull(q.next());
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCarryFlagsTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCarryFlagsTest.java
index 8c25e05986..529d5a9f09 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCarryFlagsTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCarryFlagsTest.java
@@ -39,7 +39,7 @@ public class RevWalkCarryFlagsTest extends RevWalkTestCase {
 	/**
 	 * Similar to {@link #testRevWalkCarryUninteresting_fastClock()} but the
 	 * last merge commit is created so fast that he has the same creationdate as
-	 * the previous commit. This will cause the underlying {@link DateRevQueue}
+	 * the previous commit. This will cause the underlying {@link AbstractRevQueue}
 	 * is not able to sort the commits in a way matching the topology. A parent
 	 * (one of the commits which are merged) is handled before the child (the
 	 * merge commit). This makes carrying over flags more complicated
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 3798e3f5f8..c54c811b57 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -557,6 +557,7 @@ nothingToPush=Nothing to push.
 notMergedExceptionMessage=Branch was not deleted as it has not been merged yet; use the force option to delete it anyway
 notShallowedUnshallow=The server sent a unshallow for a commit that wasn''t marked as shallow: {0}
 noXMLParserAvailable=No XML parser available.
+nullRevCommit=RevCommit is null
 numberDoesntFit=Number doesn't fit in a single byte
 objectAtHasBadZlibStream=Object at {0} in {1} has bad zlib stream
 objectIsCorrupt=Object {0} is corrupt: {1}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
index c8509121b4..b7175508ee 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -587,6 +587,7 @@ public class JGitText extends TranslationBundle {
 	/***/ public String notMergedExceptionMessage;
 	/***/ public String notShallowedUnshallow;
 	/***/ public String noXMLParserAvailable;
+	/***/ public String nullRevCommit;
 	/***/ public String numberDoesntFit;
 	/***/ public String objectAtHasBadZlibStream;
 	/***/ public String objectIsCorrupt;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevPriorityQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevPriorityQueue.java
new file mode 100644
index 0000000000..233dd64a3c
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevPriorityQueue.java
@@ -0,0 +1,150 @@
+/*
+ * Copyright (C) 2023, GerritForge Ltd
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.revwalk;
+
+import java.util.concurrent.atomic.AtomicInteger;
+
+import org.eclipse.jgit.annotations.Nullable;
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.JGitText;
+
+import java.io.IOException;
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+/**
+ * A queue of commits sorted by commit time order using a Java PriorityQueue.
+ * For the commits with the same commit time insertion order will be preserved.
+ */
+class DateRevPriorityQueue extends DateRevQueue {
+	private PriorityQueue<RevCommitEntry> queue;
+
+	private final AtomicInteger sequence = new AtomicInteger(1);
+
+	/**
+	 * Create an empty queue of commits sorted by commit time order.
+	 */
+	public DateRevPriorityQueue() {
+		this(false);
+	}
+
+	/**
+	 * Create an empty queue of commits sorted by commit time order.
+	 *
+	 * @param firstParent
+	 *            treat first element as a parent
+	 */
+	DateRevPriorityQueue(boolean firstParent) {
+		super(firstParent);
+		initPriorityQueue();
+	}
+
+	private void initPriorityQueue() {
+		sequence.set(1);
+		queue = new PriorityQueue<>(Comparator.comparingInt(
+						(RevCommitEntry ent) -> ent.getEntry().getCommitTime())
+				.reversed()
+				.thenComparingInt(RevCommitEntry::getInsertSequenceNumber));
+	}
+
+    DateRevPriorityQueue(Generator s) throws MissingObjectException,
+			IncorrectObjectTypeException, IOException {
+		this(s.firstParent);
+		for (;;) {
+			final RevCommit c = s.next();
+			if (c == null) {
+				break;
+			}
+			add(c);
+		}
+	}
+
+	@Override
+	public void add(RevCommit c) {
+		// PriorityQueue does not accept null values. To keep the same behaviour
+		// do the same check and throw the same exception before creating entry
+		if (c == null) {
+			throw new NullPointerException(JGitText.get().nullRevCommit);
+		}
+		queue.add(new RevCommitEntry(sequence.getAndIncrement(), c));
+	}
+
+	@Override
+	public RevCommit next() {
+		RevCommitEntry entry = queue.poll();
+		return entry == null ? null : entry.getEntry();
+	}
+
+	/**
+	 * Peek at the next commit, without removing it.
+	 *
+	 * @return the next available commit; null if there are no commits left.
+	 */
+	@Override
+	public @Nullable RevCommit peek() {
+		RevCommitEntry entry = queue.peek();
+		return entry == null ? null : entry.getEntry();
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	@Override
+	public void clear() {
+		sequence.set(1);
+		queue.clear();
+	}
+
+	@Override
+	boolean everbodyHasFlag(int f) {
+		return queue.stream().map(RevCommitEntry::getEntry)
+				.noneMatch(c -> (c.flags & f) == 0);
+	}
+
+	@Override
+	boolean anybodyHasFlag(int f) {
+		return queue.stream().map(RevCommitEntry::getEntry)
+				.anyMatch(c -> (c.flags & f) != 0);
+	}
+
+	@Override
+	int outputType() {
+		return outputType | SORT_COMMIT_TIME_DESC;
+	}
+
+	@Override
+	public String toString() {
+		final StringBuilder s = new StringBuilder();
+		for (RevCommitEntry e : queue) {
+			describe(s, e.getEntry());
+		}
+		return s.toString();
+	}
+
+	private static class RevCommitEntry {
+		private final int insertSequenceNumber;
+
+		private final RevCommit entry;
+
+		public RevCommitEntry(int insertSequenceNumber, RevCommit entry) {
+			this.insertSequenceNumber = insertSequenceNumber;
+			this.entry = entry;
+		}
+
+		public int getInsertSequenceNumber() {
+			return insertSequenceNumber;
+		}
+
+		public RevCommit getEntry() {
+			return entry;
+		}
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java
index 4ec9afc718..905dcb62ad 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java
@@ -8,11 +8,11 @@
  *
  * SPDX-License-Identifier: BSD-3-Clause
  */
-
 package org.eclipse.jgit.revwalk;
 
 import java.io.IOException;
 
+import org.eclipse.jgit.annotations.Nullable;
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
 import org.eclipse.jgit.errors.MissingObjectException;
 
@@ -36,11 +36,17 @@ public class DateRevQueue extends AbstractRevQueue {
 
 	private int last = -1;
 
-	/** Create an empty date queue. */
+	/** Create an empty DateRevQueue. */
 	public DateRevQueue() {
 		super(false);
 	}
 
+	/**
+	 * Create an empty DateRevQueue.
+	 *
+	 * @param firstParent
+	 *            treat first element as a parent
+	 */
 	DateRevQueue(boolean firstParent) {
 		super(firstParent);
 	}
@@ -133,7 +139,7 @@ public class DateRevQueue extends AbstractRevQueue {
 	 *
 	 * @return the next available commit; null if there are no commits left.
 	 */
-	public RevCommit peek() {
+	public @Nullable RevCommit peek() {
 		return head != null ? head.commit : null;
 	}
 
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 0d9ccdbc1b..76c14e9c26 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -21,6 +21,7 @@ import java.util.Collection;
 import java.util.EnumSet;
 import java.util.Iterator;
 import java.util.List;
+import java.util.Optional;
 
 import org.eclipse.jgit.annotations.NonNull;
 import org.eclipse.jgit.annotations.Nullable;
@@ -235,7 +236,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		idBuffer = new MutableObjectId();
 		objects = new ObjectIdOwnerMap<>();
 		roots = new ArrayList<>();
-		queue = new DateRevQueue(false);
+		queue = newDateRevQueue(false);
 		pending = new StartGenerator(this);
 		sorting = EnumSet.of(RevSort.NONE);
 		filter = RevFilter.ALL;
@@ -244,6 +245,30 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		commitGraph = null;
 	}
 
+	static AbstractRevQueue newDateRevQueue(boolean firstParent) {
+		if(usePriorityQueue()) {
+			return new DateRevPriorityQueue(firstParent);
+		}
+
+		return new DateRevQueue(firstParent);
+	}
+
+	static DateRevQueue newDateRevQueue(Generator g) throws IOException {
+		if(usePriorityQueue()) {
+			return new DateRevPriorityQueue(g);
+		}
+
+		return new DateRevQueue(g);
+	}
+
+	@SuppressWarnings("boxing")
+	private static boolean usePriorityQueue() {
+		return Optional
+				.ofNullable(System.getProperty("REVWALK_USE_PRIORITY_QUEUE")) //$NON-NLS-1$
+							.map(Boolean::parseBoolean)
+							.orElse(false);
+	}
+
 	/**
 	 * Get the reader this walker is using to load objects.
 	 *
@@ -847,7 +872,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		assertNotStarted();
 		assertNoCommitsMarkedStart();
 		firstParent = enable;
-		queue = new DateRevQueue(firstParent);
+		queue = newDateRevQueue(firstParent);
 		pending = new StartGenerator(this);
 	}
 
@@ -1567,7 +1592,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		}
 
 		roots.clear();
-		queue = new DateRevQueue(firstParent);
+		queue = newDateRevQueue(firstParent);
 		pending = new StartGenerator(this);
 	}
 
@@ -1588,7 +1613,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		firstParent = false;
 		objects.clear();
 		roots.clear();
-		queue = new DateRevQueue(firstParent);
+		queue = newDateRevQueue(firstParent);
 		pending = new StartGenerator(this);
 		shallowCommitsInitialized = false;
 	}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
index a79901ca10..414af30486 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
@@ -93,10 +93,11 @@ class StartGenerator extends Generator {
 
 		final DateRevQueue pending;
 		int pendingOutputType = 0;
-		if (q instanceof DateRevQueue)
-			pending = (DateRevQueue)q;
-		else
-			pending = new DateRevQueue(q);
+		if (q instanceof DateRevQueue) {
+			pending = (DateRevQueue) q;
+		} else {
+			pending = RevWalk.newDateRevQueue(q);
+		}
 		if (tf != TreeFilter.ALL) {
 			int rewriteFlag;
 			if (w.getRewriteParents()) {