Speed up unpack_trees()

v5 fixes some minor comments from round 4 and a big mistake in 5/5. Junio's scary feeling turns out true. There is a missing invalidation in keep_entry() which is not added in 6/7. 7/7 makes sure that similar problems will not slip through.

I had to rebase this series on top of 'master' because 7/7 caught a bad cache-tree situation that has been fixed by Elijah in ad3762042a (read-cache: fix directory/file conflict handling in read_index_unmerged() - 2018-07-31). I believe the issue was we prime cache-tree in 'git reset --hard' even though the index has conflicts.

Range-diff (before the rebase):

1: a192faf79e ! 1: ed8763726b trace.h: support nested performance tracing

    @@ -49,13 +49,16 @@
      	struct untracked_cache_dir *untracked;
     -	uint64_t start = getnanotime();
      
    - 	if (has_symlink_leading_path(path, len))
    +-	if (has_symlink_leading_path(path, len))
    ++	trace_performance_enter();
    ++
    ++	if (has_symlink_leading_path(path, len)) {
    ++		trace_performance_leave("read directory %.*s", len, path);
      		return dir->nr;
    ++	}
      
    -+	trace_performance_enter();
      	untracked = validate_untracked_cache(dir, len, pathspec);
      	if (!untracked)
    - 		/*
     @@
      		dir->nr = i;
      	}
2:  9afe7c488a = 2:  9b70652fa2 unpack-trees: add performance tracing
3:  74101edb60 ! 3:  8b3cfea623 unpack-trees: optimize walking same trees with cache-tree
    @@ -141,7 +141,7 @@
     +
     +	/*
     +	 * Do what unpack_callback() and unpack_nondirectories() normally
    -+	 * do. But we walk all paths recursively in just one loop instead.
    ++	 * 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
4:  9261c5920e = 4:  5af28d44ca unpack-trees: reduce malloc in cache-tree walk
5:  43fac1154f = 5:  5657c92fe9 unpack-trees: reuse (still valid) cache-tree from src_index
-:  ---------- > 6:  3b91783afc unpack-trees: add missing cache invalidation
-:  ---------- > 7:  0d5464c0dc cache-tree: verify valid cache-tree in the test suite

Nguyễn Thái Ngọc Duy (7):
trace.h: support nested performance tracing
unpack-trees: add performance tracing
unpack-trees: optimize walking same trees with cache-tree
unpack-trees: reduce malloc in cache-tree walk
unpack-trees: reuse (still valid) cache-tree from src_index
unpack-trees: add missing cache invalidation
cache-tree: verify valid cache-tree in the test suite

 cache-tree.c    |  80 +++++++++++++++++++++++++
 cache-tree.h    |   1 +
 diff-lib.c      |   4 +-
 dir.c           |   9 ++-
 name-hash.c     |   4 +-
 preload-index.c |   4 +-
 read-cache.c    |  16 +++--
 t/test-lib.sh   |   6 ++
 trace.c         |  69 ++++++++++++++++++++--
 trace.h         |  15 +++++
 unpack-trees.c  | 154 +++++++++++++++++++++++++++++++++++++++++++++++-
 11 files changed, 340 insertions(+), 22 deletions(-)

2.18.0.1004.g6639190530