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

[Duy Nguyen <pclouds@gmail.com>]

On Fri, Jul 27, 2018 at 07:52:33PM +0200, Duy Nguyen wrote:
> Just FYI I'm still trying to reduce execution time further and this
> change happens to half traverse_trees() time (which is a huge deal)
> 
> diff --git a/unpack-trees.c b/unpack-trees.c
> index f0be9f298d..a2e63ad5bf 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -201,7 +201,7 @@ static int do_add_entry(struct
> unpack_trees_options *o, struct cache_entry *ce,
> 
>         ce->ce_flags = (ce->ce_flags & ~clear) | set;
>         return add_index_entry(&o->result, ce,
> -                              ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
> +                              ADD_CACHE_JUST_APPEND |
> ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
>  }
> 
>  static struct cache_entry *dup_entry(const struct cache_entry *ce)
> 
> It's probably not the right thing to do of course. But perhaps we
> could do something in that direction (e.g. validate everything at the
> end of traverse_by_cache_tree...)

It's just too much computation that could be reduced. The following
patch gives more or less the same performance gain as adding
ADD_CACHE_JUST_APPEND (traverse_trees() time cut down by half).

Of these, the walking cache-tree inside add_index_entry_with_check()
is most expensive and we probably could just walk the cache-tree in
traverse_by_cache_tree() loop and do the invalidation there instead.

-- 8< --
diff --git a/cache.h b/cache.h
index 8b447652a7..e6f7ee4b64 100644
--- a/cache.h
+++ b/cache.h
@@ -673,6 +673,7 @@ extern int index_name_pos(const struct index_state *, const char *name, int name
 #define ADD_CACHE_JUST_APPEND 8		/* Append only; tree.c::read_tree() */
 #define ADD_CACHE_NEW_ONLY 16		/* Do not replace existing ones */
 #define ADD_CACHE_KEEP_CACHE_TREE 32	/* Do not invalidate cache-tree */
+#define ADD_CACHE_SKIP_VERIFY_PATH 64	/* Do not verify path */
 extern int add_index_entry(struct index_state *, struct cache_entry *ce, int option);
 extern void rename_index_entry_at(struct index_state *, int pos, const char *new_name);
 
diff --git a/read-cache.c b/read-cache.c
index e865254bea..b0b5df5de7 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1170,6 +1170,7 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e
 	int ok_to_add = option & ADD_CACHE_OK_TO_ADD;
 	int ok_to_replace = option & ADD_CACHE_OK_TO_REPLACE;
 	int skip_df_check = option & ADD_CACHE_SKIP_DFCHECK;
+	int skip_verify_path = option & ADD_CACHE_SKIP_VERIFY_PATH;
 	int new_only = option & ADD_CACHE_NEW_ONLY;
 
 	if (!(option & ADD_CACHE_KEEP_CACHE_TREE))
@@ -1210,7 +1211,7 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e
 
 	if (!ok_to_add)
 		return -1;
-	if (!verify_path(ce->name, ce->ce_mode))
+	if (!skip_verify_path && !verify_path(ce->name, ce->ce_mode))
 		return error("Invalid path '%s'", ce->name);
 
 	if (!skip_df_check &&
diff --git a/unpack-trees.c b/unpack-trees.c
index f2a2db6ab8..ff6a0f2bd3 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -201,6 +201,7 @@ static int do_add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
 
 	ce->ce_flags = (ce->ce_flags & ~clear) | set;
 	return add_index_entry(&o->result, ce,
+			       o->extra_add_index_flags |
 			       ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
 }
 
@@ -678,6 +679,25 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
 	const char *first_name = o->src_index->cache[pos]->name;
 	int dirlen = (strrchr(first_name, '/') - first_name)+1;
 
+	/*
+	 * Try to keep add_index_entry() as fast as possible since
+	 * we're going to do a lot of them.
+	 *
+	 * Skipping verify_path() should totally be safe because these
+	 * paths are from the source index, which must have been
+	 * verified.
+	 *
+	 * Skipping D/F and cache-tree validation checks is trickier
+	 * because it assumes what n-merge code would do when all
+	 * trees and the index are the same. We probably could just
+	 * optimize those code instead (e.g. we don't invalidate that
+	 * many cache-tree, but the searching for them is very
+	 * expensive).
+	 */
+	o->extra_add_index_flags = ADD_CACHE_SKIP_DFCHECK;
+	o->extra_add_index_flags |= ADD_CACHE_KEEP_CACHE_TREE;
+	o->extra_add_index_flags |= ADD_CACHE_SKIP_VERIFY_PATH;
+
 	/*
 	 * Do what unpack_callback() and unpack_nondirectories() normally
 	 * do. But we do it in one function call (for even nested trees)
@@ -721,6 +741,7 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
 
 		mark_ce_used(src[0], o);
 	}
+	o->extra_add_index_flags = 0;
 	free(tree_ce);
 	trace_printf("Quick traverse over %d entries from %s to %s\n",
 		     nr_entries,
diff --git a/unpack-trees.h b/unpack-trees.h
index c2b434c606..94e1b14078 100644
--- a/unpack-trees.h
+++ b/unpack-trees.h
@@ -80,6 +80,7 @@ struct unpack_trees_options {
 	struct index_state result;
 
 	struct exclude_list *el; /* for internal use */
+	unsigned int extra_add_index_flags;
 };
 
 extern int unpack_trees(unsigned n, struct tree_desc *t,
-- 8< --