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

[PATCH v3 12/13] name-hash: allow to lookup a name with precalculated base hash

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

index_name_exists_base() differs from index_name_exists() in how the hash is calculated. It uses the base hash as the seed and skips the baselen part.

The intention is to reduce hashing cost during directory traversal, where the hash of the directory is calculated once, and used as base hash for all entries inside.

This poses a constraint in hash function. The function has not changed since 2008. With luck it'll never change again. If resuming hashing at any characters are not feasible with a new (better) hash function, maybe we could stop at directory boundary.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Makefile          |  1 +
 cache.h           |  2 --
 dir.c             |  1 +
 name-hash.c       | 48 ++++++++++++++++++++++--------------------------
 name-hash.h (new) | 45 +++++++++++++++++++++++++++++++++++++++++++++
 read-cache.c      |  1 +
 unpack-trees.c    |  1 +
 7 files changed, 71 insertions(+), 28 deletions(-)
 create mode 100644 name-hash.h
diff --git a/Makefile b/Makefile
index 26d3332..8d753af 100644
--- a/Makefile
+++ b/Makefile
@@ -690,6 +690,7 @@ LIB_H += mailmap.h
 LIB_H += merge-blobs.h
 LIB_H += merge-recursive.h
 LIB_H += mergesort.h
+LIB_H += name-hash.h
 LIB_H += notes-cache.h
 LIB_H += notes-merge.h
 LIB_H += notes.h
diff --git a/cache.h b/cache.h
index e493563..cf33c67 100644
--- a/cache.h
+++ b/cache.h
@@ -313,7 +313,6 @@ static inline void remove_name_hash(struct cache_entry *ce)
 #define refresh_cache(flags) refresh_index(&the_index, (flags), NULL, NULL, NULL)
 #define ce_match_stat(ce, st, options) ie_match_stat(&the_index, (ce), (st), (options))
 #define ce_modified(ce, st, options) ie_modified(&the_index, (ce), (st), (options))
-#define cache_name_exists(name, namelen, igncase) index_name_exists(&the_index, (name), (namelen), (igncase))
 #define cache_name_is_other(name, namelen) index_name_is_other(&the_index, (name), (namelen))
 #define resolve_undo_clear() resolve_undo_clear_index(&the_index)
 #define unmerge_cache_entry_at(at) unmerge_index_entry_at(&the_index, at)
@@ -442,7 +441,6 @@ extern int write_index(struct index_state *, int newfd);
 extern int discard_index(struct index_state *);
 extern int unmerged_index(const struct index_state *);
 extern int verify_path(const char *path);
-extern struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int igncase);
 extern int index_name_pos(const struct index_state *, const char *name, int namelen);
 #define ADD_CACHE_OK_TO_ADD 1		/* Ok to add */
 #define ADD_CACHE_OK_TO_REPLACE 2	/* Ok to replace file/directory */
diff --git a/dir.c b/dir.c
index 6809dd2..5fda5af 100644
--- a/dir.c
+++ b/dir.c
@@ -11,6 +11,7 @@
 #include "dir.h"
 #include "refs.h"
 #include "wildmatch.h"
+#include "name-hash.h"
 
 #ifdef MEASURE_EXCLUDE
 static uint32_t tv_treat_leading_path;
diff --git a/name-hash.c b/name-hash.c
index 1287a19..572d232 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -7,30 +7,7 @@
  */
 #define NO_THE_INDEX_COMPATIBILITY_MACROS
 #include "cache.h"
-
-/*
- * This removes bit 5 if bit 6 is set.
- *
- * That will make US-ASCII characters hash to their upper-case
- * equivalent. We could easily do this one whole word at a time,
- * but that's for future worries.
- */
-static inline unsigned char icase_hash(unsigned char c)
-{
-	return c & ~((c & 0x40) >> 1);
-}
-
-static unsigned int hash_name(const char *name, int namelen)
-{
-	unsigned int hash = 0x123;
-
-	while (namelen--) {
-		unsigned char c = *name++;
-		c = icase_hash(c);
-		hash = hash*101 + c;
-	}
-	return hash;
-}
+#include "name-hash.h"
 
 static void hash_index_entry_directories(struct index_state *istate, struct cache_entry *ce)
 {
@@ -152,9 +129,11 @@ static int same_name(const struct cache_entry *ce, const char *name, int namelen
 	return slow_same_name(name, namelen, ce->name, namelen < len ? namelen : len);
 }
 
-struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int icase)
+static inline struct cache_entry *find_entry_by_hash(struct index_state *istate,
+						     const char *name, int namelen,
+						     unsigned int hash,
+						     int icase)
 {
-	unsigned int hash = hash_name(name, namelen);
 	struct cache_entry *ce;
 
 	lazy_init_name_hash(istate);
@@ -189,3 +168,20 @@ struct cache_entry *index_name_exists(struct index_state *istate, const char *na
 	}
 	return NULL;
 }
+
+struct cache_entry *index_name_exists(struct index_state *istate,
+				      const char *name, int namelen,
+				      int icase)
+{
+	unsigned int hash = hash_name(name, namelen);
+	return find_entry_by_hash(istate, name, namelen, hash, icase);
+}
+
+struct cache_entry *index_name_exists_base(struct index_state *istate,
+					   unsigned int basehash, int baselen,
+					   const char *name, int namelen,
+					   int icase)
+{
+	unsigned int hash = hash_name_from(basehash, name + baselen, namelen - baselen);
+	return find_entry_by_hash(istate, name, namelen, hash, icase);
+}
diff --git a/name-hash.h b/name-hash.h
new file mode 100644
index 0000000..997de30
--- /dev/null
+++ b/name-hash.h
@@ -0,0 +1,45 @@
+#ifndef NAME_HASH_H
+#define NAME_HASH_H
+
+extern struct cache_entry *index_name_exists(struct index_state *istate,
+					     const char *name, int namelen,
+					     int igncase);
+extern struct cache_entry *index_name_exists_base(struct index_state *istate,
+						  unsigned int basehash, int baselen,
+						  const char *name, int namelen,
+						  int igncase);
+
+static inline struct cache_entry *cache_name_exists(const char *name, int namelen, int igncase)
+{
+	return index_name_exists(&the_index, name, namelen, igncase);
+}
+
+/*
+ * This removes bit 5 if bit 6 is set.
+ *
+ * That will make US-ASCII characters hash to their upper-case
+ * equivalent. We could easily do this one whole word at a time,
+ * but that's for future worries.
+ */
+static inline unsigned char icase_hash(unsigned char c)
+{
+	return c & ~((c & 0x40) >> 1);
+}
+
+static inline unsigned int hash_name_from(unsigned int hash,
+					  const char *name, int namelen)
+{
+	while (namelen--) {
+		unsigned char c = *name++;
+		c = icase_hash(c);
+		hash = hash*101 + c;
+	}
+	return hash;
+}
+
+static inline unsigned int hash_name(const char *name, int namelen)
+{
+	return hash_name_from(0x123, name, namelen);
+}
+
+#endif
diff --git a/read-cache.c b/read-cache.c
index 827ae55..8bd3ec8 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -14,6 +14,7 @@
 #include "resolve-undo.h"
 #include "strbuf.h"
 #include "varint.h"
+#include "name-hash.h"
 
 static struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int really);
 
diff --git a/unpack-trees.c b/unpack-trees.c
index 09e53df..60fa5d4 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -8,6 +8,7 @@
 #include "progress.h"
 #include "refs.h"
 #include "attr.h"
+#include "name-hash.h"
 
 /*
  * Error messages expected by scripts out of plumbing commands such as

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