Re: [PATCH v2 4/4] unpack-trees: cheaper index update when walking by cache-tree

[Elijah Newren <newren@gmail.com>]

On Sun, Jul 29, 2018 at 3:36 AM Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
>
> With the new cache-tree, we could mostly avoid I/O (due to odb access)
> the code mostly becomes a loop of "check this, check that, add the
> entry to the index". We could skip a couple checks in this giant loop
> to go faster:
>
> - We know here that we're copying entries from the source index to the
>   result one. All paths in the source index must have been validated
>   at load time already (and we're not taking strange paths from tree
>   objects) which means we can skip verify_path() without compromise.
>
> - We also know that D/F conflicts can't happen for all these entries
>   (since cache-tree and all the trees are the same) so we can skip
>   that as well.
>
> This gives rather nice speedups for "unpack trees" rows where "unpack
> trees" time is now cut in half compared to when
> traverse_by_cache_tree() is added, or 1/7 of the original "unpack
> trees" time.
>
>    baseline      cache-tree    this patch
>  --------------------------------------------------------------------
>    0.018239226   0.019365414   0.020519621 s: read cache .git/index
>    0.052541655   0.049605548   0.048814384 s: preload index
>    0.001537598   0.001571695   0.001575382 s: refresh index
>    0.168167768   0.049677212   0.024719308 s: unpack trees
>    0.002897186   0.002845256   0.002805555 s: update worktree after a merge
>    0.131661745   0.136597522   0.134891617 s: repair cache-tree
>    0.075389117   0.075422517   0.074832291 s: write index, changed mask = 2a
>    0.111702023   0.032813253   0.008616479 s: unpack trees
>    0.000023245   0.000022002   0.000026630 s: update worktree after a merge
>    0.111793866   0.032933140   0.008714071 s: diff-index
>    0.587933288   0.398924370   0.380452871 s: git command: /home/pclouds/w/git/git
>
> Total saving of this new patch looks even less impressive, now that
> time spent in unpacking trees is so small. Which is why the next
> attempt should be on that "repair cache-tree" line.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  cache.h        |  1 +
>  read-cache.c   |  3 ++-
>  unpack-trees.c | 27 +++++++++++++++++++++++++++
>  unpack-trees.h |  1 +
>  4 files changed, 31 insertions(+), 1 deletion(-)
>
> diff --git a/cache.h b/cache.h
> index 8b447652a7..e6f7ee4b64 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -673,6 +673,7 @@ extern int index_name_pos(const struct index_state *, const char *name, int name
>  #define ADD_CACHE_JUST_APPEND 8                /* Append only; tree.c::read_tree() */
>  #define ADD_CACHE_NEW_ONLY 16          /* Do not replace existing ones */
>  #define ADD_CACHE_KEEP_CACHE_TREE 32   /* Do not invalidate cache-tree */
> +#define ADD_CACHE_SKIP_VERIFY_PATH 64  /* Do not verify path */
>  extern int add_index_entry(struct index_state *, struct cache_entry *ce, int option);
>  extern void rename_index_entry_at(struct index_state *, int pos, const char *new_name);
>
> diff --git a/read-cache.c b/read-cache.c
> index e865254bea..b0b5df5de7 100644
> --- a/read-cache.c
> +++ b/read-cache.c
> @@ -1170,6 +1170,7 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e
>         int ok_to_add = option & ADD_CACHE_OK_TO_ADD;
>         int ok_to_replace = option & ADD_CACHE_OK_TO_REPLACE;
>         int skip_df_check = option & ADD_CACHE_SKIP_DFCHECK;
> +       int skip_verify_path = option & ADD_CACHE_SKIP_VERIFY_PATH;
>         int new_only = option & ADD_CACHE_NEW_ONLY;
>
>         if (!(option & ADD_CACHE_KEEP_CACHE_TREE))
> @@ -1210,7 +1211,7 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e
>
>         if (!ok_to_add)
>                 return -1;
> -       if (!verify_path(ce->name, ce->ce_mode))
> +       if (!skip_verify_path && !verify_path(ce->name, ce->ce_mode))
>                 return error("Invalid path '%s'", ce->name);
>
>         if (!skip_df_check &&
> diff --git a/unpack-trees.c b/unpack-trees.c
> index c33ebaf001..dc62afd968 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -201,6 +201,7 @@ static int do_add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
>
>         ce->ce_flags = (ce->ce_flags & ~clear) | set;
>         return add_index_entry(&o->result, ce,
> +                              o->extra_add_index_flags |
>                                ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
>  }
>
> @@ -701,6 +702,24 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
>         if (!o->merge)
>                 BUG("We need cache-tree to do this optimization");
>
> +       /*
> +        * Try to keep add_index_entry() as fast as possible since
> +        * we're going to do a lot of them.
> +        *
> +        * Skipping verify_path() should totally be safe because these
> +        * paths are from the source index, which must have been
> +        * verified.
> +        *
> +        * Skipping D/F and cache-tree validation checks is trickier
> +        * because it assumes what n-merge code would do when all
> +        * trees and the index are the same. We probably could just
> +        * optimize those code instead (e.g. we don't invalidate that
> +        * many cache-tree, but the searching for them is very
> +        * expensive).
> +        */
> +       o->extra_add_index_flags = ADD_CACHE_SKIP_DFCHECK;
> +       o->extra_add_index_flags |= ADD_CACHE_SKIP_VERIFY_PATH;
> +

In sum of this whole patch, you notice that the Nway_merge functions
are still a bit of a bottleneck, but you know you have a special case
where you want them to put an entry in the index that matches what is
already there, so you try to set some extra flags to short-circuit
part of their logic and get to what you know is the correct result.

This seems a little scary to me.  I think it's probably safe as long
as o->fn is one of {oneway_merge, twoway_merge, threeway_merge,
bind_merge} (the cases you have in mind and which the current code
uses), but the caller isn't limited to those.  Right now in
diff-lib.c, there's a caller that has their own function, oneway_diff.
More could be added in the future.

If we're going to go this route, I think we should first check that
o->fn is one of those known safe functions.  And if we're going that
route, the comments I bring up on patch 2 about possibly avoiding
call_unpack_fn() altogether might even obviate this patch while
speeding things up more.

>         /*
>          * Do what unpack_callback() and unpack_nondirectories() normally
>          * do. But we walk all paths recursively in just one loop instead.
> @@ -742,6 +761,7 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
>
>                 mark_ce_used(src[0], o);
>         }
> +       o->extra_add_index_flags = 0;
>         free(tree_ce);
>         if (o->debug_unpack)
>                 printf("Unpacked %d entries from %s to %s using cache-tree\n",
> @@ -1561,6 +1581,13 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
>                 if (!ret) {
>                         if (!o->result.cache_tree)
>                                 o->result.cache_tree = cache_tree();
> +                       /*
> +                        * TODO: Walk o.src_index->cache_tree, quickly check
> +                        * if o->result.cache has the exact same content for
> +                        * any valid cache-tree in o.src_index, then we can
> +                        * just copy the cache-tree over instead of hashing a
> +                        * new tree object.
> +                        */

Interesting.  I really don't know how cache_tree works...but if we
avoided calling call_unpack_fn, and thus left the original index entry
in place instead of replacing it with an equal one, would that as a
side effect speed up the cache_tree_valid/cache_tree_update calls for
us?  Or is there still work here?

>                         if (!cache_tree_fully_valid(o->result.cache_tree))
>                                 cache_tree_update(&o->result,
>                                                   WRITE_TREE_SILENT |
> diff --git a/unpack-trees.h b/unpack-trees.h
> index c2b434c606..94e1b14078 100644
> --- a/unpack-trees.h
> +++ b/unpack-trees.h
> @@ -80,6 +80,7 @@ struct unpack_trees_options {
>         struct index_state result;
>
>         struct exclude_list *el; /* for internal use */
> +       unsigned int extra_add_index_flags;
>  };
>
>  extern int unpack_trees(unsigned n, struct tree_desc *t,
> --
> 2.18.0.656.gda699b98b3