Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

[Tao Klerks]

Hi folks,

With the new "core.useBuiltinFSMonitor" support in the Windows
installer, I think this subject is worth calling out explicitly (and
my apologies if I missed prior discussion):

TL;DR:
 - I believe "core.untrackedcache" should be enabled by default in
Windows (and it does not appear to be)
 - If a user enables "core.useBuiltinFSMonitor" (eg in the installer)
in the hopes of getting snappy "git status" on a repo with a large
deep working tree, they will be *unnecessarily* disappointed if
"core.untrackedcache" is not enabled
 - There is also a lingering "problem" with "git status -uall", with
both "core.useBuiltinFSMonitor" and "core.fsmonitor", but that seems
far less trivial to address

Detail:

I just started testing the new "core.useBuiltinFSMonitor" option in
the new installer, and it's amazing, thanks Ben, Alex, Johannes and
Kevin!

However, when I first enabled it, I was getting slightly *worse* git
status times than without it... and those worse git status times were
accompanied by a message along the lines of:
---
It took 5.88 seconds to enumerate untracked files. 'status -uno' may
speed it up, but you have to be careful not to forget to add new files
yourself (see 'git help status').
---

For context, this is in a repo with 200,000 or so files, within 40,000
folders (avg path depth 4 I think?), with a reasonably-intricate set
of .gitignore patterns. Obviously that's not "your average user", but
I would imagine it matches "the target audience for
'core.useBuiltinFSMonitor'" pretty well.

After a little head-scratching, I recalled an exchange with Johannes
from last year:
https://lore.kernel.org/git/CAPMMpohJicVeCaKsPvommYbGEH-D1V02TTMaiVTV8ux+9z9vkQ@mail.gmail.com/

I never did understand the relevant code paths in much detail, but the
practical conclusions were:
 - Without "core.untrackedcache" enabled, git ends up iterating
through the entire path structure of the working tree *even if
"core.fsmonitor" (and now "core.useBuiltinFSMonitor") is enabled*,
looking for untracked files to report
 - Even with "core.untrackedcache" enabled, if "core.fsmonitor" (and
now "core.useBuiltinFSMonitor") is enabled, git iterates through the
entire path structure of the working tree *single-threaded* when the
"--untracked-files" mode is set to "all" (by config or command-line)

Now, I imagine that addressing/improving these behaviors is very
non-trivial, but the impact could be reasonably limited if:
 - core.untrackedcache were defaulted to "true", at least under
Windows, at least when the installer is asked to set
core.useBuiltinFSMonitor
 - The "It took N.NN seconds to enumerate untracked files" message
were to include a hint about core.untrackedcache, at least when the
"--untracked-files" mode is set to "normal".

Final note: I personally would love to see "core.useBuiltinFSMonitor
actually makes things slower, when --untracked-files=all is specified"
behavior be addressed, because common windows git integrations or
front-ends like Git Extensions or IntelliJ IDEA commonly use those
options, and therefore "suffer" a performance degradation on at least
some operations when core.useBuiltinFSMonitor is enabled.

I don't know whether this is the right place to report Windows-centric
concerns, if not, my apologies.

Thanks,
Tao

Re: Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

[Johannes Schindelin]

Hi Tao,

thank you for chiming in! It is good to see that more people are dabbling
with the built-in FSMonitor.

On Thu, 10 Jun 2021, Tao Klerks wrote:

> With the new "core.useBuiltinFSMonitor" support in the Windows
> installer, I think this subject is worth calling out explicitly (and
> my apologies if I missed prior discussion):
>
> TL;DR:
>  - I believe "core.untrackedcache" should be enabled by default in
> Windows (and it does not appear to be)

Stolee indicated something similar that matches your observation:
https://lore.kernel.org/git/af7a671c-fa32-6d9a-7d75-65582fdbcf24@gmail.com/

	Interestingly, the untracked cache extension makes a big
	difference here. The performance of the overall behavior is much
	faster if the untracked cache exists (when paired with the builtin
	FS Monitor; it doesn't make a significant difference when FS
	Monitor is disabled).

>  - If a user enables "core.useBuiltinFSMonitor" (eg in the installer)
> in the hopes of getting snappy "git status" on a repo with a large
> deep working tree, they will be *unnecessarily* disappointed if
> "core.untrackedcache" is not enabled

Yes.

And. Unfortunately, there is an "and". I recently got a chance to work
with the Functional Tests of Scalar ("an opinionated repository management
tool" on top of Git, see https://github.com/microsoft/scalar#readme for
more details). Essentially, you can think of that test suite as
integration tests for Git in a large-scale context. And there, I ran into
trouble with the untracked cache on Windows (where it really provides the
most benefit).

The gist of it is that _sometimes_, the mtime of a directory seems not to
be updated immediately after an item in it was modified/added/deleted. And
that mtime is precisely what the untracked cache depends on.

The funny thing is: while the output of `git status` will therefore at
first fail to pick up on, say, a new untracked file, running `git status`
_immediately_ afterwards _will succeed_ to see that untracked file. So
there is something fishy going on with updating things (it might even be a
foul interaction between the FSCache and the untracked cache, but I have
no evidence to back that up or to disprove it).

