From: Ben Peart Date: Mon, 30 Jul 2018 20:52:54 GMT Subject: Re: [PATCH v2 2/4] unpack-trees: optimize walking same trees with cache-tree Message-ID: <2b97c84e-0634-3879-18a1-8f96a7b4a30d@gmail.com> In-Reply-To: <20180729103306.16403-3-pclouds@gmail.com> On 7/29/2018 6:33 AM, Nguyễn Thái Ngọc Duy wrote: > From: Duy Nguyen > > 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". > > 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 > 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 > > 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 > --- > unpack-trees.c | 119 ++++++++++++++++++++++++++++++++++++++++++++++++- > 1 file changed, 118 insertions(+), 1 deletion(-) > > diff --git a/unpack-trees.c b/unpack-trees.c > index dc58d1f5ae..39566b28fb 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); > +} > + > +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 > + * 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); > + I don't like the overhead of having to create an entirely new cache entry here but I see you clean this up in the next patch. > + 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); > + } > + 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"); > + 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 funciton s/funciton/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 > + * 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, }; > @@ -1280,7 +1397,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options > uint64_t start = getnanotime(); > > if (len > MAX_UNPACK_TREES) > - die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES); > + die(_("unpack_trees takes at most %d trees"), MAX_UNPACK_TREES); > I'd like to see this get in independently of this patch series. > memset(&el, 0, sizeof(el)); > if (!core_apply_sparse_checkout || !o->update) >