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

[PATCH v3 13/13] read_directory: calculate name hashes incrementally

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

Instead of index_name_exists() calculating a hash for full pathname for every entry, we calculate partial hash per directory, use it as a seed. The number of characters that icase_hash has to chew will reduce.

treat_leading_path: 0.000 0.000 read_directory: 1.296 1.235 +treat_one_path: 0.599 0.531 ++is_excluded: 0.102 0.102 +++prep_exclude: 0.040 0.040 +++matching: 0.035 0.035 ++dir_exist: 0.035 0.035 ++index_name_exists: 0.292 0.225 lazy_init_name_hash: 0.155 0.155 +simplify_away: 0.082 0.083 +dir_add_name: 0.000 0.000

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 dir.c | 44 +++++++++++++++++++++++++++++++++-----------
 1 file changed, 33 insertions(+), 11 deletions(-)
diff --git a/dir.c b/dir.c
index 5fda5af..8638dcd 100644
--- a/dir.c
+++ b/dir.c
@@ -46,6 +46,7 @@ struct path_simplify {
 
 static void read_directory_recursive(struct dir_struct *dir,
 				     const char *path, int len,
+				     unsigned int hash,
 				     int check_only,
 				     const struct path_simplify *simplify,
 				     int *contents);
@@ -1044,12 +1045,17 @@ static struct dir_entry *dir_entry_new(const char *pathname, int len)
 	return ent;
 }
 
-static struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)
+static struct dir_entry *dir_add_name(struct dir_struct *dir,
+				      const char *pathname, int len,
+				      unsigned int hash, int baselen)
 {
 	if (!(dir->flags & DIR_SHOW_IGNORED)) {
 		struct cache_entry *ce;
 		START_CLOCK();
-		ce = cache_name_exists(pathname, len, ignore_case);
+		ce = index_name_exists_base(&the_index,
+					    hash, baselen,
+					    pathname, len,
+					    ignore_case);
 		STOP_CLOCK(tv_index_name_exists);
 		if (ce)
 			return NULL;
@@ -1225,7 +1231,9 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,
 	if ((dir->flags & DIR_SHOW_IGNORED) && !exclude) {
 		dir->flags &= ~DIR_SHOW_IGNORED;
 		dir->flags |= DIR_HIDE_EMPTY_DIRECTORIES;
-		read_directory_recursive(dir, dirname, len, 1, simplify, &contents);
+		read_directory_recursive(dir, dirname, len,
+					 hash_name(dirname, len),
+					 1, simplify, &contents);
 		dir->flags &= ~DIR_HIDE_EMPTY_DIRECTORIES;
 		dir->flags |= DIR_SHOW_IGNORED;
 
@@ -1234,7 +1242,9 @@ static enum directory_treatment treat_directory(struct dir_struct *dir,
 	if (!(dir->flags & DIR_SHOW_IGNORED) &&
 	    !(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
 		return show_directory;
-	read_directory_recursive(dir, dirname, len, 1, simplify, &contents);
+	read_directory_recursive(dir, dirname, len,
+				 hash_name(dirname, len),
+				 1, simplify, &contents);
 	if (!contents)
 		return ignore_directory;
 	return show_directory;
@@ -1401,6 +1411,8 @@ enum path_treatment {
 
 static enum path_treatment treat_one_path(struct dir_struct *dir,
 					  struct strbuf *path,
+					  unsigned int hash,
+					  int baselen,
 					  const struct path_simplify *simplify,
 					  int dtype, struct dirent *de,
 					  int exclude_shortcut_ok)
@@ -1416,7 +1428,8 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,
 	    dtype != DT_DIR) {
 		struct cache_entry *ce;
 		START_CLOCK();
-		ce = cache_name_exists(path->buf, path->len, ignore_case);
+		ce = index_name_exists_base(&the_index, hash, baselen,
+					    path->buf, path->len, ignore_case);
 		STOP_CLOCK(tv_index_name_exists);
 		if (ce)
 			return path_ignored;
@@ -1467,6 +1480,7 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,
 static enum path_treatment treat_path(struct dir_struct *dir,
 				      struct dirent *de,
 				      struct strbuf *path,
+				      unsigned int hash,
 				      int baselen,
 				      const struct path_simplify *simplify,
 				      int exclude_shortcut_ok)
@@ -1485,7 +1499,8 @@ static enum path_treatment treat_path(struct dir_struct *dir,
 
 	dtype = DTYPE(de);
 	START_CLOCK();
-	ret = treat_one_path(dir, path, simplify, dtype, de, exclude_shortcut_ok);
+	ret = treat_one_path(dir, path, hash, baselen,
+			     simplify, dtype, de, exclude_shortcut_ok);
 	STOP_CLOCK(tv_treat_one_path);
 	return ret;
 }
@@ -1501,6 +1516,7 @@ static enum path_treatment treat_path(struct dir_struct *dir,
  */
 static void read_directory_recursive(struct dir_struct *dir,
 				     const char *base, int baselen,
+				     unsigned int hash,
 				     int check_only,
 				     const struct path_simplify *simplify,
 				     int *contents)
@@ -1517,12 +1533,16 @@ static void read_directory_recursive(struct dir_struct *dir,
 
 	dir->exclude_prepared = 0;
 	while ((de = readdir(fdir)) != NULL) {
-		switch (treat_path(dir, de, &path, baselen,
+		switch (treat_path(dir, de, &path, hash, baselen,
 				   simplify,
 				   !check_only && !contents)) {
 		case path_recurse:
 			read_directory_recursive(dir, path.buf,
-						 path.len, 0,
+						 path.len,
+						 hash_name_from(hash,
+								path.buf + baselen,
+								path.len - baselen),
+						 0,
 						 simplify,
 						 contents);
 			continue;
@@ -1543,7 +1563,7 @@ static void read_directory_recursive(struct dir_struct *dir,
 		if (check_only)
 			break;
 		START_CLOCK();
-		dir_add_name(dir, path.buf, path.len);
+		dir_add_name(dir, path.buf, path.len, hash, baselen);
 		STOP_CLOCK(tv_dir_add_name);
 	}
 	closedir(fdir);
@@ -1619,7 +1639,7 @@ static int treat_leading_path(struct dir_struct *dir,
 		if (simplify_away(sb.buf, sb.len, simplify))
 			break;
 		dir->exclude_prepared = 0;
-		if (treat_one_path(dir, &sb, simplify,
+		if (treat_one_path(dir, &sb, 0, 0, simplify,
 				   DT_DIR, NULL, 0) == path_ignored)
 			break; /* do not recurse into it */
 		if (len <= baselen) {
@@ -1648,7 +1668,9 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const char
 		STOP_CLOCK(tv_lazy_init_name_hash);
 #endif
 		START_CLOCK();
-		read_directory_recursive(dir, path, len, 0, simplify, NULL);
+		read_directory_recursive(dir, path, len,
+					 hash_name(path, len),
+					 0, simplify, NULL);
 		STOP_CLOCK(tv_read_directory);
 	}
 #ifdef MEASURE_EXCLUDE

-- 
1.8.1.2.536.gf441e6d
Previous: Nguyễn Thái Ngọc DuyNext: Duy Nguyen
Message 47 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.