It is one of my big TODOs to look into that. If you have any insights, or
time to investigate, I woud be really interested.

>  - There is also a lingering "problem" with "git status -uall", with
> both "core.useBuiltinFSMonitor" and "core.fsmonitor", but that seems
> far less trivial to address

Interesting. I guess the untracked cache might become too clunky with many
untracked files? Or is there something else going on?

> Detail:
>
> I just started testing the new "core.useBuiltinFSMonitor" option in
> the new installer, and it's amazing, thanks Ben, Alex, Johannes and
> Kevin!

Not to forget Jeff Hostetler, who essentially spent the past half year on
it on his own.

> However, when I first enabled it, I was getting slightly *worse* git
> status times than without it... and those worse git status times were
> accompanied by a message along the lines of:
> ---
> It took 5.88 seconds to enumerate untracked files. 'status -uno' may
> speed it up, but you have to be careful not to forget to add new files
> yourself (see 'git help status').
> ---
>
> For context, this is in a repo with 200,000 or so files, within 40,000
> folders (avg path depth 4 I think?), with a reasonably-intricate set
> of .gitignore patterns. Obviously that's not "your average user", but
> I would imagine it matches "the target audience for
> 'core.useBuiltinFSMonitor'" pretty well.

Right. I had a somewhat similar setup, with Git for Windows' SDK, which
consists of ~160k files in ~8k directories.

My `.gitignore` consists of only ~40 heavily commented lines (containing
five lines with wildcards), but I do have a `.git/info/exclude` that
contains a set of generated file/directory lists, i.e. without any
wildcards. This `exclude` file is ~26k lines long.

A cold-cache `git status` takes ~24sec, a warm-cache one ~10sec (with the
built-in FSMonitor daemon now active).

My guess is that the amount of work to match the untracked vs ignored
files is dominating the entire operation, by a lot.

> After a little head-scratching, I recalled an exchange with Johannes
> from last year:
> https://lore.kernel.org/git/CAPMMpohJicVeCaKsPvommYbGEH-D1V02TTMaiVTV8ux+9z9vkQ@mail.gmail.com/
>
> I never did understand the relevant code paths in much detail, but the
> practical conclusions were:
>  - Without "core.untrackedcache" enabled, git ends up iterating
> through the entire path structure of the working tree *even if
> "core.fsmonitor" (and now "core.useBuiltinFSMonitor") is enabled*,
> looking for untracked files to report
>  - Even with "core.untrackedcache" enabled, if "core.fsmonitor" (and
> now "core.useBuiltinFSMonitor") is enabled, git iterates through the
> entire path structure of the working tree *single-threaded* when the
> "--untracked-files" mode is set to "all" (by config or command-line)
>
> Now, I imagine that addressing/improving these behaviors is very
> non-trivial, but the impact could be reasonably limited if:
>  - core.untrackedcache were defaulted to "true", at least under
> Windows, at least when the installer is asked to set
> core.useBuiltinFSMonitor

As soon as I can fix the flakiness of the untracked cache on Windows, I
will do that!

>  - The "It took N.NN seconds to enumerate untracked files" message
> were to include a hint about core.untrackedcache, at least when the
> "--untracked-files" mode is set to "normal".
>
> Final note: I personally would love to see "core.useBuiltinFSMonitor
> actually makes things slower, when --untracked-files=all is specified"
> behavior be addressed,

Yes, we need to spend some quality time with some perf tools there.

> because common windows git integrations or front-ends like Git
> Extensions or IntelliJ IDEA commonly use those options, and therefore
> "suffer" a performance degradation on at least some operations when
> core.useBuiltinFSMonitor is enabled.
>
> I don't know whether this is the right place to report Windows-centric
> concerns, if not, my apologies.

I would not necessarily call them "Windows-centric", even if yes, at the
moment the built-in FSMonitor is most easily enabled on Windows (because I
added that experimental option in Git for Windows' installer, after
integrating the experimental feature).

Instead, I consider this more the type of feedback concerning large
worktrees, and what Git can do to support that use case better.

In particular the built-in FSMonitor, which already supports Windows and
macOS, and hopefully we will find volunteers to work on the Linux side
soon, too. In my mind, the built-in FSMonitor, the untracked cache, and
`git maintenance` are _crucial_ tools to allow Git to scale up.

So: thank you for your wonderful feedback!

Ciao,
Dscho

Re: Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

[Tao Klerks]

[-- Attachment #1: Type: text/plain, Size: 8895 bytes --]

Hi Johannes,

Thanks for the detailed reply!

My apologies for the subsequent delay - I've been trying to understand
the behavior so that I can describe it in more detail, and that
required me to learn a little C along the way :)

On Fri, Jun 11, 2021 at 11:49 AM Johannes Schindelin
<Johannes.Schindelin@gmx.de> wrote:
> _sometimes_, the mtime of a directory seems not to
> be updated immediately after an item in it was modified/added/deleted. And
> that mtime is precisely what the untracked cache depends on.
>
> The funny thing is: while the output of `git status` will therefore at
> first fail to pick up on, say, a new untracked file, running `git status`
> _immediately_ afterwards _will succeed_ to see that untracked file.

