Re: [PATCH v2 0/4] Speed up unpack_trees()

> On Tue, Jul 31, 2018 at 01:31:31PM -0400, Ben Peart wrote:
>>
>>
>> On 7/31/2018 12:50 PM, Ben Peart wrote:
>>>
>>>
>>> On 7/31/2018 11:31 AM, Duy Nguyen wrote:
>>
>>>>
>>>>> In the performance game of whack-a-mole, that call to repair cache-tree
>>>>> is now looking quite expensive...
>>>>
>>>> Yeah and I think we can whack that mole too. I did some measurement.
>>>> Best case possible, we just need to scan through two indexes (one with
>>>> many good cache-tree, one with no cache-tree), compare and copy
>>>> cache-tree over. The scanning takes like 1% time of current repair
>>>> step and I suspect it's the hashing that takes most of the time. Of
>>>> course real world won't have such nice numbers, but I guess we could
>>>> maybe half cache-tree update/repair time.
>>>>
>>>
>>> I have some great profiling tools available so will take a look at this
>>> next and see exactly where the time is being spent.
>>
>> Good instincts.  In cache_tree_update, the heavy hitter is definitely
>> hash_object_file followed by has_object_file.
>>
>> Name                               	Inc %	     Inc
>> + git!cache_tree_update            	 12.4	   4,935
>> |+ git!update_one                  	 11.8	   4,706
>> | + git!update_one                 	 11.8	   4,706
>> |  + git!hash_object_file          	  6.1	   2,406
>> |  + git!has_object_file           	  2.0	     813
>> |  + OTHER <<vcruntime140d!strchr>>	  0.5	     203
>> |  + git!strbuf_addf               	  0.4	     155
>> |  + git!strbuf_release            	  0.4	     143
>> |  + git!strbuf_add                	  0.3	     121
>> |  + OTHER <<vcruntime140d!memcmp>>	  0.2	      93
>> |  + git!strbuf_grow               	  0.1	      25
> 
> Ben, if you work on this, this could be a good starting point. I will
> not work on this because I still have some other things to catch up
> and follow through. You can have my sign off if you reuse something
> from this patch
> 
> Even if it's a naive implementation, the initial numbers look pretty
> good. Without the patch we have
> 
> 18:31:05.970621 unpack-trees.c:1437     performance: 0.000001029 s: copy
> 18:31:05.975729 unpack-trees.c:1444     performance: 0.005082004 s: update
> 
> And with the patch
> 
> 18:31:13.295655 unpack-trees.c:1437     performance: 0.000198017 s: copy
> 18:31:13.296757 unpack-trees.c:1444     performance: 0.001075935 s: update
> 
> Time saving is about 80% by the look of this (best possible case
> because only the top tree needs to be hashed and written out).
> 
> -- 8< --
> diff --git a/cache-tree.c b/cache-tree.c
> index 6b46711996..67a4a93100 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -440,6 +440,147 @@ int cache_tree_update(struct index_state *istate, int flags)
>   	return 0;
>   }
>   
> +static int same(const struct cache_entry *a, const struct cache_entry *b)
> +{
> +	if (ce_stage(a) || ce_stage(b))
> +		return 0;
> +	if ((a->ce_flags | b->ce_flags) & CE_CONFLICTED)
> +		return 0;
> +	return a->ce_mode == b->ce_mode &&
> +	       !oidcmp(&a->oid, &b->oid);
> +}
> +
> +static int cache_tree_name_pos(const struct index_state *istate,
> +			       const struct strbuf *path)
> +{
> +	int pos;
> +
> +	if (!path->len)
> +		return 0;
> +
> +	pos = index_name_pos(istate, path->buf, path->len);
> +	if (pos >= 0)
> +		BUG("No no no, directory path must not exist in index");
> +	return -pos - 1;
> +}
> +
> +/*
> + * Locate the same cache-tree in two separate indexes. Check the
> + * cache-tree is still valid for the "to" index (i.e. it contains the
> + * same set of entries in the "from" index).
> + */
> +static int verify_one_cache_tree(const struct index_state *to,
> +				 const struct index_state *from,
> +				 const struct cache_tree *it,
> +				 const struct strbuf *path)
> +{
> +	int i, spos, dpos;
> +
> +	spos = cache_tree_name_pos(from, path);
> +	if (spos + it->entry_count > from->cache_nr)
> +		return -1;
> +
> +	dpos = cache_tree_name_pos(to, path);
> +	if (dpos + it->entry_count > to->cache_nr)
> +		return -1;
> +
> +	/* Can we quickly check head and tail and bail out early */
> +	if (!same(from->cache[spos], to->cache[spos]) ||
> +	    !same(from->cache[spos + it->entry_count - 1],
> +		  to->cache[spos + it->entry_count - 1]))
> +		return -1;
> +
> +	for (i = 1; i < it->entry_count - 1; i++)
> +		if (!same(from->cache[spos + i],
> +			  to->cache[dpos + i]))
> +			return -1;
> +
> +	return 0;
> +}
> +
> +static int verify_and_invalidate(struct index_state *to,
> +				 const struct index_state *from,
> +				 struct cache_tree *it,
> +				 struct strbuf *path)
> +{
> +	/*
> +	 * Optimistically verify the current tree first. Alternatively
> +	 * we could verify all the subtrees first then do this
> +	 * last. Any invalid subtree would also invalidates its
> +	 * ancestors.
> +	 */
> +	if (it->entry_count != -1 &&
> +	    verify_one_cache_tree(to, from, it, path))
> +		it->entry_count = -1;
> +
> +	/*
> +	 * If the current tree is valid, don't bother checking
> +	 * inside. All subtrees _should_ also be valid
> +	 */
> +	if (it->entry_count == -1) {
> +		int i, len = path->len;
> +
> +		for (i = 0; i < it->subtree_nr; i++) {
> +			struct cache_tree_sub *down = it->down[i];
> +
> +			if (!down || !down->cache_tree)
> +				continue;
> +
> +			strbuf_setlen(path, len);
> +			strbuf_add(path, down->name, down->namelen);
> +			strbuf_addch(path, '/');
> +			if (verify_and_invalidate(to, from,
> +						  down->cache_tree, path))
> +				return -1;
> +		}
> +		strbuf_setlen(path, len);
> +	}
> +	return 0;
> +}
> +
> +static struct cache_tree *duplicate_cache_tree(const struct cache_tree *src)
> +{
> +	struct cache_tree *dst;
> +	int i;
> +
> +	if (!src)
> +		return NULL;
> +
> +	dst = xmalloc(sizeof(*dst));
> +	dst->entry_count = src->entry_count;
> +	oidcpy(&dst->oid, &src->oid);
> +	dst->subtree_nr = src->subtree_nr;
> +	dst->subtree_alloc = dst->subtree_nr;
> +	ALLOC_ARRAY(dst->down, dst->subtree_alloc);
> +	for (i = 0; i < src->subtree_nr; i++) {
> +		struct cache_tree_sub *dsrc = src->down[i];
> +		struct cache_tree_sub *down;
> +
> +		FLEX_ALLOC_MEM(down, name, dsrc->name, dsrc->namelen);
> +		down->count = dsrc->count;
> +		down->namelen = dsrc->namelen;
> +		down->used = dsrc->used;
> +		down->cache_tree = duplicate_cache_tree(dsrc->cache_tree);
> +		dst->down[i] = down;
> +	}
> +	return dst;
> +}
> +
> +int cache_tree_copy(struct index_state *to, const struct index_state *from)
> +{
> +	struct cache_tree *it = duplicate_cache_tree(from->cache_tree);
> +	struct strbuf path = STRBUF_INIT;
> +	int ret;
> +
> +	if (to->cache_tree)
> +		BUG("Sorry merging cache-tree is not supported yet");
> +	ret = verify_and_invalidate(to, from, it, &path);
> +	to->cache_tree = it;
> +	to->cache_changed |= CACHE_TREE_CHANGED;
> +	strbuf_release(&path);
> +	return ret;
> +}
> +
>   static void write_one(struct strbuf *buffer, struct cache_tree *it,
>                         const char *path, int pathlen)
>   {
> diff --git a/cache-tree.h b/cache-tree.h
> index cfd5328cc9..6981da8e0d 100644
> --- a/cache-tree.h
> +++ b/cache-tree.h
> @@ -53,4 +53,6 @@ void prime_cache_tree(struct index_state *, struct tree *);
>   
>   extern int cache_tree_matches_traversal(struct cache_tree *, struct name_entry *ent, struct traverse_info *info);
>   
> +int cache_tree_copy(struct index_state *to, const struct index_state *from);
> +
>   #endif
> diff --git a/unpack-trees.c b/unpack-trees.c
> index cd0680f11e..cb3fdd42a6 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -1427,12 +1427,22 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
>   	ret = check_updates(o) ? (-2) : 0;
>   	if (o->dst_index) {
>   		if (!ret) {
> -			if (!o->result.cache_tree)
> +			if (!o->result.cache_tree) {
> +				uint64_t start = getnanotime();
> +#if 0
>   				o->result.cache_tree = cache_tree();
> -			if (!cache_tree_fully_valid(o->result.cache_tree))
> +#else
> +				cache_tree_copy(&o->result, o->src_index);
> +#endif
> +				trace_performance_since(start, "copy");
> +			}
> +			if (!cache_tree_fully_valid(o->result.cache_tree)) {
> +				uint64_t start = getnanotime();
>   				cache_tree_update(&o->result,
>   						  WRITE_TREE_SILENT |
>   						  WRITE_TREE_REPAIR);
> +				trace_performance_since(start, "update");
> +			}
>   		}
>   		move_index_extensions(&o->result, o->src_index);
>   		discard_index(o->dst_index);
> -- 8< --
>