Re: [PATCH v3 2/4] unpack-trees: optimize walking same trees with cache-tree
- From
Elijah Newren <newren@gmail.com>
- Date
- Aug 8, 2018, 18:23 UTC
- Message-ID
- <CABPp-BGcPV0RA624_1UOXYkvaNhW4yR2ifhV_MVFZQOgBb_Ydg@mail.gmail.com>
- In-Reply-To
- <20180804053723.4695-3-pclouds@gmail.com>
On Fri, Aug 3, 2018 at 10:39 PM Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
Show 9 quoted lines
> From: Duy Nguyen <pclouds@gmail.com> > > In order to merge one or many trees with the index, unpack-trees code > walks multiple trees in parallel with the index and performs n-way > merge. If we find out at start of a directory that all trees are the > same (by comparing OID) and cache-tree happens to be available for > that directory as well, we could avoid walking the trees because we > already know what these trees contain: it's flattened in what's called > "the index".
This is cool.
> The upside is of course a lot less I/O since we can potentially skip > lots of trees (think subtrees). We also save CPU because we don't have > to inflate and the apply deltas. The downside is of course more
s/and the apply/and apply the/
Show 72 quoted lines
> fragile code since the logic in some functions are now duplicated
> elsewhere.
>
> "checkout -" with this patch on gcc.git:
>
> baseline new
> --------------------------------------------------------------------
> 0.018239226 0.019365414 s: read cache .git/index
> 0.052541655 0.049605548 s: preload index
> 0.001537598 0.001571695 s: refresh index
> 0.168167768 0.049677212 s: unpack trees
> 0.002897186 0.002845256 s: update worktree after a merge
> 0.131661745 0.136597522 s: repair cache-tree
> 0.075389117 0.075422517 s: write index, changed mask = 2a
> 0.111702023 0.032813253 s: unpack trees
> 0.000023245 0.000022002 s: update worktree after a merge
> 0.111793866 0.032933140 s: diff-index
> 0.587933288 0.398924370 s: git command: /home/pclouds/w/git/git
>
> Another measurement from Ben's running "git checkout" with over 500k
> trees (on the whole series):
>
> baseline new
> ----------------------------------------------------------------------
> 0.535510167 0.556558733 s: read cache .git/index
> 0.3057373 0.3147105 s: initialize name hash
> 0.0184082 0.023558433 s: preload index
> 0.086910967 0.089085967 s: refresh index
> 7.889590767 2.191554433 s: unpack trees
> 0.120760833 0.131941267 s: update worktree after a merge
> 2.2583504 2.572663167 s: repair cache-tree
> 0.8916137 0.959495233 s: write index, changed mask = 28
> 3.405199233 0.2710663 s: unpack trees
> 0.000999667 0.0021554 s: update worktree after a merge
> 3.4063306 0.273318333 s: diff-index
> 16.9524923 9.462943133 s: git command: git.exe checkout
>
> This command calls unpack_trees() twice, the first time on 2way merge
> and the second 1way merge. In both times, "unpack trees" time is
> reduced to one third. Overall time reduction is not that impressive of
> course because index operations take a big chunk. And there's that
> repair cache-tree line.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
> unpack-trees.c | 117 +++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 117 insertions(+)
>
> 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.
Show 44 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 /* slash */ + 1 /* NUL */);
> + int pos;
> +
> + make_traverse_path(name, info, names);
> + name[len++] = '/';
> + name[len] = '\0';
> + pos = index_name_pos(o->src_index, name, len);
> + if (pos >= 0)
> + BUG("This is a directory and should not exist in index");
> + pos = -pos - 1;
> + if (!starts_with(o->src_index->cache[pos]->name, name) ||
> + (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name)))
> + BUG("pos must point at the first entry in this directory");
> + free(name);
> + return pos;
> +}
> +
> +/*
> + * 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;
> +
> + if (!o->merge)
> + BUG("We need cache-tree to do this optimization");
> +
> + /*
> + * 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.
Show 17 quoted lines
> + * 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...
> + 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).
> + 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. 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?
Show 30 quoted lines
> + free(tree_ce);
> + if (rc < 0)
> + return rc;
> +
> + mark_ce_used(src[0], o);
> + }
> + if (o->debug_unpack)
> + printf("Unpacked %d entries from %s to %s using cache-tree\n",
> + nr_entries,
> + o->src_index->cache[pos]->name,
> + o->src_index->cache[pos + nr_entries - 1]->name);
> + return 0;
> +}
> +
> static int traverse_trees_recursive(int n, unsigned long dirmask,
> unsigned long df_conflicts,
> struct name_entry *names,
> @@ -655,6 +751,17 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,
> void *buf[MAX_UNPACK_TREES];
> struct traverse_info newinfo;
> struct name_entry *p;
> + int nr_entries;
> +
> + nr_entries = all_trees_same_as_cache_tree(n, dirmask, names, info);
> + if (nr_entries > 0) {
> + struct unpack_trees_options *o = info->data;
> + int pos = index_pos_by_traverse_info(names, info);
> +
> + if (!o->merge || df_conflicts)
> + BUG("Wrong condition to get here buddy");heh. :)
Show 23 quoted lines
> + return traverse_by_cache_tree(pos, nr_entries, n, names, info); > + } > > p = names; > while (!p->mode) > @@ -814,6 +921,11 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info, con > return ce; > } > > +/* > + * Note that traverse_by_cache_tree() duplicates some logic in this function > + * without actually calling it. If you change the logic here you may need to > + * check and change there as well. > + */ > static int unpack_nondirectories(int n, unsigned long mask, > unsigned long dirmask, > struct cache_entry **src, > @@ -998,6 +1110,11 @@ static void debug_unpack_callback(int n, > debug_name_entry(i, names + i); > } > > +/* > + * Note that traverse_by_cache_tree() duplicates some logic in this funciton
s/funciton/function/
Show 8 quoted lines
> + * without actually calling it. If you change the logic here you may need to
> + * check and change there as well.
> + */
> static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
> {
> struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
> --
> 2.18.0.656.gda699b98b3