tree 9fd2589c411da758136dc4e97b9fd2355651594d
parent 5e0cfce5ad48b84ca12526ef12461a72dde2800c
author Kaushik Lingarkar <quic_kaushikl@quicinc.com> 1620856669 -0700
committer Kaushik Lingarkar <quic_kaushikl@quicinc.com> 1621886368 -0700

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>