tree 81ed497ee77f7862e067d28590e33b34be71459b
parent a6b90b7ec5c238692dc323e25ef927e4433edb1d
author Gal Paikin <paiking@google.com> 1607350714 +0100
committer Gal Paikin <paiking@google.com> 1611732171 -0500

Compare getting all refs except specific refs with seek and with filter

There are currently two ways to get all refs except a specific ref, we
add two methods that perform both and compare the two different approaches.

This change adds two methods that compares the two different approaches
of such query:
1. Get all the refs, and then filter by refs that don't start with the
prefix (current approach).
2. Get all refs until encountering a ref that is part of the prefix we
should exclude, skip using seekPastPrefix, and continue (new approach).
This works since the refs are sorted.

Specifically in Gerrit, we often have thousands of refs that are not
refs/changes, and millions of refs/changes, hence the second approach
should be much faster. In Jgit in general it's still expected to provide
a better result even if we're skipping a smaller chunk of the refs
since the complexity here is O(logn) with a binary search, rather than
O(number of skipped refs).

We ran this benchmark on a big chunk of chromium/src's reftable. To run
it, we first create the reftable:

  git ls-remote https://chromium.googlesource.com/chromium/src > lsr

  bazel build org.eclipse.jgit.pgm:jgit && rm -rf /tmp/reftable* && \
    ./bazel-bin/org.eclipse.jgit.pgm/jgit debug-benchmark-reftable \
    --test write_stack lsr /tmp/reftable

Then, we actually test the created reftable. Note that we can't test all
of them at once since there are multiple ones, but below is a good
example.

bazel build org.eclipse.jgit.pgm:jgit  && \
./bazel-bin/org.eclipse.jgit.pgm/jgit debug-benchmark-reftable \
--test get_refs_excluding_ref --ref refs/changes \
lsr /tmp/reftable/000000000001-0000001e0371.ref

Result:
total time the action took using seek:      36925 usec
total time the action took using filter:     874382 usec
number of refs that start with prefix: 4266.
number of refs that don't start with prefix: 1962695.

Similarly for Android's biggest repository, platform/frameworks/base
(still only partial result):
total time the action took using seek:       9020 usec
total time the action took using filter:     143166 usec
number of refs that start with prefix: 296.
number of refs that don't start with prefix: 60400.

In conclusion, it's easy to see an improvement of a factor of 15-20x for
large Gerrit repositories!

Signed-off-by: Gal Paikin <paiking@google.com>
Change-Id: I36d9b63eb259804c774864429cf2c761cd099cc3