[PATCH 0/2] [RFC] for-each-ref: add --count-matches mode

I'm leaving this as an RFC for now because I can't decide if this new option
in git for-each-ref is good or if this needs an entirely new builtin. I'm
open to whatever people think is best, I'd just like a way to count matches
based on refspecs.

Thanks, -Stolee

Derrick Stolee (2):
  for-each-ref: extract ref output loop
  for-each-ref: add --count-matches option

 Documentation/git-for-each-ref.txt |  5 ++
 builtin/for-each-ref.c             | 80 +++++++++++++++++++++---------
 ref-filter.c                       | 47 ++++++++++++++++++
 ref-filter.h                       |  7 +++
 t/perf/p1501-ref-iteration.sh      | 35 +++++++++++++
 t/t6300-for-each-ref.sh            | 28 +++++++++++
 6 files changed, 179 insertions(+), 23 deletions(-)
 create mode 100755 t/perf/p1501-ref-iteration.sh


base-commit: d7d8841f67f29e6ecbad85a11805c907d0f00d5d
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1548%2Fderrickstolee%2Ffor-each-ref-count-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1548/derrickstolee/for-each-ref-count-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1548
-- 
gitgitgadget

From: Derrick Stolee <redacted>

In order to count references of different types based on their initial
prefixes, there are two current approaches:

 1. Run 'git for-each-ref' on all refs and parse the output to count
    those that match each prefix.

 2. Run 'git for-each-ref "prefix/"' and pipe that output to 'wc -l' to
    count the number of output lines.

Each of these approaches is wasteful as it requires sending the list of
matching reference names across a pipe plus the cost of parsing that
output.

Instead, it would be helpful to have a Git command that counts the
number of refs matching a list of patterns.

This change adds a new mode, '--count-matches' to 'git for-each-ref' so
we can make use of the existing infrastructure around parsing refspecs
in the correct places. '--count' is already taken as a "maximum number"
of refs to output.

An alternative approach could be to make a brand-new builtin that is
focused on counting ref matches. This would involve duplicating a bit of
code around parsing refpecs, but would not be terribly difficult. The
actual overlap of implementation here with 'git for-each-ref' is small
enough that we could instead extract this elsewhere. My gut feeling is
that this behavior doesn't merit a new builtin.

The implementation is extremely simple: iterate through all references
and compare each ref to each refspec. On a match, increment a counter
value for that refspec.

In the end, output each refspec followed by the count.

If all given refspecs were prefixes, then it is tempting to instead use
a counting behavior that we can use in things like "how many OIDs start
with this short hex string?" Navigating to the start and end of the
range of refs starting with that prefix is possible in the packed-refs
file. However, the records do not have a constant size so we cannot
infer the number of references in that range using the current format.
(Perhaps, in the future we will have a ref storage system that allows
this kind of counting to be easy to do in O(log N) time.)

A new performance test is included to check the performance of iterating
through these references and counting them appropriately. This presents
a 3x improvement over the trivial piping through to 'wc -l', and that
assumes there is a single pattern to match instead of multiple. We can
see that testing three patterns sequentially adds to the total time, but
doing a single process with --count-match continues to be as fast. (It's
difficult to tell since it _also_ matches the sum of the three for this
example repo.)

Test                                                         this tree
----------------------------------------------------------------------------
1501.2: count refs/heads/: git for-each-ref | wc -l          0.01(0.00+0.01)
1501.3: count refs/heads/: git for-each-ref --count-match    0.00(0.00+0.00)
1501.4: count refs/tags/: git for-each-ref | wc -l           0.02(0.00+0.02)
1501.5: count refs/tags/: git for-each-ref --count-match     0.00(0.00+0.00)
1501.6: count refs/remotes: git for-each-ref | wc -l         0.15(0.08+0.07)
1501.7: count refs/remotes: git for-each-ref --count-match   0.04(0.01+0.02)
1501.8: count all patterns: git for-each-ref | wc -l         0.18(0.08+0.10)
1501.9: count all patterns: git for-each-ref --count-match   0.04(0.02+0.02)

