diff options
| author | Dariusz Luksza <dariusz.luksza@gmail.com> | 2023-11-09 11:18:38 +0000 |
|---|---|---|
| committer | Matthias Sohn <matthias.sohn@sap.com> | 2023-11-12 13:31:16 +0100 |
| commit | 4f18c5095049116350828e9bb499964ea887ac02 (patch) | |
| tree | c28abccba578d5d811a27488cafde98dd2a69402 | |
| parent | 1b28c2d0018b06ee54de2d1237b5d42d98160706 (diff) | |
| download | jgit-4f18c5095049116350828e9bb499964ea887ac02.tar.gz jgit-4f18c5095049116350828e9bb499964ea887ac02.zip | |
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
4 files changed, 81 insertions, 0 deletions
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/RefDirectoryTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/RefDirectoryTest.java index 619e585a90..2bafde65d3 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/RefDirectoryTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/RefDirectoryTest.java @@ -51,6 +51,7 @@ import org.eclipse.jgit.lib.Repository; import org.eclipse.jgit.revwalk.RevCommit; import org.eclipse.jgit.revwalk.RevTag; import org.eclipse.jgit.util.FS; +import org.eclipse.jgit.util.StringUtils; import org.junit.Before; import org.junit.Test; @@ -1349,6 +1350,18 @@ public class RefDirectoryTest extends LocalDiskRepositoryTestCase { assertEquals(Storage.LOOSE, ref.getStorage()); } + @Test + public void testCommonRefPrefix() { + assertEquals("", StringUtils.commonPrefix()); + assertEquals("HEAD", StringUtils.commonPrefix("HEAD")); + assertEquals("", StringUtils.commonPrefix("HEAD", "")); + assertEquals("", StringUtils.commonPrefix("HEAD", "refs/heads/")); + assertEquals("refs/heads/", + StringUtils.commonPrefix("refs/heads/master", "refs/heads/")); + assertEquals("refs/heads/", + StringUtils.commonPrefix("refs/heads/", "refs/heads/main")); + } + void writePackedRef(String name, AnyObjectId id) throws IOException { writePackedRefs(id.name() + " " + name + "\n"); } diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/StringUtilsTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/StringUtilsTest.java index aa7247e105..015da164c3 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/StringUtilsTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/StringUtilsTest.java @@ -153,4 +153,23 @@ public class StringUtilsTest { () -> StringUtils.parseLongWithSuffix("8000000000000000000G", false)); } + + @Test + public void testCommonPrefix() { + assertEquals("", StringUtils.commonPrefix((String[]) null)); + assertEquals("", StringUtils.commonPrefix(new String[] {})); + assertEquals("", StringUtils.commonPrefix(new String[] { null })); + assertEquals("", StringUtils.commonPrefix(null, null)); + assertEquals("", StringUtils.commonPrefix("", "")); + assertEquals("", StringUtils.commonPrefix(null, "")); + assertEquals("", StringUtils.commonPrefix("abcd", null, null)); + assertEquals("", StringUtils.commonPrefix(null, null, "abcd")); + assertEquals("", StringUtils.commonPrefix("", "abcd")); + assertEquals("", StringUtils.commonPrefix("abcd", "efgh")); + assertEquals("abcd", StringUtils.commonPrefix("abcd")); + assertEquals("ab", StringUtils.commonPrefix("abcd", "ab")); + assertEquals("abcd", StringUtils.commonPrefix("abcd", "abcdefgh")); + assertEquals("foo bar ", + StringUtils.commonPrefix("foo bar 42", "foo bar 24")); + } } 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; + } } |