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>

1 files changed, 137 insertions, 0 deletions

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();
+	}
+
+}