patch, 2 parts[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

From: Derrick Stolee <derrickstolee@github.com>

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 <derrickstolee@github.com>
---
 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

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

For for-each-ref (which can be reused by branch and tag for no cost), I am on the fence but slightly in favor (partly because the code has already been written). But I have to wonder where changes that come from the above reasoning need to end, though.

Do we count branches and tags because "git branch --list | wc -l" is too costly? Should we teach "git remote" the same trick? How about "git stash list"? "git show-index $pack_index"? "git ls-files"?

How do we decide where to draw the line? When a command invocation in a large repository can produce records exceeding a million?

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

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:

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

Phillip Wood <phillip.wood123@gmail.com> writes:

This is interesting. The default format over just 'x' is to concatenate the refname with hexadecimal form of the object name, while (at least as the code originally was intended):

 * the cost of parsing the "--format=<format>" string into series of
   atoms is one-time O(1), and there is nothing specially tricky in
   there.

 * the cost of computing these atoms should be miniscule, as
   in the default format, the per-ref cost come from these:

   - populate_value() -> get_refname() -> show_ref() for the refname
     would merely be a xstrdup() of the refname.

   - populate_value() -> grab_oid() -> do_grab_oid() should be using
     O_FULL so there shouldn't be any find_unique_abbrev() cost.
     Just binary-to-hex.

   - populate_value() -> get_object() -> oid_object_info_extended() ->
     grab_common_values() asks for ATOM_OBJECTTYPE that should be a
     single xstrdup(), but oid_object_info_extended() needs to parse
     the object, but .info.contentp ought to be NULL and we should
     not be calling parse_object_buffer().

So it might be worth looking into where the time is going (didn't Peff or somebody do that a few years ago, though?) when using the default format and optimize or special case the codepath, but the responses I have seen from two of you makes me suspect that the new option is not the best general approach.

Thanks.

On Tue, Jun 27, 2023 at 11:22:02AM -0700, Junio C Hamano wrote:

This is the atom that I expect to give most of the cost. We should definitely be computing that just with a pack lookup (and chasing deltas through the pack, though commits usually aren't deltas). But without that atom, I think we would not even mmap the idx or pack file at all.

The ref-filter code is also pretty keen to malloc() little strings. When we're measuring 5ms total runtimes and there's just not that much actual work to do, those little things start to matter more.

Running:

 perf record -g git for-each-ref --format='%(refname) %(objecttype)' >/dev/null
 perf script report flamegraph

in linux.git shows that we spend a lot of time faulting in .idx pages.

A lot of the time is attributed to ref_array_sort(), but I think that's a red herring. It lazy-loads the atom values, so that's where most of the work is happening (though I would have thought it would just do the refname atom, not all of them; but I guess it doesn't really matter since we'll eventually need them to print anyway). Commenting out the sort call just shows the same time spent in format_ref_array_item().

The patches you're thinking of are probably:

  https://lore.kernel.org/git/YTNpQ7Od1U%2F5i0R7@coredump.intra.peff.net/

which are mostly about micro-optimizing out those mallocs. They do still help a little in the '%(refname)' case, but not nearly as much as dropping '%(objecttype)' does.

(Using --format=x in theory drops out some mallocs, but I wasn't able to measure any actual speedup).

Yeah, my feeling is that with the reduced format, eliminating the pipe/wc overhead is a pretty small improvement.

-Peff

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

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

Phillip Wood <phillip.wood123@gmail.com> writes:

If we compare what is done in packfile.c:packed_object_info() and object-file.c:loose_object_info() when we are only interested in finding out the object type, there aren't that many differences in the set of system calls each codepath needs to make.

 * The packfile codepath needs to open and mmap *.pack and *.idx,
   binary search in the .idx for the object location, then read a
   few bytes from .pack, before being able to decode the header to
   find out the type.

 * The loose object codepath needs to open and mmap the loose object
   file, read a few bytes from there, before being abole to decode
   the header to find out the type. After that, it needs to munmap.

The cost of open/mmap for packfile codepath amortises over number of objects (hence number of refs) very well. If there are many refs that point at the same object, cache object layer will kick in to avoid disk access for second and subsequent accesses to the same object, but it helps both codepaths equally, so there should not be much difference either way.

Thanks for a interesting piece of food for thought.

Am 27.06.23 um 12:05 schrieb Phillip Wood:

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é

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

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

From: Derrick Stolee <derrickstolee@github.com>

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 <derrickstolee@github.com>
---
 builtin/for-each-ref.c | 58 ++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 22 deletions(-)