(I have nothing to add here - I don't understand what
synchronous-acknowledgement or ordering guarantees we rely on to
determine when we *expect* a change to be available to the fsmonitor,
nor to I have any familiarity with the underlying APIs we use)

> On Thu, 10 Jun 2021, Tao Klerks wrote:
> >  - There is also a lingering "problem" with "git status -uall", with
> > both "core.useBuiltinFSMonitor" and "core.fsmonitor", but that seems
> > far less trivial to address
>
> Interesting. I guess the untracked cache might become too clunky with many
> untracked files? Or is there something else going on?

I think I understand this now, but I don't think I can explain it
particularly well/succinctly.

I've attached a sort of "truth table" of performance data for a
particular repository, running *warm* git status calls (no cold-cache
testing at all) with various config and command-line options, and
reporting the durations of various phases/processes captured using
GIT_TRACE2_PERF=1.

The claimed "problem" with "git status -uall", when both
"core.useBuiltinFSMonitor" and "core.fsmonitor" are enabled, only
exists from the perspective of someone who's got core.fscache enabled
all the time:
* core.fscache works (in the Windows port only) by doing slightly more
expensive work up-front on first directory query within a
request/process lifetime, and then intercepting subsequent filesystem
"queries"/operations
* The context within which most of this more-expensive work typically
occurs, in a "git status" request, is an explicitly and intentionally
multi-threaded filesystem "lstat"-checking process in preload-index.c
(always 20 threads, for a large repo)
* There are two sets of filesystem-iteration in a simple/naive git
status call with core.preloadindex enabled as by default - the
lstat-checking multithreaded loops for files in the index, and the
recursive directory scanning for untracked files that happens later
* That second (not-multithreaded) set of work, with fscache enabled,
gets to reuse a bunch of cached fs data from the first one. A walk
that cost 7s without fscache now costs only 2.5s, for example.
* With fsmonitor enabled (and warm), the first walk simply doesn't
happen, so fscache stops making any difference to that
untracked-file-searching directory walk; it goes back to taking 7s;
every directory is queried once in series, so fscache has no impact at
all.
* Because the preload-index lstat-querying loop is parallelized, with
fscache the initial cache population happens fast-ish - the total time
taken for git status is eg 5s (2.5s of parallelized & accelerated
lstat-querying and 2.5s of
untracked-folder-iterating-and-processing-from-fscache)
* So, with fscache enabled, turning on fsmonitor actually makes "git
status" *slower* - it changes the "lstat + untracked" time from "2.5s
+ 2.5s" to "0s + 7s"
* We can hide/mitigate that by enabling the untracked cache - but that
"fails out" in all sorts of conditions specified in dir.c
validate_untracked_cache(), including specifying "-uall"/"-u" to "git
status
* -> it is only in the context of fscache being enabled, and already
speeding up the filesystem work, that fsmonitor can make things worse
by making the first directory-querying loop happen in a non-parallel
area of code, and thereby cancel fscache's impact.
* -> fsmonitor never makes things worse on linux, since there is no
fscache and so untracked folder iteration never benefits from any
multithreading
* -> when the untracked cache does apply, fsmonitor can *help* it,
avoiding the need for any sort of directory walk at all, on the basis
that "nothing in the filesystem appears to have changed"

Based on this understanding, it looks like there are at least three
possible directions to be explored:

1. Making the untracked cache less sensitive to configuration in
dir.c#validate_untracked_cache(), at the cost of doing more work in
the cold cases & saving more data in the index file (specific
untracked files, and .git folder names or something)
 ** This would result in peak performance, with no
filesystem-iterating at all in the ideal case
 ** This would apply / add substantial value in Windows and Linux
 ** This is probably the most complex change - dir.c is not easy to
understand/navigate

2. Making the untracked directory-search happen in a multithreaded way
 ** This would raise the performance with "-uall" to approximately the
same as it was before fsmonitor was introduced on windows, and speed
it up slightly on linux
 ** This change would probably not be worthwhile, - its impact would
not be huge except in very specific cases, and it would still
introduce non-trivial complexity

3. Forcing preload-index to actually "do its multithreaded work", even
when fsmonitor is there, if we know that the untracked cached cannot
be used and fsmonitor is enabled
 ** This would raise the performance with "-uall" to approximately the
same as it was before fsmonitor was introduced on windows
 ** This change would probably be pretty easy - the main challenge is
how to get untracked-cache-applicability information at preload-index
time, since these happen in completely different parts of the codebase

I mocked up a local hack for the third option, and confirmed that
forcing preload-index to ignore it does indeed bring "git status
-uall"  performance back to the same level as before enabling
fsmonitor.

> > I just started testing the new "core.useBuiltinFSMonitor" option in
> > the new installer, and it's amazing, thanks Ben, Alex, Johannes and
> > Kevin!
>
> Not to forget Jeff Hostetler, who essentially spent the past half year on
> it on his own.

Argh, thank you for the correction, and thank you Jeff also for all
your work on this.

