Optimize RefDirectory.getRefsByPrefix(String...)

Currently for file-based repositories JGit will go over all refs in the
repository forach `ref-prefix` listed in the `ls-refs` command in git
protocol v2 request.

Native git, uses a different approach, where all refs are read once and
then for each ref, all `ref-prefix` filter values are checked in one
pass.

This change implements this approach in JGit only in the `RefDirectory`
backend. And makes `ref-prefix` filtering ~40% faster for repositories
with packed refs.

Different implementations were tested on a synthetic file repository
with 10k refs in `refs/heads/` and `290k` in `refs/changes`. Before
testing `git pack-refs` command was executed. All results are in
seconds.

Current Impl:               39.340   37.093   35.996
Nested for loops:           25.077   24.742   24.748
Nested streams:             24.827   24.890   27.525
Parallel stream + stream:   23.357   23.318   23.174
Nested parallel streams:    23.490   23.318   23.317
Stream + for loop:          23.147   23.210   23.126
Parallel stream + for loop: 23.317   23.423   22.847

The elapsed time was measured around `getRefByPrefix` call in
`Uploadapack.getFilteredRefs(Collection<String>)` (around lines 952 and
954). For testing a modified version of
`UploadPackTest.testV2LsRefsRefPrefix()` was used. The modifications
here included:
  * shadowing protected `repo` variable with `FileRepository` pointing
    to the synthetic repo with 300k refs described above,
  * mimicking the git client clone request by adding `ref-prefix HEAD`,
    `ref-prefix refs/heads/` and `ref-prefix refs/tags/`

Based on the above results, the implementation with parallel stream and
stream was selected.

Bug: 578550
Signed-off-by: Dariusz Luksza <dariusz.luksza@gmail.com>
Change-Id: I6416846c074b611ff6ec9d351dbafcfbcaf68e66

2 files changed, 49 insertions, 0 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java
index 88d5d652e0..a00b80bb7d 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java
@@ -50,6 +50,7 @@ import java.util.Map;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
 import java.util.concurrent.locks.ReentrantLock;
+import java.util.stream.Collectors;
 import java.util.stream.Stream;
 
 import org.eclipse.jgit.annotations.NonNull;
@@ -81,6 +82,7 @@ import org.eclipse.jgit.util.IO;
 import org.eclipse.jgit.util.RawParseUtils;
 import org.eclipse.jgit.util.RefList;
 import org.eclipse.jgit.util.RefMap;
+import org.eclipse.jgit.util.StringUtils;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -392,6 +394,15 @@ public class RefDirectory extends RefDatabase {
 	}
 
 	@Override
+	public List<Ref> getRefsByPrefix(String... prefixes) throws IOException {
+		return getRefsByPrefix(StringUtils.commonPrefix(prefixes))
+				.parallelStream()
+				.filter(ref -> Stream.of(prefixes)
+						.anyMatch(ref.getName()::startsWith))
+				.collect(Collectors.toUnmodifiableList());
+	}
+
+	@Override
 	public List<Ref> getAdditionalRefs() throws IOException {
 		List<Ref> ret = new LinkedList<>();
 		for (String name : additionalRefsNames) {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java
index 274706042b..e1567c1864 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/StringUtils.java
@@ -14,6 +14,7 @@ import java.text.MessageFormat;
 import java.util.Collection;
 
 import org.eclipse.jgit.annotations.NonNull;
+import org.eclipse.jgit.annotations.Nullable;
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.lib.Constants;
 
@@ -22,6 +23,8 @@ import org.eclipse.jgit.lib.Constants;
  */
 public final class StringUtils {
 
+	private static final String EMPTY = ""; //$NON-NLS-1$
+
 	private static final long KiB = 1024;
 
 	private static final long MiB = 1024 * KiB;
@@ -463,4 +466,39 @@ public final class StringUtils {
 		}
 		return String.valueOf(value);
 	}
+
+	/**
+	 * Compares Strings and returns the initial sequence of characters that is
+	 * common to all of them.
+	 *
+	 * @param strings
+	 *            Strings to consider
+	 * @return common prefix of all Strings
+	 * @since 6.8
+	 */
+	public static @NonNull String commonPrefix(@Nullable String... strings) {
+		if (strings == null || strings.length == 0) {
+			return EMPTY;
+		}
+		if (strings.length == 1) {
+			return strings[0] == null ? EMPTY : strings[0];
+		}
+		String first = strings[0];
+		if (first == null) {
+			return EMPTY;
+		}
+		for (int i = 0; i < first.length(); i++) {
+			char currentChar = first.charAt(i);
+			for (int j = 1; j < strings.length; j++) {
+				String str = strings[j];
+				if (str == null) {
+					return EMPTY;
+				}
+				if (str.length() == i || currentChar != str.charAt(i)) {
+					return str.substring(0, i);
+				}
+			}
+		}
+		return first;
+	}
 }