refs: speed up `refs_for_each_glob_ref_in()`

The function `refs_for_each_glob_ref_in()` can be used to iterate
through all refs in a specific prefix with globbing. The logic to handle
this is currently hosted by `refs_for_each_glob_ref_in()`, which sets up
a callback function that knows to filter out refs that _don't_ match the
given globbing pattern.

The way we do this is somewhat inefficient though: even though the
function is expected to only yield refs in the given prefix, we still
end up iterating through _all_ references, regardless of whether or not
their name matches the given prefix.

Extend `refs_for_each_ref_ext()` so that it can handle patterns and
adapt `refs_for_each_glob_ref_in()` to use it. This means we continue to
use the same callback-based infrastructure to filter individual refs via
the globbing pattern, but we can now also use the other functionality of
the `_ext()` variant.

Most importantly, this means that we now properly handle the prefix.
This results in a performance improvement when using a prefix where a
significant majority of refs exists outside of the prefix. The following
benchmark is an extreme case, with 1 million refs that exist outside the
prefix and a single ref that exists inside it:

    Benchmark 1: git rev-parse --branches=refs/heads/* (rev = HEAD~)
      Time (mean ± σ):     115.9 ms ±   0.7 ms    [User: 113.0 ms, System: 2.4 ms]
      Range (min … max):   114.9 ms … 117.8 ms    25 runs

    Benchmark 2: git rev-parse --branches=refs/heads/* (rev = HEAD)
      Time (mean ± σ):       1.1 ms ±   0.1 ms    [User: 0.3 ms, System: 0.7 ms]
      Range (min … max):     1.0 ms …   2.3 ms    2092 runs

    Summary
      git rev-parse --branches=refs/heads/* (rev = HEAD) ran
      107.01 ± 6.49 times faster than git rev-parse --branches=refs/heads/* (rev = HEAD~)

Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 10 insertions, 0 deletions

diff --git a/refs.h b/refs.h
index bb9c64a51c..a66dbf3865 100644
--- a/refs.h
+++ b/refs.h
@@ -459,6 +459,16 @@ struct refs_for_each_ref_options {
 	const char *prefix;
 
 	/*
+	 * A globbing pattern that can be used to only yield refs that match.
+	 * If given, refs will be matched against the pattern with
+	 * `wildmatch()`.
+	 *
+	 * If the pattern doesn't contain any globbing characters then it is
+	 * treated as if it was ending with "/" and "*".
+	 */
+	const char *pattern;
+
+	/*
 	 * Exclude any references that match any of these patterns on a
 	 * best-effort basis. The caller needs to be prepared for the exclude
 	 * patterns to be ignored.