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>

2 files changed, 110 insertions, 1 deletions

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