From: Ben Peart Date: Mon, 20 Aug 2018 12:43:22 GMT Subject: Re: [PATCH v5 3/7] unpack-trees: optimize walking same trees with cache-tree Message-ID: In-Reply-To: <20180818144128.19361-4-pclouds@gmail.com> On 8/18/2018 10:41 AM, Nguyễn Thái Ngọc Duy wrote: > 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 apply the deltas. The downside is of course more > fragile code since the logic in some functions are now duplicated > elsewhere. > > "checkout -" with this patch on webkit.git (275k files): > > baseline new > -------------------------------------------------------------------- > 0.056651714 0.080394752 s: read cache .git/index > 0.183101080 0.216010838 s: preload index > 0.008584433 0.008534301 s: refresh index > 0.633767589 0.251992198 s: traverse_trees > 0.340265448 0.377031383 s: check_updates > 0.381884638 0.372768105 s: cache_tree_update > 1.401562947 1.045887251 s: unpack_trees > 0.338687914 0.314983512 s: write index, changed mask = 2e > 0.411927922 0.062572653 s: traverse_trees > 0.000023335 0.000022544 s: check_updates > 0.423697246 0.073795585 s: unpack_trees > 0.423708360 0.073807557 s: diff-index > 2.559524127 1.938191592 s: git command: git checkout - > > 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. > > PS. A note about cache-tree invalidation and the use of it in this > code. > > We do invalidate cache-tree in _source_ index when we add new entries > to the (temporary) "result" index. But we also use the cache-tree from > source index in this optimization. Does this mean we end up having no > cache-tree in the source index to activate this optimization? > > The answer is twisted: the order of finding a good cache-tree and > invalidating it matters. In this case we check for a good cache-tree > first in all_trees_same_as_cache_tree(), then we start to merge things > and potentially invalidate that same cache-tree in the process. Since > cache-tree invalidation happens after the optimization kicks in, we're > still good. But we may lose that cache-tree at the very first > call_unpack_fn() call in traverse_by_cache_tree(). > > Signed-off-by: Nguyễn Thái Ngọc Duy > Signed-off-by: Junio C Hamano > --- > unpack-trees.c | 127 +++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 127 insertions(+) > > diff --git a/unpack-trees.c b/unpack-trees.c > index 6d9f692ea6..8376663b59 100644 > --- a/unpack-trees.c > +++ b/unpack-trees.c > @@ -635,6 +635,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 nit, not worth a re-roll "We'll walk these trees in an iterative loop using cache-tree/index..." > + * 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 in an iterative loop instead. > + * > + * D/F conflicts and higher stage 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); > + > + 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, > @@ -646,6 +742,27 @@ 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"); > + > + /* > + * All entries up to 'pos' must have been processed > + * (i.e. marked CE_UNPACKED) at this point. But to be safe, > + * save and restore cache_bottom anyway to not miss > + * unprocessed entries before 'pos'. > + */ > + bottom = o->cache_bottom; > + ret = traverse_by_cache_tree(pos, nr_entries, n, names, info); > + o->cache_bottom = bottom; > + return ret; > + } > > p = names; > while (!p->mode) > @@ -812,6 +929,11 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info, > 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, > @@ -1004,6 +1126,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 function > + * 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, }; >