{"thread":{"id":"61657","subject":"[PATCH 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","startedAt":"2024-06-20T16:11:21Z","lastAt":"2024-06-28T19:34:20Z","messageCount":44,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Derrick Stolee","Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"497405","messageId":"pull.1754.git.1718899877.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":null,"subject":"[PATCH 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-20T16:11:12Z","receivedAt":"2024-06-20T16:11:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"While doing some investigation in a private monorepo with sparse-checkout\nand a sparse index, I accidentally left a modified file outside of my\nsparse-checkout cone. This caused my Git commands to slow to a crawl, so I\nreran with GIT_TRACE2_PERF=1.\n\nWhile I was able to identify clear_skip_worktree_from_present_files() as the\nculprit, it took longer than desired to figure out what was going on. This\nseries intends to both fix the performance issue (as much as possible) and\ndo some refactoring to make it easier to understand what is happening.\n\nIn the end, I was able to reduce the number of lstat() calls in my case from\nover 170,000 to about 6,500, improving the time from 2.5s to 71ms on a warm\ndisk cache.   Thanks, Stolee\n\nDerrick Stolee (5):\n sparse-index: refactor skip worktree retry logic\n sparse-index: refactor path_found()\n sparse-index: use strbuf in path_found()\n sparse-index: count lstat() calls\n sparse-index: improve lstat caching of sparse paths\n\n sparse-index.c | 220 +++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 167 insertions(+), 53 deletions(-)\n\n\nbase-commit: 66ac6e4bcd111be3fa9c2a6b3fafea718d00678d\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1754%2Fderrickstolee%2Fclear-skip-speed-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1754/derrickstolee/clear-skip-speed-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1754\n-- \ngitgitgadget\n"},{"id":"497406","messageId":"ddd8a9a90cea10be47eba4775bb90f01a9b80443.1718899877.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.git.1718899877.gitgitgadget@gmail.com","subject":"[PATCH 1/5] sparse-index: refactor skip worktree retry logic","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-20T16:11:13Z","receivedAt":"2024-06-20T16:11:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree_from_present_files() method was introduced in\naf6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files present\nin worktree, 2022-01-14) to help cases where the sparse index is enabled\nbut some paths outside of the sparse-checkout cone also exist on disk.\nThis operation can be slow as it needs to check path existence in a way\nthat is not stored in the collapsed index, so caching was introduced in\nd79d299352 (Accelerate clear_skip_worktree_from_present_files() by\ncaching, 2022-01-14).\n\nIf users are having trouble with the performance of this operation and\ndon't care about paths outside of the sparse-checkout cone, they can\ndisable them using the sparse.expectFilesOutsideOfPatterns config option\nintroduced in ecc7c8841d (repo_read_index: add config to expect files\noutside sparse patterns, 2022-02-25).\n\nEven with that caching, it was noticed that this could take a long time\nto execute. 89aaab11a3 (index: add trace2 region for clear skip\nworktree, 2022-11-03) introduced trace2 regions to measure this time.\nFurther, the way the loop repeats itself was slightly confusing and\nprone to breakage, so a BUG() statement was added in 8c7abdc596 (index:\nraise a bug if the index is materialised more than once, 2022-11-03) to\nbe sure that the second run of the loop does not hit any sparse trees.\n\nOne thing that can be confusing about the current setup is that the\ntrace2 regions nest and it is not clear that a second loop is running\nafter the index is expanded. Here is an example of what the regions look\nlike in a typical case:\n\n| region_enter | ... | label:clear_skip_worktree_from_present_files\n| region_enter | ... | ..label:update\n| region_leave | ... | ..label:update\n| region_enter | ... | ..label:ensure_full_index\n| region_enter | ... | ....label:update\n| region_leave | ... | ....label:update\n| region_leave | ... | ..label:ensure_full_index\n| data | ... | ..sparse_path_count:1\n| data | ... | ..sparse_path_count_full:269538\n| region_leave | ... | label:clear_skip_worktree_from_present_files\n\nOne thing that is particularly difficult to understand about these\nregions is that most of the time is spent between the close of the\nensure_full_index region and the reporting of the end data. This is\nbecause of the restart of the loop being within the same region as the\nfirst iteration of the loop.\n\nThis change refactors the method into two separate methods that are\ntraced separately. This will be more important later when we change\nother features of the methods, but for now the only functional change is\nthe difference in the structure of the trace regions.\n\nAfter this change, the same telemetry section is split into three\ndistinct chunks:\n\n| region_enter | ... | label:clear_skip_worktree_from_present_files_sparse\n| data | ... | ..sparse_path_count:1\n| region_leave | ... | label:clear_skip_worktree_from_present_files_sparse\n| region_enter | ... | label:update\n| region_leave | ... | label:update\n| region_enter | ... | label:ensure_full_index\n| region_enter | ... | ..label:update\n| region_leave | ... | ..label:update\n| region_leave | ... | label:ensure_full_index\n| region_enter | ... | label:clear_skip_worktree_from_present_files_full\n| data | ... | ..full_path_count:269538\n| region_leave | ... | label:clear_skip_worktree_from_present_files_full\n\nHere, we see the sparse loop terminating early with its first sparse\npath being a sparse directory containing a file. Then, that loop's\nregion terminates before ensure_full_index begins (in this case, the\ncache-tree must also be computed). Then, _after_ the index is expanded,\nthe full loop begins with its own region.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 77 ++++++++++++++++++++++++++++++++++----------------\n 1 file changed, 53 insertions(+), 24 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex e48e40cae71..e0457c87fff 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -486,49 +486,78 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \treturn 0;\n }\n \n-void clear_skip_worktree_from_present_files(struct index_state *istate)\n+static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n {\n \tconst char *last_dirname = NULL;\n \tsize_t dir_len = 0;\n \tint dir_found = 1;\n \n-\tint i;\n-\tint path_count[2] = {0, 0};\n-\tint restarted = 0;\n+\tint path_count = 0;\n+\tint to_restart = 0;\n \n-\tif (!core_apply_sparse_checkout ||\n-\t sparse_expect_files_outside_of_patterns)\n-\t\treturn;\n-\n-\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files\",\n+\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n-restart:\n-\tfor (i = 0; i < istate->cache_nr; i++) {\n+\tfor (int i = 0; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i];\n \n \t\tif (ce_skip_worktree(ce)) {\n-\t\t\tpath_count[restarted]++;\n+\t\t\tpath_count++;\n \t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n \t\t\t\tif (S_ISSPARSEDIR(ce->ce_mode)) {\n-\t\t\t\t\tif (restarted)\n-\t\t\t\t\t\tBUG(\"ensure-full-index did not fully flatten?\");\n-\t\t\t\t\tensure_full_index(istate);\n-\t\t\t\t\trestarted = 1;\n-\t\t\t\t\tgoto restart;\n+\t\t\t\t\tto_restart = 1;\n+\t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n \t\t\t}\n \t\t}\n \t}\n \n-\tif (path_count[0])\n-\t\ttrace2_data_intmax(\"index\", istate->repo,\n-\t\t\t\t \"sparse_path_count\", path_count[0]);\n-\tif (restarted)\n-\t\ttrace2_data_intmax(\"index\", istate->repo,\n-\t\t\t\t \"sparse_path_count_full\", path_count[1]);\n-\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files\",\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"sparse_path_count\", path_count);\n+\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n+\t\t\t istate->repo);\n+\treturn to_restart;\n+}\n+\n+static void clear_skip_worktree_from_present_files_full(struct index_state *istate)\n+{\n+\tconst char *last_dirname = NULL;\n+\tsize_t dir_len = 0;\n+\tint dir_found = 1;\n+\n+\tint path_count = 0;\n+\n+\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n+\tfor (int i = 0; i < istate->cache_nr; i++) {\n+\t\tstruct cache_entry *ce = istate->cache[i];\n+\n+\t\tif (S_ISSPARSEDIR(ce->ce_mode))\n+\t\t\tBUG(\"ensure-full-index did not fully flatten?\");\n+\n+\t\tif (ce_skip_worktree(ce)) {\n+\t\t\tpath_count++;\n+\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found))\n+\t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n+\t\t}\n+\t}\n+\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"full_path_count\", path_count);\n+\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n+\t\t\t istate->repo);\n+}\n+\n+void clear_skip_worktree_from_present_files(struct index_state *istate)\n+{\n+\tif (!core_apply_sparse_checkout ||\n+\t sparse_expect_files_outside_of_patterns)\n+\t\treturn;\n+\n+\tif (clear_skip_worktree_from_present_files_sparse(istate)) {\n+\t\tensure_full_index(istate);\n+\t\tclear_skip_worktree_from_present_files_full(istate);\n+\t}\n }\n \n /*\n-- \ngitgitgadget\n\n"},{"id":"497407","messageId":"7c3b545ee5ea3a0e6686594afe582fa1a19929f6.1718899877.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.git.1718899877.gitgitgadget@gmail.com","subject":"[PATCH 2/5] sparse-index: refactor path_found()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-20T16:11:14Z","receivedAt":"2024-06-20T16:11:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn advance of changing the behavior of path_found(), take all of the\nintermediate data values and group them into a single struct. This\nsimplifies the method prototype as well as the initialization. Future\nchanges can be made directly to the struct and method without changing\nthe callers with this approach.\n\nNote that the clear_path_found_data() method is currently empty, as\nthere is nothing to free. However, this will change in the future, so\nplace the method and its callers for now.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 45 +++++++++++++++++++++++++++++----------------\n 1 file changed, 29 insertions(+), 16 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex e0457c87fff..de6e727f5c1 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -439,8 +439,22 @@ void ensure_correct_sparsity(struct index_state *istate)\n \t\tensure_full_index(istate);\n }\n \n-static int path_found(const char *path, const char **dirname, size_t *dir_len,\n-\t\t int *dir_found)\n+struct path_found_data {\n+\tconst char *dirname;\n+\tsize_t dir_len;\n+\tint dir_found;\n+};\n+\n+#define PATH_FOUND_DATA_INIT { \\\n+\t.dir_found = 1 \\\n+}\n+\n+static void clear_path_found_data(struct path_found_data *data)\n+{\n+\treturn;\n+}\n+\n+static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n \tchar *newdir;\n@@ -450,7 +464,7 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \t * If dirname corresponds to a directory that doesn't exist, and this\n \t * path starts with dirname, then path can't exist.\n \t */\n-\tif (!*dir_found && !memcmp(path, *dirname, *dir_len))\n+\tif (!data->dir_found && !memcmp(path, data->dirname, data->dir_len))\n \t\treturn 0;\n \n \t/*\n@@ -472,15 +486,16 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \t * If path starts with directory (which we already lstat'ed and found),\n \t * then no need to lstat parent directory again.\n \t */\n-\tif (*dir_found && *dirname && memcmp(path, *dirname, *dir_len))\n+\tif (data->dir_found && data->dirname &&\n+\t memcmp(path, data->dirname, data->dir_len))\n \t\treturn 0;\n \n \t/* Free previous dirname, and cache path's dirname */\n-\t*dirname = path;\n-\t*dir_len = newdir - path + 1;\n+\tdata->dirname = path;\n+\tdata->dir_len = newdir - path + 1;\n \n-\ttmp = xstrndup(path, *dir_len);\n-\t*dir_found = !lstat(tmp, &st);\n+\ttmp = xstrndup(path, data->dir_len);\n+\tdata->dir_found = !lstat(tmp, &st);\n \tfree(tmp);\n \n \treturn 0;\n@@ -488,9 +503,7 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \n static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n {\n-\tconst char *last_dirname = NULL;\n-\tsize_t dir_len = 0;\n-\tint dir_found = 1;\n+\tstruct path_found_data data = PATH_FOUND_DATA_INIT;\n \n \tint path_count = 0;\n \tint to_restart = 0;\n@@ -502,7 +515,7 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \n \t\tif (ce_skip_worktree(ce)) {\n \t\t\tpath_count++;\n-\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n+\t\t\tif (path_found(ce->name, &data)) {\n \t\t\t\tif (S_ISSPARSEDIR(ce->ce_mode)) {\n \t\t\t\t\tto_restart = 1;\n \t\t\t\t\tbreak;\n@@ -516,14 +529,13 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \t\t\t \"sparse_path_count\", path_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n+\tclear_path_found_data(&data);\n \treturn to_restart;\n }\n \n static void clear_skip_worktree_from_present_files_full(struct index_state *istate)\n {\n-\tconst char *last_dirname = NULL;\n-\tsize_t dir_len = 0;\n-\tint dir_found = 1;\n+\tstruct path_found_data data = PATH_FOUND_DATA_INIT;\n \n \tint path_count = 0;\n \n@@ -537,7 +549,7 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \n \t\tif (ce_skip_worktree(ce)) {\n \t\t\tpath_count++;\n-\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found))\n+\t\t\tif (path_found(ce->name, &data))\n \t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n \t\t}\n \t}\n@@ -546,6 +558,7 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \t\t\t \"full_path_count\", path_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n+\tclear_path_found_data(&data);\n }\n \n void clear_skip_worktree_from_present_files(struct index_state *istate)\n-- \ngitgitgadget\n\n"},{"id":"497408","messageId":"217594ffb103969c1a6debc07a6c7f72f6ee4749.1718899877.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.git.1718899877.gitgitgadget@gmail.com","subject":"[PATCH 3/5] sparse-index: use strbuf in path_found()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-20T16:11:15Z","receivedAt":"2024-06-20T16:11:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe path_found() method previously reused strings from the cache entries\nthe calling methods were using. This prevents string manipulation in\nplace and causes some odd reallocation before the final lstat() call in\nthe method.\n\nRefactor the method to use strbufs and copy the path into the strbuf,\nbut also only the parent directory and not the whole path. This looks\nlike extra copying when assigning the path to the strbuf, but we save an\nallocation by dropping the 'tmp' string, and we are \"reusing\" the copy\nfrom 'tmp' to put the data in the strbuf.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 21 +++++++++------------\n 1 file changed, 9 insertions(+), 12 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex de6e727f5c1..fec4f393360 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -440,31 +440,30 @@ void ensure_correct_sparsity(struct index_state *istate)\n }\n \n struct path_found_data {\n-\tconst char *dirname;\n-\tsize_t dir_len;\n+\tstruct strbuf dir;\n \tint dir_found;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n+\t.dir = STRBUF_INIT, \\\n \t.dir_found = 1 \\\n }\n \n static void clear_path_found_data(struct path_found_data *data)\n {\n-\treturn;\n+\tstrbuf_release(&data->dir);\n }\n \n static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n \tchar *newdir;\n-\tchar *tmp;\n \n \t/*\n \t * If dirname corresponds to a directory that doesn't exist, and this\n \t * path starts with dirname, then path can't exist.\n \t */\n-\tif (!data->dir_found && !memcmp(path, data->dirname, data->dir_len))\n+\tif (!data->dir_found && !memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/*\n@@ -486,17 +485,15 @@ static int path_found(const char *path, struct path_found_data *data)\n \t * If path starts with directory (which we already lstat'ed and found),\n \t * then no need to lstat parent directory again.\n \t */\n-\tif (data->dir_found && data->dirname &&\n-\t memcmp(path, data->dirname, data->dir_len))\n+\tif (data->dir_found && data->dir.buf &&\n+\t memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/* Free previous dirname, and cache path's dirname */\n-\tdata->dirname = path;\n-\tdata->dir_len = newdir - path + 1;\n+\tstrbuf_reset(&data->dir);\n+\tstrbuf_add(&data->dir, path, newdir - path + 1);\n \n-\ttmp = xstrndup(path, data->dir_len);\n-\tdata->dir_found = !lstat(tmp, &st);\n-\tfree(tmp);\n+\tdata->dir_found = !lstat(data->dir.buf, &st);\n \n \treturn 0;\n }\n-- \ngitgitgadget\n\n"},{"id":"497410","messageId":"88a3145e585169fde8cd7d43a435daa07eb82667.1718899877.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.git.1718899877.gitgitgadget@gmail.com","subject":"[PATCH 4/5] sparse-index: count lstat() calls","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-20T16:11:16Z","receivedAt":"2024-06-20T16:11:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree.. methods already report some statistics about\nhow many cache entries are checked against path_found() due to having\nthe skip-worktree bit set. However, due to path_found() performing some\ncaching, this isn't the only information that would be helpful to\nreport.\n\nAdd a new lstat_count member to the path_found_data struct to count the\nnumber of times path_found() calls lstat(). This will be helpful to help\nexplain performance problems in this method as well as to demonstrate\nfuture changes to the caching algorithm in a more concrete way than\nend-to-end timings.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex fec4f393360..8577fa726b8 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -442,6 +442,7 @@ void ensure_correct_sparsity(struct index_state *istate)\n struct path_found_data {\n \tstruct strbuf dir;\n \tint dir_found;\n+\tsize_t lstat_count;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n@@ -469,6 +470,7 @@ static int path_found(const char *path, struct path_found_data *data)\n \t/*\n \t * If path itself exists, return 1.\n \t */\n+\tdata->lstat_count++;\n \tif (!lstat(path, &st))\n \t\treturn 1;\n \n@@ -493,6 +495,7 @@ static int path_found(const char *path, struct path_found_data *data)\n \tstrbuf_reset(&data->dir);\n \tstrbuf_add(&data->dir, path, newdir - path + 1);\n \n+\tdata->lstat_count++;\n \tdata->dir_found = !lstat(data->dir.buf, &st);\n \n \treturn 0;\n@@ -524,6 +527,8 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \n \ttrace2_data_intmax(\"index\", istate->repo,\n \t\t\t \"sparse_path_count\", path_count);\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"sparse_lstat_count\", data.lstat_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n \tclear_path_found_data(&data);\n@@ -553,6 +558,8 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \n \ttrace2_data_intmax(\"index\", istate->repo,\n \t\t\t \"full_path_count\", path_count);\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"full_lstat_count\", data.lstat_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n \tclear_path_found_data(&data);\n-- \ngitgitgadget\n\n"},{"id":"497409","messageId":"2654fcb7142a606c5684c762ed28bb5e8d9b4712.1718899877.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.git.1718899877.gitgitgadget@gmail.com","subject":"[PATCH 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-20T16:11:17Z","receivedAt":"2024-06-20T16:11:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree_from_present_files() method was first introduced\nin af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files\npresent in worktree, 2022-01-14) to allow better interaction with the\nworking directory in the presence of paths outside of the\nsparse-checkout cone. The initial implementation would lstat() every\nsingle sparse tree to see if it existed, and if one did, then the sparse\nindex would expand and every sparse file would be checked.\n\nSince these lstat() calls were very expensive, this was improved in\nd79d299352 (Accelerate clear_skip_worktree_from_present_files() by\ncaching, 2022-01-14) by caching directories that do not exist. However,\nthere are some inefficiencies in that caching mechanism.\n\nThe caching mechanism stored only the parent directory as not existing,\neven if a higher parent directory also does not exist. This means that\nwasted lstat() calls would occur when the sparse files change immediate\nparent directories but within the same root directory that does not\nexist.\n\nTo set up a scenario that triggers this code in an interesting way, we\nneed a sparse-checkout in cone mode and a sparse index. To trigger the\nfull index expansion and a call to the\nclear_skip_worktree_from_present_files_full() method, we need one of the\nsparse trees to actually exist on disk. The performance test script\np2000-sparse-operations.sh takes the sample repository and copies its\nHEAD to several copies nested in directories of the form f/f/f\nwhere i, j, and k are numbers from 1 to 4. The sparse-checkout cone is\nthen selected as \"f2/f4/\". Creating \"f1/f1/\" will trigger the behavior\nand also lead to some interesting cases for the caching algorithm since\n\"f1/f1/\" exists but \"f1/f2/\" and \"f3/\" do not.\n\nThis is difficult to notice when running performance tests using the Git\nrepository (or a blow-up of the Git repository, as in\np2000-sparse-operations.sh) because Git has a very shallow directory\nstructure.\n\nThis change reorganizes the caching algorithm to focus on storing both\nthe deepest _existing_ directory and the next-level non-existing\ndirectory. By doing a little extra work on the first sparse file, we can\nshort-circuit all of the sparse files that exist in that non-existing\ndirectory. When in a repository where the first sparse file is likely to\nhave a much deeper path than the first non-existing directory, this can\nrealize significant gains.\n\nThe details of this algorithm require careful attention, so the new\nimplementation of path_found() has detailed comments, including the use\nof a new max_common_dir_prefix() method that may be of independent\ninterest.\n\nIt's worth noting that this is not universally positive, since we are\ndoing extra lstat() calls to establish the exact path to cache. In the\nblow-up of the Git repository, we can see that the lstat count\n_increases_ from 28 to 31. However, these numbers were already\nartificially low.\n\nUsing an internal monorepo with over two million paths at HEAD and a\ntypical sparse-checkout cone such that the index contains ~190,000\nentries (including over two thousand sparse trees), I was able to\nmeasure these lstat counts when one sparse directory actually exists on\ndisk:\n\n Sparse files in expanded index: 1,841,997\n full_lstat_count (before): 173,259\n full_lstat_count (after): 6,521\n\nThis resulted in this absolute time change, on a warm disk:\n\n Time in full loop (before): 2.527 s\n Time in full loop (after): 0.071 s\n\n(These times were calculated on a Windows machine, where lstat() is\nslower than a similar Linux machine.)\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 118 ++++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 93 insertions(+), 25 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 8577fa726b8..cccd8550dfe 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -440,14 +440,21 @@ void ensure_correct_sparsity(struct index_state *istate)\n }\n \n struct path_found_data {\n+\t/**\n+\t * The path stored in 'dir', if non-empty, corresponds to the most-\n+\t * recent path that we checked where:\n+\t *\n+\t * 1. The path should be a directory, according to the index.\n+\t * 2. The path does not exist.\n+\t * 3. The parent path _does_ exist. (This may be the root of the\n+\t * working directory.)\n+\t */\n \tstruct strbuf dir;\n-\tint dir_found;\n \tsize_t lstat_count;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n-\t.dir = STRBUF_INIT, \\\n-\t.dir_found = 1 \\\n+\t.dir = STRBUF_INIT \\\n }\n \n static void clear_path_found_data(struct path_found_data *data)\n@@ -455,50 +462,111 @@ static void clear_path_found_data(struct path_found_data *data)\n \tstrbuf_release(&data->dir);\n }\n \n+/**\n+ * Return the length of the largest common substring that ends in a\n+ * slash ('/') to indicate the largest common parent directory. Returns\n+ * zero if no common directory exists.\n+ */\n+static size_t max_common_dir_prefix(const char *path1, const char *path2)\n+{\n+\tsize_t common_prefix = 0;\n+\tfor (size_t i = 0; path1[i] && path2[i]; i++) {\n+\t\tif (path1[i] != path2[i])\n+\t\t\tbreak;\n+\n+\t\t/*\n+\t\t * If they agree at a directory separator, then add one\n+\t\t * to make sure it is included in the common prefix string.\n+\t\t */\n+\t\tif (path1[i] == '/')\n+\t\t\tcommon_prefix = i + 1;\n+\t}\n+\n+\treturn common_prefix;\n+}\n+\n static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n-\tchar *newdir;\n+\tsize_t common_prefix;\n \n \t/*\n-\t * If dirname corresponds to a directory that doesn't exist, and this\n-\t * path starts with dirname, then path can't exist.\n+\t * If data->dir is non-empty, then it contains a path that doesn't\n+\t * exist, including an ending slash ('/'). If it is a prefix of 'path',\n+\t * then we can return 0.\n \t */\n-\tif (!data->dir_found && !memcmp(path, data->dir.buf, data->dir.len))\n+\tif (data->dir.len && !memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/*\n-\t * If path itself exists, return 1.\n+\t * Otherwise, we must check if the current path exists. If it does, then\n+\t * return 1. The cached directory will be skipped until we come across\n+\t * a missing path again.\n \t */\n \tdata->lstat_count++;\n \tif (!lstat(path, &st))\n \t\treturn 1;\n \n \t/*\n-\t * Otherwise, path does not exist so we'll return 0...but we'll first\n-\t * determine some info about its parent directory so we can avoid\n-\t * lstat calls for future cache entries.\n+\t * At this point, we know that 'path' doesn't exist, and we know that\n+\t * the parent directory of 'data->dir' does exist. Let's set 'data->dir'\n+\t * to be the top-most non-existing directory of 'path'. If the first\n+\t * parent of 'path' exists, then we will act ast though 'path'\n+\t * corresponds to a directory (by adding a slash).\n \t */\n-\tnewdir = strrchr(path, '/');\n-\tif (!newdir)\n-\t\treturn 0; /* Didn't find a parent dir; just return 0 now. */\n+\tcommon_prefix = max_common_dir_prefix(path, data->dir.buf);\n \n \t/*\n-\t * If path starts with directory (which we already lstat'ed and found),\n-\t * then no need to lstat parent directory again.\n+\t * At this point, 'path' and 'data->dir' have a common existing parent\n+\t * directory given by path[0..common_prefix] (which could have length 0).\n+\t * We \"grow\" the data->dir buffer by checking for existing directories\n+\t * along 'path'.\n \t */\n-\tif (data->dir_found && data->dir.buf &&\n-\t memcmp(path, data->dir.buf, data->dir.len))\n-\t\treturn 0;\n \n-\t/* Free previous dirname, and cache path's dirname */\n-\tstrbuf_reset(&data->dir);\n-\tstrbuf_add(&data->dir, path, newdir - path + 1);\n+\tstrbuf_setlen(&data->dir, common_prefix);\n+\twhile (1) {\n+\t\t/* Find the next directory in 'path'. */\n+\t\tconst char *next_slash = strchr(path + data->dir.len, '/');\n \n-\tdata->lstat_count++;\n-\tdata->dir_found = !lstat(data->dir.buf, &st);\n+\t\t/*\n+\t\t * If there are no more slashes, then 'path' doesn't contain a\n+\t\t * non-existent _parent_ directory. Set 'data->dir' to be equal\n+\t\t * to 'path' plus an additional slash, so it can be used for\n+\t\t * caching in the future. The filename of 'path' is considered\n+\t\t * a non-existent directory.\n+\t\t *\n+\t\t * Note: if \"{path}/\" exists as a directory, then it will never\n+\t\t * appear as a prefix of other callers to this method, assuming\n+\t\t * the context from the clear_skip_worktree... methods. If this\n+\t\t * method is reused, then this must be reconsidered.\n+\t\t */\n+\t\tif (!next_slash) {\n+\t\t\tstrbuf_addstr(&data->dir, path + data->dir.len);\n+\t\t\tstrbuf_addch(&data->dir, '/');\n+\t\t\tbreak;\n+\t\t}\n \n-\treturn 0;\n+\t\t/*\n+\t\t * Now that we have a slash, let's grow 'data->dir' to include\n+\t\t * this slash, then test if we should stop.\n+\t\t */\n+\t\tstrbuf_add(&data->dir, path + data->dir.len,\n+\t\t\t (next_slash - path) - data->dir.len + 1);\n+\n+\t\t/* If the path doesn't exist, then stop here. */\n+\t\tdata->lstat_count++;\n+\t\tif (lstat(data->dir.buf, &st))\n+\t\t\treturn 0;\n+\t}\n+\n+\t/*\n+\t * At this point, 'data->dir' is equal to 'path' plus a slash character,\n+\t * and the parent directory of 'path' definitely exists. Let's return\n+\t * the case of whether 'path' exists.\n+\t */\n+\n+\tdata->lstat_count++;\n+\treturn !lstat(path, &st);\n }\n \n static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n-- \ngitgitgadget\n"},{"id":"497428","messageId":"xmqqiky3tofw.fsf@gitster.g","threadId":"61657","inReplyTo":"pull.1754.git.1718899877.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-06-20T19:16:19Z","receivedAt":"2024-06-20T19:16:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> While doing some investigation in a private monorepo with sparse-checkout\n> and a sparse index, I accidentally left a modified file outside of my\n> sparse-checkout cone. This caused my Git commands to slow to a crawl, so I\n> reran with GIT_TRACE2_PERF=1.\n>\n> While I was able to identify clear_skip_worktree_from_present_files() as the\n> culprit, it took longer than desired to figure out what was going on. This\n> series intends to both fix the performance issue (as much as possible) and\n> do some refactoring to make it easier to understand what is happening.\n>\n> In the end, I was able to reduce the number of lstat() calls in my case from\n> over 170,000 to about 6,500, improving the time from 2.5s to 71ms on a warm\n> disk cache.   Thanks, Stolee\n\nThat's impressive but I cannot offhand tell how big 170k (or 6.5k\nfor that matter) is relative to the size of the tree. How many\npaths are there in the entire tree (i.e. \"git ls-tree -r HEAD | wc\n-l\") vs the number of the in-cone paths in the working tree? \n\nIf 6.5k is in the same ballpark as the latter, it would be really\ngood.\n\nThanks.\n"},{"id":"497430","messageId":"77974c37-b82f-42fb-848f-e060495c4f49@gmail.com","threadId":"61657","inReplyTo":"xmqqiky3tofw.fsf@gitster.g","subject":"Re: [PATCH 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-06-20T20:21:20Z","receivedAt":"2024-06-20T20:21:23Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/20/24 3:16 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> While doing some investigation in a private monorepo with sparse-checkout\n>> and a sparse index, I accidentally left a modified file outside of my\n>> sparse-checkout cone. This caused my Git commands to slow to a crawl, so I\n>> reran with GIT_TRACE2_PERF=1.\n>>\n>> While I was able to identify clear_skip_worktree_from_present_files() as the\n>> culprit, it took longer than desired to figure out what was going on. This\n>> series intends to both fix the performance issue (as much as possible) and\n>> do some refactoring to make it easier to understand what is happening.\n>>\n>> In the end, I was able to reduce the number of lstat() calls in my case from\n>> over 170,000 to about 6,500, improving the time from 2.5s to 71ms on a warm\n>> disk cache.   Thanks, Stolee\n> \n> That's impressive but I cannot offhand tell how big 170k (or 6.5k\n> for that matter) is relative to the size of the tree. How many\n> paths are there in the entire tree (i.e. \"git ls-tree -r HEAD | wc\n> -l\") vs the number of the in-cone paths in the working tree?\n> \n> If 6.5k is in the same ballpark as the latter, it would be really\n> good.\n\nYou're right, I didn't include the full context here. The repo has\nabout 2.1 million paths at HEAD, but most of them are sparse.\n\nIn Patch 5, I detail that there are 1,841,997 total sparse files in\nthe expanded index. Thus, the previous caching algorithm was already\ndoing decent work and calling lstat() 11x fewer times than the naive\nimplementation.\n\nThe new caching algorithm improves this to 6,521, which is a 282x\nimprovement over naive and and 26x improvement over the previous\ncaching algorithm.\n\nBut what you are really asking is how close this is to the optimal.\nI didn't include that in Patch 5 details, but I was able to look at\nmy notes and see that the sparse_path_count data point was 1,962,\nmeaning there are that many sparse trees in the sparse index before\nexpanding. Thus, the 6,521 lstat() calls are 3.3x more than the\nabsolute minimum required.\n\nDoes that help answer the questions you had? I'm happy to provide\nmore information.\n\nThanks,\n-Stolee\n"},{"id":"497432","messageId":"xmqq7cejtjix.fsf@gitster.g","threadId":"61657","inReplyTo":"77974c37-b82f-42fb-848f-e060495c4f49@gmail.com","subject":"Re: [PATCH 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-06-20T21:02:30Z","receivedAt":"2024-06-20T21:02:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> But what you are really asking is how close this is to the optimal.\n> I didn't include that in Patch 5 details, but I was able to look at\n> my notes and see that the sparse_path_count data point was 1,962,\n> meaning there are that many sparse trees in the sparse index before\n> expanding. Thus, the 6,521 lstat() calls are 3.3x more than the\n> absolute minimum required.\n\nNice, and still impressive. Thanks.\n"},{"id":"497590","messageId":"CABPp-BF=8y2yC0WvF7BhNFiyW10A_yKs5s6euEi3FwYSsmHnWg@mail.gmail.com","threadId":"61657","inReplyTo":"ddd8a9a90cea10be47eba4775bb90f01a9b80443.1718899877.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/5] sparse-index: refactor skip worktree retry logic","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-24T22:12:53Z","receivedAt":"2024-06-24T22:13:05Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 20, 2024 at 10:11 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> The clear_skip_worktree_from_present_files() method was introduced in\n> af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files present\n> in worktree, 2022-01-14) to help cases where the sparse index is enabled\n\ns/index/checkout/; the code in af6a51875a made no assumptions about\nsparse index being enabled.\n\n> but some paths outside of the sparse-checkout cone also exist on disk.\n\ns/cone//; it wasn't specific to cone mode.\n\n> This operation can be slow as it needs to check path existence in a way\n> that is not stored in the collapsed index, so caching was introduced in\n> d79d299352 (Accelerate clear_skip_worktree_from_present_files() by\n> caching, 2022-01-14).\n\nThis is worded in a way that seems to imply the code is only relevant\nwith a sparse index. Part of the code was written to be faster in\ngeneral with a sparse-index, but having a sparse-index was not\nassumed. Perhaps,\n\nThis operation could be slow since it needs to check path existence\nfor the paths outside the sparse checkout, which may vastly outnumber\nthe number of paths inside the sparse checkout. To address this,\ncaching was introduced in d79d299352 (Accelerate\nclear_skip_worktree_from_present_files() by caching, 2022-01-14).\n\n> If users are having trouble with the performance of this operation and\n> don't care about paths outside of the sparse-checkout cone, they can\n> disable them using the sparse.expectFilesOutsideOfPatterns config option\n> introduced in ecc7c8841d (repo_read_index: add config to expect files\n> outside sparse patterns, 2022-02-25).\n>\n> Even with that caching, it was noticed that this could take a long time\n> to execute. 89aaab11a3 (index: add trace2 region for clear skip\n> worktree, 2022-11-03) introduced trace2 regions to measure this time.\n> Further, the way the loop repeats itself was slightly confusing and\n> prone to breakage, so a BUG() statement was added in 8c7abdc596 (index:\n> raise a bug if the index is materialised more than once, 2022-11-03) to\n> be sure that the second run of the loop does not hit any sparse trees.\n>\n> One thing that can be confusing about the current setup is that the\n> trace2 regions nest and it is not clear that a second loop is running\n> after the index is expanded. Here is an example of what the regions look\n> like in a typical case:\n>\n> | region_enter | ... | label:clear_skip_worktree_from_present_files\n> | region_enter | ... | ..label:update\n> | region_leave | ... | ..label:update\n> | region_enter | ... | ..label:ensure_full_index\n> | region_enter | ... | ....label:update\n> | region_leave | ... | ....label:update\n> | region_leave | ... | ..label:ensure_full_index\n> | data | ... | ..sparse_path_count:1\n> | data | ... | ..sparse_path_count_full:269538\n> | region_leave | ... | label:clear_skip_worktree_from_present_files\n>\n> One thing that is particularly difficult to understand about these\n> regions is that most of the time is spent between the close of the\n> ensure_full_index region and the reporting of the end data. This is\n> because of the restart of the loop being within the same region as the\n> first iteration of the loop.\n>\n> This change refactors the method into two separate methods that are\n> traced separately. This will be more important later when we change\n> other features of the methods, but for now the only functional change is\n> the difference in the structure of the trace regions.\n>\n> After this change, the same telemetry section is split into three\n> distinct chunks:\n>\n> | region_enter | ... | label:clear_skip_worktree_from_present_files_sparse\n> | data | ... | ..sparse_path_count:1\n> | region_leave | ... | label:clear_skip_worktree_from_present_files_sparse\n> | region_enter | ... | label:update\n> | region_leave | ... | label:update\n> | region_enter | ... | label:ensure_full_index\n> | region_enter | ... | ..label:update\n> | region_leave | ... | ..label:update\n> | region_leave | ... | label:ensure_full_index\n> | region_enter | ... | label:clear_skip_worktree_from_present_files_full\n> | data | ... | ..full_path_count:269538\n> | region_leave | ... | label:clear_skip_worktree_from_present_files_full\n>\n> Here, we see the sparse loop terminating early with its first sparse\n> path being a sparse directory containing a file. Then, that loop's\n> region terminates before ensure_full_index begins (in this case, the\n> cache-tree must also be computed). Then, _after_ the index is expanded,\n> the full loop begins with its own region.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> sparse-index.c | 77 ++++++++++++++++++++++++++++++++++----------------\n> 1 file changed, 53 insertions(+), 24 deletions(-)\n>\n> diff --git a/sparse-index.c b/sparse-index.c\n> index e48e40cae71..e0457c87fff 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -486,49 +486,78 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n> return 0;\n> }\n>\n> -void clear_skip_worktree_from_present_files(struct index_state *istate)\n> +static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n> {\n> const char *last_dirname = NULL;\n> size_t dir_len = 0;\n> int dir_found = 1;\n>\n> - int i;\n> - int path_count[2] = {0, 0};\n> - int restarted = 0;\n> + int path_count = 0;\n> + int to_restart = 0;\n>\n> - if (!core_apply_sparse_checkout ||\n> - sparse_expect_files_outside_of_patterns)\n> - return;\n> -\n> - trace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files\",\n> + trace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n> istate->repo);\n> -restart:\n> - for (i = 0; i < istate->cache_nr; i++) {\n> + for (int i = 0; i < istate->cache_nr; i++) {\n> struct cache_entry *ce = istate->cache[i];\n>\n> if (ce_skip_worktree(ce)) {\n> - path_count[restarted]++;\n> + path_count++;\n> if (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n> if (S_ISSPARSEDIR(ce->ce_mode)) {\n> - if (restarted)\n> - BUG(\"ensure-full-index did not fully flatten?\");\n> - ensure_full_index(istate);\n> - restarted = 1;\n> - goto restart;\n> + to_restart = 1;\n> + break;\n> }\n> ce->ce_flags &= ~CE_SKIP_WORKTREE;\n> }\n> }\n> }\n>\n> - if (path_count[0])\n> - trace2_data_intmax(\"index\", istate->repo,\n> - \"sparse_path_count\", path_count[0]);\n> - if (restarted)\n> - trace2_data_intmax(\"index\", istate->repo,\n> - \"sparse_path_count_full\", path_count[1]);\n> - trace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files\",\n> + trace2_data_intmax(\"index\", istate->repo,\n> + \"sparse_path_count\", path_count);\n> + trace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n> + istate->repo);\n> + return to_restart;\n> +}\n> +\n> +static void clear_skip_worktree_from_present_files_full(struct index_state *istate)\n> +{\n> + const char *last_dirname = NULL;\n> + size_t dir_len = 0;\n> + int dir_found = 1;\n> +\n> + int path_count = 0;\n> +\n> + trace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_full\",\n> istate->repo);\n> + for (int i = 0; i < istate->cache_nr; i++) {\n> + struct cache_entry *ce = istate->cache[i];\n> +\n> + if (S_ISSPARSEDIR(ce->ce_mode))\n> + BUG(\"ensure-full-index did not fully flatten?\");\n> +\n> + if (ce_skip_worktree(ce)) {\n> + path_count++;\n> + if (path_found(ce->name, &last_dirname, &dir_len, &dir_found))\n> + ce->ce_flags &= ~CE_SKIP_WORKTREE;\n> + }\n> + }\n> +\n> + trace2_data_intmax(\"index\", istate->repo,\n> + \"full_path_count\", path_count);\n> + trace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n> + istate->repo);\n> +}\n> +\n> +void clear_skip_worktree_from_present_files(struct index_state *istate)\n> +{\n> + if (!core_apply_sparse_checkout ||\n> + sparse_expect_files_outside_of_patterns)\n> + return;\n> +\n> + if (clear_skip_worktree_from_present_files_sparse(istate)) {\n> + ensure_full_index(istate);\n> + clear_skip_worktree_from_present_files_full(istate);\n> + }\n> }\n>\n> /*\n> --\n> gitgitgadget\n\nAlthough I had a few wording quibbles with the commit message, overall\nthe commit message was clear about what you were trying to achieve.\nAlso, the change in this patch is a straightforward splitting of the\nold function into three new functions (one of which is the overall\ndriver calling the other two).\n"},{"id":"497591","messageId":"CABPp-BHnUpPgg_wP67q2eSB_j01urbEaPV2Dqk1L+gUfqbZtpA@mail.gmail.com","threadId":"61657","inReplyTo":"7c3b545ee5ea3a0e6686594afe582fa1a19929f6.1718899877.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/5] sparse-index: refactor path_found()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-24T22:13:13Z","receivedAt":"2024-06-24T22:13:25Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 20, 2024 at 10:11 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> In advance of changing the behavior of path_found(), take all of the\n> intermediate data values and group them into a single struct. This\n> simplifies the method prototype as well as the initialization. Future\n> changes can be made directly to the struct and method without changing\n> the callers with this approach.\n>\n> Note that the clear_path_found_data() method is currently empty, as\n> there is nothing to free. However, this will change in the future, so\n> place the method and its callers for now.\n\nI can't parse the second half of the final sentence. What was meant here?\n\n> Signed-off-by: Derrick Stolee \n> ---\n> sparse-index.c | 45 +++++++++++++++++++++++++++++----------------\n> 1 file changed, 29 insertions(+), 16 deletions(-)\n>\n> diff --git a/sparse-index.c b/sparse-index.c\n> index e0457c87fff..de6e727f5c1 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -439,8 +439,22 @@ void ensure_correct_sparsity(struct index_state *istate)\n> ensure_full_index(istate);\n> }\n>\n> -static int path_found(const char *path, const char **dirname, size_t *dir_len,\n> - int *dir_found)\n> +struct path_found_data {\n> + const char *dirname;\n> + size_t dir_len;\n> + int dir_found;\n> +};\n> +\n> +#define PATH_FOUND_DATA_INIT { \\\n> + .dir_found = 1 \\\n> +}\n> +\n> +static void clear_path_found_data(struct path_found_data *data)\n> +{\n> + return;\n> +}\n> +\n> +static int path_found(const char *path, struct path_found_data *data)\n> {\n> struct stat st;\n> char *newdir;\n> @@ -450,7 +464,7 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n> * If dirname corresponds to a directory that doesn't exist, and this\n> * path starts with dirname, then path can't exist.\n> */\n> - if (!*dir_found && !memcmp(path, *dirname, *dir_len))\n> + if (!data->dir_found && !memcmp(path, data->dirname, data->dir_len))\n> return 0;\n>\n> /*\n> @@ -472,15 +486,16 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n> * If path starts with directory (which we already lstat'ed and found),\n> * then no need to lstat parent directory again.\n> */\n> - if (*dir_found && *dirname && memcmp(path, *dirname, *dir_len))\n> + if (data->dir_found && data->dirname &&\n> + memcmp(path, data->dirname, data->dir_len))\n> return 0;\n>\n> /* Free previous dirname, and cache path's dirname */\n> - *dirname = path;\n> - *dir_len = newdir - path + 1;\n> + data->dirname = path;\n> + data->dir_len = newdir - path + 1;\n>\n> - tmp = xstrndup(path, *dir_len);\n> - *dir_found = !lstat(tmp, &st);\n> + tmp = xstrndup(path, data->dir_len);\n> + data->dir_found = !lstat(tmp, &st);\n> free(tmp);\n>\n> return 0;\n> @@ -488,9 +503,7 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n>\n> static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n> {\n> - const char *last_dirname = NULL;\n> - size_t dir_len = 0;\n> - int dir_found = 1;\n> + struct path_found_data data = PATH_FOUND_DATA_INIT;\n>\n> int path_count = 0;\n> int to_restart = 0;\n> @@ -502,7 +515,7 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n>\n> if (ce_skip_worktree(ce)) {\n> path_count++;\n> - if (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n> + if (path_found(ce->name, &data)) {\n> if (S_ISSPARSEDIR(ce->ce_mode)) {\n> to_restart = 1;\n> break;\n> @@ -516,14 +529,13 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n> \"sparse_path_count\", path_count);\n> trace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n> istate->repo);\n> + clear_path_found_data(&data);\n> return to_restart;\n> }\n>\n> static void clear_skip_worktree_from_present_files_full(struct index_state *istate)\n> {\n> - const char *last_dirname = NULL;\n> - size_t dir_len = 0;\n> - int dir_found = 1;\n> + struct path_found_data data = PATH_FOUND_DATA_INIT;\n>\n> int path_count = 0;\n>\n> @@ -537,7 +549,7 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n>\n> if (ce_skip_worktree(ce)) {\n> path_count++;\n> - if (path_found(ce->name, &last_dirname, &dir_len, &dir_found))\n> + if (path_found(ce->name, &data))\n> ce->ce_flags &= ~CE_SKIP_WORKTREE;\n> }\n> }\n> @@ -546,6 +558,7 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n> \"full_path_count\", path_count);\n> trace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n> istate->repo);\n> + clear_path_found_data(&data);\n> }\n>\n> void clear_skip_worktree_from_present_files(struct index_state *istate)\n> --\n> gitgitgadget\n\nIt's surprising how much a simple, straightforward translation of the\ncode can improve its readability; I should have done it this way all\nalong.\n"},{"id":"497592","messageId":"CABPp-BE4f6_zQmFiH6sxonyVt2nMOjZN4gHrP8_rNv95GpLPpw@mail.gmail.com","threadId":"61657","inReplyTo":"217594ffb103969c1a6debc07a6c7f72f6ee4749.1718899877.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/5] sparse-index: use strbuf in path_found()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-24T22:13:28Z","receivedAt":"2024-06-24T22:13:39Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 20, 2024 at 10:11 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> The path_found() method previously reused strings from the cache entries\n> the calling methods were using. This prevents string manipulation in\n> place and causes some odd reallocation before the final lstat() call in\n> the method.\n>\n> Refactor the method to use strbufs and copy the path into the strbuf,\n> but also only the parent directory and not the whole path. This looks\n> like extra copying when assigning the path to the strbuf, but we save an\n> allocation by dropping the 'tmp' string, and we are \"reusing\" the copy\n> from 'tmp' to put the data in the strbuf.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> sparse-index.c | 21 +++++++++------------\n> 1 file changed, 9 insertions(+), 12 deletions(-)\n>\n> diff --git a/sparse-index.c b/sparse-index.c\n> index de6e727f5c1..fec4f393360 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -440,31 +440,30 @@ void ensure_correct_sparsity(struct index_state *istate)\n> }\n>\n> struct path_found_data {\n> - const char *dirname;\n> - size_t dir_len;\n> + struct strbuf dir;\n> int dir_found;\n> };\n>\n> #define PATH_FOUND_DATA_INIT { \\\n> + .dir = STRBUF_INIT, \\\n> .dir_found = 1 \\\n> }\n>\n> static void clear_path_found_data(struct path_found_data *data)\n> {\n> - return;\n> + strbuf_release(&data->dir);\n> }\n>\n> static int path_found(const char *path, struct path_found_data *data)\n> {\n> struct stat st;\n> char *newdir;\n> - char *tmp;\n>\n> /*\n> * If dirname corresponds to a directory that doesn't exist, and this\n> * path starts with dirname, then path can't exist.\n> */\n> - if (!data->dir_found && !memcmp(path, data->dirname, data->dir_len))\n> + if (!data->dir_found && !memcmp(path, data->dir.buf, data->dir.len))\n> return 0;\n>\n> /*\n> @@ -486,17 +485,15 @@ static int path_found(const char *path, struct path_found_data *data)\n> * If path starts with directory (which we already lstat'ed and found),\n> * then no need to lstat parent directory again.\n> */\n> - if (data->dir_found && data->dirname &&\n> - memcmp(path, data->dirname, data->dir_len))\n> + if (data->dir_found && data->dir.buf &&\n> + memcmp(path, data->dir.buf, data->dir.len))\n> return 0;\n>\n> /* Free previous dirname, and cache path's dirname */\n> - data->dirname = path;\n> - data->dir_len = newdir - path + 1;\n> + strbuf_reset(&data->dir);\n> + strbuf_add(&data->dir, path, newdir - path + 1);\n>\n> - tmp = xstrndup(path, data->dir_len);\n> - data->dir_found = !lstat(tmp, &st);\n> - free(tmp);\n> + data->dir_found = !lstat(data->dir.buf, &st);\n>\n> return 0;\n> }\n> --\n> gitgitgadget\n\nAnother simple translation; the series looks good so far...\n"},{"id":"497593","messageId":"CABPp-BH6apqur+zzE12yqL1ZHNP30_2MFgEEeGxYa2K3f7hNRw@mail.gmail.com","threadId":"61657","inReplyTo":"88a3145e585169fde8cd7d43a435daa07eb82667.1718899877.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 4/5] sparse-index: count lstat() calls","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-24T22:13:40Z","receivedAt":"2024-06-24T22:13:51Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 20, 2024 at 10:12 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> The clear_skip_worktree.. methods already report some statistics about\n> how many cache entries are checked against path_found() due to having\n> the skip-worktree bit set. However, due to path_found() performing some\n> caching, this isn't the only information that would be helpful to\n> report.\n>\n> Add a new lstat_count member to the path_found_data struct to count the\n> number of times path_found() calls lstat(). This will be helpful to help\n> explain performance problems in this method as well as to demonstrate\n> future changes to the caching algorithm in a more concrete way than\n> end-to-end timings.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> sparse-index.c | 7 +++++++\n> 1 file changed, 7 insertions(+)\n>\n> diff --git a/sparse-index.c b/sparse-index.c\n> index fec4f393360..8577fa726b8 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -442,6 +442,7 @@ void ensure_correct_sparsity(struct index_state *istate)\n> struct path_found_data {\n> struct strbuf dir;\n> int dir_found;\n> + size_t lstat_count;\n> };\n>\n> #define PATH_FOUND_DATA_INIT { \\\n> @@ -469,6 +470,7 @@ static int path_found(const char *path, struct path_found_data *data)\n> /*\n> * If path itself exists, return 1.\n> */\n> + data->lstat_count++;\n> if (!lstat(path, &st))\n> return 1;\n>\n> @@ -493,6 +495,7 @@ static int path_found(const char *path, struct path_found_data *data)\n> strbuf_reset(&data->dir);\n> strbuf_add(&data->dir, path, newdir - path + 1);\n>\n> + data->lstat_count++;\n> data->dir_found = !lstat(data->dir.buf, &st);\n>\n> return 0;\n> @@ -524,6 +527,8 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n>\n> trace2_data_intmax(\"index\", istate->repo,\n> \"sparse_path_count\", path_count);\n> + trace2_data_intmax(\"index\", istate->repo,\n> + \"sparse_lstat_count\", data.lstat_count);\n> trace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n> istate->repo);\n> clear_path_found_data(&data);\n> @@ -553,6 +558,8 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n>\n> trace2_data_intmax(\"index\", istate->repo,\n> \"full_path_count\", path_count);\n> + trace2_data_intmax(\"index\", istate->repo,\n> + \"full_lstat_count\", data.lstat_count);\n> trace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n> istate->repo);\n> clear_path_found_data(&data);\n> --\n> gitgitgadget\n\nMakes sense. I'm getting really curious to see how this all fits into\nthe big improvements you made; I guess I'll see that in the next\npatch...\n"},{"id":"497594","messageId":"CABPp-BFgg8DOy-SUUsXLyfsWr0DOUUc1vQKnPpihy-h+NAj_zg@mail.gmail.com","threadId":"61657","inReplyTo":"2654fcb7142a606c5684c762ed28bb5e8d9b4712.1718899877.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-24T22:14:40Z","receivedAt":"2024-06-24T22:14:52Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 20, 2024 at 10:11 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> The clear_skip_worktree_from_present_files() method was first introduced\n> in af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files\n> present in worktree, 2022-01-14) to allow better interaction with the\n> working directory in the presence of paths outside of the\n> sparse-checkout cone.\n\ns/cone//\n\n> The initial implementation would lstat() every\n> single sparse tree to see if it existed, and if one did, then the sparse\n> index would expand and every sparse file would be checked.\n\nThis sounds like the algorithm only lstat()ed the sparse directories,\nwhich feels misleading. Perhaps\n\nThe initial implementation would lstat() every SKIP_WORKTREE path to\nsee if it existed; if it ran across a sparse directory that existed\n(when a sparse-index was in use), then it would expand the index and\nthen check every SKIP_WORKTREE path.\n\n> Since these lstat() calls were very expensive, this was improved in\n> d79d299352 (Accelerate clear_skip_worktree_from_present_files() by\n> caching, 2022-01-14) by caching directories that do not exist. However,\n> there are some inefficiencies in that caching mechanism.\n\nMaybe this is obvious, but I thought a few extra words to end the\nsecond-to-last sentence would be helpful, such as \"so it could avoid\nlstat()ing any files under such directories\".\n\n> The caching mechanism stored only the parent directory as not existing,\n> even if a higher parent directory also does not exist. This means that\n> wasted lstat() calls would occur when the sparse files change immediate\n> parent directories but within the same root directory that does not\n> exist.\n\nThis is the crucial insight that makes this patch improve things so much.\n\n> To set up a scenario that triggers this code in an interesting way, we\n> need a sparse-checkout in cone mode and a sparse index. To trigger the\n\nI think you state this too strongly. While trying to duplicate, I\nfirst went with a cone mode & sparse index at first, but out of\ncuriosity tried it without either of these modes set and still saw\ndramatic improvement from your patch. What is needed is that the\nsparsity is such that entire directories are missing, and not just one\nlevel above the files of interest. That is more likely to occur when\ncone mode and perhaps sparse index are in use, but perhaps consider\nchanging \"we need\" to \"it is easiest to consider\"\n\n> full index expansion and a call to the\n> clear_skip_worktree_from_present_files_full() method, we need one of the\n> sparse trees to actually exist on disk. The performance test script\n> p2000-sparse-operations.sh takes the sample repository and copies its\n> HEAD to several copies nested in directories of the form f/f/f\n> where i, j, and k are numbers from 1 to 4. The sparse-checkout cone is\n> then selected as \"f2/f4/\". Creating \"f1/f1/\" will trigger the behavior\n> and also lead to some interesting cases for the caching algorithm since\n> \"f1/f1/\" exists but \"f1/f2/\" and \"f3/\" do not.\n\nFor some reason I had difficulty triggering a case using this guide.\nI might have made an error, but I decided I wanted a deeper directory\ntree to test with anyway. After some playing around to come up with\nan interesting testcase, I eventually came up with the following steps\nto reproduce in case anyone else wants to try:\n\n git clone https://github.com/newren/gvfs-like-git-bomb\n cd gvfs-like-git-bomb\n ./runme.sh\n git sparse-checkout set bomb/b/c # incidentally cone mode\n mkdir -p bomb/d/e/f/a/a\n git ls-files -t | colrm 2 | sort | uniq -c # optional, but interesting\n GIT_TRACE2_PERF=$(pwd)/trace git ls-files -t >/dev/null\n grep lstat_count trace\n\nFurther, you can recompile the git version in use in another window,\nthen come back to this one and run 'rm trace' followed by the last two\ncommands to retest.\n\nThe commands above create a 'gvfs-like-git-bomb' git directory that\nhas 1,000,001 files in HEAD.\n\nWith this test directory, before applying this patch, I see:\n ..sparse_lstat_count:722011\nAfter applying this patch I see\n ..sparse_lstat_count:135\nand with a slight tweak to your patch I see\n ..sparse_lstat_count:125\nI'll comment on the slight tweak at the end of the patch.\n\n> This is difficult to notice when running performance tests using the Git\n> repository (or a blow-up of the Git repository, as in\n> p2000-sparse-operations.sh) because Git has a very shallow directory\n> structure.\n>\n> This change reorganizes the caching algorithm to focus on storing both\n> the deepest _existing_ directory and the next-level non-existing\n> directory.\n\nThis was slightly hard to parse for me, and misled me into thinking\nyou were tracking two directories. Maybe:\n\nThis change reorganizes the caching algorithm to focus on storing the\nhighest level leading directory that does not exist (i.e. we are\nrestricting to the leading directory whose parent directory does\nexist).\n\n> By doing a little extra work on the first sparse file, we can\n> short-circuit all of the sparse files that exist in that non-existing\n> directory.\n\nHere you use \"exist\" as \"tracked by git\" in one case, and \"appears in\nthe working tree\" in another. That's a problem, because the files in\nquestion are tracked by git but do not appear in the working tree,\nmaking it impossible for people to understand unless they guess the\ncorrect definition for each use. I think we want \"exist\" to just mean\n\"appears in the working tree\" here, so we'd need to s/sparse files\nthat exist in/sparse files underneath/ (or something similar) to fix\nthis sentence.\n\nAlso, you've used the phrase \"sparse file(s)\" a number of times in\nthis commit message; I think I know what you mean, but it is not\ndefined in the vocabulary section of\nDocumentation/technical/sparse-checkout.txt. Together with the above\nproblem, it made me question what was meant, re-read all the\ndefinitions, etc. Perhaps \"sparse file(s)\" should be added to that\nvocabulary section, though...especially if we are going to use it and\nsince we never fixed \"sparse directory\" despite mentioning that we\nwanted to?\n\n> When in a repository where the first sparse file is likely to\n> have a much deeper path than the first non-existing directory, this can\n> realize significant gains.\n>\n> The details of this algorithm require careful attention, so the new\n> implementation of path_found() has detailed comments, including the use\n> of a new max_common_dir_prefix() method that may be of independent\n> interest.\n\nThese comments are well written and very helpful; thanks for including them.\n\n> It's worth noting that this is not universally positive, since we are\n> doing extra lstat() calls to establish the exact path to cache. In the\n> blow-up of the Git repository, we can see that the lstat count\n> _increases_ from 28 to 31. However, these numbers were already\n> artificially low.\n\nYeah, I spent a while thinking about whether there were funny cases\nwhere your algorithm might significantly increase the number of\nlstat() calls for non-sparse-index, non-cone mode cases and came up\nkind of empty handed. It seems you only ever add a modest number of\nlstat() calls, and in common scenarios (entire non-leaf directories\nmissing) you remove a dramatic number of lstat() calls.\n\n> Using an internal monorepo with over two million paths at HEAD and a\n> typical sparse-checkout cone such that the index contains ~190,000\n> entries (including over two thousand sparse trees), I was able to\n> measure these lstat counts when one sparse directory actually exists on\n> disk:\n>\n> Sparse files in expanded index: 1,841,997\n> full_lstat_count (before): 173,259\n> full_lstat_count (after): 6,521\n>\n> This resulted in this absolute time change, on a warm disk:\n>\n> Time in full loop (before): 2.527 s\n> Time in full loop (after): 0.071 s\n\nVery nice. :-)\n\n> (These times were calculated on a Windows machine, where lstat() is\n> slower than a similar Linux machine.)\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> sparse-index.c | 118 ++++++++++++++++++++++++++++++++++++++-----------\n> 1 file changed, 93 insertions(+), 25 deletions(-)\n>\n> diff --git a/sparse-index.c b/sparse-index.c\n> index 8577fa726b8..cccd8550dfe 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -440,14 +440,21 @@ void ensure_correct_sparsity(struct index_state *istate)\n> }\n>\n> struct path_found_data {\n> + /**\n> + * The path stored in 'dir', if non-empty, corresponds to the most-\n> + * recent path that we checked where:\n> + *\n> + * 1. The path should be a directory, according to the index.\n> + * 2. The path does not exist.\n> + * 3. The parent path _does_ exist. (This may be the root of the\n> + * working directory.)\n> + */\n> struct strbuf dir;\n> - int dir_found;\n> size_t lstat_count;\n> };\n>\n> #define PATH_FOUND_DATA_INIT { \\\n> - .dir = STRBUF_INIT, \\\n> - .dir_found = 1 \\\n> + .dir = STRBUF_INIT \\\n> }\n>\n> static void clear_path_found_data(struct path_found_data *data)\n> @@ -455,50 +462,111 @@ static void clear_path_found_data(struct path_found_data *data)\n> strbuf_release(&data->dir);\n> }\n>\n> +/**\n> + * Return the length of the largest common substring that ends in a\n> + * slash ('/') to indicate the largest common parent directory. Returns\n> + * zero if no common directory exists.\n> + */\n> +static size_t max_common_dir_prefix(const char *path1, const char *path2)\n> +{\n> + size_t common_prefix = 0;\n> + for (size_t i = 0; path1[i] && path2[i]; i++) {\n> + if (path1[i] != path2[i])\n> + break;\n> +\n> + /*\n> + * If they agree at a directory separator, then add one\n> + * to make sure it is included in the common prefix string.\n> + */\n> + if (path1[i] == '/')\n> + common_prefix = i + 1;\n> + }\n> +\n> + return common_prefix;\n> +}\n> +\n> static int path_found(const char *path, struct path_found_data *data)\n> {\n> struct stat st;\n> - char *newdir;\n> + size_t common_prefix;\n>\n> /*\n> - * If dirname corresponds to a directory that doesn't exist, and this\n> - * path starts with dirname, then path can't exist.\n> + * If data->dir is non-empty, then it contains a path that doesn't\n> + * exist, including an ending slash ('/'). If it is a prefix of 'path',\n> + * then we can return 0.\n> */\n> - if (!data->dir_found && !memcmp(path, data->dir.buf, data->dir.len))\n> + if (data->dir.len && !memcmp(path, data->dir.buf, data->dir.len))\n> return 0;\n>\n> /*\n> - * If path itself exists, return 1.\n> + * Otherwise, we must check if the current path exists. If it does, then\n> + * return 1. The cached directory will be skipped until we come across\n> + * a missing path again.\n> */\n> data->lstat_count++;\n> if (!lstat(path, &st))\n> return 1;\n>\n> /*\n> - * Otherwise, path does not exist so we'll return 0...but we'll first\n> - * determine some info about its parent directory so we can avoid\n> - * lstat calls for future cache entries.\n> + * At this point, we know that 'path' doesn't exist, and we know that\n> + * the parent directory of 'data->dir' does exist. Let's set 'data->dir'\n> + * to be the top-most non-existing directory of 'path'. If the first\n> + * parent of 'path' exists, then we will act ast though 'path'\n\ns/ast/as/\n\n> + * corresponds to a directory (by adding a slash).\n> */\n> - newdir = strrchr(path, '/');\n> - if (!newdir)\n> - return 0; /* Didn't find a parent dir; just return 0 now. */\n> + common_prefix = max_common_dir_prefix(path, data->dir.buf);\n>\n> /*\n> - * If path starts with directory (which we already lstat'ed and found),\n> - * then no need to lstat parent directory again.\n> + * At this point, 'path' and 'data->dir' have a common existing parent\n> + * directory given by path[0..common_prefix] (which could have length 0).\n> + * We \"grow\" the data->dir buffer by checking for existing directories\n> + * along 'path'.\n> */\n> - if (data->dir_found && data->dir.buf &&\n> - memcmp(path, data->dir.buf, data->dir.len))\n> - return 0;\n>\n> - /* Free previous dirname, and cache path's dirname */\n> - strbuf_reset(&data->dir);\n> - strbuf_add(&data->dir, path, newdir - path + 1);\n> + strbuf_setlen(&data->dir, common_prefix);\n> + while (1) {\n> + /* Find the next directory in 'path'. */\n> + const char *next_slash = strchr(path + data->dir.len, '/');\n>\n> - data->lstat_count++;\n> - data->dir_found = !lstat(data->dir.buf, &st);\n> + /*\n> + * If there are no more slashes, then 'path' doesn't contain a\n> + * non-existent _parent_ directory. Set 'data->dir' to be equal\n> + * to 'path' plus an additional slash, so it can be used for\n> + * caching in the future. The filename of 'path' is considered\n> + * a non-existent directory.\n> + *\n> + * Note: if \"{path}/\" exists as a directory, then it will never\n> + * appear as a prefix of other callers to this method, assuming\n> + * the context from the clear_skip_worktree... methods. If this\n> + * method is reused, then this must be reconsidered.\n> + */\n> + if (!next_slash) {\n> + strbuf_addstr(&data->dir, path + data->dir.len);\n> + strbuf_addch(&data->dir, '/');\n> + break;\n> + }\n>\n> - return 0;\n> + /*\n> + * Now that we have a slash, let's grow 'data->dir' to include\n> + * this slash, then test if we should stop.\n> + */\n> + strbuf_add(&data->dir, path + data->dir.len,\n> + (next_slash - path) - data->dir.len + 1);\n\nI had to re-read this multiple times and was confused by it. I\neventually realized it was simple -- you use \"path + data->dir.len\"\n3-4 times in this loop. Could we reduce the cognitive overhead by\nsetting some variable to this value at the beginning within the loop\nand then just use it? It'd simplify this particular call to\n\n strbuf_add(&data->dir, rest, next_slash - rest + 1);\n\nor substitute any other variable name for \"rest\" there. Maybe it\nshouldn't be a big deal, but the rest of the method was complex enough\nthat I just blew my local stack space at this point. I think this\nsimple substitution would have made it easier for me.\n\n> +\n> + /* If the path doesn't exist, then stop here. */\n> + data->lstat_count++;\n> + if (lstat(data->dir.buf, &st))\n> + return 0;\n> + }\n> +\n> + /*\n> + * At this point, 'data->dir' is equal to 'path' plus a slash character,\n> + * and the parent directory of 'path' definitely exists. Let's return\n> + * the case of whether 'path' exists.\n> + */\n\nCan I suggest adding the following to this comment?\n \" path does not exist at this point or we would have already\nreturned 1 above when we lstat()ed it before the above loop. \"\n\n> +\n> + data->lstat_count++;\n> + return !lstat(path, &st);\n\n...and, as long as I didn't missing something with my above comment\nsuggestion, these two lines can be replaced by\n\n return 0;\n\nOr did I miss something here?\n\n\nAnyway, despite the many small comments I made, well done! I think\nthe method is not only much more performant, but more readable than my\noriginal. With a few small tweaks, it should be good to merge.\n"},{"id":"497597","messageId":"xmqqtthhanpy.fsf@gitster.g","threadId":"61657","inReplyTo":"CABPp-BFgg8DOy-SUUsXLyfsWr0DOUUc1vQKnPpihy-h+NAj_zg@mail.gmail.com","subject":"Re: [PATCH 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-06-25T00:08:09Z","receivedAt":"2024-06-25T00:08:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> ... It'd simplify this particular call to\n>\n> strbuf_add(&data->dir, rest, next_slash - rest + 1);\n>\n> or substitute any other variable name for \"rest\" there. Maybe it\n> shouldn't be a big deal, but ...\n\nGood observation. Naming is hard, but it often happens that a\ntemporary variable that is given an appropriate name improves the\nreadability of the code a lot.\n\n> Anyway, despite the many small comments I made, well done! I think\n> the method is not only much more performant, but more readable than my\n> original. With a few small tweaks, it should be good to merge.\n\nYup, and your review was a delight to read.\n\nThanks, both.\n\n\n\n"},{"id":"497688","messageId":"a4edb8fb-5ed4-401f-819f-4034f67cd27e@gmail.com","threadId":"61657","inReplyTo":"CABPp-BF=8y2yC0WvF7BhNFiyW10A_yKs5s6euEi3FwYSsmHnWg@mail.gmail.com","subject":"Re: [PATCH 1/5] sparse-index: refactor skip worktree retry logic","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-06-26T12:42:11Z","receivedAt":"2024-06-26T12:42:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/24/24 6:12 PM, Elijah Newren wrote:\n> On Thu, Jun 20, 2024 at 10:11 AM Derrick Stolee via GitGitGadget\n> wrote:\n>>\n>> From: Derrick Stolee \n>>\n>> The clear_skip_worktree_from_present_files() method was introduced in\n>> af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files present\n>> in worktree, 2022-01-14) to help cases where the sparse index is enabled\n> \n> s/index/checkout/; the code in af6a51875a made no assumptions about\n> sparse index being enabled.\n> \n>> but some paths outside of the sparse-checkout cone also exist on disk.\n> \n> s/cone//; it wasn't specific to cone mode.\n\nThanks for the context that this is a generic sparse-checkout feature,\nand is not limited to the sparse index (which is limited to cone mode).\nI made assumptions based on the code's location in sparse-index.c.\n\n> Although I had a few wording quibbles with the commit message, overall\n> the commit message was clear about what you were trying to achieve.\n> Also, the change in this patch is a straightforward splitting of the\n> old function into three new functions (one of which is the overall\n> driver calling the other two).\n\nI have reworded locally and will have a v2 later today with a better\nmessage. Thanks for your attention to detail.\n\nThanks,\n-Stolee\n"},{"id":"497689","messageId":"21977dab-31b9-405b-975b-6d022b080591@gmail.com","threadId":"61657","inReplyTo":"CABPp-BHnUpPgg_wP67q2eSB_j01urbEaPV2Dqk1L+gUfqbZtpA@mail.gmail.com","subject":"Re: [PATCH 2/5] sparse-index: refactor path_found()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-06-26T12:43:48Z","receivedAt":"2024-06-26T12:43:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/24/24 6:13 PM, Elijah Newren wrote:\n> On Thu, Jun 20, 2024 at 10:11 AM Derrick Stolee via GitGitGadget\n> wrote:\n>>\n>> From: Derrick Stolee \n>>\n>> In advance of changing the behavior of path_found(), take all of the\n>> intermediate data values and group them into a single struct. This\n>> simplifies the method prototype as well as the initialization. Future\n>> changes can be made directly to the struct and method without changing\n>> the callers with this approach.\n>>\n>> Note that the clear_path_found_data() method is currently empty, as\n>> there is nothing to free. However, this will change in the future, so\n>> place the method and its callers for now.\n> \n> I can't parse the second half of the final sentence. What was meant here?\n\nI was trying to point out how this method looks a bit silly:\n\n>> +static void clear_path_found_data(struct path_found_data *data)\n>> +{\n>> + return;\n>> +}\n\nIt will be filled in with a meaningful implementation later on, but\nI wanted to establish its callers here. I'll try to find a better\nway to communicate this.\n\nThanks,\n-Stolee\n"},{"id":"497692","messageId":"cfb20e54-eee5-4043-abcb-63c8211635d3@gmail.com","threadId":"61657","inReplyTo":"CABPp-BFgg8DOy-SUUsXLyfsWr0DOUUc1vQKnPpihy-h+NAj_zg@mail.gmail.com","subject":"Re: [PATCH 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-06-26T13:06:51Z","receivedAt":"2024-06-26T13:06:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/24/24 6:14 PM, Elijah Newren wrote:\n> On Thu, Jun 20, 2024 at 10:11 AM Derrick Stolee via GitGitGadget\n> wrote:\n>>\n>> From: Derrick Stolee \n>>\n>> The clear_skip_worktree_from_present_files() method was first introduced\n>> in af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files\n>> present in worktree, 2022-01-14) to allow better interaction with the\n>> working directory in the presence of paths outside of the\n>> sparse-checkout cone.\n> \n> s/cone//\n> \n>> The initial implementation would lstat() every\n>> single sparse tree to see if it existed, and if one did, then the sparse\n>> index would expand and every sparse file would be checked.\n> \n> This sounds like the algorithm only lstat()ed the sparse directories,\n> which feels misleading. Perhaps\n> \n> The initial implementation would lstat() every SKIP_WORKTREE path to\n> see if it existed; if it ran across a sparse directory that existed\n> (when a sparse-index was in use), then it would expand the index and\n> then check every SKIP_WORKTREE path.\n> \n>> Since these lstat() calls were very expensive, this was improved in\n>> d79d299352 (Accelerate clear_skip_worktree_from_present_files() by\n>> caching, 2022-01-14) by caching directories that do not exist. However,\n>> there are some inefficiencies in that caching mechanism.\n> \n> Maybe this is obvious, but I thought a few extra words to end the\n> second-to-last sentence would be helpful, such as \"so it could avoid\n> lstat()ing any files under such directories\".\n\nThanks. I will use both of these suggestions verbatim.\n\n>> To set up a scenario that triggers this code in an interesting way, we\n>> need a sparse-checkout in cone mode and a sparse index. To trigger the\n> \n> I think you state this too strongly. While trying to duplicate, I\n> first went with a cone mode & sparse index at first, but out of\n> curiosity tried it without either of these modes set and still saw\n> dramatic improvement from your patch. What is needed is that the\n> sparsity is such that entire directories are missing, and not just one\n> level above the files of interest. That is more likely to occur when\n> cone mode and perhaps sparse index are in use, but perhaps consider\n> changing \"we need\" to \"it is easiest to consider\"\n\nAbsolutely. This stems from my earlier assumption that the sparse index\nwas required, but it is not. I have reworded locally.\n\n>> full index expansion and a call to the\n>> clear_skip_worktree_from_present_files_full() method, we need one of the\n>> sparse trees to actually exist on disk. The performance test script\n>> p2000-sparse-operations.sh takes the sample repository and copies its\n>> HEAD to several copies nested in directories of the form f/f/f\n>> where i, j, and k are numbers from 1 to 4. The sparse-checkout cone is\n>> then selected as \"f2/f4/\". Creating \"f1/f1/\" will trigger the behavior\n>> and also lead to some interesting cases for the caching algorithm since\n>> \"f1/f1/\" exists but \"f1/f2/\" and \"f3/\" do not.\n> \n> For some reason I had difficulty triggering a case using this guide.\n> I might have made an error, but I decided I wanted a deeper directory\n> tree to test with anyway. After some playing around to come up with\n> an interesting testcase, I eventually came up with the following steps\n> to reproduce in case anyone else wants to try:\n> \n> git clone https://github.com/newren/gvfs-like-git-bomb\n> cd gvfs-like-git-bomb\n> ./runme.sh\n> git sparse-checkout set bomb/b/c # incidentally cone mode\n> mkdir -p bomb/d/e/f/a/a\n> git ls-files -t | colrm 2 | sort | uniq -c # optional, but interesting\n> GIT_TRACE2_PERF=$(pwd)/trace git ls-files -t >/dev/null\n> grep lstat_count trace\n> \n> Further, you can recompile the git version in use in another window,\n> then come back to this one and run 'rm trace' followed by the last two\n> commands to retest.\n> \n> The commands above create a 'gvfs-like-git-bomb' git directory that\n> has 1,000,001 files in HEAD.\n> \n> With this test directory, before applying this patch, I see:\n> ..sparse_lstat_count:722011\n> After applying this patch I see\n> ..sparse_lstat_count:135\n> and with a slight tweak to your patch I see\n> ..sparse_lstat_count:125\n> I'll comment on the slight tweak at the end of the patch.\n\nThanks for these numbers! Are you willing to keep that example repo\non GitHub so I can refer to it in the message?\n\n>> This is difficult to notice when running performance tests using the Git\n>> repository (or a blow-up of the Git repository, as in\n>> p2000-sparse-operations.sh) because Git has a very shallow directory\n>> structure.\n>>\n>> This change reorganizes the caching algorithm to focus on storing both\n>> the deepest _existing_ directory and the next-level non-existing\n>> directory.\n> \n> This was slightly hard to parse for me, and misled me into thinking\n> you were tracking two directories. Maybe:\n> \n> This change reorganizes the caching algorithm to focus on storing the\n> highest level leading directory that does not exist (i.e. we are\n> restricting to the leading directory whose parent directory does\n> exist).\n\nI have reworded in a slightly different way, but with the same meaning\nas you provide here.\n\n>> By doing a little extra work on the first sparse file, we can\n>> short-circuit all of the sparse files that exist in that non-existing\n>> directory.\n> \n> Here you use \"exist\" as \"tracked by git\" in one case, and \"appears in\n> the working tree\" in another. That's a problem, because the files in\n> question are tracked by git but do not appear in the working tree,\n> making it impossible for people to understand unless they guess the\n> correct definition for each use. I think we want \"exist\" to just mean\n> \"appears in the working tree\" here, so we'd need to s/sparse files\n> that exist in/sparse files underneath/ (or something similar) to fix\n> this sentence.\n> \n> Also, you've used the phrase \"sparse file(s)\" a number of times in\n> this commit message; I think I know what you mean, but it is not\n> defined in the vocabulary section of\n> Documentation/technical/sparse-checkout.txt. Together with the above\n> problem, it made me question what was meant, re-read all the\n> definitions, etc. Perhaps \"sparse file(s)\" should be added to that\n> vocabulary section, though...especially if we are going to use it and\n> since we never fixed \"sparse directory\" despite mentioning that we\n> wanted to?\n\nYou're right. My use of \"sparse file\" or \"sparse directory\" was intended\nto mean \"a path from a cache entry with SKIP_WORKTREE that is either a\nblob or tree\" but that isn't necessary here.\n\nInstead, I'll focus my attention on paths being passed to path_found(),\nwhich removes the context of an index. The danger there is that the\ncaching assumes that we are moving through the paths in an order such\nas in the index, but that's a natural type of ordering for paths.\n\n>> /*\n>> - * Otherwise, path does not exist so we'll return 0...but we'll first\n>> - * determine some info about its parent directory so we can avoid\n>> - * lstat calls for future cache entries.\n>> + * At this point, we know that 'path' doesn't exist, and we know that\n>> + * the parent directory of 'data->dir' does exist. Let's set 'data->dir'\n>> + * to be the top-most non-existing directory of 'path'. If the first\n>> + * parent of 'path' exists, then we will act ast though 'path'\n> \n> s/ast/as/\n\nOops! Thanks.\n\n>> + /*\n>> + * Now that we have a slash, let's grow 'data->dir' to include\n>> + * this slash, then test if we should stop.\n>> + */\n>> + strbuf_add(&data->dir, path + data->dir.len,\n>> + (next_slash - path) - data->dir.len + 1);\n> \n> I had to re-read this multiple times and was confused by it. I\n> eventually realized it was simple -- you use \"path + data->dir.len\"\n> 3-4 times in this loop. Could we reduce the cognitive overhead by\n> setting some variable to this value at the beginning within the loop\n> and then just use it? It'd simplify this particular call to\n> \n> strbuf_add(&data->dir, rest, next_slash - rest + 1);\n> \n> or substitute any other variable name for \"rest\" there. Maybe it\n> shouldn't be a big deal, but the rest of the method was complex enough\n> that I just blew my local stack space at this point. I think this\n> simple substitution would have made it easier for me.\n\nExcellent. Thanks for recognizing this pattern and recommending a\nsimplification.\n\n>> + /*\n>> + * At this point, 'data->dir' is equal to 'path' plus a slash character,\n>> + * and the parent directory of 'path' definitely exists. Let's return\n>> + * the case of whether 'path' exists.\n>> + */\n> \n> Can I suggest adding the following to this comment?\n> \" path does not exist at this point or we would have already\n> returned 1 above when we lstat()ed it before the above loop. \"\n> \n>> +\n>> + data->lstat_count++;\n>> + return !lstat(path, &st);\n> \n> ...and, as long as I didn't missing something with my above comment\n> suggestion, these two lines can be replaced by\n> \n> return 0;\n> \n> Or did I miss something here?\n\nNo, you understood correctly. Thanks for the further simplification and\nspeed improvement.\n\n> Anyway, despite the many small comments I made, well done! I think\n> the method is not only much more performant, but more readable than my\n> original. With a few small tweaks, it should be good to merge.\n\nThanks for your detailed review. I'll put these updates into a v2 and\nsend it later today. I need to retest in my monorepo example and add\nyour publicly-available example before v2 will be ready.\n\nThanks,\n-Stolee\n\n"},{"id":"497697","messageId":"pull.1754.v2.git.1719412192.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.git.1718899877.gitgitgadget@gmail.com","subject":"[PATCH v2 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-26T14:29:46Z","receivedAt":"2024-06-26T14:29:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"While doing some investigation in a private monorepo with sparse-checkout\nand a sparse index, I accidentally left a modified file outside of my\nsparse-checkout cone. This caused my Git commands to slow to a crawl, so I\nreran with GIT_TRACE2_PERF=1.\n\nWhile I was able to identify clear_skip_worktree_from_present_files() as the\nculprit, it took longer than desired to figure out what was going on. This\nseries intends to both fix the performance issue (as much as possible) and\ndo some refactoring to make it easier to understand what is happening.\n\nIn the end, I was able to reduce the number of lstat() calls in my case from\nover 1.1 million to about 4,400, improving the time from 13.4s to 81ms on a\nwarm disk cache. (These numbers are from a test after v2, which somehow hit\nthe old caching algorithm even worse than my test in v1.)\n\n\nUpdates in v2\n=============\n\nThanks to Elijah for a thorough review, leading to valuable improvements.\n\n * I was mistaken that the sparse index was required for this logic to\n happen. This has changed several descriptions across the commit messages.\n * The final lstat() in path_found() was not needed, so is removed in v2.\n This saves even more time and lstat() calls, updating the stats.\n * Elijah created a particularly nasty example for testing, which I include\n in my final patch. He gets a \"Helped-by\" credit for this.\n * Several comments, variables, and other improvements based on Elijah's\n recommendations.\n\nThanks, Stolee\n\nDerrick Stolee (5):\n sparse-checkout: refactor skip worktree retry logic\n sparse-index: refactor path_found()\n sparse-index: use strbuf in path_found()\n sparse-index: count lstat() calls\n sparse-index: improve lstat caching of sparse paths\n\n sparse-index.c | 216 +++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 164 insertions(+), 52 deletions(-)\n\n\nbase-commit: 66ac6e4bcd111be3fa9c2a6b3fafea718d00678d\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1754%2Fderrickstolee%2Fclear-skip-speed-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1754/derrickstolee/clear-skip-speed-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1754\n\nRange-diff vs v1:\n\n 1: ddd8a9a90ce ! 1: 93d0baed0b0 sparse-index: refactor skip worktree retry logic\n @@ Metadata\n Author: Derrick Stolee \n \n ## Commit message ##\n - sparse-index: refactor skip worktree retry logic\n + sparse-checkout: refactor skip worktree retry logic\n \n The clear_skip_worktree_from_present_files() method was introduced in\n af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files present\n - in worktree, 2022-01-14) to help cases where the sparse index is enabled\n - but some paths outside of the sparse-checkout cone also exist on disk.\n - This operation can be slow as it needs to check path existence in a way\n - that is not stored in the collapsed index, so caching was introduced in\n - d79d299352 (Accelerate clear_skip_worktree_from_present_files() by\n - caching, 2022-01-14).\n + in worktree, 2022-01-14) to help cases where sparse-checkout is enabled\n + but some paths outside of the sparse-checkout also exist on disk. This\n + operation can be slow as it needs to check path existence in a way not\n + stored in the index, so caching was introduced in d79d299352 (Accelerate\n + clear_skip_worktree_from_present_files() by caching, 2022-01-14).\n \n If users are having trouble with the performance of this operation and\n - don't care about paths outside of the sparse-checkout cone, they can\n - disable them using the sparse.expectFilesOutsideOfPatterns config option\n + don't care about paths outside of the sparse-checkout, they can disable\n + them using the sparse.expectFilesOutsideOfPatterns config option\n introduced in ecc7c8841d (repo_read_index: add config to expect files\n outside sparse patterns, 2022-02-25).\n \n + This check is particularly confusing in the presence of a sparse index,\n + as a sparse tree entry corresponding to an existing directory must first\n + be expanded to a full index before examining the paths within. This is\n + currently implemented using a 'goto' and a boolean variable to ensure we\n + restart only once.\n +\n Even with that caching, it was noticed that this could take a long time\n to execute. 89aaab11a3 (index: add trace2 region for clear skip\n worktree, 2022-11-03) introduced trace2 regions to measure this time.\n @@ Commit message\n \n One thing that can be confusing about the current setup is that the\n trace2 regions nest and it is not clear that a second loop is running\n - after the index is expanded. Here is an example of what the regions look\n - like in a typical case:\n + after a sparse index is expanded. Here is an example of what the regions\n + look like in a typical case:\n \n | region_enter | ... | label:clear_skip_worktree_from_present_files\n | region_enter | ... | ..label:update\n 2: 7c3b545ee5e ! 2: 69c3beaabf7 sparse-index: refactor path_found()\n @@ Commit message\n the callers with this approach.\n \n Note that the clear_path_found_data() method is currently empty, as\n - there is nothing to free. However, this will change in the future, so\n - place the method and its callers for now.\n + there is nothing to free. This method is a placeholder for future\n + changes that require a non-trivial implementation. Its stub is created\n + now so consumers could call it now and not change in future changes.\n \n Signed-off-by: Derrick Stolee \n \n 3: 217594ffb10 = 3: 0a82e6b4183 sparse-index: use strbuf in path_found()\n 4: 88a3145e585 = 4: 9549f5b8062 sparse-index: count lstat() calls\n 5: 2654fcb7142 ! 5: 0cb344ac14f sparse-index: improve lstat caching of sparse paths\n @@ Commit message\n in af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files\n present in worktree, 2022-01-14) to allow better interaction with the\n working directory in the presence of paths outside of the\n - sparse-checkout cone. The initial implementation would lstat() every\n - single sparse tree to see if it existed, and if one did, then the sparse\n - index would expand and every sparse file would be checked.\n + sparse-checkout. The initial implementation would lstat() every single\n + SKIP_WORKTREE path to see if it existed; if it ran across a sparse\n + directory that existed (when a sparse index was in use), then it would\n + expand the index and then check every SKIP_WORKTREE path.\n \n Since these lstat() calls were very expensive, this was improved in\n d79d299352 (Accelerate clear_skip_worktree_from_present_files() by\n - caching, 2022-01-14) by caching directories that do not exist. However,\n - there are some inefficiencies in that caching mechanism.\n + caching, 2022-01-14) by caching directories that do not exist so it\n + could avoid lstat()ing any files under such directories. However, there\n + are some inefficiencies in that caching mechanism.\n \n The caching mechanism stored only the parent directory as not existing,\n even if a higher parent directory also does not exist. This means that\n - wasted lstat() calls would occur when the sparse files change immediate\n - parent directories but within the same root directory that does not\n - exist.\n + wasted lstat() calls would occur when the paths passed to path_found()\n + change immediate parent directories but within the same parent directory\n + that does not exist.\n +\n + To create an example repository that demonstrates this problem, it helps\n + to have a directory outside of the sparse-checkout that contains many\n + deep paths. In particular, the first paths (in lexicographic order)\n + underneath the sparse directory should have deep directory structures,\n + maximizing the difference between the old caching algorithm that looks\n + to a single parent and the new caching algorithm that looks to the\n + top-most missing directory.\n \n - To set up a scenario that triggers this code in an interesting way, we\n - need a sparse-checkout in cone mode and a sparse index. To trigger the\n - full index expansion and a call to the\n - clear_skip_worktree_from_present_files_full() method, we need one of the\n - sparse trees to actually exist on disk. The performance test script\n - p2000-sparse-operations.sh takes the sample repository and copies its\n - HEAD to several copies nested in directories of the form f/f/f\n - where i, j, and k are numbers from 1 to 4. The sparse-checkout cone is\n - then selected as \"f2/f4/\". Creating \"f1/f1/\" will trigger the behavior\n - and also lead to some interesting cases for the caching algorithm since\n - \"f1/f1/\" exists but \"f1/f2/\" and \"f3/\" do not.\n + The performance test script p2000-sparse-operations.sh takes the sample\n + repository and copies its HEAD to several copies nested in directories\n + of the form f/f/f where i, j, and k are numbers from 1 to 4.\n + The sparse-checkout cone is then selected as \"f2/f4/\". Creating \"f1/f1/\"\n + will trigger the behavior and also lead to some interesting cases for\n + the caching algorithm since \"f1/f1/\" exists but \"f1/f2/\" and \"f3/\" do\n + not.\n \n This is difficult to notice when running performance tests using the Git\n repository (or a blow-up of the Git repository, as in\n p2000-sparse-operations.sh) because Git has a very shallow directory\n structure.\n \n - This change reorganizes the caching algorithm to focus on storing both\n - the deepest _existing_ directory and the next-level non-existing\n - directory. By doing a little extra work on the first sparse file, we can\n - short-circuit all of the sparse files that exist in that non-existing\n - directory. When in a repository where the first sparse file is likely to\n - have a much deeper path than the first non-existing directory, this can\n - realize significant gains.\n + This change reorganizes the caching algorithm to focus on storing the\n + highest level leading directory that does not exist; specifically this\n + means that that directory's parent _does_ exist. By doing a little extra\n + work on a path passed to path_found(), we can short-circuit all of the\n + paths passed to path_found() afterwards that match a prefix with that\n + non-existing directory. When in a repository where the first sparse file\n + is likely to have a much deeper path than the first non-existing\n + directory, this can realize significant gains.\n \n The details of this algorithm require careful attention, so the new\n implementation of path_found() has detailed comments, including the use\n @@ Commit message\n _increases_ from 28 to 31. However, these numbers were already\n artificially low.\n \n + Contributor Elijah Newren created a publicly-available test repository\n + that demonstrates the difference in these caching algorithms in the most\n + extreme way. To test, follow these steps:\n +\n + git clone --sparse https://github.com/newren/gvfs-like-git-bomb\n + cd gvfs-like-git-bomb\n + ./runme.sh # NOTE: check scripts before running!\n +\n + At this point, assuming you do not have index.sparse=true set globally,\n + the index has one million paths with the SKIP_WORKTREE bit and they will\n + all be sent to path_found() in the sparse loop. You can measure this by\n + running 'git status' with GIT_TRACE2_PERF=1:\n +\n + Sparse files in the index: 1,000,000\n + sparse_lstat_count (before): 200,000\n + sparse_lstat_count (after): 2\n +\n + And here are the performance numbers:\n +\n + Benchmark 1: old\n + Time (mean ± σ): 397.5 ms ± 4.1 ms\n + Range (min … max): 391.2 ms … 404.8 ms 10 runs\n +\n + Benchmark 2: new\n + Time (mean ± σ): 252.7 ms ± 3.1 ms\n + Range (min … max): 249.4 ms … 259.5 ms 11 runs\n +\n + Summary\n + 'new' ran\n + 1.57 ± 0.02 times faster than 'old'\n +\n + By modifying this example further, we can demonstrate a more realistic\n + example and include the sparse index expansion. Continue by creating\n + this directory, confusing both caching algorithms somewhat:\n +\n + mkdir -p bomb/d/e/f/a/a\n +\n + Then re-run the 'git status' tests to see these statistics:\n +\n + Sparse files in the index: 1,000,000\n + sparse_lstat_count (before): 724,010\n + sparse_lstat_count (after): 106\n +\n + Benchmark 1: old\n + Time (mean ± σ): 753.0 ms ± 3.5 ms\n + Range (min … max): 749.7 ms … 760.9 ms 10 runs\n +\n + Benchmark 2: new\n + Time (mean ± σ): 201.4 ms ± 3.2 ms\n + Range (min … max): 196.0 ms … 207.9 ms 14 runs\n +\n + Summary\n + 'new' ran\n + 3.74 ± 0.06 times faster than 'old'\n +\n + Note that if this repository had a sparse index enabled, the additional\n + cost of expanding the sparse index affects the total time of these\n + commands by over four seconds, significantly diminishing the benefit of\n + the caching algorithm. Having existing paths outside of the\n + sparse-checkout is a known performance issue for the sparse index and is\n + a known trade-off for the performance benefits given when no such paths\n + exist.\n +\n Using an internal monorepo with over two million paths at HEAD and a\n - typical sparse-checkout cone such that the index contains ~190,000\n - entries (including over two thousand sparse trees), I was able to\n - measure these lstat counts when one sparse directory actually exists on\n - disk:\n + typical sparse-checkout cone such that the sparse index contains\n + ~190,000 entries (including over two thousand sparse trees), I was able\n + to measure these lstat counts when one sparse directory actually exists\n + on disk:\n \n Sparse files in expanded index: 1,841,997\n - full_lstat_count (before): 173,259\n - full_lstat_count (after): 6,521\n + full_lstat_count (before): 1,188,161\n + full_lstat_count (after): 4,404\n \n This resulted in this absolute time change, on a warm disk:\n \n - Time in full loop (before): 2.527 s\n - Time in full loop (after): 0.071 s\n + Time in full loop (before): 13.481 s\n + Time in full loop (after): 0.081 s\n \n (These times were calculated on a Windows machine, where lstat() is\n slower than a similar Linux machine.)\n \n + Helped-by: Elijah Newren \n Signed-off-by: Derrick Stolee \n \n ## sparse-index.c ##\n @@ sparse-index.c: static void clear_path_found_data(struct path_found_data *data)\n +\t * At this point, we know that 'path' doesn't exist, and we know that\n +\t * the parent directory of 'data->dir' does exist. Let's set 'data->dir'\n +\t * to be the top-most non-existing directory of 'path'. If the first\n -+\t * parent of 'path' exists, then we will act ast though 'path'\n ++\t * parent of 'path' exists, then we will act as though 'path'\n +\t * corresponds to a directory (by adding a slash).\n \t */\n -\tnewdir = strrchr(path, '/');\n @@ sparse-index.c: static void clear_path_found_data(struct path_found_data *data)\n +\tstrbuf_setlen(&data->dir, common_prefix);\n +\twhile (1) {\n +\t\t/* Find the next directory in 'path'. */\n -+\t\tconst char *next_slash = strchr(path + data->dir.len, '/');\n ++\t\tconst char *rest = path + data->dir.len;\n ++\t\tconst char *next_slash = strchr(rest, '/');\n \n -\tdata->lstat_count++;\n -\tdata->dir_found = !lstat(data->dir.buf, &st);\n @@ sparse-index.c: static void clear_path_found_data(struct path_found_data *data)\n +\t\t * method is reused, then this must be reconsidered.\n +\t\t */\n +\t\tif (!next_slash) {\n -+\t\t\tstrbuf_addstr(&data->dir, path + data->dir.len);\n ++\t\t\tstrbuf_addstr(&data->dir, rest);\n +\t\t\tstrbuf_addch(&data->dir, '/');\n +\t\t\tbreak;\n +\t\t}\n \n --\treturn 0;\n +\t\t/*\n +\t\t * Now that we have a slash, let's grow 'data->dir' to include\n +\t\t * this slash, then test if we should stop.\n +\t\t */\n -+\t\tstrbuf_add(&data->dir, path + data->dir.len,\n -+\t\t\t (next_slash - path) - data->dir.len + 1);\n ++\t\tstrbuf_add(&data->dir, rest, next_slash - rest + 1);\n +\n -+\t\t/* If the path doesn't exist, then stop here. */\n ++\t\t/* If the parent dir doesn't exist, then stop here. */\n +\t\tdata->lstat_count++;\n +\t\tif (lstat(data->dir.buf, &st))\n +\t\t\treturn 0;\n @@ sparse-index.c: static void clear_path_found_data(struct path_found_data *data)\n +\n +\t/*\n +\t * At this point, 'data->dir' is equal to 'path' plus a slash character,\n -+\t * and the parent directory of 'path' definitely exists. Let's return\n -+\t * the case of whether 'path' exists.\n ++\t * and the parent directory of 'path' definitely exists. Moreover, we\n ++\t * know that 'path' doesn't exist, or we would have returned 1 earlier.\n +\t */\n -+\n -+\tdata->lstat_count++;\n -+\treturn !lstat(path, &st);\n + \treturn 0;\n }\n \n - static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n\n-- \ngitgitgadget\n"},{"id":"497698","messageId":"93d0baed0b0f435e5656cef04cf103b5e2e0f41a.1719412192.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v2.git.1719412192.gitgitgadget@gmail.com","subject":"[PATCH v2 1/5] sparse-checkout: refactor skip worktree retry logic","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-26T14:29:47Z","receivedAt":"2024-06-26T14:29:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree_from_present_files() method was introduced in\naf6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files present\nin worktree, 2022-01-14) to help cases where sparse-checkout is enabled\nbut some paths outside of the sparse-checkout also exist on disk. This\noperation can be slow as it needs to check path existence in a way not\nstored in the index, so caching was introduced in d79d299352 (Accelerate\nclear_skip_worktree_from_present_files() by caching, 2022-01-14).\n\nIf users are having trouble with the performance of this operation and\ndon't care about paths outside of the sparse-checkout, they can disable\nthem using the sparse.expectFilesOutsideOfPatterns config option\nintroduced in ecc7c8841d (repo_read_index: add config to expect files\noutside sparse patterns, 2022-02-25).\n\nThis check is particularly confusing in the presence of a sparse index,\nas a sparse tree entry corresponding to an existing directory must first\nbe expanded to a full index before examining the paths within. This is\ncurrently implemented using a 'goto' and a boolean variable to ensure we\nrestart only once.\n\nEven with that caching, it was noticed that this could take a long time\nto execute. 89aaab11a3 (index: add trace2 region for clear skip\nworktree, 2022-11-03) introduced trace2 regions to measure this time.\nFurther, the way the loop repeats itself was slightly confusing and\nprone to breakage, so a BUG() statement was added in 8c7abdc596 (index:\nraise a bug if the index is materialised more than once, 2022-11-03) to\nbe sure that the second run of the loop does not hit any sparse trees.\n\nOne thing that can be confusing about the current setup is that the\ntrace2 regions nest and it is not clear that a second loop is running\nafter a sparse index is expanded. Here is an example of what the regions\nlook like in a typical case:\n\n| region_enter | ... | label:clear_skip_worktree_from_present_files\n| region_enter | ... | ..label:update\n| region_leave | ... | ..label:update\n| region_enter | ... | ..label:ensure_full_index\n| region_enter | ... | ....label:update\n| region_leave | ... | ....label:update\n| region_leave | ... | ..label:ensure_full_index\n| data | ... | ..sparse_path_count:1\n| data | ... | ..sparse_path_count_full:269538\n| region_leave | ... | label:clear_skip_worktree_from_present_files\n\nOne thing that is particularly difficult to understand about these\nregions is that most of the time is spent between the close of the\nensure_full_index region and the reporting of the end data. This is\nbecause of the restart of the loop being within the same region as the\nfirst iteration of the loop.\n\nThis change refactors the method into two separate methods that are\ntraced separately. This will be more important later when we change\nother features of the methods, but for now the only functional change is\nthe difference in the structure of the trace regions.\n\nAfter this change, the same telemetry section is split into three\ndistinct chunks:\n\n| region_enter | ... | label:clear_skip_worktree_from_present_files_sparse\n| data | ... | ..sparse_path_count:1\n| region_leave | ... | label:clear_skip_worktree_from_present_files_sparse\n| region_enter | ... | label:update\n| region_leave | ... | label:update\n| region_enter | ... | label:ensure_full_index\n| region_enter | ... | ..label:update\n| region_leave | ... | ..label:update\n| region_leave | ... | label:ensure_full_index\n| region_enter | ... | label:clear_skip_worktree_from_present_files_full\n| data | ... | ..full_path_count:269538\n| region_leave | ... | label:clear_skip_worktree_from_present_files_full\n\nHere, we see the sparse loop terminating early with its first sparse\npath being a sparse directory containing a file. Then, that loop's\nregion terminates before ensure_full_index begins (in this case, the\ncache-tree must also be computed). Then, _after_ the index is expanded,\nthe full loop begins with its own region.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 77 ++++++++++++++++++++++++++++++++++----------------\n 1 file changed, 53 insertions(+), 24 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex e48e40cae71..e0457c87fff 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -486,49 +486,78 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \treturn 0;\n }\n \n-void clear_skip_worktree_from_present_files(struct index_state *istate)\n+static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n {\n \tconst char *last_dirname = NULL;\n \tsize_t dir_len = 0;\n \tint dir_found = 1;\n \n-\tint i;\n-\tint path_count[2] = {0, 0};\n-\tint restarted = 0;\n+\tint path_count = 0;\n+\tint to_restart = 0;\n \n-\tif (!core_apply_sparse_checkout ||\n-\t sparse_expect_files_outside_of_patterns)\n-\t\treturn;\n-\n-\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files\",\n+\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n-restart:\n-\tfor (i = 0; i < istate->cache_nr; i++) {\n+\tfor (int i = 0; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i];\n \n \t\tif (ce_skip_worktree(ce)) {\n-\t\t\tpath_count[restarted]++;\n+\t\t\tpath_count++;\n \t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n \t\t\t\tif (S_ISSPARSEDIR(ce->ce_mode)) {\n-\t\t\t\t\tif (restarted)\n-\t\t\t\t\t\tBUG(\"ensure-full-index did not fully flatten?\");\n-\t\t\t\t\tensure_full_index(istate);\n-\t\t\t\t\trestarted = 1;\n-\t\t\t\t\tgoto restart;\n+\t\t\t\t\tto_restart = 1;\n+\t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n \t\t\t}\n \t\t}\n \t}\n \n-\tif (path_count[0])\n-\t\ttrace2_data_intmax(\"index\", istate->repo,\n-\t\t\t\t \"sparse_path_count\", path_count[0]);\n-\tif (restarted)\n-\t\ttrace2_data_intmax(\"index\", istate->repo,\n-\t\t\t\t \"sparse_path_count_full\", path_count[1]);\n-\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files\",\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"sparse_path_count\", path_count);\n+\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n+\t\t\t istate->repo);\n+\treturn to_restart;\n+}\n+\n+static void clear_skip_worktree_from_present_files_full(struct index_state *istate)\n+{\n+\tconst char *last_dirname = NULL;\n+\tsize_t dir_len = 0;\n+\tint dir_found = 1;\n+\n+\tint path_count = 0;\n+\n+\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n+\tfor (int i = 0; i < istate->cache_nr; i++) {\n+\t\tstruct cache_entry *ce = istate->cache[i];\n+\n+\t\tif (S_ISSPARSEDIR(ce->ce_mode))\n+\t\t\tBUG(\"ensure-full-index did not fully flatten?\");\n+\n+\t\tif (ce_skip_worktree(ce)) {\n+\t\t\tpath_count++;\n+\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found))\n+\t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n+\t\t}\n+\t}\n+\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"full_path_count\", path_count);\n+\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n+\t\t\t istate->repo);\n+}\n+\n+void clear_skip_worktree_from_present_files(struct index_state *istate)\n+{\n+\tif (!core_apply_sparse_checkout ||\n+\t sparse_expect_files_outside_of_patterns)\n+\t\treturn;\n+\n+\tif (clear_skip_worktree_from_present_files_sparse(istate)) {\n+\t\tensure_full_index(istate);\n+\t\tclear_skip_worktree_from_present_files_full(istate);\n+\t}\n }\n \n /*\n-- \ngitgitgadget\n\n"},{"id":"497699","messageId":"69c3beaabf7ca8ccf5bbaa248328f77b1be915ba.1719412192.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v2.git.1719412192.gitgitgadget@gmail.com","subject":"[PATCH v2 2/5] sparse-index: refactor path_found()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-26T14:29:48Z","receivedAt":"2024-06-26T14:29:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn advance of changing the behavior of path_found(), take all of the\nintermediate data values and group them into a single struct. This\nsimplifies the method prototype as well as the initialization. Future\nchanges can be made directly to the struct and method without changing\nthe callers with this approach.\n\nNote that the clear_path_found_data() method is currently empty, as\nthere is nothing to free. This method is a placeholder for future\nchanges that require a non-trivial implementation. Its stub is created\nnow so consumers could call it now and not change in future changes.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 45 +++++++++++++++++++++++++++++----------------\n 1 file changed, 29 insertions(+), 16 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex e0457c87fff..de6e727f5c1 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -439,8 +439,22 @@ void ensure_correct_sparsity(struct index_state *istate)\n \t\tensure_full_index(istate);\n }\n \n-static int path_found(const char *path, const char **dirname, size_t *dir_len,\n-\t\t int *dir_found)\n+struct path_found_data {\n+\tconst char *dirname;\n+\tsize_t dir_len;\n+\tint dir_found;\n+};\n+\n+#define PATH_FOUND_DATA_INIT { \\\n+\t.dir_found = 1 \\\n+}\n+\n+static void clear_path_found_data(struct path_found_data *data)\n+{\n+\treturn;\n+}\n+\n+static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n \tchar *newdir;\n@@ -450,7 +464,7 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \t * If dirname corresponds to a directory that doesn't exist, and this\n \t * path starts with dirname, then path can't exist.\n \t */\n-\tif (!*dir_found && !memcmp(path, *dirname, *dir_len))\n+\tif (!data->dir_found && !memcmp(path, data->dirname, data->dir_len))\n \t\treturn 0;\n \n \t/*\n@@ -472,15 +486,16 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \t * If path starts with directory (which we already lstat'ed and found),\n \t * then no need to lstat parent directory again.\n \t */\n-\tif (*dir_found && *dirname && memcmp(path, *dirname, *dir_len))\n+\tif (data->dir_found && data->dirname &&\n+\t memcmp(path, data->dirname, data->dir_len))\n \t\treturn 0;\n \n \t/* Free previous dirname, and cache path's dirname */\n-\t*dirname = path;\n-\t*dir_len = newdir - path + 1;\n+\tdata->dirname = path;\n+\tdata->dir_len = newdir - path + 1;\n \n-\ttmp = xstrndup(path, *dir_len);\n-\t*dir_found = !lstat(tmp, &st);\n+\ttmp = xstrndup(path, data->dir_len);\n+\tdata->dir_found = !lstat(tmp, &st);\n \tfree(tmp);\n \n \treturn 0;\n@@ -488,9 +503,7 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \n static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n {\n-\tconst char *last_dirname = NULL;\n-\tsize_t dir_len = 0;\n-\tint dir_found = 1;\n+\tstruct path_found_data data = PATH_FOUND_DATA_INIT;\n \n \tint path_count = 0;\n \tint to_restart = 0;\n@@ -502,7 +515,7 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \n \t\tif (ce_skip_worktree(ce)) {\n \t\t\tpath_count++;\n-\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n+\t\t\tif (path_found(ce->name, &data)) {\n \t\t\t\tif (S_ISSPARSEDIR(ce->ce_mode)) {\n \t\t\t\t\tto_restart = 1;\n \t\t\t\t\tbreak;\n@@ -516,14 +529,13 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \t\t\t \"sparse_path_count\", path_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n+\tclear_path_found_data(&data);\n \treturn to_restart;\n }\n \n static void clear_skip_worktree_from_present_files_full(struct index_state *istate)\n {\n-\tconst char *last_dirname = NULL;\n-\tsize_t dir_len = 0;\n-\tint dir_found = 1;\n+\tstruct path_found_data data = PATH_FOUND_DATA_INIT;\n \n \tint path_count = 0;\n \n@@ -537,7 +549,7 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \n \t\tif (ce_skip_worktree(ce)) {\n \t\t\tpath_count++;\n-\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found))\n+\t\t\tif (path_found(ce->name, &data))\n \t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n \t\t}\n \t}\n@@ -546,6 +558,7 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \t\t\t \"full_path_count\", path_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n+\tclear_path_found_data(&data);\n }\n \n void clear_skip_worktree_from_present_files(struct index_state *istate)\n-- \ngitgitgadget\n\n"},{"id":"497700","messageId":"0a82e6b4183e007316a8b027086ad3c960901103.1719412192.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v2.git.1719412192.gitgitgadget@gmail.com","subject":"[PATCH v2 3/5] sparse-index: use strbuf in path_found()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-26T14:29:49Z","receivedAt":"2024-06-26T14:29:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe path_found() method previously reused strings from the cache entries\nthe calling methods were using. This prevents string manipulation in\nplace and causes some odd reallocation before the final lstat() call in\nthe method.\n\nRefactor the method to use strbufs and copy the path into the strbuf,\nbut also only the parent directory and not the whole path. This looks\nlike extra copying when assigning the path to the strbuf, but we save an\nallocation by dropping the 'tmp' string, and we are \"reusing\" the copy\nfrom 'tmp' to put the data in the strbuf.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 21 +++++++++------------\n 1 file changed, 9 insertions(+), 12 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex de6e727f5c1..fec4f393360 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -440,31 +440,30 @@ void ensure_correct_sparsity(struct index_state *istate)\n }\n \n struct path_found_data {\n-\tconst char *dirname;\n-\tsize_t dir_len;\n+\tstruct strbuf dir;\n \tint dir_found;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n+\t.dir = STRBUF_INIT, \\\n \t.dir_found = 1 \\\n }\n \n static void clear_path_found_data(struct path_found_data *data)\n {\n-\treturn;\n+\tstrbuf_release(&data->dir);\n }\n \n static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n \tchar *newdir;\n-\tchar *tmp;\n \n \t/*\n \t * If dirname corresponds to a directory that doesn't exist, and this\n \t * path starts with dirname, then path can't exist.\n \t */\n-\tif (!data->dir_found && !memcmp(path, data->dirname, data->dir_len))\n+\tif (!data->dir_found && !memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/*\n@@ -486,17 +485,15 @@ static int path_found(const char *path, struct path_found_data *data)\n \t * If path starts with directory (which we already lstat'ed and found),\n \t * then no need to lstat parent directory again.\n \t */\n-\tif (data->dir_found && data->dirname &&\n-\t memcmp(path, data->dirname, data->dir_len))\n+\tif (data->dir_found && data->dir.buf &&\n+\t memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/* Free previous dirname, and cache path's dirname */\n-\tdata->dirname = path;\n-\tdata->dir_len = newdir - path + 1;\n+\tstrbuf_reset(&data->dir);\n+\tstrbuf_add(&data->dir, path, newdir - path + 1);\n \n-\ttmp = xstrndup(path, data->dir_len);\n-\tdata->dir_found = !lstat(tmp, &st);\n-\tfree(tmp);\n+\tdata->dir_found = !lstat(data->dir.buf, &st);\n \n \treturn 0;\n }\n-- \ngitgitgadget\n\n"},{"id":"497701","messageId":"9549f5b8062909253fef1fc9a62dae9114c43481.1719412192.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v2.git.1719412192.gitgitgadget@gmail.com","subject":"[PATCH v2 4/5] sparse-index: count lstat() calls","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-26T14:29:50Z","receivedAt":"2024-06-26T14:29:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree.. methods already report some statistics about\nhow many cache entries are checked against path_found() due to having\nthe skip-worktree bit set. However, due to path_found() performing some\ncaching, this isn't the only information that would be helpful to\nreport.\n\nAdd a new lstat_count member to the path_found_data struct to count the\nnumber of times path_found() calls lstat(). This will be helpful to help\nexplain performance problems in this method as well as to demonstrate\nfuture changes to the caching algorithm in a more concrete way than\nend-to-end timings.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex fec4f393360..8577fa726b8 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -442,6 +442,7 @@ void ensure_correct_sparsity(struct index_state *istate)\n struct path_found_data {\n \tstruct strbuf dir;\n \tint dir_found;\n+\tsize_t lstat_count;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n@@ -469,6 +470,7 @@ static int path_found(const char *path, struct path_found_data *data)\n \t/*\n \t * If path itself exists, return 1.\n \t */\n+\tdata->lstat_count++;\n \tif (!lstat(path, &st))\n \t\treturn 1;\n \n@@ -493,6 +495,7 @@ static int path_found(const char *path, struct path_found_data *data)\n \tstrbuf_reset(&data->dir);\n \tstrbuf_add(&data->dir, path, newdir - path + 1);\n \n+\tdata->lstat_count++;\n \tdata->dir_found = !lstat(data->dir.buf, &st);\n \n \treturn 0;\n@@ -524,6 +527,8 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \n \ttrace2_data_intmax(\"index\", istate->repo,\n \t\t\t \"sparse_path_count\", path_count);\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"sparse_lstat_count\", data.lstat_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n \tclear_path_found_data(&data);\n@@ -553,6 +558,8 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \n \ttrace2_data_intmax(\"index\", istate->repo,\n \t\t\t \"full_path_count\", path_count);\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"full_lstat_count\", data.lstat_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n \tclear_path_found_data(&data);\n-- \ngitgitgadget\n\n"},{"id":"497702","messageId":"0cb344ac14fa942f781221663e2324fd2225fb5f.1719412192.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v2.git.1719412192.gitgitgadget@gmail.com","subject":"[PATCH v2 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-26T14:29:51Z","receivedAt":"2024-06-26T14:30:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree_from_present_files() method was first introduced\nin af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files\npresent in worktree, 2022-01-14) to allow better interaction with the\nworking directory in the presence of paths outside of the\nsparse-checkout. The initial implementation would lstat() every single\nSKIP_WORKTREE path to see if it existed; if it ran across a sparse\ndirectory that existed (when a sparse index was in use), then it would\nexpand the index and then check every SKIP_WORKTREE path.\n\nSince these lstat() calls were very expensive, this was improved in\nd79d299352 (Accelerate clear_skip_worktree_from_present_files() by\ncaching, 2022-01-14) by caching directories that do not exist so it\ncould avoid lstat()ing any files under such directories. However, there\nare some inefficiencies in that caching mechanism.\n\nThe caching mechanism stored only the parent directory as not existing,\neven if a higher parent directory also does not exist. This means that\nwasted lstat() calls would occur when the paths passed to path_found()\nchange immediate parent directories but within the same parent directory\nthat does not exist.\n\nTo create an example repository that demonstrates this problem, it helps\nto have a directory outside of the sparse-checkout that contains many\ndeep paths. In particular, the first paths (in lexicographic order)\nunderneath the sparse directory should have deep directory structures,\nmaximizing the difference between the old caching algorithm that looks\nto a single parent and the new caching algorithm that looks to the\ntop-most missing directory.\n\nThe performance test script p2000-sparse-operations.sh takes the sample\nrepository and copies its HEAD to several copies nested in directories\nof the form f/f/f where i, j, and k are numbers from 1 to 4.\nThe sparse-checkout cone is then selected as \"f2/f4/\". Creating \"f1/f1/\"\nwill trigger the behavior and also lead to some interesting cases for\nthe caching algorithm since \"f1/f1/\" exists but \"f1/f2/\" and \"f3/\" do\nnot.\n\nThis is difficult to notice when running performance tests using the Git\nrepository (or a blow-up of the Git repository, as in\np2000-sparse-operations.sh) because Git has a very shallow directory\nstructure.\n\nThis change reorganizes the caching algorithm to focus on storing the\nhighest level leading directory that does not exist; specifically this\nmeans that that directory's parent _does_ exist. By doing a little extra\nwork on a path passed to path_found(), we can short-circuit all of the\npaths passed to path_found() afterwards that match a prefix with that\nnon-existing directory. When in a repository where the first sparse file\nis likely to have a much deeper path than the first non-existing\ndirectory, this can realize significant gains.\n\nThe details of this algorithm require careful attention, so the new\nimplementation of path_found() has detailed comments, including the use\nof a new max_common_dir_prefix() method that may be of independent\ninterest.\n\nIt's worth noting that this is not universally positive, since we are\ndoing extra lstat() calls to establish the exact path to cache. In the\nblow-up of the Git repository, we can see that the lstat count\n_increases_ from 28 to 31. However, these numbers were already\nartificially low.\n\nContributor Elijah Newren created a publicly-available test repository\nthat demonstrates the difference in these caching algorithms in the most\nextreme way. To test, follow these steps:\n\n git clone --sparse https://github.com/newren/gvfs-like-git-bomb\n cd gvfs-like-git-bomb\n ./runme.sh # NOTE: check scripts before running!\n\nAt this point, assuming you do not have index.sparse=true set globally,\nthe index has one million paths with the SKIP_WORKTREE bit and they will\nall be sent to path_found() in the sparse loop. You can measure this by\nrunning 'git status' with GIT_TRACE2_PERF=1:\n\n Sparse files in the index: 1,000,000\n sparse_lstat_count (before): 200,000\n sparse_lstat_count (after): 2\n\nAnd here are the performance numbers:\n\n Benchmark 1: old\n Time (mean ± σ): 397.5 ms ± 4.1 ms\n Range (min … max): 391.2 ms … 404.8 ms 10 runs\n\n Benchmark 2: new\n Time (mean ± σ): 252.7 ms ± 3.1 ms\n Range (min … max): 249.4 ms … 259.5 ms 11 runs\n\n Summary\n 'new' ran\n 1.57 ± 0.02 times faster than 'old'\n\nBy modifying this example further, we can demonstrate a more realistic\nexample and include the sparse index expansion. Continue by creating\nthis directory, confusing both caching algorithms somewhat:\n\n mkdir -p bomb/d/e/f/a/a\n\nThen re-run the 'git status' tests to see these statistics:\n\n Sparse files in the index: 1,000,000\n sparse_lstat_count (before): 724,010\n sparse_lstat_count (after): 106\n\n Benchmark 1: old\n Time (mean ± σ): 753.0 ms ± 3.5 ms\n Range (min … max): 749.7 ms … 760.9 ms 10 runs\n\n Benchmark 2: new\n Time (mean ± σ): 201.4 ms ± 3.2 ms\n Range (min … max): 196.0 ms … 207.9 ms 14 runs\n\n Summary\n 'new' ran\n 3.74 ± 0.06 times faster than 'old'\n\nNote that if this repository had a sparse index enabled, the additional\ncost of expanding the sparse index affects the total time of these\ncommands by over four seconds, significantly diminishing the benefit of\nthe caching algorithm. Having existing paths outside of the\nsparse-checkout is a known performance issue for the sparse index and is\na known trade-off for the performance benefits given when no such paths\nexist.\n\nUsing an internal monorepo with over two million paths at HEAD and a\ntypical sparse-checkout cone such that the sparse index contains\n~190,000 entries (including over two thousand sparse trees), I was able\nto measure these lstat counts when one sparse directory actually exists\non disk:\n\n Sparse files in expanded index: 1,841,997\n full_lstat_count (before): 1,188,161\n full_lstat_count (after): 4,404\n\nThis resulted in this absolute time change, on a warm disk:\n\n Time in full loop (before): 13.481 s\n Time in full loop (after): 0.081 s\n\n(These times were calculated on a Windows machine, where lstat() is\nslower than a similar Linux machine.)\n\nHelped-by: Elijah Newren \nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 114 ++++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 90 insertions(+), 24 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 8577fa726b8..7e433250248 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -440,14 +440,21 @@ void ensure_correct_sparsity(struct index_state *istate)\n }\n \n struct path_found_data {\n+\t/**\n+\t * The path stored in 'dir', if non-empty, corresponds to the most-\n+\t * recent path that we checked where:\n+\t *\n+\t * 1. The path should be a directory, according to the index.\n+\t * 2. The path does not exist.\n+\t * 3. The parent path _does_ exist. (This may be the root of the\n+\t * working directory.)\n+\t */\n \tstruct strbuf dir;\n-\tint dir_found;\n \tsize_t lstat_count;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n-\t.dir = STRBUF_INIT, \\\n-\t.dir_found = 1 \\\n+\t.dir = STRBUF_INIT \\\n }\n \n static void clear_path_found_data(struct path_found_data *data)\n@@ -455,49 +462,108 @@ static void clear_path_found_data(struct path_found_data *data)\n \tstrbuf_release(&data->dir);\n }\n \n+/**\n+ * Return the length of the largest common substring that ends in a\n+ * slash ('/') to indicate the largest common parent directory. Returns\n+ * zero if no common directory exists.\n+ */\n+static size_t max_common_dir_prefix(const char *path1, const char *path2)\n+{\n+\tsize_t common_prefix = 0;\n+\tfor (size_t i = 0; path1[i] && path2[i]; i++) {\n+\t\tif (path1[i] != path2[i])\n+\t\t\tbreak;\n+\n+\t\t/*\n+\t\t * If they agree at a directory separator, then add one\n+\t\t * to make sure it is included in the common prefix string.\n+\t\t */\n+\t\tif (path1[i] == '/')\n+\t\t\tcommon_prefix = i + 1;\n+\t}\n+\n+\treturn common_prefix;\n+}\n+\n static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n-\tchar *newdir;\n+\tsize_t common_prefix;\n \n \t/*\n-\t * If dirname corresponds to a directory that doesn't exist, and this\n-\t * path starts with dirname, then path can't exist.\n+\t * If data->dir is non-empty, then it contains a path that doesn't\n+\t * exist, including an ending slash ('/'). If it is a prefix of 'path',\n+\t * then we can return 0.\n \t */\n-\tif (!data->dir_found && !memcmp(path, data->dir.buf, data->dir.len))\n+\tif (data->dir.len && !memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/*\n-\t * If path itself exists, return 1.\n+\t * Otherwise, we must check if the current path exists. If it does, then\n+\t * return 1. The cached directory will be skipped until we come across\n+\t * a missing path again.\n \t */\n \tdata->lstat_count++;\n \tif (!lstat(path, &st))\n \t\treturn 1;\n \n \t/*\n-\t * Otherwise, path does not exist so we'll return 0...but we'll first\n-\t * determine some info about its parent directory so we can avoid\n-\t * lstat calls for future cache entries.\n+\t * At this point, we know that 'path' doesn't exist, and we know that\n+\t * the parent directory of 'data->dir' does exist. Let's set 'data->dir'\n+\t * to be the top-most non-existing directory of 'path'. If the first\n+\t * parent of 'path' exists, then we will act as though 'path'\n+\t * corresponds to a directory (by adding a slash).\n \t */\n-\tnewdir = strrchr(path, '/');\n-\tif (!newdir)\n-\t\treturn 0; /* Didn't find a parent dir; just return 0 now. */\n+\tcommon_prefix = max_common_dir_prefix(path, data->dir.buf);\n \n \t/*\n-\t * If path starts with directory (which we already lstat'ed and found),\n-\t * then no need to lstat parent directory again.\n+\t * At this point, 'path' and 'data->dir' have a common existing parent\n+\t * directory given by path[0..common_prefix] (which could have length 0).\n+\t * We \"grow\" the data->dir buffer by checking for existing directories\n+\t * along 'path'.\n \t */\n-\tif (data->dir_found && data->dir.buf &&\n-\t memcmp(path, data->dir.buf, data->dir.len))\n-\t\treturn 0;\n \n-\t/* Free previous dirname, and cache path's dirname */\n-\tstrbuf_reset(&data->dir);\n-\tstrbuf_add(&data->dir, path, newdir - path + 1);\n+\tstrbuf_setlen(&data->dir, common_prefix);\n+\twhile (1) {\n+\t\t/* Find the next directory in 'path'. */\n+\t\tconst char *rest = path + data->dir.len;\n+\t\tconst char *next_slash = strchr(rest, '/');\n \n-\tdata->lstat_count++;\n-\tdata->dir_found = !lstat(data->dir.buf, &st);\n+\t\t/*\n+\t\t * If there are no more slashes, then 'path' doesn't contain a\n+\t\t * non-existent _parent_ directory. Set 'data->dir' to be equal\n+\t\t * to 'path' plus an additional slash, so it can be used for\n+\t\t * caching in the future. The filename of 'path' is considered\n+\t\t * a non-existent directory.\n+\t\t *\n+\t\t * Note: if \"{path}/\" exists as a directory, then it will never\n+\t\t * appear as a prefix of other callers to this method, assuming\n+\t\t * the context from the clear_skip_worktree... methods. If this\n+\t\t * method is reused, then this must be reconsidered.\n+\t\t */\n+\t\tif (!next_slash) {\n+\t\t\tstrbuf_addstr(&data->dir, rest);\n+\t\t\tstrbuf_addch(&data->dir, '/');\n+\t\t\tbreak;\n+\t\t}\n \n+\t\t/*\n+\t\t * Now that we have a slash, let's grow 'data->dir' to include\n+\t\t * this slash, then test if we should stop.\n+\t\t */\n+\t\tstrbuf_add(&data->dir, rest, next_slash - rest + 1);\n+\n+\t\t/* If the parent dir doesn't exist, then stop here. */\n+\t\tdata->lstat_count++;\n+\t\tif (lstat(data->dir.buf, &st))\n+\t\t\treturn 0;\n+\t}\n+\n+\t/*\n+\t * At this point, 'data->dir' is equal to 'path' plus a slash character,\n+\t * and the parent directory of 'path' definitely exists. Moreover, we\n+\t * know that 'path' doesn't exist, or we would have returned 1 earlier.\n+\t */\n \treturn 0;\n }\n \n-- \ngitgitgadget\n"},{"id":"497763","messageId":"xmqq7ceat83v.fsf@gitster.g","threadId":"61657","inReplyTo":"93d0baed0b0f435e5656cef04cf103b5e2e0f41a.1719412192.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/5] sparse-checkout: refactor skip worktree retry logic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-06-27T20:59:32Z","receivedAt":"2024-06-27T20:59:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> -void clear_skip_worktree_from_present_files(struct index_state *istate)\n> +static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n> {\n> \tconst char *last_dirname = NULL;\n> \tsize_t dir_len = 0;\n> \tint dir_found = 1;\n> \n> -\tint i;\n> -\tint path_count[2] = {0, 0};\n> -\tint restarted = 0;\n> +\tint path_count = 0;\n> +\tint to_restart = 0;\n> \n> -\tif (!core_apply_sparse_checkout ||\n> -\t sparse_expect_files_outside_of_patterns)\n> -\t\treturn;\n> -\n> -\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files\",\n> +\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n> \t\t\t istate->repo);\n> -restart:\n> -\tfor (i = 0; i < istate->cache_nr; i++) {\n> +\tfor (int i = 0; i < istate->cache_nr; i++) {\n> \t\tstruct cache_entry *ce = istate->cache[i];\n> \n> \t\tif (ce_skip_worktree(ce)) {\n> -\t\t\tpath_count[restarted]++;\n> +\t\t\tpath_count++;\n> \t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n> \t\t\t\tif (S_ISSPARSEDIR(ce->ce_mode)) {\n> -\t\t\t\t\tif (restarted)\n> -\t\t\t\t\t\tBUG(\"ensure-full-index did not fully flatten?\");\n> -\t\t\t\t\tensure_full_index(istate);\n> -\t\t\t\t\trestarted = 1;\n> -\t\t\t\t\tgoto restart;\n> +\t\t\t\t\tto_restart = 1;\n> +\t\t\t\t\tbreak;\n> \t\t\t\t}\n> \t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n> \t\t\t}\n> \t\t}\n> \t}\n\nBoth original and the rewritten code shares one trait, which is that\nit goes from the beginning to check all paths that are marked with\nSKIP_WORKTREE bit to clear CE_SKIP_WORKTREE bits from them, until\nthey find a S_ISSPARSEDIR entry and lazily call ensure_full_index(),\nbut then when retrying after calling ensure_full_index(), it\nrestarts from the beginning. I wonder if it would help, especially\nif the S_ISSPARSEDIR entry comes very late in the index (e.g., by\nreturning \"here is where we have already checked during the first\nrun, until we realized that we first need to do ensure_full_index()\"\nto the caller from here, and then the caller tells the second phase\nto restart from there), to reduce the number of calls to path_found()?\n"},{"id":"497764","messageId":"xmqqy16qrsup.fsf@gitster.g","threadId":"61657","inReplyTo":"0cb344ac14fa942f781221663e2324fd2225fb5f.1719412192.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-06-27T21:14:22Z","receivedAt":"2024-06-27T21:14:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> struct path_found_data {\n> +\t/**\n> +\t * The path stored in 'dir', if non-empty, corresponds to the most-\n> +\t * recent path that we checked where:\n> +\t *\n> +\t * 1. The path should be a directory, according to the index.\n> +\t * 2. The path does not exist.\n> +\t * 3. The parent path _does_ exist. (This may be the root of the\n> +\t * working directory.)\n> +\t */\n> \tstruct strbuf dir;\n> -\tint dir_found;\n> \tsize_t lstat_count;\n> };\n> \n> #define PATH_FOUND_DATA_INIT { \\\n> -\t.dir = STRBUF_INIT, \\\n> -\t.dir_found = 1 \\\n> +\t.dir = STRBUF_INIT \\\n> }\n> \n> static void clear_path_found_data(struct path_found_data *data)\n> @@ -455,49 +462,108 @@ static void clear_path_found_data(struct path_found_data *data)\n> \tstrbuf_release(&data->dir);\n> }\n> \n> +/**\n> + * Return the length of the largest common substring that ends in a\n\n\"largest\" here is understandable (it means longest).\n\n> + * slash ('/') to indicate the largest common parent directory. Returns\n\nhere I find it a bit confusing. It is the deepest common parent\ndirectory between the two (or \"the common parent directory with the\nlongest path\"), but my initial reaction was \"largest common parent\ndirectory? wouldn't the root level by definition the 'largest'\n(having the largest number of paths underneath) directory that is\ncommon?)\".\n\n> + * zero if no common directory exists.\n> + */\n> +static size_t max_common_dir_prefix(const char *path1, const char *path2)\n> +{\n> +\tsize_t common_prefix = 0;\n> +\tfor (size_t i = 0; path1[i] && path2[i]; i++) {\n> +\t\tif (path1[i] != path2[i])\n> +\t\t\tbreak;\n> +\n> +\t\t/*\n> +\t\t * If they agree at a directory separator, then add one\n> +\t\t * to make sure it is included in the common prefix string.\n> +\t\t */\n> +\t\tif (path1[i] == '/')\n> +\t\t\tcommon_prefix = i + 1;\n> +\t}\n> +\n> +\treturn common_prefix;\n> +}\n\nLooking good. I assume that these two paths are relative to the\ntop-level of the working tree (in other words, they do not begin\nwith a slash)?\n\n> static int path_found(const char *path, struct path_found_data *data)\n> {\n> ...\n> +\t * At this point, we know that 'path' doesn't exist, and we know that\n> +\t * the parent directory of 'data->dir' does exist. Let's set 'data->dir'\n> +\t * to be the top-most non-existing directory of 'path'. If the first\n> +\t * parent of 'path' exists, then we will act as though 'path'\n> +\t * corresponds to a directory (by adding a slash).\n> \t */\n> -\tnewdir = strrchr(path, '/');\n> -\tif (!newdir)\n> -\t\treturn 0; /* Didn't find a parent dir; just return 0 now. */\n> +\tcommon_prefix = max_common_dir_prefix(path, data->dir.buf);\n> ...\n> +\tstrbuf_setlen(&data->dir, common_prefix);\n> +\twhile (1) {\n\nOooh, nice. So you learned /a/b/c/d did not exist, so check /a/b/c,\nand then /a/b/ and stop, because you know /a does exist already.\nWith luck, our next query is for /a/b/c/e or for /a/b/f, and knowing\nthat /a/b/ does not exist would allow us to say \"no, they do not\nexist\" without having to lstat(). OK.\n\n"},{"id":"497767","messageId":"xmqqv81uqcsi.fsf@gitster.g","threadId":"61657","inReplyTo":"pull.1754.v2.git.1719412192.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-06-27T21:46:37Z","receivedAt":"2024-06-27T21:46:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> Updates in v2\n> =============\n>\n> Thanks to Elijah for a thorough review, leading to valuable improvements.\n>\n> * I was mistaken that the sparse index was required for this logic to\n> happen. This has changed several descriptions across the commit messages.\n> * The final lstat() in path_found() was not needed, so is removed in v2.\n> This saves even more time and lstat() calls, updating the stats.\n> * Elijah created a particularly nasty example for testing, which I include\n> in my final patch. He gets a \"Helped-by\" credit for this.\n> * Several comments, variables, and other improvements based on Elijah's\n> recommendations.\n>\n> Thanks, Stolee\n\nThanks, both. This round was a pleasant read.\n\nLet's mark it for 'next' soonish.\n\n\n \n"},{"id":"497768","messageId":"CABPp-BEHP1h244etkRANCiY9Oz6qsQrNB+Sk4s=kXdE9vucfNQ@mail.gmail.com","threadId":"61657","inReplyTo":"cfb20e54-eee5-4043-abcb-63c8211635d3@gmail.com","subject":"Re: [PATCH 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-28T00:10:26Z","receivedAt":"2024-06-28T00:10:38Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jun 26, 2024 at 6:06 AM Derrick Stolee wrote:\n>\n> On 6/24/24 6:14 PM, Elijah Newren wrote:\n[...]\n> > Further, you can recompile the git version in use in another window,\n> > then come back to this one and run 'rm trace' followed by the last two\n> > commands to retest.\n> >\n> > The commands above create a 'gvfs-like-git-bomb' git directory that\n> > has 1,000,001 files in HEAD.\n> >\n> > With this test directory, before applying this patch, I see:\n> > ..sparse_lstat_count:722011\n> > After applying this patch I see\n> > ..sparse_lstat_count:135\n> > and with a slight tweak to your patch I see\n> > ..sparse_lstat_count:125\n> > I'll comment on the slight tweak at the end of the patch.\n>\n> Thanks for these numbers! Are you willing to keep that example repo\n> on GitHub so I can refer to it in the message?\n\nSure, I've had it up for several years already without change (though\nthe anachronistic 'gvfs' in the repository name feels like it should\nbe updated...)\n"},{"id":"497769","messageId":"CABPp-BFzxOjGto+1GGk1xq3XX7OQ3mmmRYm0zU+2mCYZ6h_OfQ@mail.gmail.com","threadId":"61657","inReplyTo":"93d0baed0b0f435e5656cef04cf103b5e2e0f41a.1719412192.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/5] sparse-checkout: refactor skip worktree retry logic","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-28T00:31:18Z","receivedAt":"2024-06-28T00:31:30Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jun 26, 2024 at 7:29 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n[...]\n> If users are having trouble with the performance of this operation and\n> don't care about paths outside of the sparse-checkout, they can disable\n> them using the sparse.expectFilesOutsideOfPatterns config option\n> introduced in ecc7c8841d (repo_read_index: add config to expect files\n> outside sparse patterns, 2022-02-25).\n\nSo, I had some heartburn with this paragraph when reading v1, but\ndecided to focus on other stuff. But it still really bugs me while\nreading v2. So...\n\nThe purpose for the sparse.expectFilesOutsideOfPatterns option is very\nspecifically for the virtual-filesystem usecase (Google, specifically)\nwhere sparse files aren't meant to stay sparse but be brought to life\nthe instant they are accessed (via a specialized filesystem and kernel\nmodules and whatnot). Using it for any other reason, such as a\nworkaround for performance issues here, seems risky to me and I don't\nlike seeing it suggested. The \"if users...don't care about paths\noutside of the sparse-checkout\" really doesn't do it justice. See the\n\"User-facing issues\" section of\nhttps://lore.kernel.org/git/b263cc75b7d4f426fb051d2cae5ae0fabeebb9c9.1642092230.git.gitgitgadget@gmail.com/;\nwe're foisting all those bugs back on users if they don't have such a\nspecialized filesystem and turn this knob on. And then we'll get many\nbug reports that are close to impossible to track down, and virtually\nimpossible to fix even if we do track it down. I had for a while\nsuggested numerous fixes we needed in order to make\nSKIP_WORKTREE-but-actually-present files work better, which required\nfixes all over the codebase and which was serving as an impediment\ne.g. to Victoria's desired sparse-index changes. We gave up on those\nother efforts long ago in favor of this much cleaner and simpler\nsolution of just clearing the SKIP_WORKTREE bit if the file wasn't\nmissing.\n\nFurther, I've seen people read git.git commit messages on Stack\nOverflow and make suggestions based off them, so I'm a bit worried\nthis paragraph as worded will end up causing active harm, when I think\nit's original intent was merely to provide full context around the\nhistory of the clear_skip_worktree_from_present_files_sparse()\nfunction. While this bit of information is part of the history of\nthis function, I'm not sure it's really all that relevant to your\nseries.\n\nCould we omit this paragraph, or if you want to keep it, reword it in\nsome way that doesn't make it look like some tradeoff that isn't that\nbig of a deal for non-specialized-vfs users?\n"},{"id":"497772","messageId":"CABPp-BExeTYSpg0d-5F5cdwM8UZzU625A+6uaDhpWgBRjVrd7A@mail.gmail.com","threadId":"61657","inReplyTo":"xmqq7ceat83v.fsf@gitster.g","subject":"Re: [PATCH v2 1/5] sparse-checkout: refactor skip worktree retry logic","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-28T00:51:00Z","receivedAt":"2024-06-28T00:51:23Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 27, 2024 at 1:59 PM Junio C Hamano wrote:\n>\n> \"Derrick Stolee via GitGitGadget\" writes:\n>\n> > -void clear_skip_worktree_from_present_files(struct index_state *istate)\n> > +static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n> > {\n> > const char *last_dirname = NULL;\n> > size_t dir_len = 0;\n> > int dir_found = 1;\n> >\n> > - int i;\n> > - int path_count[2] = {0, 0};\n> > - int restarted = 0;\n> > + int path_count = 0;\n> > + int to_restart = 0;\n> >\n> > - if (!core_apply_sparse_checkout ||\n> > - sparse_expect_files_outside_of_patterns)\n> > - return;\n> > -\n> > - trace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files\",\n> > + trace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n> > istate->repo);\n> > -restart:\n> > - for (i = 0; i < istate->cache_nr; i++) {\n> > + for (int i = 0; i < istate->cache_nr; i++) {\n> > struct cache_entry *ce = istate->cache[i];\n> >\n> > if (ce_skip_worktree(ce)) {\n> > - path_count[restarted]++;\n> > + path_count++;\n> > if (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n> > if (S_ISSPARSEDIR(ce->ce_mode)) {\n> > - if (restarted)\n> > - BUG(\"ensure-full-index did not fully flatten?\");\n> > - ensure_full_index(istate);\n> > - restarted = 1;\n> > - goto restart;\n> > + to_restart = 1;\n> > + break;\n> > }\n> > ce->ce_flags &= ~CE_SKIP_WORKTREE;\n> > }\n> > }\n> > }\n>\n> Both original and the rewritten code shares one trait, which is that\n> it goes from the beginning to check all paths that are marked with\n> SKIP_WORKTREE bit to clear CE_SKIP_WORKTREE bits from them, until\n> they find a S_ISSPARSEDIR entry and lazily call ensure_full_index(),\n> but then when retrying after calling ensure_full_index(), it\n> restarts from the beginning. I wonder if it would help, especially\n> if the S_ISSPARSEDIR entry comes very late in the index (e.g., by\n\n\"the S_ISSPARSEDIR entry\"? Are you assuming there is only one?\n\n> returning \"here is where we have already checked during the first\n> run, until we realized that we first need to do ensure_full_index()\"\n> to the caller from here, and then the caller tells the second phase\n> to restart from there), to reduce the number of calls to path_found()?\n\nMy first assumption about how to \"restart from there\", was to pass the\ncurrent index, i, to the more involved check. That might fail to be\nthe correct index when there are multiple S_ISSPARSEDIR entries and\nthe first one (or more) are actually missing from the working copy as\nexpected. However, if \"restart from there\" is just passing the\nname of the relevant directory and we do some kind of binary search to\nfind where the earliest entry under that directory would exist in the\nexpanded index, then that seems like a reasonable additional\noptimization.\n"},{"id":"497773","messageId":"CABPp-BFLGrPmUq-rhz7K-G5b__U2jeq8SPdfFDrSa6QkjPMnWg@mail.gmail.com","threadId":"61657","inReplyTo":"xmqqv81uqcsi.fsf@gitster.g","subject":"Re: [PATCH v2 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-28T00:59:00Z","receivedAt":"2024-06-28T00:59:29Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 27, 2024 at 2:46 PM Junio C Hamano wrote:\n>\n> \"Derrick Stolee via GitGitGadget\" writes:\n>\n> > Updates in v2\n> > =============\n> >\n> > Thanks to Elijah for a thorough review, leading to valuable improvements.\n> >\n> > * I was mistaken that the sparse index was required for this logic to\n> > happen. This has changed several descriptions across the commit messages.\n> > * The final lstat() in path_found() was not needed, so is removed in v2.\n> > This saves even more time and lstat() calls, updating the stats.\n> > * Elijah created a particularly nasty example for testing, which I include\n> > in my final patch. He gets a \"Helped-by\" credit for this.\n> > * Several comments, variables, and other improvements based on Elijah's\n> > recommendations.\n> >\n> > Thanks, Stolee\n>\n> Thanks, both. This round was a pleasant read.\n>\n> Let's mark it for 'next' soonish.\n\nYeah, this version looks pretty good. There was a possible further\nimprovement you suggested, but I think that wouldn't need to hold up\nthis series.\n\nHowever, there is one paragraph from the commit message of 1/5 that\nI'd like to see stricken first (or rewritten). Once that's done, I\nthink this series is ready for next.\n"},{"id":"497774","messageId":"724057c1-568b-4e41-ae4d-192dc0cf0869@gmail.com","threadId":"61657","inReplyTo":"CABPp-BExeTYSpg0d-5F5cdwM8UZzU625A+6uaDhpWgBRjVrd7A@mail.gmail.com","subject":"Re: [PATCH v2 1/5] sparse-checkout: refactor skip worktree retry logic","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-06-28T01:49:04Z","receivedAt":"2024-06-28T01:49:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/27/24 8:51 PM, Elijah Newren wrote:\n> On Thu, Jun 27, 2024 at 1:59 PM Junio C Hamano wrote:\n>>\n>> Both original and the rewritten code shares one trait, which is that\n>> it goes from the beginning to check all paths that are marked with\n>> SKIP_WORKTREE bit to clear CE_SKIP_WORKTREE bits from them, until\n>> they find a S_ISSPARSEDIR entry and lazily call ensure_full_index(),\n>> but then when retrying after calling ensure_full_index(), it\n>> restarts from the beginning. I wonder if it would help, especially\n>> if the S_ISSPARSEDIR entry comes very late in the index (e.g., by\n> \n> \"the S_ISSPARSEDIR entry\"? Are you assuming there is only one?\n\nIn fact, the situation is more drastic when there are many sparse\ndirectories and this is one late in the list. The ensure_full_index()\ncall could cause many new entries that should be no-ops earlier in\nthe lex order.\n\n>> returning \"here is where we have already checked during the first\n>> run, until we realized that we first need to do ensure_full_index()\"\n>> to the caller from here, and then the caller tells the second phase\n>> to restart from there), to reduce the number of calls to path_found()?\n> \n> My first assumption about how to \"restart from there\", was to pass the\n> current index, i, to the more involved check. That might fail to be\n> the correct index when there are multiple S_ISSPARSEDIR entries and\n> the first one (or more) are actually missing from the working copy as\n> expected. However, if \"restart from there\" is just passing the\n> name of the relevant directory and we do some kind of binary search to\n> find where the earliest entry under that directory would exist in the\n> expanded index, then that seems like a reasonable additional\n> optimization.\n\nYes, you're on the right track. Requires replacing the response from\nthe sparse loop to be the existing cache entry position or path\ninstead of only a boolean \"should restart\" indicator.\n\nAnother option would be to explore the whole index for the sparse\ndirectories that exist, then expand the index only to those paths.\nThat should be fastest, but would require using the partially-\nexpanded state that has so far only happened inside of the\nsparse-checkout builtin.\n\nAll this to say: there are some interesting directions to go from\nhere. I'm willing to take some time to explore the options. Should\nwe consider merging this improvement now and then consider further\nimprovements in a follow-up series (if they are fruitful)?\n\nThanks,\n-Stolee\n"},{"id":"497775","messageId":"90731058-8079-45af-97e5-bbee4ec85378@gmail.com","threadId":"61657","inReplyTo":"xmqqy16qrsup.fsf@gitster.g","subject":"Re: [PATCH v2 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-06-28T01:56:40Z","receivedAt":"2024-06-28T01:56:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/27/24 5:14 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n>> +/**\n>> + * Return the length of the largest common substring that ends in a\n> \n> \"largest\" here is understandable (it means longest).\n> \n>> + * slash ('/') to indicate the largest common parent directory. Returns\n> \n> here I find it a bit confusing. It is the deepest common parent\n> directory between the two (or \"the common parent directory with the\n> longest path\"), but my initial reaction was \"largest common parent\n> directory? wouldn't the root level by definition the 'largest'\n> (having the largest number of paths underneath) directory that is\n> common?)\".\n\nI'm not sure why my brain got stuck on \"largest\" here when \"longest\"\nwould be a better choice.\n\n>> + * zero if no common directory exists.\n>> + */\n>> +static size_t max_common_dir_prefix(const char *path1, const char *path2)\n>> +{\n>> +\tsize_t common_prefix = 0;\n>> +\tfor (size_t i = 0; path1[i] && path2[i]; i++) {\n>> +\t\tif (path1[i] != path2[i])\n>> +\t\t\tbreak;\n>> +\n>> +\t\t/*\n>> +\t\t * If they agree at a directory separator, then add one\n>> +\t\t * to make sure it is included in the common prefix string.\n>> +\t\t */\n>> +\t\tif (path1[i] == '/')\n>> +\t\t\tcommon_prefix = i + 1;\n>> +\t}\n>> +\n>> +\treturn common_prefix;\n>> +}\n> \n> Looking good. I assume that these two paths are relative to the\n> top-level of the working tree (in other words, they do not begin\n> with a slash)?\n\nYes, they do not begin with a slash. In this specific application, they\nare paths from cache entries in the index. If this were generalized for\nuse elsewhere then paths beginning with a slash should be considered.\n\n>> static int path_found(const char *path, struct path_found_data *data)\n>> {\n>> ...\n>> +\t * At this point, we know that 'path' doesn't exist, and we know that\n>> +\t * the parent directory of 'data->dir' does exist. Let's set 'data->dir'\n>> +\t * to be the top-most non-existing directory of 'path'. If the first\n>> +\t * parent of 'path' exists, then we will act as though 'path'\n>> +\t * corresponds to a directory (by adding a slash).\n>> \t */\n>> -\tnewdir = strrchr(path, '/');\n>> -\tif (!newdir)\n>> -\t\treturn 0; /* Didn't find a parent dir; just return 0 now. */\n>> +\tcommon_prefix = max_common_dir_prefix(path, data->dir.buf);\n>> ...\n>> +\tstrbuf_setlen(&data->dir, common_prefix);\n>> +\twhile (1) {\n> \n> Oooh, nice. So you learned /a/b/c/d did not exist, so check /a/b/c,\n> and then /a/b/ and stop, because you know /a does exist already.\n> With luck, our next query is for /a/b/c/e or for /a/b/f, and knowing\n> that /a/b/ does not exist would allow us to say \"no, they do not\n> exist\" without having to lstat(). OK.\n\nI probably should have led with an example like this, as it makes the\npoint more clearly than my abstract description.\n\nThanks,\n-Stolee\n"},{"id":"497776","messageId":"321be5c1-dfb9-485c-ab5f-0c8c64971ec8@gmail.com","threadId":"61657","inReplyTo":"CABPp-BFzxOjGto+1GGk1xq3XX7OQ3mmmRYm0zU+2mCYZ6h_OfQ@mail.gmail.com","subject":"Re: [PATCH v2 1/5] sparse-checkout: refactor skip worktree retry logic","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-06-28T01:56:57Z","receivedAt":"2024-06-28T01:56:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/27/24 8:31 PM, Elijah Newren wrote:\n> On Wed, Jun 26, 2024 at 7:29 AM Derrick Stolee via GitGitGadget\n> wrote:\n>>\n>> From: Derrick Stolee \n>>\n> [...]\n>> If users are having trouble with the performance of this operation and\n>> don't care about paths outside of the sparse-checkout, they can disable\n>> them using the sparse.expectFilesOutsideOfPatterns config option\n>> introduced in ecc7c8841d (repo_read_index: add config to expect files\n>> outside sparse patterns, 2022-02-25).\n> \n> So, I had some heartburn with this paragraph when reading v1, but\n> decided to focus on other stuff. But it still really bugs me while\n> reading v2. So...\n\nThanks for bringing this up with the details I've omitted from the\ncontext of my response.\n\n> Could we omit this paragraph, or if you want to keep it, reword it in\n> some way that doesn't make it look like some tradeoff that isn't that\n> big of a deal for non-specialized-vfs users?\n\nMakes sense to delete the paragraph. I could ship a v3, or is this\na commit-message surgery you'd be willing to do on my behalf, Junio?\n\nThanks,\n-Stolee\n"},{"id":"497777","messageId":"a1060279-aa30-4e01-8681-a6819bd6bfc8@gmail.com","threadId":"61657","inReplyTo":"CABPp-BFLGrPmUq-rhz7K-G5b__U2jeq8SPdfFDrSa6QkjPMnWg@mail.gmail.com","subject":"Re: [PATCH v2 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-06-28T01:57:52Z","receivedAt":"2024-06-28T01:57:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/27/24 8:59 PM, Elijah Newren wrote:\n> On Thu, Jun 27, 2024 at 2:46 PM Junio C Hamano wrote:\n>>\n>> \"Derrick Stolee via GitGitGadget\" writes:\n>>\n>>> Updates in v2\n>>> =============\n>>>\n>>> Thanks to Elijah for a thorough review, leading to valuable improvements.\n>>>\n>>> * I was mistaken that the sparse index was required for this logic to\n>>> happen. This has changed several descriptions across the commit messages.\n>>> * The final lstat() in path_found() was not needed, so is removed in v2.\n>>> This saves even more time and lstat() calls, updating the stats.\n>>> * Elijah created a particularly nasty example for testing, which I include\n>>> in my final patch. He gets a \"Helped-by\" credit for this.\n>>> * Several comments, variables, and other improvements based on Elijah's\n>>> recommendations.\n>>>\n>>> Thanks, Stolee\n>>\n>> Thanks, both. This round was a pleasant read.\n>>\n>> Let's mark it for 'next' soonish.\n> \n> Yeah, this version looks pretty good. There was a possible further\n> improvement you suggested, but I think that wouldn't need to hold up\n> this series.\n> \n> However, there is one paragraph from the commit message of 1/5 that\n> I'd like to see stricken first (or rewritten). Once that's done, I\n> think this series is ready for next.\n\nI agree about the removal of that paragraph, but also there is a\n\"largest\" to \"longest\" replacement in a few comments that makes sense\nto change.\n\nI can send a v3 with these changes.\n\nThanks,\n-Stolee\n"},{"id":"497787","messageId":"xmqqpls1r4xv.fsf@gitster.g","threadId":"61657","inReplyTo":"CABPp-BExeTYSpg0d-5F5cdwM8UZzU625A+6uaDhpWgBRjVrd7A@mail.gmail.com","subject":"Re: [PATCH v2 1/5] sparse-checkout: refactor skip worktree retry logic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-06-28T05:50:52Z","receivedAt":"2024-06-28T05:50:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n>> restarts from the beginning. I wonder if it would help, especially\n>> if the S_ISSPARSEDIR entry comes very late in the index (e.g., by\n>\n> \"the S_ISSPARSEDIR entry\"? Are you assuming there is only one?\n\nNo, but I was referring to the first one we encounter in the first\nattempt loop that causes us to run the ensure_full() thing. If the\nfirst SPARSEDIR comes very late, there are many index entries before\nthat one that are already dealt with in the first attempt loop, and\nfor these early entries that are already handled, the second attempt\nloop will do nothing but just skip.\n\n> expected. However, if \"restart from there\" is just passing the\n> name of the relevant directory and we do some kind of binary search to\n> find where the earliest entry under that directory would exist in the\n> expanded index, then that seems like a reasonable additional\n> optimization.\n\nPerhaps. I do not think it is known if it is worth doing, and I do\nthink it is better to finish this current round and then explore\nfurther optimization opportunities on top after the dust settles.\n\nThanks.\n\n"},{"id":"497805","messageId":"pull.1754.v3.git.1719578605.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v2.git.1719412192.gitgitgadget@gmail.com","subject":"[PATCH v3 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-28T12:43:20Z","receivedAt":"2024-06-28T12:43:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"While doing some investigation in a private monorepo with sparse-checkout\nand a sparse index, I accidentally left a modified file outside of my\nsparse-checkout cone. This caused my Git commands to slow to a crawl, so I\nreran with GIT_TRACE2_PERF=1.\n\nWhile I was able to identify clear_skip_worktree_from_present_files() as the\nculprit, it took longer than desired to figure out what was going on. This\nseries intends to both fix the performance issue (as much as possible) and\ndo some refactoring to make it easier to understand what is happening.\n\nIn the end, I was able to reduce the number of lstat() calls in my case from\nover 1.1 million to about 4,400, improving the time from 13.4s to 81ms on a\nwarm disk cache. (These numbers are from a test after v2, which somehow hit\nthe old caching algorithm even worse than my test in v1.)\n\n\nUpdates in v3\n=============\n\n * Removed the incorrect paragraph in the commit message of patch 1.\n * Replaced \"largest\" with \"longest\" in the final patch.\n\nThanks, Stolee\n\nDerrick Stolee (5):\n sparse-checkout: refactor skip worktree retry logic\n sparse-index: refactor path_found()\n sparse-index: use strbuf in path_found()\n sparse-index: count lstat() calls\n sparse-index: improve lstat caching of sparse paths\n\n sparse-index.c | 216 +++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 164 insertions(+), 52 deletions(-)\n\n\nbase-commit: 66ac6e4bcd111be3fa9c2a6b3fafea718d00678d\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1754%2Fderrickstolee%2Fclear-skip-speed-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1754/derrickstolee/clear-skip-speed-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/1754\n\nRange-diff vs v2:\n\n 1: 93d0baed0b0 ! 1: 0844cda94cf sparse-checkout: refactor skip worktree retry logic\n @@ Commit message\n stored in the index, so caching was introduced in d79d299352 (Accelerate\n clear_skip_worktree_from_present_files() by caching, 2022-01-14).\n \n - If users are having trouble with the performance of this operation and\n - don't care about paths outside of the sparse-checkout, they can disable\n - them using the sparse.expectFilesOutsideOfPatterns config option\n - introduced in ecc7c8841d (repo_read_index: add config to expect files\n - outside sparse patterns, 2022-02-25).\n -\n This check is particularly confusing in the presence of a sparse index,\n as a sparse tree entry corresponding to an existing directory must first\n be expanded to a full index before examining the paths within. This is\n 2: 69c3beaabf7 = 2: c242e2c9168 sparse-index: refactor path_found()\n 3: 0a82e6b4183 = 3: ad63bf746ca sparse-index: use strbuf in path_found()\n 4: 9549f5b8062 = 4: db6ded0df0d sparse-index: count lstat() calls\n 5: 0cb344ac14f ! 5: 1f58e19691f sparse-index: improve lstat caching of sparse paths\n @@ sparse-index.c: static void clear_path_found_data(struct path_found_data *data)\n }\n \n +/**\n -+ * Return the length of the largest common substring that ends in a\n -+ * slash ('/') to indicate the largest common parent directory. Returns\n ++ * Return the length of the longest common substring that ends in a\n ++ * slash ('/') to indicate the longest common parent directory. Returns\n + * zero if no common directory exists.\n + */\n +static size_t max_common_dir_prefix(const char *path1, const char *path2)\n\n-- \ngitgitgadget\n"},{"id":"497806","messageId":"0844cda94cffd76ea9e86a0837731cfb4dc7bf88.1719578605.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v3.git.1719578605.gitgitgadget@gmail.com","subject":"[PATCH v3 1/5] sparse-checkout: refactor skip worktree retry logic","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-28T12:43:21Z","receivedAt":"2024-06-28T12:43:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree_from_present_files() method was introduced in\naf6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files present\nin worktree, 2022-01-14) to help cases where sparse-checkout is enabled\nbut some paths outside of the sparse-checkout also exist on disk. This\noperation can be slow as it needs to check path existence in a way not\nstored in the index, so caching was introduced in d79d299352 (Accelerate\nclear_skip_worktree_from_present_files() by caching, 2022-01-14).\n\nThis check is particularly confusing in the presence of a sparse index,\nas a sparse tree entry corresponding to an existing directory must first\nbe expanded to a full index before examining the paths within. This is\ncurrently implemented using a 'goto' and a boolean variable to ensure we\nrestart only once.\n\nEven with that caching, it was noticed that this could take a long time\nto execute. 89aaab11a3 (index: add trace2 region for clear skip\nworktree, 2022-11-03) introduced trace2 regions to measure this time.\nFurther, the way the loop repeats itself was slightly confusing and\nprone to breakage, so a BUG() statement was added in 8c7abdc596 (index:\nraise a bug if the index is materialised more than once, 2022-11-03) to\nbe sure that the second run of the loop does not hit any sparse trees.\n\nOne thing that can be confusing about the current setup is that the\ntrace2 regions nest and it is not clear that a second loop is running\nafter a sparse index is expanded. Here is an example of what the regions\nlook like in a typical case:\n\n| region_enter | ... | label:clear_skip_worktree_from_present_files\n| region_enter | ... | ..label:update\n| region_leave | ... | ..label:update\n| region_enter | ... | ..label:ensure_full_index\n| region_enter | ... | ....label:update\n| region_leave | ... | ....label:update\n| region_leave | ... | ..label:ensure_full_index\n| data | ... | ..sparse_path_count:1\n| data | ... | ..sparse_path_count_full:269538\n| region_leave | ... | label:clear_skip_worktree_from_present_files\n\nOne thing that is particularly difficult to understand about these\nregions is that most of the time is spent between the close of the\nensure_full_index region and the reporting of the end data. This is\nbecause of the restart of the loop being within the same region as the\nfirst iteration of the loop.\n\nThis change refactors the method into two separate methods that are\ntraced separately. This will be more important later when we change\nother features of the methods, but for now the only functional change is\nthe difference in the structure of the trace regions.\n\nAfter this change, the same telemetry section is split into three\ndistinct chunks:\n\n| region_enter | ... | label:clear_skip_worktree_from_present_files_sparse\n| data | ... | ..sparse_path_count:1\n| region_leave | ... | label:clear_skip_worktree_from_present_files_sparse\n| region_enter | ... | label:update\n| region_leave | ... | label:update\n| region_enter | ... | label:ensure_full_index\n| region_enter | ... | ..label:update\n| region_leave | ... | ..label:update\n| region_leave | ... | label:ensure_full_index\n| region_enter | ... | label:clear_skip_worktree_from_present_files_full\n| data | ... | ..full_path_count:269538\n| region_leave | ... | label:clear_skip_worktree_from_present_files_full\n\nHere, we see the sparse loop terminating early with its first sparse\npath being a sparse directory containing a file. Then, that loop's\nregion terminates before ensure_full_index begins (in this case, the\ncache-tree must also be computed). Then, _after_ the index is expanded,\nthe full loop begins with its own region.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 77 ++++++++++++++++++++++++++++++++++----------------\n 1 file changed, 53 insertions(+), 24 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex e48e40cae71..e0457c87fff 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -486,49 +486,78 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \treturn 0;\n }\n \n-void clear_skip_worktree_from_present_files(struct index_state *istate)\n+static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n {\n \tconst char *last_dirname = NULL;\n \tsize_t dir_len = 0;\n \tint dir_found = 1;\n \n-\tint i;\n-\tint path_count[2] = {0, 0};\n-\tint restarted = 0;\n+\tint path_count = 0;\n+\tint to_restart = 0;\n \n-\tif (!core_apply_sparse_checkout ||\n-\t sparse_expect_files_outside_of_patterns)\n-\t\treturn;\n-\n-\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files\",\n+\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n-restart:\n-\tfor (i = 0; i < istate->cache_nr; i++) {\n+\tfor (int i = 0; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i];\n \n \t\tif (ce_skip_worktree(ce)) {\n-\t\t\tpath_count[restarted]++;\n+\t\t\tpath_count++;\n \t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n \t\t\t\tif (S_ISSPARSEDIR(ce->ce_mode)) {\n-\t\t\t\t\tif (restarted)\n-\t\t\t\t\t\tBUG(\"ensure-full-index did not fully flatten?\");\n-\t\t\t\t\tensure_full_index(istate);\n-\t\t\t\t\trestarted = 1;\n-\t\t\t\t\tgoto restart;\n+\t\t\t\t\tto_restart = 1;\n+\t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n \t\t\t}\n \t\t}\n \t}\n \n-\tif (path_count[0])\n-\t\ttrace2_data_intmax(\"index\", istate->repo,\n-\t\t\t\t \"sparse_path_count\", path_count[0]);\n-\tif (restarted)\n-\t\ttrace2_data_intmax(\"index\", istate->repo,\n-\t\t\t\t \"sparse_path_count_full\", path_count[1]);\n-\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files\",\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"sparse_path_count\", path_count);\n+\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n+\t\t\t istate->repo);\n+\treturn to_restart;\n+}\n+\n+static void clear_skip_worktree_from_present_files_full(struct index_state *istate)\n+{\n+\tconst char *last_dirname = NULL;\n+\tsize_t dir_len = 0;\n+\tint dir_found = 1;\n+\n+\tint path_count = 0;\n+\n+\ttrace2_region_enter(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n+\tfor (int i = 0; i < istate->cache_nr; i++) {\n+\t\tstruct cache_entry *ce = istate->cache[i];\n+\n+\t\tif (S_ISSPARSEDIR(ce->ce_mode))\n+\t\t\tBUG(\"ensure-full-index did not fully flatten?\");\n+\n+\t\tif (ce_skip_worktree(ce)) {\n+\t\t\tpath_count++;\n+\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found))\n+\t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n+\t\t}\n+\t}\n+\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"full_path_count\", path_count);\n+\ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n+\t\t\t istate->repo);\n+}\n+\n+void clear_skip_worktree_from_present_files(struct index_state *istate)\n+{\n+\tif (!core_apply_sparse_checkout ||\n+\t sparse_expect_files_outside_of_patterns)\n+\t\treturn;\n+\n+\tif (clear_skip_worktree_from_present_files_sparse(istate)) {\n+\t\tensure_full_index(istate);\n+\t\tclear_skip_worktree_from_present_files_full(istate);\n+\t}\n }\n \n /*\n-- \ngitgitgadget\n\n"},{"id":"497807","messageId":"c242e2c9168108e814b4a428b77caca674045351.1719578605.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v3.git.1719578605.gitgitgadget@gmail.com","subject":"[PATCH v3 2/5] sparse-index: refactor path_found()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-28T12:43:22Z","receivedAt":"2024-06-28T12:43:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn advance of changing the behavior of path_found(), take all of the\nintermediate data values and group them into a single struct. This\nsimplifies the method prototype as well as the initialization. Future\nchanges can be made directly to the struct and method without changing\nthe callers with this approach.\n\nNote that the clear_path_found_data() method is currently empty, as\nthere is nothing to free. This method is a placeholder for future\nchanges that require a non-trivial implementation. Its stub is created\nnow so consumers could call it now and not change in future changes.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 45 +++++++++++++++++++++++++++++----------------\n 1 file changed, 29 insertions(+), 16 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex e0457c87fff..de6e727f5c1 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -439,8 +439,22 @@ void ensure_correct_sparsity(struct index_state *istate)\n \t\tensure_full_index(istate);\n }\n \n-static int path_found(const char *path, const char **dirname, size_t *dir_len,\n-\t\t int *dir_found)\n+struct path_found_data {\n+\tconst char *dirname;\n+\tsize_t dir_len;\n+\tint dir_found;\n+};\n+\n+#define PATH_FOUND_DATA_INIT { \\\n+\t.dir_found = 1 \\\n+}\n+\n+static void clear_path_found_data(struct path_found_data *data)\n+{\n+\treturn;\n+}\n+\n+static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n \tchar *newdir;\n@@ -450,7 +464,7 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \t * If dirname corresponds to a directory that doesn't exist, and this\n \t * path starts with dirname, then path can't exist.\n \t */\n-\tif (!*dir_found && !memcmp(path, *dirname, *dir_len))\n+\tif (!data->dir_found && !memcmp(path, data->dirname, data->dir_len))\n \t\treturn 0;\n \n \t/*\n@@ -472,15 +486,16 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \t * If path starts with directory (which we already lstat'ed and found),\n \t * then no need to lstat parent directory again.\n \t */\n-\tif (*dir_found && *dirname && memcmp(path, *dirname, *dir_len))\n+\tif (data->dir_found && data->dirname &&\n+\t memcmp(path, data->dirname, data->dir_len))\n \t\treturn 0;\n \n \t/* Free previous dirname, and cache path's dirname */\n-\t*dirname = path;\n-\t*dir_len = newdir - path + 1;\n+\tdata->dirname = path;\n+\tdata->dir_len = newdir - path + 1;\n \n-\ttmp = xstrndup(path, *dir_len);\n-\t*dir_found = !lstat(tmp, &st);\n+\ttmp = xstrndup(path, data->dir_len);\n+\tdata->dir_found = !lstat(tmp, &st);\n \tfree(tmp);\n \n \treturn 0;\n@@ -488,9 +503,7 @@ static int path_found(const char *path, const char **dirname, size_t *dir_len,\n \n static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)\n {\n-\tconst char *last_dirname = NULL;\n-\tsize_t dir_len = 0;\n-\tint dir_found = 1;\n+\tstruct path_found_data data = PATH_FOUND_DATA_INIT;\n \n \tint path_count = 0;\n \tint to_restart = 0;\n@@ -502,7 +515,7 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \n \t\tif (ce_skip_worktree(ce)) {\n \t\t\tpath_count++;\n-\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {\n+\t\t\tif (path_found(ce->name, &data)) {\n \t\t\t\tif (S_ISSPARSEDIR(ce->ce_mode)) {\n \t\t\t\t\tto_restart = 1;\n \t\t\t\t\tbreak;\n@@ -516,14 +529,13 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \t\t\t \"sparse_path_count\", path_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n+\tclear_path_found_data(&data);\n \treturn to_restart;\n }\n \n static void clear_skip_worktree_from_present_files_full(struct index_state *istate)\n {\n-\tconst char *last_dirname = NULL;\n-\tsize_t dir_len = 0;\n-\tint dir_found = 1;\n+\tstruct path_found_data data = PATH_FOUND_DATA_INIT;\n \n \tint path_count = 0;\n \n@@ -537,7 +549,7 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \n \t\tif (ce_skip_worktree(ce)) {\n \t\t\tpath_count++;\n-\t\t\tif (path_found(ce->name, &last_dirname, &dir_len, &dir_found))\n+\t\t\tif (path_found(ce->name, &data))\n \t\t\t\tce->ce_flags &= ~CE_SKIP_WORKTREE;\n \t\t}\n \t}\n@@ -546,6 +558,7 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \t\t\t \"full_path_count\", path_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n+\tclear_path_found_data(&data);\n }\n \n void clear_skip_worktree_from_present_files(struct index_state *istate)\n-- \ngitgitgadget\n\n"},{"id":"497808","messageId":"ad63bf746caccc0f3359053826d102551dc519e8.1719578605.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v3.git.1719578605.gitgitgadget@gmail.com","subject":"[PATCH v3 3/5] sparse-index: use strbuf in path_found()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-28T12:43:23Z","receivedAt":"2024-06-28T12:43:32Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe path_found() method previously reused strings from the cache entries\nthe calling methods were using. This prevents string manipulation in\nplace and causes some odd reallocation before the final lstat() call in\nthe method.\n\nRefactor the method to use strbufs and copy the path into the strbuf,\nbut also only the parent directory and not the whole path. This looks\nlike extra copying when assigning the path to the strbuf, but we save an\nallocation by dropping the 'tmp' string, and we are \"reusing\" the copy\nfrom 'tmp' to put the data in the strbuf.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 21 +++++++++------------\n 1 file changed, 9 insertions(+), 12 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex de6e727f5c1..fec4f393360 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -440,31 +440,30 @@ void ensure_correct_sparsity(struct index_state *istate)\n }\n \n struct path_found_data {\n-\tconst char *dirname;\n-\tsize_t dir_len;\n+\tstruct strbuf dir;\n \tint dir_found;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n+\t.dir = STRBUF_INIT, \\\n \t.dir_found = 1 \\\n }\n \n static void clear_path_found_data(struct path_found_data *data)\n {\n-\treturn;\n+\tstrbuf_release(&data->dir);\n }\n \n static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n \tchar *newdir;\n-\tchar *tmp;\n \n \t/*\n \t * If dirname corresponds to a directory that doesn't exist, and this\n \t * path starts with dirname, then path can't exist.\n \t */\n-\tif (!data->dir_found && !memcmp(path, data->dirname, data->dir_len))\n+\tif (!data->dir_found && !memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/*\n@@ -486,17 +485,15 @@ static int path_found(const char *path, struct path_found_data *data)\n \t * If path starts with directory (which we already lstat'ed and found),\n \t * then no need to lstat parent directory again.\n \t */\n-\tif (data->dir_found && data->dirname &&\n-\t memcmp(path, data->dirname, data->dir_len))\n+\tif (data->dir_found && data->dir.buf &&\n+\t memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/* Free previous dirname, and cache path's dirname */\n-\tdata->dirname = path;\n-\tdata->dir_len = newdir - path + 1;\n+\tstrbuf_reset(&data->dir);\n+\tstrbuf_add(&data->dir, path, newdir - path + 1);\n \n-\ttmp = xstrndup(path, data->dir_len);\n-\tdata->dir_found = !lstat(tmp, &st);\n-\tfree(tmp);\n+\tdata->dir_found = !lstat(data->dir.buf, &st);\n \n \treturn 0;\n }\n-- \ngitgitgadget\n\n"},{"id":"497809","messageId":"db6ded0df0d8abed01442cb44703f3d662a06294.1719578605.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v3.git.1719578605.gitgitgadget@gmail.com","subject":"[PATCH v3 4/5] sparse-index: count lstat() calls","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-28T12:43:24Z","receivedAt":"2024-06-28T12:43:34Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree.. methods already report some statistics about\nhow many cache entries are checked against path_found() due to having\nthe skip-worktree bit set. However, due to path_found() performing some\ncaching, this isn't the only information that would be helpful to\nreport.\n\nAdd a new lstat_count member to the path_found_data struct to count the\nnumber of times path_found() calls lstat(). This will be helpful to help\nexplain performance problems in this method as well as to demonstrate\nfuture changes to the caching algorithm in a more concrete way than\nend-to-end timings.\n\nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex fec4f393360..8577fa726b8 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -442,6 +442,7 @@ void ensure_correct_sparsity(struct index_state *istate)\n struct path_found_data {\n \tstruct strbuf dir;\n \tint dir_found;\n+\tsize_t lstat_count;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n@@ -469,6 +470,7 @@ static int path_found(const char *path, struct path_found_data *data)\n \t/*\n \t * If path itself exists, return 1.\n \t */\n+\tdata->lstat_count++;\n \tif (!lstat(path, &st))\n \t\treturn 1;\n \n@@ -493,6 +495,7 @@ static int path_found(const char *path, struct path_found_data *data)\n \tstrbuf_reset(&data->dir);\n \tstrbuf_add(&data->dir, path, newdir - path + 1);\n \n+\tdata->lstat_count++;\n \tdata->dir_found = !lstat(data->dir.buf, &st);\n \n \treturn 0;\n@@ -524,6 +527,8 @@ static int clear_skip_worktree_from_present_files_sparse(struct index_state *ist\n \n \ttrace2_data_intmax(\"index\", istate->repo,\n \t\t\t \"sparse_path_count\", path_count);\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"sparse_lstat_count\", data.lstat_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_sparse\",\n \t\t\t istate->repo);\n \tclear_path_found_data(&data);\n@@ -553,6 +558,8 @@ static void clear_skip_worktree_from_present_files_full(struct index_state *ista\n \n \ttrace2_data_intmax(\"index\", istate->repo,\n \t\t\t \"full_path_count\", path_count);\n+\ttrace2_data_intmax(\"index\", istate->repo,\n+\t\t\t \"full_lstat_count\", data.lstat_count);\n \ttrace2_region_leave(\"index\", \"clear_skip_worktree_from_present_files_full\",\n \t\t\t istate->repo);\n \tclear_path_found_data(&data);\n-- \ngitgitgadget\n\n"},{"id":"497810","messageId":"1f58e19691f2dd6ff525cc19c98158861d6fe411.1719578605.git.gitgitgadget@gmail.com","threadId":"61657","inReplyTo":"pull.1754.v3.git.1719578605.gitgitgadget@gmail.com","subject":"[PATCH v3 5/5] sparse-index: improve lstat caching of sparse paths","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-06-28T12:43:25Z","receivedAt":"2024-06-28T12:43:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe clear_skip_worktree_from_present_files() method was first introduced\nin af6a51875a (repo_read_index: clear SKIP_WORKTREE bit from files\npresent in worktree, 2022-01-14) to allow better interaction with the\nworking directory in the presence of paths outside of the\nsparse-checkout. The initial implementation would lstat() every single\nSKIP_WORKTREE path to see if it existed; if it ran across a sparse\ndirectory that existed (when a sparse index was in use), then it would\nexpand the index and then check every SKIP_WORKTREE path.\n\nSince these lstat() calls were very expensive, this was improved in\nd79d299352 (Accelerate clear_skip_worktree_from_present_files() by\ncaching, 2022-01-14) by caching directories that do not exist so it\ncould avoid lstat()ing any files under such directories. However, there\nare some inefficiencies in that caching mechanism.\n\nThe caching mechanism stored only the parent directory as not existing,\neven if a higher parent directory also does not exist. This means that\nwasted lstat() calls would occur when the paths passed to path_found()\nchange immediate parent directories but within the same parent directory\nthat does not exist.\n\nTo create an example repository that demonstrates this problem, it helps\nto have a directory outside of the sparse-checkout that contains many\ndeep paths. In particular, the first paths (in lexicographic order)\nunderneath the sparse directory should have deep directory structures,\nmaximizing the difference between the old caching algorithm that looks\nto a single parent and the new caching algorithm that looks to the\ntop-most missing directory.\n\nThe performance test script p2000-sparse-operations.sh takes the sample\nrepository and copies its HEAD to several copies nested in directories\nof the form f/f/f where i, j, and k are numbers from 1 to 4.\nThe sparse-checkout cone is then selected as \"f2/f4/\". Creating \"f1/f1/\"\nwill trigger the behavior and also lead to some interesting cases for\nthe caching algorithm since \"f1/f1/\" exists but \"f1/f2/\" and \"f3/\" do\nnot.\n\nThis is difficult to notice when running performance tests using the Git\nrepository (or a blow-up of the Git repository, as in\np2000-sparse-operations.sh) because Git has a very shallow directory\nstructure.\n\nThis change reorganizes the caching algorithm to focus on storing the\nhighest level leading directory that does not exist; specifically this\nmeans that that directory's parent _does_ exist. By doing a little extra\nwork on a path passed to path_found(), we can short-circuit all of the\npaths passed to path_found() afterwards that match a prefix with that\nnon-existing directory. When in a repository where the first sparse file\nis likely to have a much deeper path than the first non-existing\ndirectory, this can realize significant gains.\n\nThe details of this algorithm require careful attention, so the new\nimplementation of path_found() has detailed comments, including the use\nof a new max_common_dir_prefix() method that may be of independent\ninterest.\n\nIt's worth noting that this is not universally positive, since we are\ndoing extra lstat() calls to establish the exact path to cache. In the\nblow-up of the Git repository, we can see that the lstat count\n_increases_ from 28 to 31. However, these numbers were already\nartificially low.\n\nContributor Elijah Newren created a publicly-available test repository\nthat demonstrates the difference in these caching algorithms in the most\nextreme way. To test, follow these steps:\n\n git clone --sparse https://github.com/newren/gvfs-like-git-bomb\n cd gvfs-like-git-bomb\n ./runme.sh # NOTE: check scripts before running!\n\nAt this point, assuming you do not have index.sparse=true set globally,\nthe index has one million paths with the SKIP_WORKTREE bit and they will\nall be sent to path_found() in the sparse loop. You can measure this by\nrunning 'git status' with GIT_TRACE2_PERF=1:\n\n Sparse files in the index: 1,000,000\n sparse_lstat_count (before): 200,000\n sparse_lstat_count (after): 2\n\nAnd here are the performance numbers:\n\n Benchmark 1: old\n Time (mean ± σ): 397.5 ms ± 4.1 ms\n Range (min … max): 391.2 ms … 404.8 ms 10 runs\n\n Benchmark 2: new\n Time (mean ± σ): 252.7 ms ± 3.1 ms\n Range (min … max): 249.4 ms … 259.5 ms 11 runs\n\n Summary\n 'new' ran\n 1.57 ± 0.02 times faster than 'old'\n\nBy modifying this example further, we can demonstrate a more realistic\nexample and include the sparse index expansion. Continue by creating\nthis directory, confusing both caching algorithms somewhat:\n\n mkdir -p bomb/d/e/f/a/a\n\nThen re-run the 'git status' tests to see these statistics:\n\n Sparse files in the index: 1,000,000\n sparse_lstat_count (before): 724,010\n sparse_lstat_count (after): 106\n\n Benchmark 1: old\n Time (mean ± σ): 753.0 ms ± 3.5 ms\n Range (min … max): 749.7 ms … 760.9 ms 10 runs\n\n Benchmark 2: new\n Time (mean ± σ): 201.4 ms ± 3.2 ms\n Range (min … max): 196.0 ms … 207.9 ms 14 runs\n\n Summary\n 'new' ran\n 3.74 ± 0.06 times faster than 'old'\n\nNote that if this repository had a sparse index enabled, the additional\ncost of expanding the sparse index affects the total time of these\ncommands by over four seconds, significantly diminishing the benefit of\nthe caching algorithm. Having existing paths outside of the\nsparse-checkout is a known performance issue for the sparse index and is\na known trade-off for the performance benefits given when no such paths\nexist.\n\nUsing an internal monorepo with over two million paths at HEAD and a\ntypical sparse-checkout cone such that the sparse index contains\n~190,000 entries (including over two thousand sparse trees), I was able\nto measure these lstat counts when one sparse directory actually exists\non disk:\n\n Sparse files in expanded index: 1,841,997\n full_lstat_count (before): 1,188,161\n full_lstat_count (after): 4,404\n\nThis resulted in this absolute time change, on a warm disk:\n\n Time in full loop (before): 13.481 s\n Time in full loop (after): 0.081 s\n\n(These times were calculated on a Windows machine, where lstat() is\nslower than a similar Linux machine.)\n\nHelped-by: Elijah Newren \nSigned-off-by: Derrick Stolee \n---\n sparse-index.c | 114 ++++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 90 insertions(+), 24 deletions(-)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex 8577fa726b8..9913a6078cd 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -440,14 +440,21 @@ void ensure_correct_sparsity(struct index_state *istate)\n }\n \n struct path_found_data {\n+\t/**\n+\t * The path stored in 'dir', if non-empty, corresponds to the most-\n+\t * recent path that we checked where:\n+\t *\n+\t * 1. The path should be a directory, according to the index.\n+\t * 2. The path does not exist.\n+\t * 3. The parent path _does_ exist. (This may be the root of the\n+\t * working directory.)\n+\t */\n \tstruct strbuf dir;\n-\tint dir_found;\n \tsize_t lstat_count;\n };\n \n #define PATH_FOUND_DATA_INIT { \\\n-\t.dir = STRBUF_INIT, \\\n-\t.dir_found = 1 \\\n+\t.dir = STRBUF_INIT \\\n }\n \n static void clear_path_found_data(struct path_found_data *data)\n@@ -455,49 +462,108 @@ static void clear_path_found_data(struct path_found_data *data)\n \tstrbuf_release(&data->dir);\n }\n \n+/**\n+ * Return the length of the longest common substring that ends in a\n+ * slash ('/') to indicate the longest common parent directory. Returns\n+ * zero if no common directory exists.\n+ */\n+static size_t max_common_dir_prefix(const char *path1, const char *path2)\n+{\n+\tsize_t common_prefix = 0;\n+\tfor (size_t i = 0; path1[i] && path2[i]; i++) {\n+\t\tif (path1[i] != path2[i])\n+\t\t\tbreak;\n+\n+\t\t/*\n+\t\t * If they agree at a directory separator, then add one\n+\t\t * to make sure it is included in the common prefix string.\n+\t\t */\n+\t\tif (path1[i] == '/')\n+\t\t\tcommon_prefix = i + 1;\n+\t}\n+\n+\treturn common_prefix;\n+}\n+\n static int path_found(const char *path, struct path_found_data *data)\n {\n \tstruct stat st;\n-\tchar *newdir;\n+\tsize_t common_prefix;\n \n \t/*\n-\t * If dirname corresponds to a directory that doesn't exist, and this\n-\t * path starts with dirname, then path can't exist.\n+\t * If data->dir is non-empty, then it contains a path that doesn't\n+\t * exist, including an ending slash ('/'). If it is a prefix of 'path',\n+\t * then we can return 0.\n \t */\n-\tif (!data->dir_found && !memcmp(path, data->dir.buf, data->dir.len))\n+\tif (data->dir.len && !memcmp(path, data->dir.buf, data->dir.len))\n \t\treturn 0;\n \n \t/*\n-\t * If path itself exists, return 1.\n+\t * Otherwise, we must check if the current path exists. If it does, then\n+\t * return 1. The cached directory will be skipped until we come across\n+\t * a missing path again.\n \t */\n \tdata->lstat_count++;\n \tif (!lstat(path, &st))\n \t\treturn 1;\n \n \t/*\n-\t * Otherwise, path does not exist so we'll return 0...but we'll first\n-\t * determine some info about its parent directory so we can avoid\n-\t * lstat calls for future cache entries.\n+\t * At this point, we know that 'path' doesn't exist, and we know that\n+\t * the parent directory of 'data->dir' does exist. Let's set 'data->dir'\n+\t * to be the top-most non-existing directory of 'path'. If the first\n+\t * parent of 'path' exists, then we will act as though 'path'\n+\t * corresponds to a directory (by adding a slash).\n \t */\n-\tnewdir = strrchr(path, '/');\n-\tif (!newdir)\n-\t\treturn 0; /* Didn't find a parent dir; just return 0 now. */\n+\tcommon_prefix = max_common_dir_prefix(path, data->dir.buf);\n \n \t/*\n-\t * If path starts with directory (which we already lstat'ed and found),\n-\t * then no need to lstat parent directory again.\n+\t * At this point, 'path' and 'data->dir' have a common existing parent\n+\t * directory given by path[0..common_prefix] (which could have length 0).\n+\t * We \"grow\" the data->dir buffer by checking for existing directories\n+\t * along 'path'.\n \t */\n-\tif (data->dir_found && data->dir.buf &&\n-\t memcmp(path, data->dir.buf, data->dir.len))\n-\t\treturn 0;\n \n-\t/* Free previous dirname, and cache path's dirname */\n-\tstrbuf_reset(&data->dir);\n-\tstrbuf_add(&data->dir, path, newdir - path + 1);\n+\tstrbuf_setlen(&data->dir, common_prefix);\n+\twhile (1) {\n+\t\t/* Find the next directory in 'path'. */\n+\t\tconst char *rest = path + data->dir.len;\n+\t\tconst char *next_slash = strchr(rest, '/');\n \n-\tdata->lstat_count++;\n-\tdata->dir_found = !lstat(data->dir.buf, &st);\n+\t\t/*\n+\t\t * If there are no more slashes, then 'path' doesn't contain a\n+\t\t * non-existent _parent_ directory. Set 'data->dir' to be equal\n+\t\t * to 'path' plus an additional slash, so it can be used for\n+\t\t * caching in the future. The filename of 'path' is considered\n+\t\t * a non-existent directory.\n+\t\t *\n+\t\t * Note: if \"{path}/\" exists as a directory, then it will never\n+\t\t * appear as a prefix of other callers to this method, assuming\n+\t\t * the context from the clear_skip_worktree... methods. If this\n+\t\t * method is reused, then this must be reconsidered.\n+\t\t */\n+\t\tif (!next_slash) {\n+\t\t\tstrbuf_addstr(&data->dir, rest);\n+\t\t\tstrbuf_addch(&data->dir, '/');\n+\t\t\tbreak;\n+\t\t}\n \n+\t\t/*\n+\t\t * Now that we have a slash, let's grow 'data->dir' to include\n+\t\t * this slash, then test if we should stop.\n+\t\t */\n+\t\tstrbuf_add(&data->dir, rest, next_slash - rest + 1);\n+\n+\t\t/* If the parent dir doesn't exist, then stop here. */\n+\t\tdata->lstat_count++;\n+\t\tif (lstat(data->dir.buf, &st))\n+\t\t\treturn 0;\n+\t}\n+\n+\t/*\n+\t * At this point, 'data->dir' is equal to 'path' plus a slash character,\n+\t * and the parent directory of 'path' definitely exists. Moreover, we\n+\t * know that 'path' doesn't exist, or we would have returned 1 earlier.\n+\t */\n \treturn 0;\n }\n \n-- \ngitgitgadget\n"},{"id":"497812","messageId":"CABPp-BFd7Bk68Omdao5LS0sP5bK1WQ7V6dodB5x8EsncNARxNA@mail.gmail.com","threadId":"61657","inReplyTo":"pull.1754.v3.git.1719578605.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2024-06-28T15:07:44Z","receivedAt":"2024-06-28T15:07:57Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jun 28, 2024 at 5:43 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> While doing some investigation in a private monorepo with sparse-checkout\n> and a sparse index, I accidentally left a modified file outside of my\n> sparse-checkout cone. This caused my Git commands to slow to a crawl, so I\n> reran with GIT_TRACE2_PERF=1.\n>\n> While I was able to identify clear_skip_worktree_from_present_files() as the\n> culprit, it took longer than desired to figure out what was going on. This\n> series intends to both fix the performance issue (as much as possible) and\n> do some refactoring to make it easier to understand what is happening.\n>\n> In the end, I was able to reduce the number of lstat() calls in my case from\n> over 1.1 million to about 4,400, improving the time from 13.4s to 81ms on a\n> warm disk cache. (These numbers are from a test after v2, which somehow hit\n> the old caching algorithm even worse than my test in v1.)\n>\n>\n> Updates in v3\n> =============\n>\n> * Removed the incorrect paragraph in the commit message of patch 1.\n> * Replaced \"largest\" with \"longest\" in the final patch.\n>\n> Thanks, Stolee\n>\n> Derrick Stolee (5):\n> sparse-checkout: refactor skip worktree retry logic\n> sparse-index: refactor path_found()\n> sparse-index: use strbuf in path_found()\n> sparse-index: count lstat() calls\n> sparse-index: improve lstat caching of sparse paths\n>\n> sparse-index.c | 216 +++++++++++++++++++++++++++++++++++++------------\n> 1 file changed, 164 insertions(+), 52 deletions(-)\n>\n>\n> base-commit: 66ac6e4bcd111be3fa9c2a6b3fafea718d00678d\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1754%2Fderrickstolee%2Fclear-skip-speed-v3\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1754/derrickstolee/clear-skip-speed-v3\n> Pull-Request: https://github.com/gitgitgadget/git/pull/1754\n>\n> Range-diff vs v2:\n>\n> 1: 93d0baed0b0 ! 1: 0844cda94cf sparse-checkout: refactor skip worktree retry logic\n> @@ Commit message\n> stored in the index, so caching was introduced in d79d299352 (Accelerate\n> clear_skip_worktree_from_present_files() by caching, 2022-01-14).\n>\n> - If users are having trouble with the performance of this operation and\n> - don't care about paths outside of the sparse-checkout, they can disable\n> - them using the sparse.expectFilesOutsideOfPatterns config option\n> - introduced in ecc7c8841d (repo_read_index: add config to expect files\n> - outside sparse patterns, 2022-02-25).\n> -\n> This check is particularly confusing in the presence of a sparse index,\n> as a sparse tree entry corresponding to an existing directory must first\n> be expanded to a full index before examining the paths within. This is\n> 2: 69c3beaabf7 = 2: c242e2c9168 sparse-index: refactor path_found()\n> 3: 0a82e6b4183 = 3: ad63bf746ca sparse-index: use strbuf in path_found()\n> 4: 9549f5b8062 = 4: db6ded0df0d sparse-index: count lstat() calls\n> 5: 0cb344ac14f ! 5: 1f58e19691f sparse-index: improve lstat caching of sparse paths\n> @@ sparse-index.c: static void clear_path_found_data(struct path_found_data *data)\n> }\n>\n> +/**\n> -+ * Return the length of the largest common substring that ends in a\n> -+ * slash ('/') to indicate the largest common parent directory. Returns\n> ++ * Return the length of the longest common substring that ends in a\n> ++ * slash ('/') to indicate the longest common parent directory. Returns\n> + * zero if no common directory exists.\n> + */\n> +static size_t max_common_dir_prefix(const char *path1, const char *path2)\n>\n> --\n> gitgitgadget\n\nThis version covers the last two outstanding items.\n\nReviewed-by: Elijah Newren \n"},{"id":"497826","messageId":"xmqqwmm82760.fsf@gitster.g","threadId":"61657","inReplyTo":"CABPp-BFd7Bk68Omdao5LS0sP5bK1WQ7V6dodB5x8EsncNARxNA@mail.gmail.com","subject":"Re: [PATCH v3 0/5] sparse-index: improve clear_skip_worktree_from_present_files()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-06-28T19:34:15Z","receivedAt":"2024-06-28T19:34:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> This version covers the last two outstanding items.\n>\n> Reviewed-by: Elijah Newren \n\nThanks both. Will mark it for 'next'.\n\n"}]}