On Sat, Sep 04, 2021 at 08:40:35AM -0400, Jeff King wrote:
> Somebody complained to me off-list recently that for-each-ref was slow
> when doing a trivial listing (like refname + objectname) of a large
> number of refs, even though you could get mostly the same output by
> just dumping the packed-refs file.
> 
> So I was nerd-sniped into making this horrible series, which does speed
> up some cases. It was a combination of "how fast can we easily get it",
> plus I was curious _which_ parts of for-each-ref were actually slow.
> 
> In this version there are 2 patches, tested against 'git for-each-ref
> --format="%(objectname) %(refname)"' on a fully packed repo with 500k
> refs:
> 
>   - directly outputting items rather than building up a ref_array yields
>     about a 1.5x speedup
> 
>   - avoiding the whole atom-formatting system yields a 2.5x speedup on
>     top of that

Interesting, thanks for the PoC. Your 500k refs naturally triggered me
given that I have recently been trying to optimize such repos with lots
of refs, too. So I ran your series on my gitlab-org/gitlab repository
with 2.3M ref and saw similar speedups:

    Benchmark #1: jk-for-each-ref-speedup~2: git-for-each-ref --format='%(objectname) %(refname)'
      Time (mean ± σ):      2.756 s ±  0.013 s    [User: 2.416 s, System: 0.339 s]
      Range (min … max):    2.740 s …  2.774 s    5 runs

    Benchmark #2: jk-for-each-ref-speedup~: git-for-each-ref --format='%(objectname) %(refname)'
      Time (mean ± σ):      2.009 s ±  0.015 s    [User: 1.974 s, System: 0.035 s]
      Range (min … max):    1.984 s …  2.020 s    5 runs

    Benchmark #3: jk-for-each-ref-speedup: git-for-each-ref --format='%(objectname) %(refname)'
      Time (mean ± σ):     701.8 ms ±   4.2 ms    [User: 661.3 ms, System: 40.4 ms]
      Range (min … max):   696.1 ms … 706.9 ms    5 runs

    Summary
      'jk-for-each-ref-speedup: git-for-each-ref --format='%(objectname) %(refname)'' ran
        2.86 ± 0.03 times faster than 'jk-for-each-ref-speedup~: git-for-each-ref --format='%(objectname) %(refname)''
        3.93 ± 0.03 times faster than 'jk-for-each-ref-speedup~2: git-for-each-ref --format='%(objectname) %(refname)''

[snip]
> I'm not sure I'm really advocating that we should do something like
> this, though it is tempting because it does make some common queries
> much faster. But I wanted to share it here to give some insight on where
> the time may be going in ref-filter / for-each-ref.

Well, avoiding the sort like you do in #1 feels like the right thing to
do to me. I saw similar wins when optimizing the connectivity checks,
and it only makes sense that sorting becomes increasingly expensive as
your number of refs grows. And if we do skip the sort, then decreasing
the initial latency feels like the logical next step because we know we
can stream out things directly.

The quick-formatting is a different story altogether, as you rightly
point out. Having to explain why '%(objectname) %(refname)' is 2.5x
faster than '%(refname) %(objectname)' is probably nothing we'd want to
do. But in any case, your patch does point out that the current
formatting code could use some tweaking.

In any case, this is only my 2c. Thanks for this series!

Patrick