Subject: Re: [PATCH 0/4] Performance improvement & cleanup in loose ref iteration

From: Patrick Steinhardt <[email-masked]>
Date: Tue, 10 Oct 2023 09:21:24 +0200

On Mon, Oct 09, 2023 at 02:49:14PM -0700, Victoria Dye wrote:
> Patrick Steinhardt wrote:
> > On Fri, Oct 06, 2023 at 06:09:25PM +0000, Victoria Dye via GitGitGadget wrote:
> >> While investigating ref iteration performance in builtins like
> >> 'for-each-ref' and 'show-ref', I found two small improvement opportunities.
> >>
> >> The first patch tweaks the logic around prefix matching in
> >> 'cache_ref_iterator_advance' so that we correctly skip refs that do not
> >> actually match a given prefix. The unnecessary iteration doesn't seem to be
> >> causing any bugs in the ref iteration commands that I've tested, but it
> >> doesn't hurt to be more precise (and it helps with some other patches I'm
> >> working on ;) ).
> >>
> >> The next three patches update how 'loose_fill_ref_dir' determines the type
> >> of ref cache entry to create (directory or regular). On platforms that
> >> include d_type information in 'struct dirent' (as far as I can tell, all
> >> except NonStop & certain versions of Cygwin), this allows us to skip calling
> >> 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref'
> >> by about 20%.
> > 
> > I've done a small set of benchmarks with my usual test repositories,
> > which is linux.git with a bunch of references added. The repository
> > comes in four sizes:
> > 
> > - small: 50k references
> > - medium: 500k references
> > - high:  1.1m references
> > - huge: 12m references
> > 
> > Unfortunately, I couldn't really reproduce the performance improvements.
> > In fact, the new version runs consistently a tiny bit slower than the
> > old version:
> > 
> >     # Old version, which is 3a06386e31 (The fifteenth batch, 2023-10-04).
> > 
> >     Benchmark 1: git for-each-ref (revision=old,refcount=small)
> >       Time (mean ± σ):     135.5 ms ±   1.2 ms    [User: 76.4 ms, System: 59.0 ms]
> >       Range (min … max):   134.8 ms … 136.9 ms    3 runs
> > 
> >     Benchmark 2: git for-each-ref (revision=old,refcount=medium)
> >       Time (mean ± σ):     822.7 ms ±   2.2 ms    [User: 697.4 ms, System: 125.1 ms]
> >       Range (min … max):   821.1 ms … 825.2 ms    3 runs
> > 
> >     Benchmark 3: git for-each-ref (revision=old,refcount=high)
> >       Time (mean ± σ):      1.960 s ±  0.015 s    [User: 1.702 s, System: 0.257 s]
> >       Range (min … max):    1.944 s …  1.973 s    3 runs
> > 
> >     # New version, which is your tip.
> > 
> >     Benchmark 4: git for-each-ref (revision=old,refcount=huge)
> >       Time (mean ± σ):     16.815 s ±  0.054 s    [User: 15.091 s, System: 1.722 s]
> >       Range (min … max):   16.760 s … 16.869 s    3 runs
> > 
> >     Benchmark 5: git for-each-ref (revision=new,refcount=small)
> >       Time (mean ± σ):     136.0 ms ±   0.2 ms    [User: 78.8 ms, System: 57.1 ms]
> >       Range (min … max):   135.8 ms … 136.2 ms    3 runs
> > 
> >     Benchmark 6: git for-each-ref (revision=new,refcount=medium)
> >       Time (mean ± σ):     830.4 ms ±  21.2 ms    [User: 691.3 ms, System: 138.7 ms]
> >       Range (min … max):   814.2 ms … 854.5 ms    3 runs
> > 
> >     Benchmark 7: git for-each-ref (revision=new,refcount=high)
> >       Time (mean ± σ):      1.966 s ±  0.013 s    [User: 1.717 s, System: 0.249 s]
> >       Range (min … max):    1.952 s …  1.978 s    3 runs
> > 
> >     Benchmark 8: git for-each-ref (revision=new,refcount=huge)
> >       Time (mean ± σ):     16.945 s ±  0.037 s    [User: 15.182 s, System: 1.760 s]
> >       Range (min … max):   16.910 s … 16.983 s    3 runs
> > 
> >     Summary
> >       git for-each-ref (revision=old,refcount=small) ran
> >         1.00 ± 0.01 times faster than git for-each-ref (revision=new,refcount=small)
> >         6.07 ± 0.06 times faster than git for-each-ref (revision=old,refcount=medium)
> >         6.13 ± 0.17 times faster than git for-each-ref (revision=new,refcount=medium)
> >        14.46 ± 0.17 times faster than git for-each-ref (revision=old,refcount=high)
> >        14.51 ± 0.16 times faster than git for-each-ref (revision=new,refcount=high)
> >       124.09 ± 1.15 times faster than git for-each-ref (revision=old,refcount=huge)
> >       125.05 ± 1.12 times faster than git for-each-ref (revision=new,refcount=huge)
> > 
> > The performance regression isn't all that concerning, but it makes me
> > wonder why I see things becoming slower rather than faster. My guess is
> > that this is because all my test repositories are well-packed and don't
> > have a lot of loose references. But I just wanted to confirm how you
> > benchmarked your change and what the underlying shape of your test repo
> > was.
> 
> I ran my benchmark on my (Intel) Mac with a test repository (single commit,
> one file) containing:
> 
> - 10k refs/heads/ references
> - 10k refs/tags/ references
> - 10k refs/special/ references 
> 
> All refs in the repository are loose. My Mac has historically been somewhat
> slow and inconsistent when it comes to perf testing, though, so I re-ran the
> benchmark a bit more formally on an Ubuntu VM (3 warmup iterations followed
> by at least 10 iterations per test):
> 
> ---
> 
> Benchmark 1: git for-each-ref (revision=old,refcount=3k)
>   Time (mean ± σ):      40.6 ms ±   3.9 ms    [User: 13.2 ms, System: 27.1 ms]
>   Range (min … max):    37.2 ms …  59.1 ms    76 runs
>  
>   Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.
>  
> Benchmark 2: git for-each-ref (revision=new,refcount=3k)
>   Time (mean ± σ):      38.7 ms ±   4.4 ms    [User: 13.8 ms, System: 24.5 ms]
>   Range (min … max):    35.1 ms …  57.2 ms    71 runs
>  
>   Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.
>  
> Benchmark 3: git for-each-ref (revision=old,refcount=30k)
>   Time (mean ± σ):     419.4 ms ±  43.9 ms    [User: 136.4 ms, System: 274.1 ms]
>   Range (min … max):   385.1 ms … 528.7 ms    10 runs
>  
> Benchmark 4: git for-each-ref (revision=new,refcount=30k)
>   Time (mean ± σ):     390.4 ms ±  27.2 ms    [User: 133.1 ms, System: 251.6 ms]
>   Range (min … max):   360.3 ms … 447.6 ms    10 runs
>  
> Benchmark 5: git for-each-ref (revision=old,refcount=300k)
>   Time (mean ± σ):      4.171 s ±  0.052 s    [User: 1.400 s, System: 2.715 s]
>   Range (min … max):    4.118 s …  4.283 s    10 runs
>  
> Benchmark 6: git for-each-ref (revision=new,refcount=300k)
>   Time (mean ± σ):      3.939 s ±  0.054 s    [User: 1.403 s, System: 2.466 s]
>   Range (min … max):    3.858 s …  4.026 s    10 runs
>  
> Summary
>   'git for-each-ref (revision=new,refcount=3k)' ran
>     1.05 ± 0.16 times faster than 'git for-each-ref (revision=old,refcount=3k)'
>    10.08 ± 1.34 times faster than 'git for-each-ref (revision=new,refcount=30k)'
>    10.83 ± 1.67 times faster than 'git for-each-ref (revision=old,refcount=30k)'
>   101.68 ± 11.63 times faster than 'git for-each-ref (revision=new,refcount=300k)'
>   107.67 ± 12.30 times faster than 'git for-each-ref (revision=old,refcount=300k)'
> 
> ---
> 
> So it's not the 20% speedup I saw on my local test repo (it's more like
> 5-8%), but there does appear to be a consistent improvement.

Thanks a bunch for re-doing the benchmark with a documented setup.

> As for your results, the changes in this series shouldn't affect
> packed ref operations, and the difference between old & new doesn't
> seem to indicate a regression. 

Yeah, I've also been surprised to see the performance regression for
packed-refs files. The regression is persistent and reproducable on my
machine though, so even though I tend to agree that the patches
shouldn't negatively impact packed-refs performance they somehow do. It
could just as well be something like different optimization choices by
the compler due to the added patches, or hitting different cache lines.
I dunno.

Anyway, I agree with your assessment. The regression I see is less than
1% for packed-refs, while the improvements for loose refs are a lot more
significant and conceptually make a lot of sense. So I didn't intend to
say that we shouldn't do these optimizations because of the miniscule
peformance regression with packed-refs.

Or in other words: this series looks good to me.

Thanks!
Patrick