> > For context, this is in a repo with 200,000 or so files, within 40,000
> > folders (avg path depth 4 I think?), with a reasonably-intricate set
> > of .gitignore patterns.

> My `.gitignore` consists of only ~40 heavily commented lines (containing
> five lines with wildcards), but I do have a `.git/info/exclude` that
> contains a set of generated file/directory lists, i.e. without any
> wildcards. This `exclude` file is ~26k lines long.
>
> My guess is that the amount of work to match the untracked vs ignored
> files is dominating the entire operation, by a lot.

In my case, as per the "truth table" referenced above, there are two
kinds of things in play:
1. Filesystem operations are the main thing that matters in Windows
2. Some smaller amount of overhead (0.5-1s in my case) is associated
with other work (pattern-matching etc) during untracked file
detection, even with untracked cache enabled. The only way to avoid
that work altogether is to have fsmonitor *and* untracked cache
working, so that untracked cache can "trust" the fsmonitor results to
avoid having to do any work at all. In this ideal situation fscache
makes no difference, as there is no fs iteration.

> > I don't know whether this is the right place to report Windows-centric
> > concerns, if not, my apologies.
>
> I would not necessarily call them "Windows-centric", even if yes, at the
> moment the built-in FSMonitor is most easily enabled on Windows (because I
> added that experimental option in Git for Windows' installer, after
> integrating the experimental feature).

Right - now that I understand the situation better, there are three
specific ways in which I consider these to be windows-centric
concerns:
* In my experience / in my context at least, the "naive" impact of
file operation performance differences results in a more than 10X "git
status" reduction in performance for large repos (over linux); various
optional and/or windows-specific strategies significantly close that
gap
* core.fscache is a windows-specific strategy for dealing with this,
and interacts with other features/strategies in potentially-surprising
ways
* The built-in FSMonitor is still only *easily* available in Windows

But, to your point, most of the *solutions* need not be
windows-centric at all. The "best" one, making untracked cache a
little more forgiving, would definitely have tangible performance
benefits on linux (and presumably OSX).

Thanks,
Tao

