BatchRefUpdate: Skip saving conflicting ref names and prefixes in memory

Rather than getting all ref names and prefixes and saving them
in memory to perform the check for conflicting names, rely on
RefDirectory.isNameConflicting as it is no longer an expensive
call after it was optimized in Ie994fc.

The old optimization to save ref names and prefixes in memory
was targeted towards making clones faster. With this change,
the clone performance is unaffected when tests were done with
repos containing many(~500k) refs.

Here are few recorded elapsed times for creating 10 branches
using BatchRefUpdate on NFS based repositories with varying
loose refs count. As seen here, this change helps improve the
BatchRefUpdate performance from O(n^2) to O(1).

loose_refs_count  with_change  without_change
50                241 ms        310 ms
300               263 ms        1502 ms
1k                181 ms        4241 ms
2k                204 ms        6440 ms
9k                158 ms        25930 ms
20k               154 ms        60443 ms
50k               171 ms        135199 ms
110k              157 ms        329450 ms
160k              209 ms        396328 ms

This update improves the Gerrit notedb migration performance
as it uses BatchRefUpdate to write change meta refs similar to
the test performed above.

Change-Id: I853ac6c7feb4b39c3156c01876b38cbd182accfe
Signed-off-by: Kaushik Lingarkar <quic_kaushikl@quicinc.com>

1 files changed, 13 insertions, 41 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchRefUpdate.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchRefUpdate.java
index 925b6beadb..46d2ab3397 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchRefUpdate.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchRefUpdate.java
@@ -46,7 +46,6 @@ package org.eclipse.jgit.lib;
 
 import static org.eclipse.jgit.transport.ReceiveCommand.Result.NOT_ATTEMPTED;
 import static org.eclipse.jgit.transport.ReceiveCommand.Result.REJECTED_OTHER_REASON;
-import static java.util.stream.Collectors.toCollection;
 
 import java.io.IOException;
 import java.text.MessageFormat;
@@ -62,7 +61,6 @@ import java.util.concurrent.TimeoutException;
 import org.eclipse.jgit.annotations.Nullable;
 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.internal.JGitText;
-import org.eclipse.jgit.lib.RefUpdate.Result;
 import org.eclipse.jgit.revwalk.RevWalk;
 import org.eclipse.jgit.transport.PushCertificate;
 import org.eclipse.jgit.transport.ReceiveCommand;
@@ -528,42 +526,24 @@ public class BatchRefUpdate {
 			}
 		}
 		if (!commands2.isEmpty()) {
-			// What part of the name space is already taken
-			Collection<String> takenNames = refdb.getRefs().stream()
-					.map(Ref::getName)
-					.collect(toCollection(HashSet::new));
-			Collection<String> takenPrefixes = getTakenPrefixes(takenNames);
-
-			// Now to the update that may require more room in the name space
+			// Perform updates that may require more room in the name space
 			for (ReceiveCommand cmd : commands2) {
 				try {
 					if (cmd.getResult() == NOT_ATTEMPTED) {
 						cmd.updateType(walk);
 						RefUpdate ru = newUpdate(cmd);
-						SWITCH: switch (cmd.getType()) {
-						case DELETE:
-							// Performed in the first phase
-							break;
-						case UPDATE:
-						case UPDATE_NONFASTFORWARD:
-							RefUpdate ruu = newUpdate(cmd);
-							cmd.setResult(ruu.update(walk));
-							break;
-						case CREATE:
-							for (String prefix : getPrefixes(cmd.getRefName())) {
-								if (takenNames.contains(prefix)) {
-									cmd.setResult(Result.LOCK_FAILURE);
-									break SWITCH;
-								}
-							}
-							if (takenPrefixes.contains(cmd.getRefName())) {
-								cmd.setResult(Result.LOCK_FAILURE);
-								break SWITCH;
-							}
-							ru.setCheckConflicting(false);
-							takenPrefixes.addAll(getPrefixes(cmd.getRefName()));
-							takenNames.add(cmd.getRefName());
-							cmd.setResult(ru.update(walk));
+						switch (cmd.getType()) {
+							case DELETE:
+								// Performed in the first phase
+								break;
+							case UPDATE:
+							case UPDATE_NONFASTFORWARD:
+								RefUpdate ruu = newUpdate(cmd);
+								cmd.setResult(ruu.update(walk));
+								break;
+							case CREATE:
+								cmd.setResult(ru.update(walk));
+								break;
 						}
 					}
 				} catch (IOException err) {
@@ -635,14 +615,6 @@ public class BatchRefUpdate {
 		execute(walk, monitor, null);
 	}
 
-	private static Collection<String> getTakenPrefixes(Collection<String> names) {
-		Collection<String> ref = new HashSet<>();
-		for (String name : names) {
-			addPrefixesTo(name, ref);
-		}
-		return ref;
-	}
-
 	/**
 	 * Get all path prefixes of a ref name.
 	 *