Signed-off-by: Derrick Stolee <redacted>
---
 Documentation/git-for-each-ref.txt |  5 ++++
 builtin/for-each-ref.c             | 26 +++++++++++++++--
 ref-filter.c                       | 47 ++++++++++++++++++++++++++++++
 ref-filter.h                       |  7 +++++
 t/perf/p1501-ref-iteration.sh      | 35 ++++++++++++++++++++++
 t/t6300-for-each-ref.sh            | 28 ++++++++++++++++++
 6 files changed, 145 insertions(+), 3 deletions(-)
 create mode 100755 t/perf/p1501-ref-iteration.sh

diff --git a/Documentation/git-for-each-ref.txt b/Documentation/git-for-each-ref.txt
index 1e215d4e734..74018755ed5 100644
--- a/Documentation/git-for-each-ref.txt
+++ b/Documentation/git-for-each-ref.txt

@@ -42,6 +42,11 @@ OPTIONS
 	`<pattern>`.  This option makes it stop after showing
 	that many refs.
 
+--count-matches::
+	Instead of listing references according to the given format, output
+	the number of references that match each pattern. Incompatible with
+	`--format`, `--sort`, and `--count`.
+
 --sort=<key>::
 	A field name to sort on.  Prefix `-` to sort in
 	descending order of the value.  When unspecified,

diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
index ce34940e3e6..e3db719bb87 100644
--- a/builtin/for-each-ref.c
+++ b/builtin/for-each-ref.c

@@ -50,6 +50,17 @@ static void filter_and_output_refs(struct repository *r,
 	strbuf_release(&output);
 }
 
+static void count_and_output_patterns(struct ref_filter *filter)
+{
+	uint32_t *counts = count_ref_patterns(filter);
+
+	for (int i = 0; filter->name_patterns && filter->name_patterns[i]; i++)
+		fprintf(stdout, "%s %"PRIu32"\n",
+			filter->name_patterns[i], counts[i]);
+
+	free(counts);
+}
+
 int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 {
 	struct ref_sorting *sorting;

@@ -60,6 +71,7 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 	struct ref_format format = REF_FORMAT_INIT;
 	int from_stdin = 0;
 	struct strvec vec = STRVEC_INIT;
+	const char *initial_format = "%(objectname) %(objecttype)\t%(refname)";
 
 	struct option opts[] = {
 		OPT_BIT('s', "shell", &format.quote_style,

@@ -72,6 +84,8 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 			N_("quote placeholders suitably for Tcl"), QUOTE_TCL),
 		OPT_BOOL(0, "omit-empty",  &omit_empty,
 			N_("do not output a newline after empty formatted refs")),
+		OPT_BOOL(0, "count-matches", &count_matches,
+			N_("output number of references matching each pattern instead of any other output")),
 
 		OPT_GROUP(""),
 		OPT_INTEGER( 0 , "count", &maxcount, N_("show only <n> matched refs")),

@@ -93,7 +107,7 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 	memset(&array, 0, sizeof(array));
 	memset(&filter, 0, sizeof(filter));
 
-	format.format = "%(objectname) %(objecttype)\t%(refname)";
+	format.format = initial_format;
 
 	git_config(git_default_config, NULL);
 

@@ -102,6 +116,9 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 		error("invalid --count argument: `%d'", maxcount);
 		usage_with_options(for_each_ref_usage, opts);
 	}
+	if (count_matches &&
+	    (maxcount || format.format != initial_format || sorting_options.nr))
+		die("--count-matches incompatible with --count, --format, or --sort");
 	if (HAS_MULTI_BITS(format.quote_style)) {
 		error("more than one quoting style?");
 		usage_with_options(for_each_ref_usage, opts);

@@ -131,8 +148,11 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 	}
 
 	filter.match_as_path = 1;
-	filter_and_output_refs(the_repository, &array, &filter, &format,
-			       sorting, maxcount, omit_empty);
+	if (count_matches)
+		count_and_output_patterns(&filter);
+	else
+		filter_and_output_refs(the_repository, &array, &filter, &format,
+				       sorting, maxcount, omit_empty);
 
 	ref_array_clear(&array);
 	free_commit_list(filter.with_commit);

diff --git a/ref-filter.c b/ref-filter.c
index 4991cd4f7a8..4e02a4ae98d 100644
--- a/ref-filter.c
+++ b/ref-filter.c

@@ -2560,6 +2560,53 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int
 	return ret;
 }
 
