Re: [PATCH v3 2/4] unpack-trees: optimize walking same trees with cache-tree

On Wed, Aug 8, 2018 at 8:23 PM Elijah Newren [off-list ref] wrote:

quoted

diff --git a/unpack-trees.c b/unpack-trees.c
index a32ddee159..ba3d2e947e 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c

@@ -644,6 +644,102 @@ 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 (!o->merge || dirmask != ((1 << n) - 1))
+               return 0;
+
+       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);
+}

I was curious whether this could also be extended in the case of a
merge; as long as HEAD and MERGE have the same tree, even if the base
commit doesn't match, we can still just use the tree from HEAD which
should be in the current index/cache_tree.  However, it'd be a
somewhat odd history for HEAD and MERGE to match on some significantly
sized tree when the base commit doesn't also match.

I did have 3-way merge in mind when I wrote this patch. Yes it's
unlikely except one case (I think). Consider a large "mono repo" that
contains stuff from many teams. When you branch out for your own team,
then most of your changes will be in a few directories, the rest of
the code base untouched. In that case we could have a lot of same
trees in subdirectories outside the stuff your team touches. This of
course assumes that your team keeps the same base static for some
time, not constantly rebasing/merging on top of 'master'.

quoted

+       /*
+        * Do what unpack_callback() and unpack_nondirectories() normally
+        * do. But we walk all paths recursively in just one loop instead.
+        *
+        * D/F conflicts and staged entries are not a concern because

"staged entries"?  Do you mean "higher stage entries"?  I'm not sure
the correct terminology here, but the former makes me think of changes
the user has staged but not committed (i.e. stuff found at stage #0 in
the index, but which isn't found in any tree yet) vs. the latter which
I'd use to refer to entries at stages 1 or higher.

Yep stage 1 or higher (I was thinking ce_stage() when I wrote this).
Will clarify.

quoted

+        * cache-tree would be invalidated and we would never get here
+        * in the first place.
+        */
+       for (i = 0; i < nr_entries; i++) {
+               struct cache_entry *tree_ce;
+               int len, rc;
+
+               src[0] = o->src_index->cache[pos + i];
+
+               len = ce_namelen(src[0]);
+               tree_ce = xcalloc(1, cache_entry_size(len));
+
+               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);

We do a bunch of work to setup tree_ce...

quoted

+               for (d = 1; d <= nr_names; d++)
+                       src[d] = tree_ce;

...then we make nr_names copies of tree_ce (so that *way_merge or
bind_merge or oneway_diff or whatever will have the expected number of
entries).

quoted

+               rc = call_unpack_fn((const struct cache_entry * const *)src, o);

...then we call o->fn (via call_unpack_fn) to do various complicated
logic to figure out which tree_ce to use??  Isn't that just an
expensive way to recompute that what we currently have in the index is
what we want to keep there?

Granted, a caller of this may have set o->fn to something other than
{one,two,three}way_merge (or bind_merge), and that function might have
important side effects...but it just seems annoying to have to do so
much work when for most uses we already know the entry in the index is
the one we already want.

I'm not so sure about that. Which is why I keep it generic.

In fact, the only other thing in the
codebase that o->fn is now set to is oneway_diff, which I think is a
no-op when the two trees match.

Would be nice if we could avoid all this, at least in the common cases
where o->fn is a function known to not have side effects.  Or did I
not read those functions closely enough and they do have important
side effects?

In one of my earlier "how about this" attempts, I introduced fn_same
[1] that can help achieve this without carving "known not to have side
effects" in common code. Which I think is still a good direction to go
if we want to optimize more aggressively. We could have something like
this

diff --git a/unpack-trees.c b/unpack-trees.c
index 1f11991a51..01b80389e0 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c

@@ -699,6 +699,9 @@ static int traverse_by_cache_tree(int pos, int

nr_entries, int nr_names,
        int ce_len = 0;
        int i, d;

+       if (o->fn_cache_tree)
+               return o->fn_cache_tree(pos, nr_entries, nr_names, names, info);
+
        if (!o->merge)
                BUG("We need cache-tree to do this optimization");

then you can add, say threeway_cache_tree_merge(), that does what
traverse_by_cache_tree() does but more efficient. This involves a lot
more work (mostly staring and those n-merge functions and making sure
you don't set the right conditions before going the fast path).

I didn't do it because.. well.. it's more work and also riskier. I
think we can leave that for later, unless you think we should do it
now.

[1] https://public-inbox.org/git/20180726163049.GA15572@duynguyen.home/
-- 
Duy