git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Elijah Newren <newren@gmail.com>
To: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>
Cc: Git Mailing List <git@vger.kernel.org>,
	Victoria Dye <vdye@github.com>, Derrick Stolee <stolee@gmail.com>,
	Lessley Dennington <lessleydennington@gmail.com>
Subject: Re: [PATCH 5/5] Accelerate clear_skip_worktree_from_present_files() by caching
Date: Thu, 13 Jan 2022 15:35:03 -0800	[thread overview]
Message-ID: <CABPp-BGHWJ9-E-OBu_be4dSovZKzS5PYEsc4DsA4VOjOZkcGMA@mail.gmail.com> (raw)
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:
>
> 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).

  reply	other threads:[~2022-01-13 23:35 UTC|newest]

Thread overview: 30+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-01-13 16:43 [PATCH 0/5] Remove the present-despite-SKIP_WORKTREE class of bugs (for sparse-checkouts) Elijah Newren via GitGitGadget
2022-01-13 16:43 ` [PATCH 1/5] t1011: add testcase demonstrating accidental loss of user modifications Elijah Newren via GitGitGadget
2022-01-13 16:43 ` [PATCH 2/5] unpack-trees: fix accidental loss of user changes Elijah Newren via GitGitGadget
2022-01-13 16:43 ` [PATCH 3/5] repo_read_index: clear SKIP_WORKTREE bit from files present in worktree Elijah Newren via GitGitGadget
2022-01-13 16:43 ` [PATCH 4/5] Update documentation related to sparsity and the skip-worktree bit Elijah Newren via GitGitGadget
2022-01-13 16:43 ` [PATCH 5/5] Accelerate clear_skip_worktree_from_present_files() by caching Elijah Newren via GitGitGadget
2022-01-13 23:35   ` Elijah Newren [this message]
2022-01-14 15:59 ` [PATCH v2 0/5] Remove the present-despite-SKIP_WORKTREE class of bugs (for sparse-checkouts) Elijah Newren via GitGitGadget
2022-01-14 15:59   ` [PATCH v2 1/5] t1011: add testcase demonstrating accidental loss of user modifications Elijah Newren via GitGitGadget
2022-02-16  8:51     ` Ævar Arnfjörð Bjarmason
2022-02-16 16:02       ` Elijah Newren
2022-01-14 15:59   ` [PATCH v2 2/5] unpack-trees: fix accidental loss of user changes Elijah Newren via GitGitGadget
2022-01-14 15:59   ` [PATCH v2 3/5] repo_read_index: clear SKIP_WORKTREE bit from files present in worktree Elijah Newren via GitGitGadget
2022-02-16  8:57     ` Ævar Arnfjörð Bjarmason
2022-02-16 16:08       ` Elijah Newren
2022-02-19  1:06     ` Jonathan Nieder
2022-02-19 16:42       ` Elijah Newren
2022-02-19 18:14         ` Jonathan Nieder
2022-02-20  5:28           ` Elijah Newren
2022-02-20 16:56       ` Derrick Stolee
2022-02-22 23:17         ` Jonathan Nieder
2022-01-14 15:59   ` [PATCH v2 4/5] Update documentation related to sparsity and the skip-worktree bit Elijah Newren via GitGitGadget
2022-02-16  9:15     ` Ævar Arnfjörð Bjarmason
2022-02-16 16:21       ` Elijah Newren
2022-01-14 15:59   ` [PATCH v2 5/5] Accelerate clear_skip_worktree_from_present_files() by caching Elijah Newren via GitGitGadget
2022-01-15  1:39     ` Victoria Dye
2022-02-16  9:32     ` Ævar Arnfjörð Bjarmason
2022-02-16 16:30       ` Elijah Newren
2022-02-17  4:40         ` Elijah Newren
2022-01-15  1:51   ` [PATCH v2 0/5] Remove the present-despite-SKIP_WORKTREE class of bugs (for sparse-checkouts) Victoria Dye

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CABPp-BGHWJ9-E-OBu_be4dSovZKzS5PYEsc4DsA4VOjOZkcGMA@mail.gmail.com \
    --to=newren@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --cc=lessleydennington@gmail.com \
    --cc=stolee@gmail.com \
    --cc=vdye@github.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).