git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 06/19] untracked cache: record/validate dir mtime and reuse cached output

From
Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Date
Oct 27, 2014, 12:10 UTC
Message-ID
<1414411846-4450-7-git-send-email-pclouds@gmail.com>
In-Reply-To
<1414411846-4450-1-git-send-email-pclouds@gmail.com>

The main readdir loop in read_directory_recursive() is replaced with a new one that checks if cached results of a directory is still valid.

If a file is added or removed from the index, the containing directory is invalidated (but not its subdirs). If directory's mtime is changed, the same happens. If a .gitignore is updated, the containing directory and all subdirs are invalidated recursively. If dir_struct#flags or other conditions change, the cache is ignored.

If a directory is invalidated, we opendir/readdir/closedir and run the exclude machinery on that directory listing as usual. If untracked cache is also enabled, we'll update the cache along the way. If a directory is validated, we simply pull the untracked listing out from the cache. The cache also records the list of direct subdirs that we have to recurse in. Fully excluded directories are seen as "untracked files".

In the best case when no dirs are invalidated, read_directory() becomes a series of

  stat(dir), open(.gitignore), fstat(), read(), close() and optionally
  hash_sha1_file()
For comparison, standard read_directory() is a sequence of
  opendir(), readdir(), open(.gitignore), fstat(), read(), close(), the
  expensive last_exclude_matching() and closedir().

We already try not to open(.gitignore) if we know it does not exist, so open/fstat/read/close sequence does not apply to every directory. The sequence could be reduced further, as noted in prep_exclude() in another patch. So in theory, the entire best-case read_directory sequence could be reduced to a series of stat() and nothing else.

This is not a silver bullet approach. When you compile a C file, for example, the old .o file is removed and a new one with the same name created, effectively invalidating the containing directory's cache (but not its subdirectories). If your build process touches every directory, this cache adds extra overhead for nothing, so it's a good idea to separate generated files from tracked files.. Editors may use the same strategy for saving files. And of course you're out of luck running your repo on an unsupported filesytem and/or operating system.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 dir.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 dir.h |   2 ++
 2 files changed, 123 insertions(+), 2 deletions(-)