+struct filter_and_counts {
+	struct ref_filter *filter;
+	uint32_t *counts;
+};
+
+static int ref_filter_counter(const char *refname,
+			      const struct object_id *oid,
+			      int flag, void *cb_data)
+{
+	struct filter_and_counts *fc = cb_data;
+	const char **pattern = fc->filter->name_patterns;
+	size_t namelen = strlen(refname);
+	unsigned flags = fc->filter->ignore_case ? WM_CASEFOLD : 0;
+
+	for (int i = 0; *pattern; i++, pattern++) {
+		const char *p = *pattern;
+		int plen = strlen(p);
+
+		if ((plen <= namelen) &&
+		    !strncmp(refname, p, plen) &&
+		    (refname[plen] == '\0' ||
+		     refname[plen] == '/' ||
+		     p[plen-1] == '/'))
+			fc->counts[i]++;
+		else if (!wildmatch(p, refname, flags))
+			fc->counts[i]++;
+	}
+	return 0;
+}
+
+uint32_t *count_ref_patterns(struct ref_filter *filter)
+{
+	int size = 0;
+	struct filter_and_counts fc = {
+		.filter = filter,
+	};
+
+	while (filter->name_patterns[size])
+		size++;
+
+	CALLOC_ARRAY(fc.counts, size);
+
+	for_each_fullref_in_pattern(filter, ref_filter_counter, &fc);
+
+	return fc.counts;
+}
+
 static int compare_detached_head(struct ref_array_item *a, struct ref_array_item *b)
 {
 	if (!(a->kind ^ b->kind))

diff --git a/ref-filter.h b/ref-filter.h
index 430701cfb76..b7e5a4f6a80 100644
--- a/ref-filter.h
+++ b/ref-filter.h

@@ -141,6 +141,13 @@ char *get_head_description(void);
 /*  Set up translated strings in the output. */
 void setup_ref_filter_porcelain_msg(void);
 
+/*
+ * Iterate over all references, counting how many match each filter
+ * pattern. Returns an array of the counts with the ith count matching the
+ * ith filter->name_pattern entry.
+ */
+uint32_t *count_ref_patterns(struct ref_filter *filter);
+
 /*
  * Print a single ref, outside of any ref-filter. Note that the
  * name must be a fully qualified refname.

diff --git a/t/perf/p1501-ref-iteration.sh b/t/perf/p1501-ref-iteration.sh
new file mode 100755
index 00000000000..609487d20b0
--- /dev/null
+++ b/t/perf/p1501-ref-iteration.sh

@@ -0,0 +1,35 @@
+#!/bin/sh
+
+test_description='Ref iteration performance tests'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+# Optimize ref backend store
+test_expect_success 'setup' '
+	git pack-refs
+'
+
+for pattern in "refs/heads/" "refs/tags/" "refs/remotes"
+do
+	test_perf "count $pattern: git for-each-ref | wc -l" "
+		git for-each-ref $pattern | wc -l
+	"
+
+	test_perf "count $pattern: git for-each-ref --count-match" "
+		git for-each-ref --count-matches $pattern
+	"
+done
+
+test_perf "count all patterns: git for-each-ref | wc -l" "
+	git for-each-ref refs/heads/ | wc -l &&
+	git for-each-ref refs/tags/ | wc -l &&
+	git for-each-ref refs/remotes/ | wc -l
+"
+
+test_perf "count all patterns: git for-each-ref --count-match" "
+	git for-each-ref --count-matches \
+		refs/heads/ refs/tags/ refs/remotes/
+"
+
+test_done

diff --git a/t/t6300-for-each-ref.sh b/t/t6300-for-each-ref.sh
index 5c00607608a..001382956e4 100755
--- a/t/t6300-for-each-ref.sh
+++ b/t/t6300-for-each-ref.sh

@@ -486,6 +486,34 @@ for i in "--perl --shell" "-s --python" "--python --tcl" "--tcl --perl"; do
 	"
 done
 
+test_expect_success '--count-matches incompatible with some options' '
+	for opt in "--format=x" "--sort=refname" "--count=10"
+	do
+		test_must_fail git for-each-ref --count-matches $opt refs/heads/ 2>err &&
+		grep "count-matches incompatible" err || return 1
+	done
+'
+
+test_expect_success '--count-matches tallies the number matching each refspec' '
+	git init multi-refs &&
+	test_commit -C multi-refs A &&
+	git -C multi-refs branch A &&
+	git -C multi-refs branch pre/A &&
+	test_commit -C multi-refs --no-tag B &&
+	git -C multi-refs branch B &&
+	git -C multi-refs for-each-ref --count-matches \
+		refs/heads/ refs/heads/pre/ refs/tags/ "*A*" >actual &&
+
+	cat >expect <<-EOF &&
+	refs/heads/ 4
+	refs/heads/pre/ 1
+	refs/tags/ 1
+	*A* 3
+	EOF
+
+	test_cmp expect actual
+'
+
 test_expect_success 'setup for upstream:track[short]' '
 	test_commit two
 '

-- 
gitgitgadget

From: Derrick Stolee <redacted>

In preparation for a new output mode of 'git for-each-ref', extract the
loop that outputs references into a static method. No functional change
here.

Signed-off-by: Derrick Stolee <redacted>
---
 builtin/for-each-ref.c | 58 ++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 22 deletions(-)

diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
index 695fc8f4a5e..ce34940e3e6 100644
--- a/builtin/for-each-ref.c
+++ b/builtin/for-each-ref.c

@@ -17,17 +17,47 @@ static char const * const for_each_ref_usage[] = {
 	NULL
 };
 
-int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
+static void filter_and_output_refs(struct repository *r,
+				   struct ref_array *array,
+				   struct ref_filter *filter,
+				   struct ref_format *format,
+				   struct ref_sorting *sorting,
+				   int maxcount,
+				   int omit_empty)
 {
 	int i;
+	struct strbuf err = STRBUF_INIT;
+	struct strbuf output = STRBUF_INIT;
+
+	filter_refs(array, filter, FILTER_REFS_ALL);
+	filter_ahead_behind(r, format, array);
+
+	ref_array_sort(sorting, array);
+
+	if (!maxcount || array->nr < maxcount)
+		maxcount = array->nr;
+	for (i = 0; i < maxcount; i++) {
+		strbuf_reset(&err);
+		strbuf_reset(&output);
+		if (format_ref_array_item(array->items[i], format, &output, &err))
+			die("%s", err.buf);
+		fwrite(output.buf, 1, output.len, stdout);
+		if (output.len || !omit_empty)
+			putchar('\n');
+	}
+
+	strbuf_release(&err);
+	strbuf_release(&output);
+}
+
+int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
+{
 	struct ref_sorting *sorting;
 	struct string_list sorting_options = STRING_LIST_INIT_DUP;
-	int maxcount = 0, icase = 0, omit_empty = 0;
+	int maxcount = 0, icase = 0, omit_empty = 0, count_matches = 0;
 	struct ref_array array;
 	struct ref_filter filter;
 	struct ref_format format = REF_FORMAT_INIT;
-	struct strbuf output = STRBUF_INIT;
-	struct strbuf err = STRBUF_INIT;
 	int from_stdin = 0;
 	struct strvec vec = STRVEC_INIT;
 

@@ -101,25 +131,9 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 	}
 
 	filter.match_as_path = 1;
-	filter_refs(&array, &filter, FILTER_REFS_ALL);
-	filter_ahead_behind(the_repository, &format, &array);
+	filter_and_output_refs(the_repository, &array, &filter, &format,
+			       sorting, maxcount, omit_empty);
 
-	ref_array_sort(sorting, &array);
-
-	if (!maxcount || array.nr < maxcount)
-		maxcount = array.nr;
-	for (i = 0; i < maxcount; i++) {
-		strbuf_reset(&err);
-		strbuf_reset(&output);
-		if (format_ref_array_item(array.items[i], &format, &output, &err))
-			die("%s", err.buf);
-		fwrite(output.buf, 1, output.len, stdout);
-		if (output.len || !omit_empty)
-			putchar('\n');
-	}
-
-	strbuf_release(&err);
-	strbuf_release(&output);
 	ref_array_clear(&array);
 	free_commit_list(filter.with_commit);
 	free_commit_list(filter.no_commit);

-- 
gitgitgadget

On Mon, Jun 26, 2023 at 03:09:57PM +0000, Derrick Stolee via GitGitGadget wrote:

+for pattern in "refs/heads/" "refs/tags/" "refs/remotes"
+do
+	test_perf "count $pattern: git for-each-ref | wc -l" "
+		git for-each-ref $pattern | wc -l
+	"
+
+	test_perf "count $pattern: git for-each-ref --count-match" "
+		git for-each-ref --count-matches $pattern
+	"
+done

I don't think this is a very realistic perf test, because for-each-ref
is doing a bunch of work to generate its default format, only to have
"wc" throw most of it away. Doing:

  git for-each-ref --format='%(refname)' | wc -l

is much better (obviously you have to remember to do that if you care
about optimizing your command, but that's true of --count-matches, too).

Running hyperfine with three variants shows that the command above is
competitive with --count-matches, though slightly slower (hyperfine
complains about short commands and outliers because these runtimes are
so tiny in the first place; I omitted those warnings from the output
below for readability):

  Benchmark 1: ./git-for-each-ref refs/remotes/ | wc -l
    Time (mean ± σ):       6.1 ms ±   0.2 ms    [User: 3.0 ms, System: 3.6 ms]
    Range (min … max):     5.6 ms …   7.1 ms    397 runs
  
  Benchmark 2: ./git-for-each-ref --format="%(refname)" refs/remotes/ | wc -l
    Time (mean ± σ):       3.3 ms ±   0.2 ms    [User: 2.2 ms, System: 1.5 ms]
    Range (min … max):     3.0 ms …   4.0 ms    774 runs
  
  Benchmark 3: ./git-for-each-ref --count-matches refs/remotes/
    Time (mean ± σ):       2.4 ms ±   0.1 ms    [User: 1.5 ms, System: 0.9 ms]
    Range (min … max):     2.2 ms …   3.4 ms    1018 runs
  
  Summary
    './git-for-each-ref --count-matches refs/remotes/' ran
      1.33 ± 0.10 times faster than './git-for-each-ref --format="%(refname)" refs/remotes/ | wc -l'
      2.48 ± 0.17 times faster than './git-for-each-ref refs/remotes/ | wc -l'

I will note this is an unloaded multi-core system, which gives the piped
version a slight edge. Total CPU is probably more interesting than
wall-clock time, but all of these are so short that I think the results
should be taken with a pretty big grain of salt (I had to switch from
the "powersave" to "performance" CPU governor just to get more
consistent results).

-Peff

On 27/06/2023 08:30, Jeff King wrote:

On Mon, Jun 26, 2023 at 03:09:57PM +0000, Derrick Stolee via GitGitGadget wrote:

quoted

+for pattern in "refs/heads/" "refs/tags/" "refs/remotes"
+do
+	test_perf "count $pattern: git for-each-ref | wc -l" "
+		git for-each-ref $pattern | wc -l
+	"
+
+	test_perf "count $pattern: git for-each-ref --count-match" "
+		git for-each-ref --count-matches $pattern
+	"
+done

I don't think this is a very realistic perf test, because for-each-ref
is doing a bunch of work to generate its default format, only to have
"wc" throw most of it away. Doing:

   git for-each-ref --format='%(refname)' | wc -l

That's a good point. I wondered if using a short fixed format string was 
even better so I tried

git init test
cd test
git commit --allow-empty -m initial
seq 0 100000 | sed "s:\(.*\):create refs/heads/some-prefix/\1 $(git 
rev-parse HEAD):" | git update-ref --stdin
git pack-refs --all
hyperfine -L fmt "","--format=%\(refname\)","--format=x" 'git 
for-each-ref {fmt} refs/heads/ | wc -l'

Which gives

Benchmark 1: git for-each-ref  refs/heads/ | wc -l
   Time (mean ± σ):      1.150 s ±  0.010 s    [User: 0.494 s, System: 
0.637 s]
   Range (min … max):    1.140 s …  1.170 s    10 runs

Benchmark 2: git for-each-ref --format=%\(refname\) refs/heads/ | wc -l
   Time (mean ± σ):      66.0 ms ±   0.3 ms    [User: 58.9 ms, System: 
9.5 ms]
   Range (min … max):    65.2 ms …  67.1 ms    43 runs

Benchmark 3: git for-each-ref --format=x refs/heads/ | wc -l
   Time (mean ± σ):      63.0 ms ±   0.5 ms    [User: 54.3 ms, System: 
9.6 ms]
   Range (min … max):    62.3 ms …  65.4 ms    44 runs

Summary
   git for-each-ref --format=x refs/heads/ | wc -l ran
     1.05 ± 0.01 times faster than git for-each-ref 
--format=%\(refname\) refs/heads/ | wc -l
    18.25 ± 0.20 times faster than git for-each-ref  refs/heads/ | wc -l

So on my somewhat slower machine the default format is over an order of 
magnitude slower than using either --format=%(refname) or --format=x and 
the short fixed format is marginally faster. I haven't applied stolee's 
patch but the 3 or 4 times improvement mentioned in the commit message 
seems likely to be from not processing the default format. One thing to 
note is that we're not comparing like-with-like when more than one 
pattern is given as --count-matches gives a separate count for each pattern.

I'm a bit suspicious of the massive speed up I'm seeing by avoiding the 
default format but it appears to be repeatable.

Best Wishes

Phillip

is much better (obviously you have to remember to do that if you care
about optimizing your command, but that's true of --count-matches, too).

Running hyperfine with three variants shows that the command above is
competitive with --count-matches, though slightly slower (hyperfine
complains about short commands and outliers because these runtimes are
so tiny in the first place; I omitted those warnings from the output
below for readability):

   Benchmark 1: ./git-for-each-ref refs/remotes/ | wc -l
     Time (mean ± σ):       6.1 ms ±   0.2 ms    [User: 3.0 ms, System: 3.6 ms]
     Range (min … max):     5.6 ms …   7.1 ms    397 runs
   
   Benchmark 2: ./git-for-each-ref --format="%(refname)" refs/remotes/ | wc -l
     Time (mean ± σ):       3.3 ms ±   0.2 ms    [User: 2.2 ms, System: 1.5 ms]
     Range (min … max):     3.0 ms …   4.0 ms    774 runs
   
   Benchmark 3: ./git-for-each-ref --count-matches refs/remotes/
     Time (mean ± σ):       2.4 ms ±   0.1 ms    [User: 1.5 ms, System: 0.9 ms]
     Range (min … max):     2.2 ms …   3.4 ms    1018 runs
   
   Summary
     './git-for-each-ref --count-matches refs/remotes/' ran
       1.33 ± 0.10 times faster than './git-for-each-ref --format="%(refname)" refs/remotes/ | wc -l'
       2.48 ± 0.17 times faster than './git-for-each-ref refs/remotes/ | wc -l'

I will note this is an unloaded multi-core system, which gives the piped
version a slight edge. Total CPU is probably more interesting than
wall-clock time, but all of these are so short that I think the results
should be taken with a pretty big grain of salt (I had to switch from
the "powersave" to "performance" CPU governor just to get more
consistent results).

-Peff

On 27/06/2023 11:05, Phillip Wood wrote:

On 27/06/2023 08:30, Jeff King wrote:

quoted

I don't think this is a very realistic perf test, because for-each-ref
is doing a bunch of work to generate its default format, only to have
"wc" throw most of it away. Doing:

   git for-each-ref --format='%(refname)' | wc -l

That's a good point. I wondered if using a short fixed format string was 
even better so I tried

git init test
cd test
git commit --allow-empty -m initial
seq 0 100000 | sed "s:\(.*\):create refs/heads/some-prefix/\1 $(git 
rev-parse HEAD):" | git update-ref --stdin
git pack-refs --all
hyperfine -L fmt "","--format=%\(refname\)","--format=x" 'git 
for-each-ref {fmt} refs/heads/ | wc -l'

Which gives
[...] 
Summary
   git for-each-ref --format=x refs/heads/ | wc -l ran
     1.05 ± 0.01 times faster than git for-each-ref 
--format=%\(refname\) refs/heads/ | wc -l
    18.25 ± 0.20 times faster than git for-each-ref  refs/heads/ | wc -l
[...] 
I'm a bit suspicious of the massive speed up I'm seeing by avoiding the 
default format but it appears to be repeatable.

Having seen Peff's mail [1] I realized that my test repo above is 
looking up the commit from a loose object. If I repack the repository 
then the default format is still slower than using "--format=%(refname)" 
but is much more competitive.

$ git repack -a
Enumerating objects: 2, done.
Counting objects: 100% (2/2), done.
Writing objects: 100% (2/2), done.
Total 2 (delta 0), reused 0 (delta 0), pack-reused 0

$ hyperfine -L fmt "","--format=%\(refname\)","--format=x" 'git 
for-each-ref {fmt} refs/heads/ | wc'
Benchmark 1: git for-each-ref  refs/heads/ | wc -l
   Time (mean ± σ):     111.4 ms ±   1.4 ms    [User: 96.9 ms, System: 
19.6 ms]
   Range (min … max):   109.6 ms … 115.1 ms    25 runs

Benchmark 2: git for-each-ref --format=%\(refname\) refs/heads/ | wc -l
   Time (mean ± σ):      66.7 ms ±   0.7 ms    [User: 59.5 ms, System: 
9.5 ms]
   Range (min … max):    65.6 ms …  68.2 ms    42 runs

Benchmark 3: git for-each-ref --format=x refs/heads/ | wc -l
   Time (mean ± σ):      63.4 ms ±   0.7 ms    [User: 56.3 ms, System: 
8.0 ms]
   Range (min … max):    61.9 ms …  65.1 ms    44 runs

Summary
   git for-each-ref --format=x refs/heads/ | wc -l ran
     1.05 ± 0.02 times faster than git for-each-ref 
--format=%\(refname\) refs/heads/ | wc -l
     1.76 ± 0.03 times faster than git for-each-ref  refs/heads/ | wc -l

So it seems most of the slowdown I was seeing yesterday was due it 
looking up a loose object. I'm surprised repacking makes such a 
difference in a repository that only contains two objects.

Best Wishes

Phillip

[1] 
https://lore.kernel.org/git/20230627195900.GC1280909@coredump.intra.peff.net

On 6/27/2023 1:30 AM, Jeff King wrote:

On Mon, Jun 26, 2023 at 03:09:57PM +0000, Derrick Stolee via GitGitGadget wrote:

quoted

+for pattern in "refs/heads/" "refs/tags/" "refs/remotes"
+do
+   test_perf "count $pattern: git for-each-ref | wc -l" "
+       git for-each-ref $pattern | wc -l
+   "
+
+   test_perf "count $pattern: git for-each-ref --count-match" "
+       git for-each-ref --count-matches $pattern
+   "
+done

I don't think this is a very realistic perf test, because for-each-ref
is doing a bunch of work to generate its default format, only to have
"wc" throw most of it away. Doing:

 git for-each-ref --format='%(refname)' | wc -l

is much better (obviously you have to remember to do that if you care
about optimizing your command, but that's true of --count-matches, too).

Thank you for pointing this out! I'll be sure to modify the test and the
analysis about it.
The other check I need to compare is when multiple refspecs are provided
at the same time, which I do believe still is a valuable thing to combine
into a single process instead of multiple pipes to 'wc'.
Did you have any thoughts on whether or not this works as an option in
'git for-each-ref' or would be better broken into a new builtin?
Thanks,
-Stolee

Am 27.06.23 um 12:05 schrieb Phillip Wood:

On 27/06/2023 08:30, Jeff King wrote:

quoted

On Mon, Jun 26, 2023 at 03:09:57PM +0000, Derrick Stolee via GitGitGadget wrote:

quoted

+for pattern in "refs/heads/" "refs/tags/" "refs/remotes"
+do
+    test_perf "count $pattern: git for-each-ref | wc -l" "
+        git for-each-ref $pattern | wc -l
+    "
+
+    test_perf "count $pattern: git for-each-ref --count-match" "
+        git for-each-ref --count-matches $pattern
+    "
+done

I don't think this is a very realistic perf test, because for-each-ref
is doing a bunch of work to generate its default format, only to have
"wc" throw most of it away. Doing:

   git for-each-ref --format='%(refname)' | wc -l

That's a good point. I wondered if using a short fixed format string was even better so I tried

git init test
cd test
git commit --allow-empty -m initial
seq 0 100000 | sed "s:\(.*\):create refs/heads/some-prefix/\1 $(git rev-parse HEAD):" | git update-ref --stdin
git pack-refs --all
hyperfine -L fmt "","--format=%\(refname\)","--format=x" 'git for-each-ref {fmt} refs/heads/ | wc -l'

Which gives

Benchmark 1: git for-each-ref  refs/heads/ | wc -l
  Time (mean ± σ):      1.150 s ±  0.010 s    [User: 0.494 s, System: 0.637 s]
  Range (min … max):    1.140 s …  1.170 s    10 runs

Benchmark 2: git for-each-ref --format=%\(refname\) refs/heads/ | wc -l
  Time (mean ± σ):      66.0 ms ±   0.3 ms    [User: 58.9 ms, System: 9.5 ms]
  Range (min … max):    65.2 ms …  67.1 ms    43 runs

Benchmark 3: git for-each-ref --format=x refs/heads/ | wc -l
  Time (mean ± σ):      63.0 ms ±   0.5 ms    [User: 54.3 ms, System: 9.6 ms]
  Range (min … max):    62.3 ms …  65.4 ms    44 runs

Summary
  git for-each-ref --format=x refs/heads/ | wc -l ran
    1.05 ± 0.01 times faster than git for-each-ref --format=%\(refname\) refs/heads/ | wc -l
   18.25 ± 0.20 times faster than git for-each-ref  refs/heads/ | wc -l

You don't need no "x", by the way; using the empty string saves some
cycles for me.  In my Git clone, no special setup, 9931 refs:

Benchmark 1: git for-each-ref --format=x | wc -l
  Time (mean ± σ):      25.1 ms ±   0.1 ms    [User: 8.7 ms, System: 16.8 ms]
  Range (min … max):    24.9 ms …  25.6 ms    109 runs

Benchmark 2: git for-each-ref --format= | wc -l
  Time (mean ± σ):      24.6 ms ±   0.1 ms    [User: 8.3 ms, System: 16.8 ms]
  Range (min … max):    24.4 ms …  25.3 ms    110 runs

Summary
  git for-each-ref --format= | wc -l ran
    1.02 ± 0.01 times faster than git for-each-ref --format=x | wc -l

René