On Fri, Jul 27, 2018 at 7:14 PM Junio C Hamano <gitster@xxxxxxxxx> wrote:
>
> Duy Nguyen <pclouds@xxxxxxxxx> 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?
You're right. This code kinda evolved from the diff_index_cached and I
forgot about this.
> > + 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?
That one takes a struct name_entry to recreate the path, which will
not be correct since we will go deep in subdirs in this loop as well.
Side note. I notice that I allocate/free (and memcpy even) more than I
should. The directory part in ce->name for example will never change.
And if the old tree_ce is large enough, we could avoid reallocation
too.
> > + 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.
I would still love to take this further. We should have cache-tree for
like 90% of HEAD, and even if we do 2 or 3 merge where the other trees
are very different, we should be able to just "recreate" HEAD from the
index by using cache-tree.
This is hard though, much trickier than dealing with this case. And I
guess that the benefit will be much smaller so probably not worth the
complexity.
> > +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.
No it's because index_name_pos does not necessarily give us the right
starting point. This is why t6020 fails, where the index has "letters"
and "letters/foo" when the cache-tree for "letters" is valid. -pos-1
would give me the position of "letters", not "letters/foo". Ideally we
should be able to get this starting index from cache-tree code since
we're searching for it in there anyway. Then this code could be gone.
The cache_bottom stuff still scares me though. I reuse mark_ce_used()
with hope that it deals with cache_bottom correctly. And as you note,
the lookahead code to deal with D/F conflicts could probably mess up
here too. You're probably the best one to check this ;-)
> > + 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.
Just FYI I'm still trying to reduce execution time further and this
change happens to half traverse_trees() time (which is a huge deal)
diff --git a/unpack-trees.c b/unpack-trees.c
index f0be9f298d..a2e63ad5bf 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -201,7 +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,
- ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
+ ADD_CACHE_JUST_APPEND |
ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
}
static struct cache_entry *dup_entry(const struct cache_entry *ce)
It's probably not the right thing to do of course. But perhaps we
could do something in that direction (e.g. validate everything at the
end of traverse_by_cache_tree...)
--
Duy
