Re: [PATCH v1 0/3] [RFC] Speeding up checkout (and merge, rebase, etc)
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Jul 27, 2018, 17:14 UTC
- Message-ID
- <xmqqpnz8ob2x.fsf@gitster-ct.c.googlers.com>
- In-Reply-To
- <20180727154241.GA21288@duynguyen.home>
Duy Nguyen <pclouds@gmail.com> writes:
Show 17 quoted lines
> 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.
Show 28 quoted lines
> + 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.
Show 9 quoted lines
> + 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?
Show 22 quoted lines
> + 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.
Show 19 quoted lines
> +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.
Show 14 quoted lines
> + 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.