[-- Attachment #2: Git status timing comparison, large repo, different OSes, fscache, untrackedcache, fsmonitor, and uall.csv --]
[-- Type: text/csv, Size: 6401 bytes --]

Input: OS,Input: FSCache,Input: UntrackedCache,Input: FSMonitor,Input: -uall,In: PreloadIndex,In: Command,Timing: read index,Timing: query fsmonitor,Timing: preload lstat 207k files,Timing: refresh,Timing: traverse trees,Timing: Name-hash-init,Timing: untracked,Approx Total Timing
Linux,(N/A),false,disabled,(irrelevant),true,export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=false -c core.fsmonitor= -c core.preloadindex=true status,0.04,0,0.07,0,0,0.06,0.82,0.99
Linux,(N/A),true,disabled,false,true,export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=true -c core.fsmonitor= -c core.preloadindex=true status,0.05,0,0.07,0,0,0.06,0.32,0.5
Linux,(N/A),true,disabled,true,true,export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=true -c core.fsmonitor= -c core.preloadindex=true status -u,0.04,0,0.07,0,0,0.07,0.78,0.96
Linux,(N/A),false,disabled,(irrelevant),false,export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=false -c core.fsmonitor= -c core.preloadindex=false status,0.04,0,0,0.37,0,0.07,0.87,1.35
Linux,(N/A),true,disabled,false,false,export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=true -c core.fsmonitor= -c core.preloadindex=false status,0.05,0,0,0.39,0,0.06,0.31,0.81
Linux,(N/A),true,disabled,true,false,export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=true -c core.fsmonitor= -c core.preloadindex=false status -u,0.05,0,0,0.38,0,0.07,0.78,1.28
Linux,(N/A),false,enabled,(irrelevant),(irrelevant),export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=false -c core.fsmonitor=/home/tao/build-git/.git/hooks/fsmonitor-watchman.sample status,0.04,0.04,0,0.02,0,0.06,0.81,0.97
Linux,(N/A),true,enabled,false,(irrelevant),export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=true -c core.fsmonitor=/home/tao/build-git/.git/hooks/fsmonitor-watchman.sample status,0.04,0.04,0,0.02,0,0.07,0.26,0.43
Linux,(N/A),true,enabled,true,(irrelevant),export GIT_TRACE2_PERF=1 && git -c core.untrackedcache=true -c core.fsmonitor=/home/tao/build-git/.git/hooks/fsmonitor-watchman.sample status -u,0.05,0.04,0,0.02,0,0.07,0.78,0.96
Windows,false,false,disabled,(irrelevant),true,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=false -c core.useBuiltInFSMonitor=false -c core.preloadindex=true status,0.07,0,3.36,0,0.32,0.03,5.89,9.67
Windows,false,true,disabled,false,true,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=true -c core.useBuiltInFSMonitor=false -c core.preloadindex=true status,0.05,0,3.1,0,0.32,0.03,2.46,5.96
Windows,false,true,disabled,true,true,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=true -c core.useBuiltInFSMonitor=false -c core.preloadindex=true status -u,0.05,0,3.05,0,0.31,0.03,5.95,9.39
Windows,false,false,disabled,(irrelevant),false,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=false -c core.useBuiltInFSMonitor=false -c core.preloadindex=false status,0.05,0,0,12.12,0.31,0.03,5.95,18.46
Windows,false,true,disabled,false,false,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=true -c core.useBuiltInFSMonitor=false -c core.preloadindex=false status,0.05,0,0,12.17,0.31,0.03,2.26,14.82
Windows,false,true,disabled,true,false,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=true -c core.useBuiltInFSMonitor=false -c core.preloadindex=false status -u,0.05,0,0,12.13,0.31,0.03,6.1,18.62
Windows,false,false,enabled,(irrelevant),(irrelevant),export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=false -c core.useBuiltInFSMonitor=true status,0.04,0,0,0.02,0.33,0.03,6.43,6.85
Windows,false,true,enabled,false,(irrelevant),export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=true -c core.useBuiltInFSMonitor=true status,0.05,0,0,0.01,0.33,0.03,0.48,0.9
Windows,false,true,enabled,true,(irrelevant),export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=false -c core.untrackedcache=true -c core.useBuiltInFSMonitor=true status -u,0.05,0,0,0.01,0.32,0.03,6.19,6.6
Windows,true,false,disabled,(irrelevant),true,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=false -c core.useBuiltInFSMonitor=false -c core.preloadindex=true status,0.05,0,1.8,0,0.31,0.03,2.1,4.29
Windows,true,true,disabled,false,true,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=true -c core.useBuiltInFSMonitor=false -c core.preloadindex=true status,0.06,0,1.5,0.01,0.35,0.03,0.98,2.93
Windows,true,true,disabled,true,true,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=true -c core.useBuiltInFSMonitor=false -c core.preloadindex=true status -u,0.05,0,1.68,0.01,0.42,0.03,2,4.19
Windows,true,false,disabled,(irrelevant),false,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=false -c core.useBuiltInFSMonitor=false -c core.preloadindex=false status,0.04,0,0,3.34,0.33,0.03,2.09,5.83
Windows,true,true,disabled,false,false,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=true -c core.useBuiltInFSMonitor=false -c core.preloadindex=false status,0.05,0,0,3.46,0.34,0.03,0.84,4.72
Windows,true,true,disabled,true,false,export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=true -c core.useBuiltInFSMonitor=false -c core.preloadindex=false status -u,0.05,0,0,3.38,0.32,0.04,1.85,5.64
Windows,true,false,enabled,(irrelevant),(irrelevant),export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=false -c core.useBuiltInFSMonitor=true status,0.04,0,0.01,0.01,0.33,0.03,4.9,5.32
Windows,true,true,enabled,false,(irrelevant),export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=true -c core.useBuiltInFSMonitor=true status,0.05,0,0.01,0.01,0.34,0.03,0.5,0.94
Windows,true,true,enabled,true,(irrelevant),export GIT_TRACE2_PERF=1 && time /usr/src/git/git.exe -c core.fscache=true -c core.untrackedcache=true -c core.useBuiltInFSMonitor=true status -u,0.06,0,0.01,0.01,0.31,0.03,5.14,5.56

Re: Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

[Jeff Hostetler]

On 6/21/21 8:50 AM, Tao Klerks wrote:
> Hi Johannes,
> 
> Thanks for the detailed reply!
> 
> My apologies for the subsequent delay - I've been trying to understand
> the behavior so that I can describe it in more detail, and that
> required me to learn a little C along the way :)
> 
> On Fri, Jun 11, 2021 at 11:49 AM Johannes Schindelin
> <Johannes.Schindelin@gmx.de> wrote:
>> _sometimes_, the mtime of a directory seems not to
>> be updated immediately after an item in it was modified/added/deleted. And
>> that mtime is precisely what the untracked cache depends on.
>>
>> The funny thing is: while the output of `git status` will therefore at
>> first fail to pick up on, say, a new untracked file, running `git status`
>> _immediately_ afterwards _will succeed_ to see that untracked file.
> 
> (I have nothing to add here - I don't understand what
> synchronous-acknowledgement or ordering guarantees we rely on to
> determine when we *expect* a change to be available to the fsmonitor,
> nor to I have any familiarity with the underlying APIs we use)
> 
>> On Thu, 10 Jun 2021, Tao Klerks wrote:
>>>   - There is also a lingering "problem" with "git status -uall", with
>>> both "core.useBuiltinFSMonitor" and "core.fsmonitor", but that seems
>>> far less trivial to address
>>
>> Interesting. I guess the untracked cache might become too clunky with many
>> untracked files? Or is there something else going on?
> 
> I think I understand this now, but I don't think I can explain it
> particularly well/succinctly.
> 
> I've attached a sort of "truth table" of performance data for a
> particular repository, running *warm* git status calls (no cold-cache
> testing at all) with various config and command-line options, and
> reporting the durations of various phases/processes captured using
> GIT_TRACE2_PERF=1.
> 
> The claimed "problem" with "git status -uall", when both
> "core.useBuiltinFSMonitor" and "core.fsmonitor" are enabled, only
> exists from the perspective of someone who's got core.fscache enabled
> all the time:
> * core.fscache works (in the Windows port only) by doing slightly more
> expensive work up-front on first directory query within a
> request/process lifetime, and then intercepting subsequent filesystem
> "queries"/operations
> * The context within which most of this more-expensive work typically
> occurs, in a "git status" request, is an explicitly and intentionally
> multi-threaded filesystem "lstat"-checking process in preload-index.c
> (always 20 threads, for a large repo)
> * There are two sets of filesystem-iteration in a simple/naive git
> status call with core.preloadindex enabled as by default - the
> lstat-checking multithreaded loops for files in the index, and the
> recursive directory scanning for untracked files that happens later
> * That second (not-multithreaded) set of work, with fscache enabled,
> gets to reuse a bunch of cached fs data from the first one. A walk
> that cost 7s without fscache now costs only 2.5s, for example.
> * With fsmonitor enabled (and warm), the first walk simply doesn't
> happen, so fscache stops making any difference to that
> untracked-file-searching directory walk; it goes back to taking 7s;
> every directory is queried once in series, so fscache has no impact at
> all.
> * Because the preload-index lstat-querying loop is parallelized, with
> fscache the initial cache population happens fast-ish - the total time
> taken for git status is eg 5s (2.5s of parallelized & accelerated
> lstat-querying and 2.5s of
> untracked-folder-iterating-and-processing-from-fscache)
> * So, with fscache enabled, turning on fsmonitor actually makes "git
> status" *slower* - it changes the "lstat + untracked" time from "2.5s
> + 2.5s" to "0s + 7s"
> * We can hide/mitigate that by enabling the untracked cache - but that
> "fails out" in all sorts of conditions specified in dir.c
> validate_untracked_cache(), including specifying "-uall"/"-u" to "git
> status
> * -> it is only in the context of fscache being enabled, and already
> speeding up the filesystem work, that fsmonitor can make things worse
> by making the first directory-querying loop happen in a non-parallel
> area of code, and thereby cancel fscache's impact.
> * -> fsmonitor never makes things worse on linux, since there is no
> fscache and so untracked folder iteration never benefits from any
> multithreading
> * -> when the untracked cache does apply, fsmonitor can *help* it,
> avoiding the need for any sort of directory walk at all, on the basis
> that "nothing in the filesystem appears to have changed"
> 
> Based on this understanding, it looks like there are at least three
> possible directions to be explored:
> 
> 1. Making the untracked cache less sensitive to configuration in
> dir.c#validate_untracked_cache(), at the cost of doing more work in
> the cold cases & saving more data in the index file (specific
> untracked files, and .git folder names or something)
>   ** This would result in peak performance, with no
> filesystem-iterating at all in the ideal case
>   ** This would apply / add substantial value in Windows and Linux
>   ** This is probably the most complex change - dir.c is not easy to
> understand/navigate
> 
> 2. Making the untracked directory-search happen in a multithreaded way
>   ** This would raise the performance with "-uall" to approximately the
> same as it was before fsmonitor was introduced on windows, and speed
> it up slightly on linux
>   ** This change would probably not be worthwhile, - its impact would
> not be huge except in very specific cases, and it would still
> introduce non-trivial complexity
> 
> 3. Forcing preload-index to actually "do its multithreaded work", even
> when fsmonitor is there, if we know that the untracked cached cannot
> be used and fsmonitor is enabled
>   ** This would raise the performance with "-uall" to approximately the
> same as it was before fsmonitor was introduced on windows
>   ** This change would probably be pretty easy - the main challenge is
> how to get untracked-cache-applicability information at preload-index
> time, since these happen in completely different parts of the codebase
> 
> I mocked up a local hack for the third option, and confirmed that
> forcing preload-index to ignore it does indeed bring "git status
> -uall"  performance back to the same level as before enabling
> fsmonitor.
> 
>>> I just started testing the new "core.useBuiltinFSMonitor" option in
>>> the new installer, and it's amazing, thanks Ben, Alex, Johannes and
>>> Kevin!
>>
>> Not to forget Jeff Hostetler, who essentially spent the past half year on
>> it on his own.
> 
> Argh, thank you for the correction, and thank you Jeff also for all
> your work on this.
> 
>>> For context, this is in a repo with 200,000 or so files, within 40,000
>>> folders (avg path depth 4 I think?), with a reasonably-intricate set
>>> of .gitignore patterns.
> 
>> My `.gitignore` consists of only ~40 heavily commented lines (containing
>> five lines with wildcards), but I do have a `.git/info/exclude` that
>> contains a set of generated file/directory lists, i.e. without any
>> wildcards. This `exclude` file is ~26k lines long.
>>
>> My guess is that the amount of work to match the untracked vs ignored
>> files is dominating the entire operation, by a lot.
> 
> In my case, as per the "truth table" referenced above, there are two
> kinds of things in play:
> 1. Filesystem operations are the main thing that matters in Windows
> 2. Some smaller amount of overhead (0.5-1s in my case) is associated
> with other work (pattern-matching etc) during untracked file
> detection, even with untracked cache enabled. The only way to avoid
> that work altogether is to have fsmonitor *and* untracked cache
> working, so that untracked cache can "trust" the fsmonitor results to
> avoid having to do any work at all. In this ideal situation fscache
> makes no difference, as there is no fs iteration.
> 
>>> I don't know whether this is the right place to report Windows-centric
>>> concerns, if not, my apologies.
>>
>> I would not necessarily call them "Windows-centric", even if yes, at the
>> moment the built-in FSMonitor is most easily enabled on Windows (because I
>> added that experimental option in Git for Windows' installer, after
>> integrating the experimental feature).
> 
> Right - now that I understand the situation better, there are three
> specific ways in which I consider these to be windows-centric
> concerns:
> * In my experience / in my context at least, the "naive" impact of
> file operation performance differences results in a more than 10X "git
> status" reduction in performance for large repos (over linux); various
> optional and/or windows-specific strategies significantly close that
> gap
> * core.fscache is a windows-specific strategy for dealing with this,
> and interacts with other features/strategies in potentially-surprising
> ways
> * The built-in FSMonitor is still only *easily* available in Windows
> 
> But, to your point, most of the *solutions* need not be
> windows-centric at all. The "best" one, making untracked cache a
> little more forgiving, would definitely have tangible performance
> benefits on linux (and presumably OSX).
> 
> Thanks,
> Tao
> 