diff --git a/dir.c b/dir.c
index 2793e57..55780a7 100644
--- a/dir.c
+++ b/dir.c
@@ -37,7 +37,12 @@ enum path_treatment {
 struct cached_dir {
 	DIR *fdir;
 	struct untracked_cache_dir *untracked;
+	int nr_files;
+	int nr_dirs;
+
 	struct dirent *de;
+	const char *file;
+	struct untracked_cache_dir *ucd;
 };
 
 static enum path_treatment read_directory_recursive(struct dir_struct *dir,
@@ -606,6 +611,14 @@ static void invalidate_gitignore(struct untracked_cache *uc,
 	do_invalidate_gitignore(dir);
 }
 
+static void invalidate_directory(struct untracked_cache *uc,
+				 struct untracked_cache_dir *dir)
+{
+	uc->dir_invalidated++;
+	dir->valid = 0;
+	dir->untracked_nr = 0;
+}
+
 /*
  * Given a file with name "fname", read it (either from disk, or from
  * the index if "check_index" is non-zero), parse it and store the
@@ -1418,6 +1431,41 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,
 	}
 }
 
+static enum path_treatment treat_path_fast(struct dir_struct *dir,
+					   struct untracked_cache_dir *untracked,
+					   struct cached_dir *cdir,
+					   struct strbuf *path,
+					   int baselen,
+					   const struct path_simplify *simplify)
+{
+	if (!cdir->ucd) {
+		strbuf_setlen(path, baselen);
+		strbuf_addstr(path, cdir->file);
+		return path_untracked;
+	}
+	strbuf_setlen(path, baselen);
+	strbuf_addstr(path, cdir->ucd->name);
+	/* treat_one_path() does this before it calls treat_directory() */
+	if (path->buf[path->len - 1] != '/')
+		strbuf_addch(path, '/');
+	if (cdir->ucd->check_only)
+		/*
+		 * check_only is set as a result of treat_directory() getting
+		 * to its bottom. Verify again the same set of directories
+		 * with check_only set.
+		 */
+		return read_directory_recursive(dir, path->buf, path->len,
+
+						cdir->ucd, 1, simplify);
+	/*
+	 * We get path_recurse in the first run when
+	 * directory_exists_in_index() returns index_nonexistent. We
+	 * are sure that new changes in the index does not impact the
+	 * outcome. Return now.
+	 */
+	return path_recurse;
+}
+
 static enum path_treatment treat_path(struct dir_struct *dir,
 				      struct untracked_cache_dir *untracked,
 				      struct cached_dir *cdir,
@@ -1428,6 +1476,9 @@ static enum path_treatment treat_path(struct dir_struct *dir,
 	int dtype;
 	struct dirent *de = cdir->de;
 
+	if (!de)
+		return treat_path_fast(dir, untracked, cdir, path,
+				       baselen, simplify);
 	if (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, ".git"))
 		return path_none;
 	strbuf_setlen(path, baselen);
@@ -1448,6 +1499,52 @@ static void add_untracked(struct untracked_cache_dir *dir, const char *name)
 	dir->untracked[dir->untracked_nr++] = xstrdup(name);
 }
 
+static int valid_cached_dir(struct dir_struct *dir,
+			    struct untracked_cache_dir *untracked,
+			    struct strbuf *path,
+			    int check_only)
+{
+	struct stat st;
+
+	if (!untracked)
+		return 0;
+
+	if (stat(path->len ? path->buf : ".", &st)) {
+		invalidate_directory(dir->untracked, untracked);
+		memset(&untracked->stat_data, 0, sizeof(untracked->stat_data));
+		return 0;
+	}
+	if (!untracked->valid ||
+	    match_stat_data(&untracked->stat_data, &st)) {
+		if (untracked->valid)
+			invalidate_directory(dir->untracked, untracked);
+		fill_stat_data(&untracked->stat_data, &st);
+		return 0;
+	}
+
+	if (untracked->check_only != !!check_only) {
+		invalidate_directory(dir->untracked, untracked);
+		return 0;
+	}
+
+	/*
+	 * prep_exclude will be called eventually on this directory,
+	 * but it's called much later in last_exclude_matching(). We
+	 * need it now to determine the validity of the cache for this
+	 * path. The next calls will be nearly no-op, the way
+	 * prep_exclude() is designed.
+	 */
+	if (path->len && path->buf[path->len - 1] != '/') {
+		strbuf_addch(path, '/');
+		prep_exclude(dir, path->buf, path->len);
+		strbuf_setlen(path, path->len - 1);
+	} else
+		prep_exclude(dir, path->buf, path->len);
+
+	/* hopefully prep_exclude() haven't invalidated this entry... */
+	return untracked->valid;
+}
+
 static int open_cached_dir(struct cached_dir *cdir,
 			   struct dir_struct *dir,
 			   struct untracked_cache_dir *untracked,
@@ -1456,7 +1553,11 @@ static int open_cached_dir(struct cached_dir *cdir,
 {
 	memset(cdir, 0, sizeof(*cdir));
 	cdir->untracked = untracked;
+	if (valid_cached_dir(dir, untracked, path, check_only))
+		return 0;
 	cdir->fdir = opendir(path->len ? path->buf : ".");
+	if (dir->untracked)
+		dir->untracked->dir_opened++;
 	if (!cdir->fdir)
 		return -1;
 	return 0;
@@ -1470,6 +1571,18 @@ int read_cached_dir(struct cached_dir *cdir)
 			return -1;
 		return 0;
 	}
+	while (cdir->nr_dirs < cdir->untracked->dirs_nr) {
+		struct untracked_cache_dir *d = cdir->untracked->dirs[cdir->nr_dirs];
+		cdir->ucd = d;
+		cdir->nr_dirs++;
+		return 0;
+	}
+	cdir->ucd = NULL;
+	if (cdir->nr_files < cdir->untracked->untracked_nr) {
+		struct untracked_cache_dir *d = cdir->untracked;
+		cdir->file = d->untracked[cdir->nr_files++];
+		return 0;
+	}
 	return -1;
 }
 
@@ -1477,6 +1590,12 @@ static void close_cached_dir(struct cached_dir *cdir)
 {
 	if (cdir->fdir)
 		closedir(cdir->fdir);
+	/*
+	 * We have gone through this directory and found no untracked
+	 * entries. Mark it valid.
+	 */
+	if (cdir->untracked && !cdir->untracked->valid)
+		cdir->untracked->valid = 1;
 }
 
 /*
@@ -1530,7 +1649,7 @@ static enum path_treatment read_directory_recursive(struct dir_struct *dir,
 		if (check_only) {
 			/* abort early if maximum state has been reached */
 			if (dir_state == path_untracked) {
-				if (untracked)
+				if (cdir.fdir)
 					add_untracked(untracked, path.buf + baselen);
 				break;
 			}
@@ -1554,7 +1673,7 @@ static enum path_treatment read_directory_recursive(struct dir_struct *dir,
 			if (dir->flags & DIR_SHOW_IGNORED)
 				break;
 			dir_add_name(dir, path.buf, path.len);
-			if (untracked)
+			if (cdir.fdir)
 				add_untracked(untracked, path.buf + baselen);
 			break;
 
diff --git a/dir.h b/dir.h
index 35701b2..1fefd4e 100644
--- a/dir.h
+++ b/dir.h
@@ -134,6 +134,8 @@ struct untracked_cache {
 	/* Statistics */
 	int dir_created;
 	int gitignore_invalidated;
+	int dir_invalidated;
+	int dir_opened;
 };
 
 struct dir_struct {

-- 
2.1.0.rc0.78.gc0d8480
Previous: Nguyễn Thái Ngọc DuyNext: Eric Sunshine
Message 12 of 65 in “Untracked cache to speed up "git status"”
  1. 00/19 Untracked cache to speed up "git status"Nguyễn Thái Ngọc Duy, Oct 27, 2014
  2. 01/19 dir.c: optionally compute sha-1 of a .gitignore fileNguyễn Thái Ngọc Duy, Oct 27, 2014
  3. Junio C HamanoOct 27, 2014
  4. Duy NguyenOct 28, 2014
  5. Torsten BögershausenOct 28, 2014
  6. Duy NguyenNov 2, 2014
  7. 02/19 untracked cache: record .gitignore information and dir hierarchyNguyễn Thái Ngọc Duy, Oct 27, 2014
  8. Torsten BögershausenOct 28, 2014
  9. 03/19 untracked cache: initial untracked cache validationNguyễn Thái Ngọc Duy, Oct 27, 2014
  10. 04/19 untracked cache: invalidate dirs recursively if .gitignore changesNguyễn Thái Ngọc Duy, Oct 27, 2014
  11. 05/19 untracked cache: make a wrapper around {open,read,close}dir()Nguyễn Thái Ngọc Duy, Oct 27, 2014
  12. 06/19 untracked cache: record/validate dir mtime and reuse cached outputNguyễn Thái Ngọc Duy, Oct 27, 2014
  13. Eric SunshineOct 30, 2014
  14. 07/19 untracked cache: mark what dirs should be recursed/savedNguyễn Thái Ngọc Duy, Oct 27, 2014
  15. 08/19 untracked cache: don't open non-existent .gitignoreNguyễn Thái Ngọc Duy, Oct 27, 2014
  16. 09/19 untracked cache: save to an index extensionNguyễn Thái Ngọc Duy, Oct 27, 2014
  17. 10/19 untracked cache: load from UNTR index extensionNguyễn Thái Ngọc Duy, Oct 27, 2014
  18. 11/19 untracked cache: invalidate at index addition or removalNguyễn Thái Ngọc Duy, Oct 27, 2014
  19. 12/19 read-cache.c: split racy stat test to a separate functionNguyễn Thái Ngọc Duy, Oct 27, 2014
  20. 13/19 untracked cache: avoid racy timestampsNguyễn Thái Ngọc Duy, Oct 27, 2014
  21. 14/19 untracked cache: print stats with $GIT_TRACE_UNTRACKED_STATSNguyễn Thái Ngọc Duy, Oct 27, 2014
  22. 15/19 untracked cache: mark index dirty if untracked cache is updatedNguyễn Thái Ngọc Duy, Oct 27, 2014
  23. 16/19 status: enable untracked cacheNguyễn Thái Ngọc Duy, Oct 27, 2014
  24. 17/19 update-index: manually enable or disable untracked cacheNguyễn Thái Ngọc Duy, Oct 27, 2014
  25. 18/19 update-index: test the system before enabling untracked cacheNguyễn Thái Ngọc Duy, Oct 27, 2014
  26. Torsten BögershausenOct 28, 2014
  27. Duy NguyenNov 3, 2014
  28. Junio C HamanoNov 3, 2014
  29. Eric SunshineOct 28, 2014
  30. 19/19 t7063: tests for untracked cacheNguyễn Thái Ngọc Duy, Oct 27, 2014
  31. 00/22 untracked cache updatesNguyễn Thái Ngọc Duy, Nov 8, 2014
  32. 01/22 dir.c: optionally compute sha-1 of a .gitignore fileNguyễn Thái Ngọc Duy, Nov 8, 2014
  33. David TurnerNov 17, 2014
  34. 02/22 untracked cache: record .gitignore information and dir hierarchyNguyễn Thái Ngọc Duy, Nov 8, 2014
  35. brian m. carlsonNov 8, 2014
  36. David TurnerNov 17, 2014
  37. 03/22 untracked cache: initial untracked cache validationNguyễn Thái Ngọc Duy, Nov 8, 2014
  38. 04/22 untracked cache: invalidate dirs recursively if .gitignore changesNguyễn Thái Ngọc Duy, Nov 8, 2014
  39. 05/22 untracked cache: make a wrapper around {open,read,close}dir()Nguyễn Thái Ngọc Duy, Nov 8, 2014
  40. 06/22 untracked cache: record/validate dir mtime and reuse cached outputNguyễn Thái Ngọc Duy, Nov 8, 2014
  41. 07/22 untracked cache: mark what dirs should be recursed/savedNguyễn Thái Ngọc Duy, Nov 8, 2014
  42. 08/22 untracked cache: don't open non-existent .gitignoreNguyễn Thái Ngọc Duy, Nov 8, 2014
  43. 09/22 untracked cache: save to an index extensionNguyễn Thái Ngọc Duy, Nov 8, 2014
  44. 10/22 untracked cache: load from UNTR index extensionNguyễn Thái Ngọc Duy, Nov 8, 2014
  45. 11/22 untracked cache: invalidate at index addition or removalNguyễn Thái Ngọc Duy, Nov 8, 2014
  46. 12/22 read-cache.c: split racy stat test to a separate functionNguyễn Thái Ngọc Duy, Nov 8, 2014
  47. 13/22 untracked cache: avoid racy timestampsNguyễn Thái Ngọc Duy, Nov 8, 2014
  48. 14/22 untracked cache: print stats with $GIT_TRACE_UNTRACKED_STATSNguyễn Thái Ngọc Duy, Nov 8, 2014
  49. 15/22 untracked cache: mark index dirty if untracked cache is updatedNguyễn Thái Ngọc Duy, Nov 8, 2014
  50. 16/22 untracked-cache: temporarily disable with $GIT_DISABLE_UNTRACKED_CACHENguyễn Thái Ngọc Duy, Nov 8, 2014
  51. 17/22 status: enable untracked cacheNguyễn Thái Ngọc Duy, Nov 8, 2014
  52. 18/22 update-index: manually enable or disable untracked cacheNguyễn Thái Ngọc Duy, Nov 8, 2014
  53. 19/22 update-index: test the system before enabling untracked cacheNguyễn Thái Ngọc Duy, Nov 8, 2014
  54. 20/22 t7063: tests for untracked cacheNguyễn Thái Ngọc Duy, Nov 8, 2014
  55. 21/22 mingw32: add uname()Nguyễn Thái Ngọc Duy, Nov 8, 2014
  56. Eric SunshineNov 9, 2014
  57. Duy NguyenNov 9, 2014
  58. Torsten BögershausenNov 9, 2014
  59. Junio C HamanoNov 9, 2014
  60. 22/22 untracked cache: guard and disable on system changesNguyễn Thái Ngọc Duy, Nov 8, 2014
  61. Eric SunshineNov 9, 2014
  62. Duy NguyenNov 9, 2014
  63. Torsten BögershausenNov 9, 2014
  64. Duy NguyenNov 9, 2014
  65. Torsten BögershausenNov 10, 2014

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.