Re: [PATCH v1 0/3] [RFC] Speeding up checkout (and merge, rebase, etc)

[Junio C Hamano <gitster@pobox.com>]

Duy Nguyen <pclouds@gmail.com> writes:

> diff --git a/unpack-trees.c b/unpack-trees.c
> index 66741130ae..9c791b55b2 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -642,6 +642,110 @@ 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 (dirmask != ((1 << n) - 1) || !S_ISDIR(names->mode) || !o->merge)
> +		return 0;

In other words, punt if (1) not all are directories, (2) the first
name entry given by the caller in names[] is not ISDIR(), or (3) we
are not merging i.e. not "Are we supposed to look at the index too?"
in unpack_callback().

I am not sure if the second one is doing us any good.  When
S_ISDIR(names->mode) is not true, then the bit in dirmask that
corresponds to the one in the entry[] traverse_trees() filled and
passed to us must be zero, so the dirmask check would reject such a
case anyway, no?

I would have moved !o->merge to the front, not for performance
reasons but to make it clear that this function helps an
optimization that matters only when we are walking tree(s) together
with the index.

> +	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);
> +}
> +
> +/*
> + * 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;
> +
> +	/*
> +	 * Do what unpack_callback() and unpack_nondirectories() normally
> +	 * do. But we do it in one function call (for even nested trees)
> +	 * instead.
> +	 *
> +	 * D/F conflicts and staged entries are not a concern because cache-tree
> +	 * would be invalidated and we would never get here in the first place.
> +	 */

We want to at least have

	if (!o->merge || ARRAY_SIZE(src) <= nr_names)
		BUG("");

here, I'd think.

> +	for (i = 0; i < nr_entries; i++) {
> +		struct cache_entry *tree_ce;
> +		int len, rc;
> +
> +		src[0] = o->src_index->cache[pos + i];
> +
> +		/* Do what unpack_nondirectories() normally does */
> +		len = ce_namelen(src[0]);
> +		tree_ce = xcalloc(1, cache_entry_size(len));

unpack_nondirectories() uses create_ce_entry() here.  Any reason why
we shouldn't use it and tell it to make a transient one?

> +		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);
> +	}
> +	trace_printf("Quick traverse over %d entries from %s to %s\n",
> +		     nr_entries,
> +		     o->src_index->cache[pos]->name,
> +		     o->src_index->cache[pos + nr_entries - 1]->name);
> +	return 0;
> +}

When I invented the cache-tree originally, primarily to speed up
writing of deeply nested trees, I had the "diff-index --cached"
optimization where a subtree with contents known to be the same as
the corresponding span in the index is entirely skipped without
getting even looked at.  I didn't realize this (now obvious)
optimization that scanning the index is faster than opening and
traversing trees (I was more focused on not even scanning, which
is what "diff-index --cached" optimization was about).

Nice.


> +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);
> +	int pos;
> +
> +	make_traverse_path(name, info, names);
> +	pos = index_name_pos(o->src_index, name, len);
> +	if (pos >= 0)
> +		BUG("This is so wrong. This is a directory and should not exist in index");
> +	pos = -pos - 1;
> +	/*
> +	 * There's no guarantee that pos points to the first entry of the
> +	 * directory. If the directory name is "letters" and there's another
> +	 * file named "letters.txt" in the index, pos will point to that file
> +	 * instead.
> +	 */

Is this trying to address the issue o->cache_bottom,
next_cache_entry(), etc. are trying to address?  i.e. an entry
"letters" appears at a different place relative to other entries in
a tree, depending on the type of the entry itself, so linear and
parallel scan of the index and the trees may miss matching entries
without backtracking?  If so, I am not sure if the loop below is
sufficient.

> +	while (pos < o->src_index->cache_nr) {
> +		const struct cache_entry *ce = o->src_index->cache[pos];
> +		if (ce_namelen(ce) > len &&
> +		    ce->name[len] == '/' &&
> +		    !memcmp(ce->name, name, len))
> +			break;
> +		pos++;
> +	}
> +	if (pos == o->src_index->cache_nr)
> +		BUG("This is still wrong");
> +	free(name);
> +	return pos;
> +}
> +

In anycase, nice progress.