git/sparse-index.c, branch v2.51.2

global: mark code units that generate warnings with `-Wsign-compare`

2024-12-06T11:20:02Z

Mark code units that generate warnings with `-Wsign-compare`. This allows for a structured approach to get rid of all such warnings over time in a way that can be easily measured. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

sparse-index: correctly free EWAH contents

2024-11-05T06:37:56Z

While we free the `fsmonitor_dirty` member of `struct index_state`, we do not free the contents of that EWAH. Do so by using `ewah_free()` instead of `FREE_AND_NULL()`. This leak is exposed by t7519, but plugging it alone does not make the test suite pass. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

Merge branch 'ds/sparse-checkout-expansion-advice'

2024-10-02T14:46:25Z

When "git sparse-checkout disable" turns a sparse checkout into a regular checkout, the index is fully expanded. This totally expected behaviour however had an "oops, we are expanding the index" advice message, which has been corrected. * ds/sparse-checkout-expansion-advice: sparse-checkout: disable advice in 'disable'

sparse-checkout: disable advice in 'disable'

2024-09-23T20:19:01Z

When running 'git sparse-checkout disable' with the sparse index enabled, Git is expected to expand the index into a full index. However, it currently outputs the advice message saying that that is unexpected and likely due to an issue with the working directory. Disable this advice message when in this code path. Establish a pattern for doing a similar removal in the future. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

environment: guard state depending on a repository

2024-09-12T17:15:42Z

In "environment.h" we have quite a lot of functions and variables that either explicitly or implicitly depend on `the_repository`. The implicit set of stateful declarations includes for example variables which get populated when parsing a repository's Git configuration. This set of variables is broken by design, as their state often depends on the last repository config that has been parsed. So they may or may not represent the state of `the_repository`. Fixing that is quite a big undertaking, and later patches in this series will demonstrate a solution for a first small set of those variables. So for now, let's guard these with `USE_THE_REPOSITORY_VARIABLE` so that callers are aware of the implicit dependency. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

Merge branch 'ds/advice-sparse-index-expansion'

2024-07-16T18:18:56Z

A new warning message is issued when a command has to expand a sparse index to handle working tree cruft that are outside of the sparse checkout. * ds/advice-sparse-index-expansion: advice: warn when sparse index expands

advice: warn when sparse index expands

2024-07-08T19:23:59Z

Typically, forcing a sparse index to expand to a full index means that Git could not determine the status of a file outside of the sparse-checkout and needed to expand sparse trees into the full list of sparse blobs. This operation can be very slow when the sparse-checkout is much smaller than the full tree at HEAD. When users are in this state, there is usually a modified or untracked file outside of the sparse-checkout mentioned by the output of 'git status'. There are a number of reasons why this is insufficient: 1. Users may not have a full understanding of which files are inside or outside of their sparse-checkout. This is more common in monorepos that manage the sparse-checkout using custom tools that map build dependencies into sparse-checkout definitions. 2. In some cases, an empty directory could exist outside the sparse-checkout and these empty directories are not reported by 'git status' and friends. 3. If the user has '.gitignore' or 'exclude' files, then 'git status' will squelch the warnings and not demonstrate any problems. In order to help users who are in this state, add a new advice message to indicate that a sparse index is expanded to a full index. This message should be written at most once per process, so add a static global 'give_advice_on_expansion' to sparse-index.c. Further, there is a case in 'git sparse-checkout set' that uses the sparse index as an in-memory data structure (even when writing a full index) so we need to disable the message in that kind of case. The t1092-sparse-checkout-compatibility.sh test script compares the behavior of several Git commands across full and sparse repositories, including sparse repositories with and without a sparse index. We need to disable the advice in the sparse-index repo to avoid differences in stderr. By leaving the advice on in the sparse-checkout repo (without the sparse index), we can test the behavior of disabling the advice in convert_to_sparse(). (Indeed, these tests are how that necessity was discovered.) Add a test that reenables the advice and demonstrates that the message is output. The advice message is defined outside of expand_index() to avoid super- wide lines. It is also defined as a macro to avoid compile issues with -Werror=format-security. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

sparse-index: improve lstat caching of sparse paths