Nice summary.  Thanks!

We're currently looking at a problem that we believe is in the
untracked-cache code.  This is causing some of our Scalar tests
to fail on Windows when the untracked-cache is turned on.  This
is independent of whether FSMonitor or FSCache is turned on.
We're still tracking this down.

And yes, the best possible solution is to turn on FSMonitor *and*
the untracked-cache, so that the "untracked" status code doesn't
have to do anything.  So I want to look at tracking down the above
problem before doing anything else.

Thanks
Jeff

Re: Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

[Tao Klerks]

Hi Jeff, thanks for the update!

On Mon, Jun 21, 2021 at 8:41 PM Jeff Hostetler <git@jeffhostetler.com> wrote:
> We're currently looking at a problem that we believe is in the
> untracked-cache code.  This is causing some of our Scalar tests
> to fail on Windows when the untracked-cache is turned on.

For what it's worth, I just discovered an untracked cache bug this
evening, although I doubt it's related to the one you mention - it's
not very exciting:

If you disable untracked cache (and write an index file), and then
enable untracked cache and run status with "-uall" (writing a new
index file), the untracked cache data written in the new index file is
empty/invalid, and subsequent "git status" calls perform just the same
as if untracked cache were disabled:
----
# write an index without untracked cache
git -c core.untrackedcache=false status

