Re: [PATCH v1 0/3] [RFC] Speeding up checkout (and merge, rebase, etc)

[Duy Nguyen <pclouds@gmail.com>]

On Thu, Jul 26, 2018 at 12:40:05PM -0700, Junio C Hamano wrote:
> Duy Nguyen <pclouds@gmail.com> writes:
> 
> > I'm excited so I decided to try out anyway. This is what I've come up
> > with. Switching trees on git.git shows it could skip plenty entries,
> > so promising. It's ugly and it fails at t6020 though, there's still
> > work ahead. But I think it'll stop here.
> 
> We are extremely shallow compared to projects like the kernel and
> stuff from java land, so that is quite an interesting find.
> 

Yeah. I've got a more or less complete patch now with full test suite
passed and even with linux.git, the numbers look pretty good.

Ben, is it possible for you to try this one out? I don't suppose it
will be that good on a real big repo. But I'm curious how much faster
could this patch does.

I'm quite happy that I don't have to make specific code for twoway
merge, which means this patch would also help real merges (3way)
too. Interestingly this also helps reduce traverse_trees() when
diff_index_cached optimization is on. I have no idea how but
well.. can't complain.

-- 8< --
Subject: [PATCH] unpack-trees: optimize walking same trees with cache-tree

In order to merge one or many trees with the index, unpack-trees code
walk multiple trees in parallel with the index and perform 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.

One nice attribute of cache-tree (and the index) is that the tree is
only flattened (and it's called "the index") and we know how many
files that directory has. With this information, we could avoid
accessing object database to walk tree objects and just take the
entries from the index instead.

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.

WIth this patch, switching between two trees on linux.git where
there's only one file changed (toplevel Makefile) seems sped up pretty
good. Total checkout time goes down from 0.543 to 0.352 (35%).
traverse_trees() one twoway merge (the big one in unpack_trees()) goes
from 0.157s to 0.036 (70%).

Note that compared to diff_index_cached optimization (which is very
similar to this) we do more work here. This is because diff_index_cached
only cares about side effect, it does not modify the index, so we can
quickly jump through a big chunk of cache entries. For n-way merge, we
need to add entries and verify stuff, so more CPU cycles.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 unpack-trees.c | 125 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 125 insertions(+)

diff --git a/unpack-trees.c b/unpack-trees.c
index 66741130ae..9c791b55b2 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -642,6 +642,110 @@ 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 (dirmask != ((1 << n) - 1) || !S_ISDIR(names->mode) || !o->merge)
+		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);
+}
+
+/*
+ * 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;
+
+	/*
+	 * Do what unpack_callback() and unpack_nondirectories() normally
+	 * do. But we do it in one function call (for even nested trees)
+	 * 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];
+
+		/* Do what unpack_nondirectories() normally does */
+		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);
+	}
+	trace_printf("Quick traverse over %d entries from %s to %s\n",
+		     nr_entries,
+		     o->src_index->cache[pos]->name,
+		     o->src_index->cache[pos + nr_entries - 1]->name);
+	return 0;
+}
+
+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);
+	int pos;
+
+	make_traverse_path(name, info, names);
+	pos = index_name_pos(o->src_index, name, len);
+	if (pos >= 0)
+		BUG("This is so wrong. This is a directory and should not exist in index");
+	pos = -pos - 1;
+	/*
+	 * There's no guarantee that pos points to the first entry of the
+	 * directory. If the directory name is "letters" and there's another
+	 * file named "letters.txt" in the index, pos will point to that file
+	 * instead.
+	 */
+	while (pos < o->src_index->cache_nr) {
+		const struct cache_entry *ce = o->src_index->cache[pos];
+		if (ce_namelen(ce) > len &&
+		    ce->name[len] == '/' &&
+		    !memcmp(ce->name, name, len))
+			break;
+		pos++;
+	}
+	if (pos == o->src_index->cache_nr)
+		BUG("This is still wrong");
+	free(name);
+	return pos;
+}
+
 static int traverse_trees_recursive(int n, unsigned long dirmask,
 				    unsigned long df_conflicts,
 				    struct name_entry *names,
@@ -653,6 +757,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)
@@ -812,6 +927,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
+ * 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,
@@ -996,6 +1116,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, };
-- 
2.18.0.656.gda699b98b3

-- 8< --
--
Duy