Re: [PATCH 5/5] Accelerate clear_skip_worktree_from_present_files() by caching

From: Elijah Newren <newren@gmail.com>
Date: Jan 13, 2022, 23:35 UTC
Message-ID: <CABPp-BGHWJ9-E-OBu_be4dSovZKzS5PYEsc4DsA4VOjOZkcGMA@mail.gmail.com>
In-Reply-To: <e68028ebe0afc1bb9e623efbdd30de5a8f0740bf.1642092230.git.gitgitgadget@gmail.com>

On Thu, Jan 13, 2022 at 8:43 AM Elijah Newren via GitGitGadget <gitgitgadget@gmail.com> wrote:

Show 7 quoted lines

>
> From: Elijah Newren <newren@gmail.com>
>
> Trying to clear the skip-worktree bit from files that are present does
> present some computational overhead, for sparse-checkouts.  (We do not
> do the bit clearing in non-sparse-checkouts.)  Optimize it as follows:
>

...

> (NOTE: t/perf/ appears to have timing resolution only down to 0.01 s,
> which presents significant measurement error when timings only differ by
> 0.01s.  I don't trust any such timings below, and yet all the optimized
> results differ by at most 0.01s.)

To follow up on this using using a tool with higher precision for a few selected cases:

> Test        Before Series    Unoptimized              Optimized
> -----------------------------------------------------------------------------

...

> *git add -A*
> full-v3     0.40(0.30+0.07)  0.56(0.36+0.17) +40.0%   0.39(0.30+0.07) -2.5%

In hyperfine, the results were:

before-series,full-v3$ hyperfine '~/floss/git/git add -A'
Benchmark #1: ~/floss/git/git add -A
  Time (mean ± σ):     129.4 ms ±   3.0 ms    [User: 84.0 ms, System: 59.9 ms]
  Range (min … max):   122.5 ms … 138.3 ms    24 runs

post-optim,full-v3$ hyperfine '~/floss/git/git add -A'
Benchmark #1: ~/floss/git/git add -A
  Time (mean ± σ):     133.4 ms ±   3.0 ms    [User: 85.6 ms, System: 61.4 ms]
  Range (min … max):   129.7 ms … 142.7 ms    22 runs

Since 133.4/129.4 ~ 1.0309, we see that we have +3.1% on the execution timing due to changes in this series. Notably, the number is actually positive as we'd expect since we are clearly doing more work, whereas the t/perf system reports -2.5% due to measurement inaccuracy.

> full-v4     0.37(0.28+0.07)  0.54(0.37+0.16) +45.9%   0.38(0.29+0.07) +2.7%
> sparse-v3   0.06(0.04+0.05)  0.08(0.05+0.05) +33.3%   0.06(0.05+0.04) +0.0%
> sparse-v4   0.05(0.03+0.05)  0.05(0.04+0.04) +0.0%    0.06(0.04+0.05) +20.0%

before-series,sparse-v4$ hyperfine '~/floss/git/git add -A'
Benchmark #1: ~/floss/git/git add -A
  Time (mean ± σ):      37.0 ms ±   1.1 ms    [User: 23.1 ms, System: 47.8 ms]
  Range (min … max):    35.6 ms …  42.1 ms    72 runs

post-optim,sparse-v4$ hyperfine '~/floss/git/git add -A'
Benchmark #1: ~/floss/git/git add -A
  Time (mean ± σ):      37.3 ms ±   0.9 ms    [User: 22.8 ms, System: 48.7 ms]
  Range (min … max):    36.2 ms …  40.7 ms    72 runs

37.3/37.0 ~ 1.008, so a +0.8% on execution timing. Hard to measure, and nice that hyperfine automatically chooses to run this 72 times just to ensure the data is more reliable. (Also, the +0.8% is much more believable than the +20.0% from lack of measurement accuracy, especially combined with data below)

> *git diff*
> full-v3     0.07(0.04+0.04)  0.24(0.11+0.14) +242.9%  0.07(0.04+0.04) +0.0%
> full-v4     0.07(0.03+0.05)  0.24(0.13+0.12) +242.9%  0.08(0.04+0.05) +14.3%

before-series,full-v4$ hyperfine '~/floss/git/git diff'
Benchmark #1: ~/floss/git/git diff
  Time (mean ± σ):      69.9 ms ±   1.9 ms    [User: 37.5 ms, System: 47.6 ms]
  Range (min … max):    66.5 ms …  74.0 ms    44 runs

post-optim,full-v4$ hyperfine '~/floss/git/git diff'
Benchmark #1: ~/floss/git/git diff
  Time (mean ± σ):      73.0 ms ±   1.7 ms    [User: 40.7 ms, System: 47.1 ms]
  Range (min … max):    70.3 ms …  76.2 ms    40 runs

So 73.0/69.9 ~ 1.044, so a +4.4% to the execution timing -- much less than the +14.3% reported due to lack of measurement accuracy.

(If I had used ~/floss/git/bin-wrappers/git instead of ~/floss/git/git, the timings would have been going from 72.3ms to 75.1ms, representing a +3.9% increase instead. Probably doesn't matter, but just in case folks were curious about what if I used the bin-wrappers.)

> sparse-v3   0.02(0.01+0.04)  0.02(0.01+0.04) +0.0%    0.02(0.01+0.05) +0.0%
> sparse-v4   0.02(0.02+0.03)  0.02(0.01+0.04) +0.0%    0.02(0.01+0.04) +0.0%

Here, the timings went from 17.5ms to 17.6ms, or +0.6%. It's really hard to measure the overhead of the changes of my patch series when sparse-index is in use, which makes sense since the extra loop only has to check the toplevel directory, not any of the entries under it. But it does show just a minor cost in runtime due to the new added check.

I think the original commit message makes it clear that with the (new) optimization, the timings are quite reasonable, but maybe this little extra flavor helps for anyone who was just looking at the percentage changes. The timings and timing differences really need to be bigger than the precision in order to trust the percentage differences, which just wasn't the case for t/perf here. But t/perf was good enough to show that the timings after my series are roughly the same as before the series (never more than 0.01s slower).