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

[Duy Nguyen <pclouds@gmail.com>]

On Fri, Jul 27, 2018 at 7:14 PM Junio C Hamano <gitster@pobox.com> wrote:
>
> 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?

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