On 6/24/24 6:14 PM, Elijah Newren wrote:
On Thu, Jun 20, 2024 at 10:11 AM Derrick Stolee via GitGitGadget
<gitgitgadget@xxxxxxxxx> wrote:
From: Derrick Stolee <stolee@xxxxxxxxx>
The clear_skip_worktree_from_present_files() method was first introduced
in af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files
present in worktree, 2022-01-14) to allow better interaction with the
working directory in the presence of paths outside of the
sparse-checkout cone.
s/cone//
The initial implementation would lstat() every
single sparse tree to see if it existed, and if one did, then the sparse
index would expand and every sparse file would be checked.
This sounds like the algorithm only lstat()ed the sparse directories,
which feels misleading. Perhaps
The initial implementation would lstat() every SKIP_WORKTREE path to
see if it existed; if it ran across a sparse directory that existed
(when a sparse-index was in use), then it would expand the index and
then check every SKIP_WORKTREE path.
Since these lstat() calls were very expensive, this was improved in
d79d299352 (Accelerate clear_skip_worktree_from_present_files() by
caching, 2022-01-14) by caching directories that do not exist. However,
there are some inefficiencies in that caching mechanism.
Maybe this is obvious, but I thought a few extra words to end the
second-to-last sentence would be helpful, such as "so it could avoid
lstat()ing any files under such directories".
Thanks. I will use both of these suggestions verbatim.
To set up a scenario that triggers this code in an interesting way, we
need a sparse-checkout in cone mode and a sparse index. To trigger the
I think you state this too strongly. While trying to duplicate, I
first went with a cone mode & sparse index at first, but out of
curiosity tried it without either of these modes set and still saw
dramatic improvement from your patch. What is needed is that the
sparsity is such that entire directories are missing, and not just one
level above the files of interest. That is more likely to occur when
cone mode and perhaps sparse index are in use, but perhaps consider
changing "we need" to "it is easiest to consider"
Absolutely. This stems from my earlier assumption that the sparse index
was required, but it is not. I have reworded locally.
full index expansion and a call to the
clear_skip_worktree_from_present_files_full() method, we need one of the
sparse trees to actually exist on disk. The performance test script
p2000-sparse-operations.sh takes the sample repository and copies its
HEAD to several copies nested in directories of the form f<i>/f<j>/f<k>
where i, j, and k are numbers from 1 to 4. The sparse-checkout cone is
then selected as "f2/f4/". Creating "f1/f1/" will trigger the behavior
and also lead to some interesting cases for the caching algorithm since
"f1/f1/" exists but "f1/f2/" and "f3/" do not.
For some reason I had difficulty triggering a case using this guide.
I might have made an error, but I decided I wanted a deeper directory
tree to test with anyway. After some playing around to come up with
an interesting testcase, I eventually came up with the following steps
to reproduce in case anyone else wants to try:
git clone https://github.com/newren/gvfs-like-git-bomb
cd gvfs-like-git-bomb
./runme.sh
git sparse-checkout set bomb/b/c # incidentally cone mode
mkdir -p bomb/d/e/f/a/a
git ls-files -t | colrm 2 | sort | uniq -c # optional, but interesting
GIT_TRACE2_PERF=$(pwd)/trace git ls-files -t >/dev/null
grep lstat_count trace
Further, you can recompile the git version in use in another window,
then come back to this one and run 'rm trace' followed by the last two
commands to retest.
The commands above create a 'gvfs-like-git-bomb' git directory that
has 1,000,001 files in HEAD.
With this test directory, before applying this patch, I see:
..sparse_lstat_count:722011
After applying this patch I see
..sparse_lstat_count:135
and with a slight tweak to your patch I see
..sparse_lstat_count:125
I'll comment on the slight tweak at the end of the patch.
Thanks for these numbers! Are you willing to keep that example repo
on GitHub so I can refer to it in the message?
This is difficult to notice when running performance tests using the Git
repository (or a blow-up of the Git repository, as in
p2000-sparse-operations.sh) because Git has a very shallow directory
structure.
This change reorganizes the caching algorithm to focus on storing both
the deepest _existing_ directory and the next-level non-existing
directory.
This was slightly hard to parse for me, and misled me into thinking
you were tracking two directories. Maybe:
This change reorganizes the caching algorithm to focus on storing the
highest level leading directory that does not exist (i.e. we are
restricting to the leading directory whose parent directory does
exist).
I have reworded in a slightly different way, but with the same meaning
as you provide here.
By doing a little extra work on the first sparse file, we can
short-circuit all of the sparse files that exist in that non-existing
directory.
Here you use "exist" as "tracked by git" in one case, and "appears in
the working tree" in another. That's a problem, because the files in
question are tracked by git but do not appear in the working tree,
making it impossible for people to understand unless they guess the
correct definition for each use. I think we want "exist" to just mean
"appears in the working tree" here, so we'd need to s/sparse files
that exist in/sparse files underneath/ (or something similar) to fix
this sentence.
Also, you've used the phrase "sparse file(s)" a number of times in
this commit message; I think I know what you mean, but it is not
defined in the vocabulary section of
Documentation/technical/sparse-checkout.txt. Together with the above
problem, it made me question what was meant, re-read all the
definitions, etc. Perhaps "sparse file(s)" should be added to that
vocabulary section, though...especially if we are going to use it and
since we never fixed "sparse directory" despite mentioning that we
wanted to?
You're right. My use of "sparse file" or "sparse directory" was intended
to mean "a path from a cache entry with SKIP_WORKTREE that is either a
blob or tree" but that isn't necessary here.
Instead, I'll focus my attention on paths being passed to path_found(),
which removes the context of an index. The danger there is that the
caching assumes that we are moving through the paths in an order such
as in the index, but that's a natural type of ordering for paths.
/*
- * Otherwise, path does not exist so we'll return 0...but we'll first
- * determine some info about its parent directory so we can avoid
- * lstat calls for future cache entries.
+ * At this point, we know that 'path' doesn't exist, and we know that
+ * the parent directory of 'data->dir' does exist. Let's set 'data->dir'
+ * to be the top-most non-existing directory of 'path'. If the first
+ * parent of 'path' exists, then we will act ast though 'path'
s/ast/as/
Oops! Thanks.
+ /*
+ * Now that we have a slash, let's grow 'data->dir' to include
+ * this slash, then test if we should stop.
+ */
+ strbuf_add(&data->dir, path + data->dir.len,
+ (next_slash - path) - data->dir.len + 1);
I had to re-read this multiple times and was confused by it. I
eventually realized it was simple -- you use "path + data->dir.len"
3-4 times in this loop. Could we reduce the cognitive overhead by
setting some variable to this value at the beginning within the loop
and then just use it? It'd simplify this particular call to
strbuf_add(&data->dir, rest, next_slash - rest + 1);
or substitute any other variable name for "rest" there. Maybe it
shouldn't be a big deal, but the rest of the method was complex enough
that I just blew my local stack space at this point. I think this
simple substitution would have made it easier for me.
Excellent. Thanks for recognizing this pattern and recommending a
simplification.
+ /*
+ * At this point, 'data->dir' is equal to 'path' plus a slash character,
+ * and the parent directory of 'path' definitely exists. Let's return
+ * the case of whether 'path' exists.
+ */
Can I suggest adding the following to this comment?
" path does not exist at this point or we would have already
returned 1 above when we lstat()ed it before the above loop. "
+
+ data->lstat_count++;
+ return !lstat(path, &st);
...and, as long as I didn't missing something with my above comment
suggestion, these two lines can be replaced by
return 0;
Or did I miss something here?
No, you understood correctly. Thanks for the further simplification and
speed improvement.
Anyway, despite the many small comments I made, well done! I think
the method is not only much more performant, but more readable than my
original. With a few small tweaks, it should be good to merge.
Thanks for your detailed review. I'll put these updates into a v2 and
send it later today. I need to retest in my monorepo example and add
your publicly-available example before v2 will be ready.
Thanks,
-Stolee
