Introduce a PriorityQueue sorting RevCommits by commit timestamp

The DateRevQueue uses a tailor-made algorithm to keep
RevCommits sorted by reversed commit timestamp, which has a O(n*n/2)
complexity and caused the explosion of the Git fetch times to
tens of seconds.

The standard Java PriorityQueue provides a O(n*log(n)) complexity
and scales much better with the increase of the number of
RevCommits.

Introduce a new implementation DateRevPriorityQueue of the DateRevQueue
based on PriorityQueue.

Enable usage of the new DateRevPriorityQueue implementation by setting
the system property REVWALK_USE_PRIORITY_QUEUE=true. By default the old
implementation DateRevQueue is used.

Benchmark results:
```
(numCommits)  (usePriorityQueue)  Mode  Cnt     Score Error  Units
           5                true  avgt   10    39,4 ±   6,1  ns/op
           5               false  avgt   10    14,1 ±   2,2  ns/op
          10                true  avgt   10    29,7 ±   3,5  ns/op
          10               false  avgt   10    13,2 ±   2,0  ns/op
          50                true  avgt   10    50,4 ±   5,3  ns/op
          50               false  avgt   10    18,6 ±   0,2  ns/op
         100                true  avgt   10    58,3 ±   5,0  ns/op
         100               false  avgt   10    20,5 ±   0,8  ns/op
         500                true  avgt   10    51,7 ±   2,6  ns/op
         500               false  avgt   10    43,3 ±   0,5  ns/op
        1000                true  avgt   10    49,2 ±   2,4  ns/op
        1000               false  avgt   10    62,7 ±   0,2  ns/op
        5000                true  avgt   10    48,8 ±   1,5  ns/op
        5000               false  avgt   10   228,3 ±   0,5  ns/op
       10000                true  avgt   10    44,2 ±   0,9  ns/op
       10000               false  avgt   10   377,6 ±   2,7  ns/op
       50000                true  avgt   10    50,3 ±   1,6  ns/op
       50000               false  avgt   10   637,0 ± 111,8  ns/op
      100000                true  avgt   10    61,8 ±   4,4  ns/op
      100000               false  avgt   10   965,1 ± 268,0  ns/op
      500000                true  avgt   10   127,2 ±   7,9  ns/op
      500000               false  avgt   10  9610,2 ± 184,8  ns/op
```

Memory allocation results:
```
Number of commits loaded: 850 000
Custom implementation: 378 245 120 Bytes
Priority queue implementation: 340 495 616 Bytes
```

Bug: 580137
Change-Id: I8b33df6e9ee88933098ecc81ce32bdb189715041
Signed-off-by: Luca Milanesio <luca.milanesio@gmail.com>

5 files changed, 194 insertions, 15 deletions

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 3b5cc3d1f5..c7cad43d96 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -580,6 +580,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 0cabf07057..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);
 	}
@@ -56,7 +62,6 @@ public class DateRevQueue extends AbstractRevQueue {
 		}
 	}
 
-	/** {@inheritDoc} */
 	@Override
 	public void add(RevCommit c) {
 		sinceLastIndex++;
@@ -102,7 +107,6 @@ public class DateRevQueue extends AbstractRevQueue {
 		}
 	}
 
-	/** {@inheritDoc} */
 	@Override
 	public RevCommit next() {
 		final Entry q = head;
@@ -135,11 +139,10 @@ 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;
 	}
 
-	/** {@inheritDoc} */
 	@Override
 	public void clear() {
 		head = null;
@@ -173,7 +176,6 @@ public class DateRevQueue extends AbstractRevQueue {
 		return outputType | SORT_COMMIT_TIME_DESC;
 	}
 
-	/** {@inheritDoc} */
 	@Override
 	public String toString() {
 		final StringBuilder s = new StringBuilder();
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 3737c6b67b..2fb3a60690 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;
@@ -236,7 +237,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;
@@ -245,6 +246,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.
 	 *
@@ -848,7 +873,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		assertNotStarted();
 		assertNoCommitsMarkedStart();
 		firstParent = enable;
-		queue = new DateRevQueue(firstParent);
+		queue = newDateRevQueue(firstParent);
 		pending = new StartGenerator(this);
 	}
 
@@ -1566,7 +1591,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		}
 
 		roots.clear();
-		queue = new DateRevQueue(firstParent);
+		queue = newDateRevQueue(firstParent);
 		pending = new StartGenerator(this);
 	}
 
@@ -1587,7 +1612,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()) {