Re: [PATCH v2 4/4] unpack-trees: cheaper index update when walking by cache-tree

[Duy Nguyen <pclouds@gmail.com>]

On Fri, Aug 10, 2018 at 8:39 PM Elijah Newren <newren@gmail.com> wrote:
>
> On Fri, Aug 10, 2018 at 9:39 AM Duy Nguyen <pclouds@gmail.com> wrote:
> >
> > On Wed, Aug 8, 2018 at 8:46 PM Elijah Newren <newren@gmail.com> wrote:
> > > > @@ -701,6 +702,24 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
>
> > > If we're going to go this route, I think we should first check that
> > > o->fn is one of those known safe functions.  And if we're going that
> > > route, the comments I bring up on patch 2 about possibly avoiding
> > > call_unpack_fn() altogether might even obviate this patch while
> > > speeding things up more.
> >
> > Yes I do need to check o->fn. I might have to think more about
> > avoiding call_unpack_fn(). Even if we avoid it though, we still go
> > through add_index_entry() and suffer the same checks every time unless
> > we do somethine like this (but then of course it's safer because
> > you're doing it in a specific x-way merge, not generic code like
> > this).
>
> Why do we still need to go through add_index_entry()?  I thought that
> the whole point was that you already checked that at the current path,
> the trees being unpacked were all equal and matched both the index and
> the cache_tree.  If so, why is there any need for an update at all?
> (Did I read your all_trees_same_as_cache_tree() function wrong, and
> you don't actually know these all match in some important way?)

Unless fn is oneway_diff, we have to create a new index (in o->result)
based on o->src_index and some other trees. So we have to add entries
to o->result and add_index_entry() is the way to do that (granted if
we feel confident we could add ADD_CACHE_JUST_APPEND which makes it
super cheap). This is the outcome of n-way merge,

all_trees_same_as_cache_tree() only gurantees the input condition (all
trees the same, index also the same) but it can't affect what fn does.
I don't think we can just simply skip and not update anything (like
o->diff_index_cached case) because o->result would be empty in the
end. And we need to create (temporary) o->result before we can swap it
to o->dst_index as the result of a merge operation.

> > > > @@ -1561,6 +1581,13 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
> > > >                 if (!ret) {
> > > >                         if (!o->result.cache_tree)
> > > >                                 o->result.cache_tree = cache_tree();
> > > > +                       /*
> > > > +                        * TODO: Walk o.src_index->cache_tree, quickly check
> > > > +                        * if o->result.cache has the exact same content for
> > > > +                        * any valid cache-tree in o.src_index, then we can
> > > > +                        * just copy the cache-tree over instead of hashing a
> > > > +                        * new tree object.
> > > > +                        */
> > >
> > > Interesting.  I really don't know how cache_tree works...but if we
> > > avoided calling call_unpack_fn, and thus left the original index entry
> > > in place instead of replacing it with an equal one, would that as a
> > > side effect speed up the cache_tree_valid/cache_tree_update calls for
> > > us?  Or is there still work here?
> >
> > Naah. Notice that we don't care at all about the source's cache-tree
> > when we update o->result one (and we never ever do anything about
> > o->result's cache-tree during the merge). Whether you invalidate or
> > not, o->result's cache-tree is always empty and you still have to
> > recreate all cache-tree in o->result. You essentially play full cost
> > of "git write-tree" here if I'm not mistaken.
>
> Oh...perhaps that answers my question above.  So we have to call
> add_index_entry() for the side effect of populating the new
> cache_tree?

I have a feeling that you're thinking we can swap o->src_index to
o->dst_index at the end? That might explain your confusion about
o->result (or I misread your replies horribly) and the original
index...
-- 
Duy