[PATCH 5/5] name-hash: remember previous dir_entry during lazy_init_name_hash

From

Johannes Schindelin <johannes.schindelin@gmx.de>

Date

Feb 14, 2017, 11:32 UTC

Message-ID

<ce9f344b4d4de06320d5914b8f2cc2eaf0fcd923.1487071883.git.johannes.schindelin@gmx.de>

In-Reply-To

<cover.1487071883.git.johannes.schindelin@gmx.de>

From: Jeff Hostetler <jeffhost@microsoft.com>

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 name-hash.c | 50 ++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 36 insertions(+), 14 deletions(-)

diff --git a/name-hash.c b/name-hash.c
index 8f8336cc868..f95054f44cb 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -39,7 +39,8 @@ static struct dir_entry *find_dir_entry(struct index_state *istate,
 }
 
 static struct dir_entry *hash_dir_entry(struct index_state *istate,
-		struct cache_entry *ce, int namelen)
+		struct cache_entry *ce, int namelen,
+		struct dir_entry **previous_dir)
 {
 	/*
 	 * Throw each directory component in the hash for quick lookup
@@ -63,11 +64,24 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 	namelen--;
 
 	/* lookup existing entry for that directory */
-	if (ce->precomputed_hash.initialized && orig_namelen == ce_namelen(ce))
-		hash = ce->precomputed_hash.dir;
-	else
-		hash = memihash(ce->name, namelen);
-	dir = find_dir_entry_1(istate, ce->name, namelen, hash);
+	if (previous_dir && *previous_dir
+	    && namelen == (*previous_dir)->namelen
+	    && memcmp(ce->name, (*previous_dir)->name, namelen) == 0) {
+		/*
+		 * When our caller is sequentially iterating through the index,
+		 * items in the same directory will be sequential, and therefore
+		 * refer to the same dir_entry.
+		 */
+		dir = *previous_dir;
+	} else {
+		if (ce->precomputed_hash.initialized &&
+		    orig_namelen == ce_namelen(ce))
+			hash = ce->precomputed_hash.dir;
+		else
+			hash = memihash(ce->name, namelen);
+		dir = find_dir_entry_1(istate, ce->name, namelen, hash);
+	}
+
 	if (!dir) {
 		/* not found, create it and add to hash table */
 		FLEX_ALLOC_MEM(dir, name, ce->name, namelen);
@@ -76,15 +90,21 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 		hashmap_add(&istate->dir_hash, dir);
 
 		/* recursively add missing parent directories */
-		dir->parent = hash_dir_entry(istate, ce, namelen);
+		dir->parent = hash_dir_entry(istate, ce, namelen, NULL);
 	}
+
+	if (previous_dir)
+		*previous_dir = dir;
+
 	return dir;
 }
 
-static void add_dir_entry(struct index_state *istate, struct cache_entry *ce)
+static void add_dir_entry(struct index_state *istate, struct cache_entry *ce,
+			  struct dir_entry **previous_dir)
 {
 	/* Add reference to the directory entry (and parents if 0). */
-	struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));
+	struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce),
+					       previous_dir);
 	while (dir && !(dir->nr++))
 		dir = dir->parent;
 }
@@ -95,7 +115,7 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)
 	 * Release reference to the directory entry. If 0, remove and continue
 	 * with parent directory.
 	 */
-	struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));
+	struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce), NULL);
 	while (dir && !(--dir->nr)) {
 		struct dir_entry *parent = dir->parent;
 		hashmap_remove(&istate->dir_hash, dir, NULL);
@@ -104,7 +124,8 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)
 	}
 }
 
-static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
+static void hash_index_entry(struct index_state *istate, struct cache_entry *ce,
+			     struct dir_entry **previous_dir)
 {
 	unsigned int h;
 
@@ -121,7 +142,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
 	hashmap_add(&istate->name_hash, ce);
 
 	if (ignore_case)
-		add_dir_entry(istate, ce);
+		add_dir_entry(istate, ce, previous_dir);
 }
 
 static int cache_entry_cmp(const struct cache_entry *ce1,
@@ -137,6 +158,7 @@ static int cache_entry_cmp(const struct cache_entry *ce1,
 
 static void lazy_init_name_hash(struct index_state *istate)
 {
+	struct dir_entry *previous_dir = NULL;
 	int nr;
 
 	if (istate->name_hash_initialized)
@@ -146,14 +168,14 @@ static void lazy_init_name_hash(struct index_state *istate)
 	hashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp,
 			istate->cache_nr);
 	for (nr = 0; nr < istate->cache_nr; nr++)
-		hash_index_entry(istate, istate->cache[nr]);
+		hash_index_entry(istate, istate->cache[nr], &previous_dir);
 	istate->name_hash_initialized = 1;
 }
 
 void add_name_hash(struct index_state *istate, struct cache_entry *ce)
 {
 	if (istate->name_hash_initialized)
-		hash_index_entry(istate, ce);
+		hash_index_entry(istate, ce, NULL);
 }
 
 void remove_name_hash(struct index_state *istate, struct cache_entry *ce)

-- 
2.11.1.windows.1