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

[PATCH v3 01/13] dir.c: add MEASURE_EXCLUDE code for tracking exclude performance

From
Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Date
Mar 12, 2013, 13:04 UTC
Message-ID
<1363093500-16796-2-git-send-email-pclouds@gmail.com>
In-Reply-To
<1363093500-16796-1-git-send-email-pclouds@gmail.com>

Hot read_directory() codepaths are tracked. This could be helpful to see how changes affect read_directory() performance.

Results are printed when environment variable GIT_MEASURE_EXCLUDE is set.
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 dir.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 100 insertions(+), 9 deletions(-)
diff --git a/dir.c b/dir.c
index 57394e4..69c045b 100644
--- a/dir.c
+++ b/dir.c
@@ -12,6 +12,32 @@
 #include "refs.h"
 #include "wildmatch.h"
 
+#ifdef MEASURE_EXCLUDE
+static uint32_t tv_treat_leading_path;
+static uint32_t tv_read_directory;
+static uint32_t tv_treat_one_path;
+static uint32_t tv_is_excluded;
+static uint32_t tv_prep_exclude;
+static uint32_t tv_last_exclude_matching;
+static uint32_t tv_dir_add_name;
+static uint32_t tv_directory_exists_in_index;
+static uint32_t tv_simplify_away;
+static uint32_t tv_index_name_exists;
+static uint32_t tv_lazy_init_name_hash;
+#define START_CLOCK() \
+	{ \
+		struct timeval tv1, tv2; \
+		gettimeofday(&tv1, NULL);
+#define STOP_CLOCK(v) \
+		gettimeofday(&tv2, NULL); \
+		v += (uint64_t)tv2.tv_sec * 1000000 + tv2.tv_usec - \
+			(uint64_t)tv1.tv_sec * 1000000 - tv1.tv_usec; \
+	}
+#else
+#define START_CLOCK()
+#define STOP_CLOCK(v)
+#endif
+
 struct path_simplify {
 	int len;
 	const char *path;
@@ -768,8 +794,11 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,
 	const char *basename = strrchr(pathname, '/');
 	basename = (basename) ? basename+1 : pathname;
 
+	START_CLOCK();
 	prep_exclude(dir, pathname, basename-pathname);
+	STOP_CLOCK(tv_prep_exclude);
 
+	START_CLOCK();
 	for (i = EXC_CMDL; i <= EXC_FILE; i++) {
 		group = &dir->exclude_list_group[i];
 		for (j = group->nr - 1; j >= 0; j--) {
@@ -780,6 +809,7 @@ static struct exclude *last_exclude_matching(struct dir_struct *dir,
 				return exclude;
 		}
 	}
+	STOP_CLOCK(tv_last_exclude_matching);
 	return NULL;
 }
 
@@ -897,9 +927,14 @@ static struct dir_entry *dir_entry_new(const char *pathname, int len)
 
 static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)
 {
-	if (!(dir->flags & DIR_SHOW_IGNORED) &&
-	    cache_name_exists(pathname, len, ignore_case))
-		return NULL;
+	if (!(dir->flags & DIR_SHOW_IGNORED)) {
+		struct cache_entry *ce;
+		START_CLOCK();
+		ce = cache_name_exists(pathname, len, ignore_case);
+		STOP_CLOCK(tv_index_name_exists);
+		if (ce)
+			return NULL;
+	}
 
 	ALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);
 	return dir->entries[dir->nr++] = dir_entry_new(pathname, len);
