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

From

Duy Nguyen <pclouds@gmail.com>

Date

Jul 27, 2018, 15:42 UTC

Message-ID

<20180727154241.GA21288@duynguyen.home>

In-Reply-To

<xmqqd0v9pyzu.fsf@gitster-ct.c.googlers.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.
> 

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

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