Optimize RefDirectory.isNameConflicting()

Avoid having to scan over ALL loose refs to determine if the
name is nested within or is a container of an existing reference.
This can get really expensive if there are too many loose refs.
Instead use exactRef and getRefsByPrefix which scan based on a
prefix.

With a simple shell script(like below) using jgit client to create
1k refs in a new repository on NFS, this change brings down the time
from 12mins to 7mins.

for ref in $(seq 1 1000); do
    jgit branch "$ref"
done

Here are few recorded elapsed times to create a new branch on NFS
based repositories with varying loose refs count. As we see here,
this change improves the name conflicting check from O(n^2) to O(1).

loose_refs_count  with_change  without_change
50                44 ms        164 ms
300               45 ms        1193 ms
1k                38 ms        2610 ms
2k                44 ms        6003 ms
9k                46 ms        27860 ms
20k               45 ms        48591 ms
50k               51 ms        135471 ms
110k              43 ms        294252 ms
160k              52 ms        430976 ms

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

1 files changed, 3 insertions, 32 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 de7e4b3f25..f7a52a54b6 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
@@ -276,47 +276,18 @@ public class RefDirectory extends RefDatabase {
 	/** {@inheritDoc} */
 	@Override
 	public boolean isNameConflicting(String name) throws IOException {
-		RefList<Ref> packed = getPackedRefs();
-		RefList<LooseRef> loose = getLooseRefs();
-
 		// Cannot be nested within an existing reference.
 		int lastSlash = name.lastIndexOf('/');
 		while (0 < lastSlash) {
 			String needle = name.substring(0, lastSlash);
-			if (loose.contains(needle) || packed.contains(needle))
+			if (exactRef(needle) != null) {
 				return true;
+			}
 			lastSlash = name.lastIndexOf('/', lastSlash - 1);
 		}
 
 		// Cannot be the container of an existing reference.
-		String prefix = name + '/';
-		int idx;
-
-		idx = -(packed.find(prefix) + 1);
-		if (idx < packed.size() && packed.get(idx).getName().startsWith(prefix))
-			return true;
-
-		idx = -(loose.find(prefix) + 1);
-		if (idx < loose.size() && loose.get(idx).getName().startsWith(prefix))
-			return true;
-
-		return false;
-	}
-
-	private RefList<LooseRef> getLooseRefs() {
-		final RefList<LooseRef> oldLoose = looseRefs.get();
-
-		LooseScanner scan = new LooseScanner(oldLoose);
-		scan.scan(ALL);
-
-		RefList<LooseRef> loose;
-		if (scan.newLoose != null) {
-			loose = scan.newLoose.toRefList();
-			if (looseRefs.compareAndSet(oldLoose, loose))
-				modCnt.incrementAndGet();
-		} else
-			loose = oldLoose;
-		return loose;
+		return !getRefsByPrefix(name + '/').isEmpty();
 	}
 
 	/** {@inheritDoc} */