@@ -1034,8 +1069,12 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,
 	const char *dirname, int len, int exclude,
 	const struct path_simplify *simplify)
 {
+	int ret;
+	START_CLOCK();
 	/* The "len-1" is to strip the final '/' */
-	switch (directory_exists_in_index(dirname, len-1)) {
+	ret = directory_exists_in_index(dirname, len-1);
+	STOP_CLOCK(tv_directory_exists_in_index);
+	switch (ret) {
 	case index_directory:
 		if ((dir->flags & DIR_SHOW_OTHER_DIRECTORIES) && exclude)
 			break;
@@ -1179,7 +1218,9 @@ static int get_index_dtype(const char *path, int len)
 	int pos;
 	struct cache_entry *ce;
 
+	START_CLOCK();
 	ce = cache_name_exists(path, len, 0);
+	STOP_CLOCK(tv_index_name_exists);
 	if (ce) {
 		if (!ce_uptodate(ce))
 			return DT_UNKNOWN;
@@ -1244,7 +1285,12 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,
 					  const struct path_simplify *simplify,
 					  int dtype, struct dirent *de)
 {
-	int exclude = is_excluded(dir, path->buf, &dtype);
+	int exclude;
+
+	START_CLOCK();
+	exclude = is_excluded(dir, path->buf,  &dtype);
+	STOP_CLOCK(tv_is_excluded);
+
 	if (exclude && (dir->flags & DIR_COLLECT_IGNORED)
 	    && exclude_matches_pathspec(path->buf, path->len, simplify))
 		dir_add_ignored(dir, path->buf, path->len);
@@ -1292,17 +1338,23 @@ static enum path_treatment treat_path(struct dir_struct *dir,
 				      int baselen,
 				      const struct path_simplify *simplify)
 {
-	int dtype;
+	int dtype, ret;
 
 	if (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, ".git"))
 		return path_ignored;
 	strbuf_setlen(path, baselen);
 	strbuf_addstr(path, de->d_name);
-	if (simplify_away(path->buf, path->len, simplify))
+	START_CLOCK();
+	ret = simplify_away(path->buf, path->len, simplify);
+	STOP_CLOCK(tv_simplify_away);
+	if (ret)
 		return path_ignored;
 
 	dtype = DTYPE(de);
-	return treat_one_path(dir, path, simplify, dtype, de);
+	START_CLOCK();
+	ret = treat_one_path(dir, path, simplify, dtype, de);
+	STOP_CLOCK(tv_treat_one_path);
+	return ret;
 }
 
 /*
@@ -1345,7 +1397,9 @@ static int read_directory_recursive(struct dir_struct *dir,
 		contents++;
 		if (check_only)
 			break;
+		START_CLOCK();
 		dir_add_name(dir, path.buf, path.len);
+		STOP_CLOCK(tv_dir_add_name);
 	}
 	closedir(fdir);
  out:
@@ -1405,6 +1459,7 @@ static int treat_leading_path(struct dir_struct *dir,
 		len--;
 	if (!len)
 		return 1;
+	START_CLOCK();
 	baselen = 0;
 	while (1) {
 		cp = path + baselen + !!baselen;
@@ -1428,6 +1483,7 @@ static int treat_leading_path(struct dir_struct *dir,
 		}
 	}
 	strbuf_release(&sb);
+	STOP_CLOCK(tv_treat_leading_path);
 	return rc;
 }
 
@@ -1439,8 +1495,43 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const char
 		return dir->nr;
 
 	simplify = create_simplify(pathspec);
-	if (!len || treat_leading_path(dir, path, len, simplify))
+	if (!len || treat_leading_path(dir, path, len, simplify)) {
+#ifdef MEASURE_EXCLUDE
+		/* The first call triggers lazy_init_name_hash() */
+		START_CLOCK();
+		index_name_exists(&the_index, "", 0, ignore_case);
+		STOP_CLOCK(tv_lazy_init_name_hash);
+#endif
+		START_CLOCK();
 		read_directory_recursive(dir, path, len, 0, simplify);
+		STOP_CLOCK(tv_read_directory);
+	}
+#ifdef MEASURE_EXCLUDE
+	if (getenv("GIT_MEASURE_EXCLUDE")) {
+		fprintf(stderr, "treat_leading_path:  %10.3f\n",
+			(float)tv_treat_leading_path / 1000000);
+		fprintf(stderr, "read_directory:      %10.3f\n",
+			(float)tv_read_directory / 1000000);
+		fprintf(stderr, "+treat_one_path:     %10.3f\n",
+			(float)tv_treat_one_path / 1000000);
+		fprintf(stderr, "++is_excluded:       %10.3f\n",
+			(float)tv_is_excluded / 1000000);
+		fprintf(stderr, "+++prep_exclude:     %10.3f\n",
+			(float)tv_prep_exclude / 1000000);
+		fprintf(stderr, "+++matching:         %10.3f\n",
+			(float)tv_last_exclude_matching / 1000000);
+		fprintf(stderr, "++dir_exist:         %10.3f\n",
+			(float)tv_directory_exists_in_index / 1000000);
+		fprintf(stderr, "++index_name_exists: %10.3f\n",
+			(float)tv_index_name_exists / 1000000);
+		fprintf(stderr, "lazy_init_name_hash: %10.3f\n",
+			(float)tv_lazy_init_name_hash / 1000000);
+		fprintf(stderr, "+simplify_away:      %10.3f\n",
+			(float)tv_simplify_away / 1000000);
+		fprintf(stderr, "+dir_add_name:       %10.3f\n",
+			(float)tv_dir_add_name / 1000000);
+	}
+#endif
 	free_simplify(simplify);
 	qsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);
 	qsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);