2024-06-28T19:32:12Z

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. The initial implementation would lstat() every single 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 so it could avoid lstat()ing any files under such directories. However, there are some inefficiencies in that caching mechanism. The caching mechanism stored only the parent directory as not existing, even if a higher parent directory also does not exist. This means that wasted lstat() calls would occur when the paths passed to path_found() change immediate parent directories but within the same parent directory that does not exist. To create an example repository that demonstrates this problem, it helps to have a directory outside of the sparse-checkout that contains many deep paths. In particular, the first paths (in lexicographic order) underneath the sparse directory should have deep directory structures, maximizing the difference between the old caching algorithm that looks to a single parent and the new caching algorithm that looks to the top-most missing directory. 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/f/f 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. 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 the highest level leading directory that does not exist; specifically this means that that directory's parent _does_ exist. By doing a little extra work on a path passed to path_found(), we can short-circuit all of the paths passed to path_found() afterwards that match a prefix with that non-existing directory. When in a repository where the first sparse file is likely to have a much deeper path than the first non-existing directory, this can realize significant gains. The details of this algorithm require careful attention, so the new implementation of path_found() has detailed comments, including the use of a new max_common_dir_prefix() method that may be of independent interest. It's worth noting that this is not universally positive, since we are doing extra lstat() calls to establish the exact path to cache. In the blow-up of the Git repository, we can see that the lstat count _increases_ from 28 to 31. However, these numbers were already artificially low. Contributor Elijah Newren created a publicly-available test repository that demonstrates the difference in these caching algorithms in the most extreme way. To test, follow these steps: git clone --sparse https://github.com/newren/gvfs-like-git-bomb cd gvfs-like-git-bomb ./runme.sh # NOTE: check scripts before running! At this point, assuming you do not have index.sparse=true set globally, the index has one million paths with the SKIP_WORKTREE bit and they will all be sent to path_found() in the sparse loop. You can measure this by running 'git status' with GIT_TRACE2_PERF=1: Sparse files in the index: 1,000,000 sparse_lstat_count (before): 200,000 sparse_lstat_count (after): 2 And here are the performance numbers: Benchmark 1: old Time (mean ± σ): 397.5 ms ± 4.1 ms Range (min … max): 391.2 ms … 404.8 ms 10 runs Benchmark 2: new Time (mean ± σ): 252.7 ms ± 3.1 ms Range (min … max): 249.4 ms … 259.5 ms 11 runs Summary 'new' ran 1.57 ± 0.02 times faster than 'old' By modifying this example further, we can demonstrate a more realistic example and include the sparse index expansion. Continue by creating this directory, confusing both caching algorithms somewhat: mkdir -p bomb/d/e/f/a/a Then re-run the 'git status' tests to see these statistics: Sparse files in the index: 1,000,000 sparse_lstat_count (before): 724,010 sparse_lstat_count (after): 106 Benchmark 1: old Time (mean ± σ): 753.0 ms ± 3.5 ms Range (min … max): 749.7 ms … 760.9 ms 10 runs Benchmark 2: new Time (mean ± σ): 201.4 ms ± 3.2 ms Range (min … max): 196.0 ms … 207.9 ms 14 runs Summary 'new' ran 3.74 ± 0.06 times faster than 'old' Note that if this repository had a sparse index enabled, the additional cost of expanding the sparse index affects the total time of these commands by over four seconds, significantly diminishing the benefit of the caching algorithm. Having existing paths outside of the sparse-checkout is a known performance issue for the sparse index and is a known trade-off for the performance benefits given when no such paths exist. Using an internal monorepo with over two million paths at HEAD and a typical sparse-checkout cone such that the sparse index contains ~190,000 entries (including over two thousand sparse trees), I was able to measure these lstat counts when one sparse directory actually exists on disk: Sparse files in expanded index: 1,841,997 full_lstat_count (before): 1,188,161 full_lstat_count (after): 4,404 This resulted in this absolute time change, on a warm disk: Time in full loop (before): 13.481 s Time in full loop (after): 0.081 s (These times were calculated on a Windows machine, where lstat() is slower than a similar Linux machine.) Helped-by: Elijah Newren Signed-off-by: Derrick Stolee Reviewed-by: Elijah Newren Signed-off-by: Junio C Hamano

sparse-index: count lstat() calls

2024-06-28T19:32:12Z
The clear_skip_worktree.. methods already report some statistics about how many cache entries are checked against path_found() due to having the skip-worktree bit set. However, due to path_found() performing some caching, this isn't the only information that would be helpful to report. Add a new lstat_count member to the path_found_data struct to count the number of times path_found() calls lstat(). This will be helpful to help explain performance problems in this method as well as to demonstrate future changes to the caching algorithm in a more concrete way than end-to-end timings. Signed-off-by: Derrick Stolee Reviewed-by: Elijah Newren Signed-off-by: Junio C Hamano

sparse-index: use strbuf in path_found()

2024-06-28T19:32:11Z
The path_found() method previously reused strings from the cache entries the calling methods were using. This prevents string manipulation in place and causes some odd reallocation before the final lstat() call in the method. Refactor the method to use strbufs and copy the path into the strbuf, but also only the parent directory and not the whole path. This looks like extra copying when assigning the path to the strbuf, but we save an allocation by dropping the 'tmp' string, and we are "reusing" the copy from 'tmp' to put the data in the strbuf. Signed-off-by: Derrick Stolee Reviewed-by: Elijah Newren Signed-off-by: Junio C Hamano