Elijah Newren wrote:
> Rather than lstat()'ing every SKIP_WORKTREE path, take advantage of the
> fact that entire directories will often be missing, especially for cone
> mode and even more so ever since commit 55dfcf9591 ("sparse-checkout:
> clear tracked sparse dirs", 2021-09-08). If we have already determined
> that the parent directory of a file (or any other previous ancestor)
> does not exist, then we already know the file cannot exist and do not
> need to lstat() it separately.
>
> Granted, the cost of ensure_skip_worktree_means_skip_worktree() might
> be considered a bit high for non-cone mode since it might now lstat()
> every SKIP_WORKTREE path when the index is loaded (an O(N) cost, with
> N the number of SKIP_WORKTREE paths), but non-cone mode users already
> have to deal with the O(N*M) cost (with N=the number of tracked files
> and M=the number of sparsity patterns), so this should be reasonable.
>
Did you write/run any performance tests to see how this optimization changed
the execution time? If not, running the `p2000` performance tests against
the patch series base, [3/5], and [5/5] would provide some really helpful
insight into the cost of `ensure_skip_worktree_means_skip_worktree`, then
how much this optimization improves it.
> Signed-off-by: Elijah Newren <newren@xxxxxxxxx>
> ---
> sparse-index.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++-
> 1 file changed, 103 insertions(+), 2 deletions(-)
>
> diff --git a/sparse-index.c b/sparse-index.c
> index 79d50e444c..608782e255 100644
> --- a/sparse-index.c
> +++ b/sparse-index.c
> @@ -341,18 +341,117 @@ void ensure_correct_sparsity(struct index_state *istate)
> ensure_full_index(istate);
> }
>
> +struct path_cache_entry {
> + struct hashmap_entry ent;
> + const char *path;
> + int path_length;
> + int is_present;
> +};
> +
> +static int path_cache_cmp(const void *unused,
> + const struct hashmap_entry *entry1,
> + const struct hashmap_entry *entry2,
> + const void *also_unused)
> +{
> + const struct path_cache_entry *e1, *e2;
> +
> + e1 = container_of(entry1, const struct path_cache_entry, ent);
> + e2 = container_of(entry2, const struct path_cache_entry, ent);
> + if (e1->path_length != e2->path_length)
> + return e1->path_length - e2->path_length;
> + return memcmp(e1->path, e2->path, e1->path_length);
> +}
> +
> +static struct path_cache_entry *find_path_cache_entry(struct hashmap *map,
> + const char *str,
> + int str_length)
> +{
> + struct path_cache_entry entry;
> + hashmap_entry_init(&entry.ent, memhash(str, str_length));
> + entry.path = str;
> + entry.path_length = str_length;
> + return hashmap_get_entry(map, &entry, ent, NULL);
> +}
> +
> +static void record(struct hashmap *path_cache,
> + struct mem_pool *pool,
> + const char *path,
> + int path_length,
> + int found)
> +{
> + struct path_cache_entry *entry;
> +
> + entry = mem_pool_alloc(pool, sizeof(*entry));
> + hashmap_entry_init(&entry->ent, memhash(path, path_length));
> + entry->path = path;
> + entry->path_length = path_length;
> + entry->is_present = found;
> + hashmap_add(path_cache, &entry->ent);
> +}
> +
> +static int path_found(struct hashmap *path_cache, struct mem_pool *pool,
> + const char *path, int path_length)
> +{
> + struct stat st;
> + int found;
> + const char *dirsep = path + path_length - 1;
> + const char *tmp;
> +
> + /* Find directory separator; memrchr is sadly glibc-specific */
> + while (dirsep > path && *dirsep != '/')
> + dirsep--;
> +
> + /* If parent of path doesn't exist, no point lstat'ing path... */
> + if (dirsep > path) {
> + struct path_cache_entry *entry;
> + int new_length, parent_found;
> +
> + /* First, check if path's parent's existence was cached */
> + new_length = dirsep - path;
> + entry = find_path_cache_entry(path_cache, path, new_length);
> + if (entry)
> + parent_found = entry->is_present;
> + else
> + parent_found = path_found(path_cache, pool,
> + path, new_length);
> +
> + if (!parent_found) {
> + /* path can't exist if parent dir doesn't */
> + record(path_cache, pool, path, path_length, 0);
> + return 0;
> + } /* else parent was found so must check path itself too... */
> + }
> +
> + /* Okay, parent dir exists, so we have to check original path */
> +
> + /* Make sure we have a NUL-terminated string to pass to lstat */
> + tmp = path;
> + if (path[path_length])
> + tmp = mem_pool_strndup(pool, path, path_length);
> + /* Determine if path exists */
> + found = !lstat(tmp, &st);
> +
> + record(path_cache, pool, path, path_length, found);
> + return found;
> +}
> +
> void ensure_skip_worktree_means_skip_worktree(struct index_state *istate)
> {
> + struct hashmap path_cache = HASHMAP_INIT(path_cache_cmp, NULL);
> + struct mem_pool pool;
> +
> int i;
> +
> if (!core_apply_sparse_checkout)
> return;
>
> + mem_pool_init(&pool, 32*1024);
> restart:
> for (i = 0; i < istate->cache_nr; i++) {
> struct cache_entry *ce = istate->cache[i];
> - struct stat st;
>
> - if (ce_skip_worktree(ce) && !lstat(ce->name, &st)) {
> + if (ce_skip_worktree(ce) &&
> + path_found(&path_cache, &pool, ce->name, strlen(ce->name))) {
> if (S_ISSPARSEDIR(ce->ce_mode)) {
> ensure_full_index(istate);
> goto restart;
> @@ -360,6 +459,8 @@ void ensure_skip_worktree_means_skip_worktree(struct index_state *istate)
> ce->ce_flags &= ~CE_SKIP_WORKTREE;
> }
> }
> + hashmap_clear(&path_cache);
> + mem_pool_discard(&pool, 0);
> }
>
>