# write another index with invalid/empty/bad untracked cache because
"-uall" skipped its population/maintenance
git -c core.untrackedcache=true status -uall # expected to be slow

# run regular "git status" (with untracked cache) any number of times,
but don't get the benefit (and you don't write a new index because
nothing appears to have changed)
git -c core.untrackedcache=true status # unexpectedly slow
git -c core.untrackedcache=true status # unexpectedly slow
git -c core.untrackedcache=true status # unexpectedly slow
---
# TO FIX:
# write a new index file without untracked cache
git -c core.untrackedcache=false status

# run regular "git status" (with untracked cache), does work and
writes a new index file
git -c core.untrackedcache=true status # slow as expected

# run regular "git status" (with untracked cache) any number of times,
is fast as expected
git -c core.untrackedcache=true status # fast as expected
git -c core.untrackedcache=true status # fast as expected
git -c core.untrackedcache=true status # fast as expected
----

I suspect this issue has bit me in the past when attempting to
understand untracked cache behavior; it can be *very* confusing, if
you're using tooling like "git extensions" that can, in the above
flow, "poison" your untracked cache if it just happens to run a "git
status -uall" in the background as you are testing.

(I discovered this issue while trying to understand the weird &
wonderful relationship between the repo-level untracked cache
reference, the dir-level untracked cache reference, and the mechanisms
that initialize a new one at dir.c#new_untracked_cache() and write the
repo-level one (even if the dir-level reference was voided due to flag
mismatch) at dir.c#write_untracked_extension())

Should I be reporting this in some more "official" form somewhere? Is
there a bug DB?

Thanks,
Tao

Re: Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

[Tao Klerks]

Fwiw, I've now submitted a patch(set) that I believe addresses this
particular issue correctly:

https://lore.kernel.org/git/pull.986.git.1624559401.gitgitgadget@gmail.com/

Thanks,
Tao

On Mon, Jun 21, 2021 at 10:52 PM Tao Klerks <tao@klerks.biz> wrote:
>
> Hi Jeff, thanks for the update!
>
> On Mon, Jun 21, 2021 at 8:41 PM Jeff Hostetler <git@jeffhostetler.com> wrote:
> > We're currently looking at a problem that we believe is in the
> > untracked-cache code.  This is causing some of our Scalar tests
> > to fail on Windows when the untracked-cache is turned on.
>
> For what it's worth, I just discovered an untracked cache bug this
> evening, although I doubt it's related to the one you mention - it's
> not very exciting:
>
> If you disable untracked cache (and write an index file), and then
> enable untracked cache and run status with "-uall" (writing a new
> index file), the untracked cache data written in the new index file is
> empty/invalid, and subsequent "git status" calls perform just the same
> as if untracked cache were disabled:
> ----
> # write an index without untracked cache
> git -c core.untrackedcache=false status
>
> # write another index with invalid/empty/bad untracked cache because
> "-uall" skipped its population/maintenance
> git -c core.untrackedcache=true status -uall # expected to be slow
>
> # run regular "git status" (with untracked cache) any number of times,
> but don't get the benefit (and you don't write a new index because
> nothing appears to have changed)
> git -c core.untrackedcache=true status # unexpectedly slow
> git -c core.untrackedcache=true status # unexpectedly slow
> git -c core.untrackedcache=true status # unexpectedly slow
> ---
> # TO FIX:
> # write a new index file without untracked cache
> git -c core.untrackedcache=false status
>
> # run regular "git status" (with untracked cache), does work and
> writes a new index file
> git -c core.untrackedcache=true status # slow as expected
>
> # run regular "git status" (with untracked cache) any number of times,
> is fast as expected
> git -c core.untrackedcache=true status # fast as expected
> git -c core.untrackedcache=true status # fast as expected
> git -c core.untrackedcache=true status # fast as expected
> ----
>
> I suspect this issue has bit me in the past when attempting to
> understand untracked cache behavior; it can be *very* confusing, if
> you're using tooling like "git extensions" that can, in the above
> flow, "poison" your untracked cache if it just happens to run a "git
> status -uall" in the background as you are testing.
>
> (I discovered this issue while trying to understand the weird &
> wonderful relationship between the repo-level untracked cache
> reference, the dir-level untracked cache reference, and the mechanisms
> that initialize a new one at dir.c#new_untracked_cache() and write the
> repo-level one (even if the dir-level reference was voided due to flag
> mismatch) at dir.c#write_untracked_extension())
>
> Should I be reporting this in some more "official" form somewhere? Is
> there a bug DB?
>
> Thanks,
> Tao

Re: Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

[Tao Klerks]

Hi Jeff,

On Mon, Jun 21, 2021 at 8:41 PM Jeff Hostetler <git@jeffhostetler.com> wrote:
> We're currently looking at a problem that we believe is in the
> untracked-cache code.  This is causing some of our Scalar tests
> to fail on Windows when the untracked-cache is turned on.  This
> is independent of whether FSMonitor or FSCache is turned on.
> We're still tracking this down.
>
> And yes, the best possible solution is to turn on FSMonitor *and*
> the untracked-cache, so that the "untracked" status code doesn't
> have to do anything.  So I want to look at tracking down the above
> problem before doing anything else.

I got a bit excited about a possible clean path forward to getting
-uall to work well with untracked cache, and submitted a patch along
those lines, but rereading the above I should probably have been a
little more patient.

Is there anything "we" can do to see/understand the
scalar-test-suite-error you describe above, or is this
microsoft-internal?

Thanks
Tao

Re: Windows: core.useBuiltinFSMonitor without core.untrackedcache - performance hazard?

[Jeff Hostetler]

On 6/24/21 1:25 AM, Tao Klerks wrote:
> Hi Jeff,
> 
> On Mon, Jun 21, 2021 at 8:41 PM Jeff Hostetler <git@jeffhostetler.com> wrote:
>> We're currently looking at a problem that we believe is in the
>> untracked-cache code.  This is causing some of our Scalar tests
>> to fail on Windows when the untracked-cache is turned on.  This
>> is independent of whether FSMonitor or FSCache is turned on.
>> We're still tracking this down.
>>
>> And yes, the best possible solution is to turn on FSMonitor *and*
>> the untracked-cache, so that the "untracked" status code doesn't
>> have to do anything.  So I want to look at tracking down the above
>> problem before doing anything else.
> 
> I got a bit excited about a possible clean path forward to getting
> -uall to work well with untracked cache, and submitted a patch along
> those lines, but rereading the above I should probably have been a
> little more patient.
> 
> Is there anything "we" can do to see/understand the
> scalar-test-suite-error you describe above, or is this
> microsoft-internal?
> 
> Thanks
> Tao
> 

Thanks for looking into this.  The untracked-cache code is pretty
dense and having another set of eyes is good.  I apologize that I'm
still working thru the backlog from my vacation and haven't gotten
to spend any "quality" time with the untracked-cache code yet, so
I need to do some homework and study the questions/issues that you've
found so far. (Thanks again)

All of our work is done in the open, so yes you should be able to
see what we're doing and the errors that we're getting.

The source for our Scalar functional tests is in:
https://github.com/microsoft/scalar

My test branch 'test-no-fscache' is in my personal development fork:
https://github.com/jeffhostetler/git

I have a PR against microsoft/git (a fork of git-for-windows
which is a fork of core git) which turns off a bunch of things
to try to isolate the failures:
https://github.com/microsoft/git/pull/383

Output for a recent run can be seen here:
https://github.com/microsoft/git/pull/383/checks?check_run_id=2884524819

Let us know if you have questions.
Jeff