-- 
1.8.1.2.536.gf441e6d
Previous: Nguyễn Thái Ngọc DuyNext: Nguyễn Thái Ngọc Duy
Message 31 of 48 in “Trivial (and small) exclude optimizations”
  1. 0/3 Trivial (and small) exclude optimizationsNguyễn Thái Ngọc Duy, Mar 9, 2013
  2. 1/3 match_pathname: avoid calling strncmp if baselen is 0Nguyễn Thái Ngọc Duy, Mar 9, 2013
  3. Antoine PelisseMar 9, 2013
  4. 2/3 dir.c: inline convenient *_icase helpersNguyễn Thái Ngọc Duy, Mar 9, 2013
  5. 3/3 match_basename: use strncmp instead of strcmpNguyễn Thái Ngọc Duy, Mar 9, 2013
  6. Junio C HamanoMar 9, 2013
  7. Fredrik GustafssonMar 9, 2013
  8. Duy NguyenMar 9, 2013
  9. 0/6 Exclude optimizationsNguyễn Thái Ngọc Duy, Mar 10, 2013
  10. 1/6 match_pathname: avoid calling strncmp if baselen is 0Nguyễn Thái Ngọc Duy, Mar 10, 2013
  11. 2/6 dir.c: inline convenient *_icase helpersNguyễn Thái Ngọc Duy, Mar 10, 2013
  12. 3/6 match_basename: use strncmp instead of strcmpNguyễn Thái Ngọc Duy, Mar 10, 2013
  13. Junio C HamanoMar 10, 2013
  14. Duy NguyenMar 10, 2013
  15. Antoine PelisseMar 10, 2013
  16. Antoine PelisseMar 10, 2013
  17. Duy NguyenMar 10, 2013
  18. Antoine PelisseMar 10, 2013
  19. Duy NguyenMar 10, 2013
  20. Junio C HamanoMar 12, 2013
  21. Duy NguyenMar 13, 2013
  22. 4/6 match_{base,path}name: replace strncmp_icase with strnequal_icaseNguyễn Thái Ngọc Duy, Mar 10, 2013
  23. 5/6 dir.c: pass pathname length to last_exclude_matchingNguyễn Thái Ngọc Duy, Mar 10, 2013
  24. 6/6 exclude: filter patterns by directory levelNguyễn Thái Ngọc Duy, Mar 10, 2013
  25. Junio C HamanoMar 10, 2013
  26. Duy NguyenMar 10, 2013
  27. Junio C HamanoMar 10, 2013
  28. Duy NguyenMar 10, 2013
  29. Duy NguyenMar 11, 2013
  30. 00/13 Exclude optimizationsNguyễn Thái Ngọc Duy, Mar 12, 2013
  31. 01/13 dir.c: add MEASURE_EXCLUDE code for tracking exclude performanceNguyễn Thái Ngọc Duy, Mar 12, 2013
  32. 02/13 match_pathname: avoid calling strncmp if baselen is 0Nguyễn Thái Ngọc Duy, Mar 12, 2013
  33. 03/13 dir.c: inline convenient *_icase helpersNguyễn Thái Ngọc Duy, Mar 12, 2013
  34. 04/13 match_basename: use strncmp instead of strcmpNguyễn Thái Ngọc Duy, Mar 12, 2013
  35. Antoine PelisseMar 12, 2013
  36. Duy NguyenMar 13, 2013
  37. 05/13 match_{base,path}name: replace strncmp_icase with memequal_icaseNguyễn Thái Ngọc Duy, Mar 12, 2013
  38. Duy NguyenMar 13, 2013
  39. 06/13 dir: pass pathname length to last_exclude_matchingNguyễn Thái Ngọc Duy, Mar 12, 2013
  40. 07/13 exclude: avoid calling prep_exclude on entries of the same directoryNguyễn Thái Ngọc Duy, Mar 12, 2013
  41. 08/13 exclude: record baselen in the patternNguyễn Thái Ngọc Duy, Mar 12, 2013
  42. 09/13 exclude: filter out patterns not applicable to the current directoryNguyễn Thái Ngọc Duy, Mar 12, 2013
  43. Eric SunshineMar 12, 2013
  44. 10/13 read_directory: avoid invoking exclude machinery on tracked filesNguyễn Thái Ngọc Duy, Mar 12, 2013
  45. 11/13 Preallocate hash tables when the number of inserts are known in advanceNguyễn Thái Ngọc Duy, Mar 12, 2013
  46. 12/13 name-hash: allow to lookup a name with precalculated base hashNguyễn Thái Ngọc Duy, Mar 12, 2013
  47. 13/13 read_directory: calculate name hashes incrementallyNguyễn Thái Ngọc Duy, Mar 12, 2013
  48. Duy NguyenMar 14, 2013

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.