Re: [PATCH 27/27] cache-tree: integrate with sparse directory entries

[Elijah Newren <newren@gmail.com>]

On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Derrick Stolee <dstolee@microsoft.com>
>
> The cache-tree extension was previously disabled with sparse indexes.
> However, the cache-tree is an important performance feature for commands
> like 'git status' and 'git add'. Integrate it with sparse directory
> entries.
>
> When writing a sparse index, completely clear and recalculate the cache
> tree. By starting from scratch, the only integration necessary is to
> check if we hit a sparse directory entry and create a leaf of the
> cache-tree that has an entry_count of one and no subtrees.
>
> Once the cache-tree exists within a sparse index, we finally get
> improved performance. I test the sparse index performance using a
> private monorepo with over 2.1 million files at HEAD, but with a
> sparse-checkout definition that has only 68,000 paths in the populated
> cone. The sparse index has about 2,000 sparse directory entries. I
> compare three scenarios:

How many .gitignore entries does this monorepo have?  What percentage
of those are populated for #2 and #3?

Can a testcase be devised that others can repeat?  For example, I
created https://github.com/newren/gvfs-like-git-bomb once upon a time
to create a very small repository with a very large index and a lot of
skip-worktree entries, mostly to test some stuff that someone (Ben
Peart?) mentioned as being slow and verify for myself that it wasn't
Windows specific.

>  1. Use the full index. The index size is ~186 MB.
>  2. Use the sparse index. The index size is ~5.5 MB.
>  3. Use a commit where HEAD matches the populated set. The full index
>     size is ~5.3MB.

I'm not sure I'm understanding the difference between #2 and #3, other
than #3 is smaller.  How did you form #2?  Also, what do you mean by
"full index size" for #3, when it's the smallest?  Isn't that index
the most sparse (or least full)?  Or is it an index for a different
commit entirely that has far fewer files in it?

> The third benchmark is included as a theoretical optimium for a

s/optimium/optimum/

> repository of the same object database.

This I'm also not understanding, but maybe this goes back to not
understanding the difference in how #2 and #3 are constructed.

> First, a clean 'git status' improves from 3.1s to 240ms.
>
> Benchmark #1: full index (git status)
>   Time (mean ± σ):      3.167 s ±  0.036 s    [User: 2.006 s, System: 1.078 s]
>   Range (min … max):    3.100 s …  3.208 s    10 runs
>
> Benchmark #2: sparse index (git status)
>   Time (mean ± σ):     239.5 ms ±   8.1 ms    [User: 189.4 ms, System: 226.8 ms]
>   Range (min … max):   226.0 ms … 251.9 ms    13 runs
>
> Benchmark #3: small tree (git status)
>   Time (mean ± σ):     195.3 ms ±   4.5 ms    [User: 116.5 ms, System: 84.4 ms]
>   Range (min … max):   188.8 ms … 202.8 ms    15 runs

Always nice to see a speedup factor greater than 10.  :-)

>
> The optimimum is still 45ms faster. This is due in part to the 2,000+

s/optimimum/optimum/

> sparse directory entries, but there might be other optimizations to make
> in the sparse-index case. In particular, I find that this performance
> difference disappears when I disable FS Monitor, which is somewhat
> disabled in the sparse-index case, but might still be adding overhead.

The FS monitor wording is unclear to me; it feels like multiple negatives.

> The performance numbers for 'git add .' are much closer to optimal:
>
> Benchmark #1: full index (git add .)
>   Time (mean ± σ):      3.076 s ±  0.022 s    [User: 2.065 s, System: 0.943 s]
>   Range (min … max):    3.044 s …  3.116 s    10 runs
>
> Benchmark #2: sparse index (git add .)
>   Time (mean ± σ):     218.0 ms ±   6.6 ms    [User: 195.7 ms, System: 206.6 ms]
>   Range (min … max):   209.8 ms … 228.2 ms    13 runs
>
> Benchmark #3: small tree (git add .)
>   Time (mean ± σ):     217.6 ms ±   5.4 ms    [User: 131.9 ms, System: 86.7 ms]
>   Range (min … max):   212.1 ms … 228.4 ms    14 runs
>
> In this test, I also used "echo >>README.md" to append a line to the
> README.md file, so the 'git add .' command is doing _something_ other
> than a no-op. Without this edit (and FS Monitor enabled) the small
> tree case again gains about 30ms on the sparse index case.

Meaning the small tree is 30 ms faster than reported here, or 30 ms
slower, or that both sparse index and small tree are faster but the
small tree decreases its time more than the sparse index one does?

Sorry, I don't mean to be dense, I'm just struggling with
understanding words today it seems.  (Also, it seems like there's a
joke in there about me being "dense" in a review of a "sparse"
feature...but I'm not quite coming up with it.)

> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  cache-tree.c   | 18 ++++++++++++++++++
>  sparse-index.c | 10 +++++++++-
>  2 files changed, 27 insertions(+), 1 deletion(-)
>
> diff --git a/cache-tree.c b/cache-tree.c
> index 5f07a39e501..9da6a4394e0 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -256,6 +256,24 @@ static int update_one(struct cache_tree *it,
>
>         *skip_count = 0;
>
> +       /*
> +        * If the first entry of this region is a sparse directory
> +        * entry corresponding exactly to 'base', then this cache_tree
> +        * struct is a "leaf" in the data structure, pointing to the
> +        * tree OID specified in the entry.
> +        */
> +       if (entries > 0) {
> +               const struct cache_entry *ce = cache[0];
> +
> +               if (S_ISSPARSEDIR(ce) &&
> +                   ce->ce_namelen == baselen &&
> +                   !strncmp(ce->name, base, baselen)) {
> +                       it->entry_count = 1;
> +                       oidcpy(&it->oid, &ce->oid);
> +                       return 1;
> +               }
> +       }
> +
>         if (0 <= it->entry_count && has_object_file(&it->oid))
>                 return it->entry_count;
>
> diff --git a/sparse-index.c b/sparse-index.c
> index a201f3b905c..9ea3b321400 100644
> --- a/sparse-index.c
> +++ b/sparse-index.c
> @@ -181,7 +181,11 @@ int convert_to_sparse(struct index_state *istate)
>         istate->cache_nr = convert_to_sparse_rec(istate,
>                                                  0, 0, istate->cache_nr,
>                                                  "", 0, istate->cache_tree);
> -       istate->drop_cache_tree = 1;
> +
> +       /* Clear and recompute the cache-tree */
> +       cache_tree_free(&istate->cache_tree);
> +       cache_tree_update(istate, 0);
> +
>         istate->sparse_index = 1;
>         trace2_region_leave("index", "convert_to_sparse", istate->repo);
>         return 0;
> @@ -278,6 +282,10 @@ void ensure_full_index(struct index_state *istate)
>
>         free(full);
>
> +       /* Clear and recompute the cache-tree */
> +       cache_tree_free(&istate->cache_tree);
> +       cache_tree_update(istate, 0);
> +
>         trace2_region_leave("index", "ensure_full_index", istate->repo);
>  }
>
> --
> gitgitgadget

This is very exciting work!!