Re: [PATCH v4 3/5] unpack-trees: optimize walking same trees with cache-tree

> In order to merge one or many trees with the index, unpack-trees code
> walks multiple trees in parallel with the index and performs n-way
> merge. If we find out at start of a directory that all trees are the
> same (by comparing OID) and cache-tree happens to be available for
> that directory as well, we could avoid walking the trees because we
> already know what these trees contain: it's flattened in what's called
> "the index".
> 
> The upside is of course a lot less I/O since we can potentially skip
> lots of trees (think subtrees). We also save CPU because we don't have
> to inflate and apply the deltas. The downside is of course more
> fragile code since the logic in some functions are now duplicated
> elsewhere.
> 
> "checkout -" with this patch on webkit.git (275k files):
> 
>      baseline      new
>    --------------------------------------------------------------------
>      0.056651714   0.080394752 s:  read cache .git/index
>      0.183101080   0.216010838 s:  preload index
>      0.008584433   0.008534301 s:  refresh index
>      0.633767589   0.251992198 s:   traverse_trees
>      0.340265448   0.377031383 s:   check_updates
>      0.381884638   0.372768105 s:   cache_tree_update
>      1.401562947   1.045887251 s:  unpack_trees
>      0.338687914   0.314983512 s:  write index, changed mask = 2e
>      0.411927922   0.062572653 s:    traverse_trees
>      0.000023335   0.000022544 s:    check_updates
>      0.423697246   0.073795585 s:   unpack_trees
>      0.423708360   0.073807557 s:  diff-index
>      2.559524127   1.938191592 s: git command: git checkout -
> 
> Another measurement from Ben's running "git checkout" with over 500k
> trees (on the whole series):
> 
>      baseline        new
>    ----------------------------------------------------------------------
>      0.535510167     0.556558733     s: read cache .git/index
>      0.3057373       0.3147105       s: initialize name hash
>      0.0184082       0.023558433     s: preload index
>      0.086910967     0.089085967     s: refresh index
>      7.889590767     2.191554433     s: unpack trees
>      0.120760833     0.131941267     s: update worktree after a merge
>      2.2583504       2.572663167     s: repair cache-tree
>      0.8916137       0.959495233     s: write index, changed mask = 28
>      3.405199233     0.2710663       s: unpack trees
>      0.000999667     0.0021554       s: update worktree after a merge
>      3.4063306       0.273318333     s: diff-index
>      16.9524923      9.462943133     s: git command: git.exe checkout
> 
> This command calls unpack_trees() twice, the first time on 2way merge
> and the second 1way merge. In both times, "unpack trees" time is
> reduced to one third. Overall time reduction is not that impressive of
> course because index operations take a big chunk. And there's that
> repair cache-tree line.
> 
> PS. A note about cache-tree invalidation and the use of it in this
> code.
> 
> We do invalidate cache-tree in _source_ index when we add new entries
> to the (temporary) "result" index. But we also use the cache-tree from
> source index in this optimization. Does this mean we end up having no
> cache-tree in the source index to activate this optimization?
> 
> The answer is twisted: the order of finding a good cache-tree and
> invalidating it matters. In this case we check for a good cache-tree
> first in all_trees_same_as_cache_tree(), then we start to merge things
> and potentially invalidate that same cache-tree in the process. Since
> cache-tree invalidation happens after the optimization kicks in, we're
> still good. But we may lose that cache-tree at the very first
> call_unpack_fn() call in traverse_by_cache_tree().
> 
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>   unpack-trees.c | 127 +++++++++++++++++++++++++++++++++++++++++++++++++
>   1 file changed, 127 insertions(+)
> 
> diff --git a/unpack-trees.c b/unpack-trees.c
> index b237eaa0f2..07456d0fb2 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -644,6 +644,102 @@ static inline int are_same_oid(struct name_entry *name_j, struct name_entry *nam
>   	return name_j->oid && name_k->oid && !oidcmp(name_j->oid, name_k->oid);
>   }
>   
> +static int all_trees_same_as_cache_tree(int n, unsigned long dirmask,
> +					struct name_entry *names,
> +					struct traverse_info *info)
> +{
> +	struct unpack_trees_options *o = info->data;
> +	int i;
> +
> +	if (!o->merge || dirmask != ((1 << n) - 1))
> +		return 0;
> +
> +	for (i = 1; i < n; i++)
> +		if (!are_same_oid(names, names + i))
> +			return 0;
> +
> +	return cache_tree_matches_traversal(o->src_index->cache_tree, names, info);
> +}
> +
> +static int index_pos_by_traverse_info(struct name_entry *names,
> +				      struct traverse_info *info)
> +{
> +	struct unpack_trees_options *o = info->data;
> +	int len = traverse_path_len(info, names);
> +	char *name = xmalloc(len + 1 /* slash */ + 1 /* NUL */);
> +	int pos;
> +
> +	make_traverse_path(name, info, names);
> +	name[len++] = '/';
> +	name[len] = '\0';
> +	pos = index_name_pos(o->src_index, name, len);
> +	if (pos >= 0)
> +		BUG("This is a directory and should not exist in index");
> +	pos = -pos - 1;
> +	if (!starts_with(o->src_index->cache[pos]->name, name) ||
> +	    (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name)))
> +		BUG("pos must point at the first entry in this directory");
> +	free(name);
> +	return pos;
> +}
> +
> +/*
> + * Fast path if we detect that all trees are the same as cache-tree at this
> + * path. We'll walk these trees recursively using cache-tree/index instead of
> + * ODB since already know what these trees contain.
> + */
> +static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
> +				  struct name_entry *names,
> +				  struct traverse_info *info)
> +{
> +	struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
> +	struct unpack_trees_options *o = info->data;
> +	int i, d;
> +
> +	if (!o->merge)
> +		BUG("We need cache-tree to do this optimization");
> +
> +	/*
> +	 * Do what unpack_callback() and unpack_nondirectories() normally
> +	 * do. But we walk all paths recursively in just one loop instead.

> +	 *
> +	 * D/F conflicts and higher stage entries are not a concern
> +	 * because cache-tree would be invalidated and we would never
> +	 * get here in the first place.
> +	 */
> +	for (i = 0; i < nr_entries; i++) {
> +		struct cache_entry *tree_ce;
> +		int len, rc;
> +
> +		src[0] = o->src_index->cache[pos + i];
> +
> +		len = ce_namelen(src[0]);
> +		tree_ce = xcalloc(1, cache_entry_size(len));
> +
> +		tree_ce->ce_mode = src[0]->ce_mode;
> +		tree_ce->ce_flags = create_ce_flags(0);
> +		tree_ce->ce_namelen = len;
> +		oidcpy(&tree_ce->oid, &src[0]->oid);
> +		memcpy(tree_ce->name, src[0]->name, len + 1);
> +
> +		for (d = 1; d <= nr_names; d++)
> +			src[d] = tree_ce;
> +
> +		rc = call_unpack_fn((const struct cache_entry * const *)src, o);

> +		free(tree_ce);
> +		if (rc < 0)
> +			return rc;
> +
> +		mark_ce_used(src[0], o);
> +	}
> +	if (o->debug_unpack)
> +		printf("Unpacked %d entries from %s to %s using cache-tree\n",
> +		       nr_entries,
> +		       o->src_index->cache[pos]->name,
> +		       o->src_index->cache[pos + nr_entries - 1]->name);
> +	return 0;
> +}
> +
>   static int traverse_trees_recursive(int n, unsigned long dirmask,
>   				    unsigned long df_conflicts,
>   				    struct name_entry *names,
> @@ -655,6 +751,27 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,
>   	void *buf[MAX_UNPACK_TREES];
>   	struct traverse_info newinfo;
>   	struct name_entry *p;
> +	int nr_entries;
> +
> +	nr_entries = all_trees_same_as_cache_tree(n, dirmask, names, info);
> +	if (nr_entries > 0) {
> +		struct unpack_trees_options *o = info->data;
> +		int pos = index_pos_by_traverse_info(names, info);
> +
> +		if (!o->merge || df_conflicts)
> +			BUG("Wrong condition to get here buddy");
> +
> +		/*
> +		 * All entries up to 'pos' must have been processed
> +		 * (i.e. marked CE_UNPACKED) at this point. But to be safe,
> +		 * save and restore cache_bottom anyway to not miss
> +		 * unprocessed entries before 'pos'.
> +		 */
> +		bottom = o->cache_bottom;
> +		ret = traverse_by_cache_tree(pos, nr_entries, n, names, info);
> +		o->cache_bottom = bottom;

> +		return ret;
> +	}
>   
>   	p = names;
>   	while (!p->mode)
> @@ -814,6 +931,11 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info, con
>   	return ce;
>   }
>   
> +/*
> + * Note that traverse_by_cache_tree() duplicates some logic in this function
> + * without actually calling it. If you change the logic here you may need to
> + * check and change there as well.
> + */
>   static int unpack_nondirectories(int n, unsigned long mask,
>   				 unsigned long dirmask,
>   				 struct cache_entry **src,
> @@ -998,6 +1120,11 @@ static void debug_unpack_callback(int n,
>   		debug_name_entry(i, names + i);
>   }
>   
> +/*
> + * Note that traverse_by_cache_tree() duplicates some logic in this function
> + * without actually calling it. If you change the logic here you may need to
> + * check and change there as well.
> + */
>   static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
>   {
>   	struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
>