Skip to contentSkip to conversation

A series of performance enhancements in the memihash and name-cache area

PATCH In review Johannes Schindelin 5 participants 25 messages Feb 14, 2017 – Mar 2, 2017

lore
Share & tools
lore
#0 lore raw

cover A series of performance enhancements in the memihash and name-cache area

On Windows, calls to memihash() and maintaining the istate.name_hash and istate.dir_hash HashMaps take significant time on very large repositories. This series of changes reduces the overall time taken for various operations by reducing the number calls to memihash(), moving some of them into multi-threaded code, and etc.

Note: one commenter in https://github.com/git-for-windows/git/pull/964
pointed out that memihash() only handles ASCII correctly. That is true. And fixing this is outside the purview of this patch series.

[jes: renamed and reformatted a few places, and replaced global constants by 1-bit fields, in the hopes to make the contribution a smoother ride.]

Jeff Hostetler (5):
name-hash: eliminate duplicate memihash call
hashmap: allow memihash computation to be continued
name-hash: precompute hash values during preload-index
name-hash: specify initial size for istate.dir_hash table
name-hash: remember previous dir_entry during lazy_init_name_hash

 cache.h         |   6 +++
 hashmap.c       |  14 +++++++
 hashmap.h       |   2 +
 name-hash.c     | 116 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 preload-index.c |   2 +
 read-cache.c    |   3 ++
 6 files changed, 127 insertions(+), 16 deletions(-)

base-commit: 5588dbffbd61e4906e453808c6ad32f792fea521
Published-As: https://github.com/dscho/git/releases/tag/memihash-perf-v1
Fetch-It-Via: git fetch https://github.com/dscho/git memihash-perf-v1

Signature · 1 line
2.11.1.windows.1
#1 lore raw

PATCH 1/5 name-hash: eliminate duplicate memihash call

From: Jeff Hostetler <[email protected]>

The existing code called memihash() to pass to the find_dir_entry() function, and if not found, called memihash() again to pass to the hashmap_add() function. Remove that duplicate memihash() call in hash_dir_entry().

---
 name-hash.c | 18 +++++++++++++-----
 1 file changed, 13 insertions(+), 5 deletions(-)
name-hash.c +13 -5
index 6d9f23e9325..ad0bc0cef73 100644
@@ -23,15 +23,21 @@ static int dir_entry_cmp(const struct dir_entry *e1,
 			name ? name : e2->name, e1->namelen);
 }
 
-static struct dir_entry *find_dir_entry(struct index_state *istate,
-		const char *name, unsigned int namelen)
+static struct dir_entry *find_dir_entry_1(struct index_state *istate,
+		const char *name, unsigned int namelen, unsigned int hash)
 {
 	struct dir_entry key;
-	hashmap_entry_init(&key, memihash(name, namelen));
+	hashmap_entry_init(&key, hash);
 	key.namelen = namelen;
 	return hashmap_get(&istate->dir_hash, &key, name);
 }
 
+static struct dir_entry *find_dir_entry(struct index_state *istate,
+		const char *name, unsigned int namelen)
+{
+	return find_dir_entry_1(istate, name, namelen, memihash(name, namelen));
+}
+
 static struct dir_entry *hash_dir_entry(struct index_state *istate,
 		struct cache_entry *ce, int namelen)
 {
@@ -43,6 +49,7 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 	 * in index_state.name_hash (as ordinary cache_entries).
 	 */
 	struct dir_entry *dir;
+	unsigned int hash;
 
 	/* get length of parent directory */
 	while (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))
@@ -52,11 +59,12 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 	namelen--;
 
 	/* lookup existing entry for that directory */
-	dir = find_dir_entry(istate, ce->name, namelen);
+	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);
-		hashmap_entry_init(dir, memihash(ce->name, namelen));
+		hashmap_entry_init(dir, hash);
 		dir->namelen = namelen;
 		hashmap_add(&istate->dir_hash, dir);
 
Signature · 1 line
2.11.1.windows.1
#2 lore raw

PATCH 2/5 hashmap: allow memihash computation to be continued

In reply to Johannes Schindelin

From: Jeff Hostetler <[email protected]>

There are times when we compute the hash on
a full path and then the hash on just the path to the parent directory. This can be expensive on large repositories.

With the new memihash_continue() function, we can hash the parent directory first, and reuse that computed hash for all directory entries.

---
 hashmap.c | 14 ++++++++++++++
 hashmap.h |  2 ++
 2 files changed, 16 insertions(+)
hashmap.c +14 -0
index b10b642229c..061b7d61da6 100644
@@ -50,6 +50,20 @@ unsigned int memihash(const void *buf, size_t len)
 	return hash;
 }
 
+/* Incoporate another chunk of data into a memihash computation. */
+unsigned int memihash_continue(unsigned int hash,
+			       const void *buf, size_t len)
+{
+	const unsigned char *p = buf;
+	while (len--) {
+		unsigned int c = *p++;
+		if (c >= 'a' && c <= 'z')
+			c -= 'a' - 'A';
+		hash = (hash * FNV32_PRIME) ^ c;
+	}
+	return hash;
+}
+
 #define HASHMAP_INITIAL_SIZE 64
 /* grow / shrink by 2^2 */
 #define HASHMAP_RESIZE_BITS 2
hashmap.h +2 -0
index ab7958ae333..78e14dfde71 100644
@@ -12,6 +12,8 @@ extern unsigned int strhash(const char *buf);
 extern unsigned int strihash(const char *buf);
 extern unsigned int memhash(const void *buf, size_t len);
 extern unsigned int memihash(const void *buf, size_t len);
+extern unsigned int memihash_continue(unsigned int hash_seed,
+				      const void *buf, size_t len);
 
 static inline unsigned int sha1hash(const unsigned char *sha1)
 {
Signature · 1 line
2.11.1.windows.1
#3 lore raw

Re: [PATCH 2/5] hashmap: allow memihash computation to be continued

Quoted 11 lines · Johannes Schindelin
hashmap.c +3 -0
index b10b642229c..061b7d61da6 100644
@@ -50,6 +50,20 @@ unsigned int memihash(const void *buf, size_t len)
 	return hash;
 }
 
+/* Incoporate another chunk of data into a memihash computation. */
+unsigned int memihash_continue(unsigned int hash,
+			       const void *buf, size_t len)

hashmap.c unsigned int memihash(const void *buf, size_t len) · line 65

Quoted 10 lines
hashmap.c +10 -0
+{
+	const unsigned char *p = buf;
+	while (len--) {
+		unsigned int c = *p++;
+		if (c >= 'a' && c <= 'z')
+			c -= 'a' - 'A';
+		hash = (hash * FNV32_PRIME) ^ c;
+	}
+	return hash;
+}

This makes me wonder if we want to reduce the duplication (primarily to avoid risking the loop body to go out of sync) by doing:

	unsigned int memihash(const void *buf, size_t len)
	{
		return memihash_continue(buf, len, FNV32_BASE);
	}                

If an extra call level really matters, its "inline" equivalent in the header would probably be good.

#4 lore raw

Re: [PATCH 2/5] hashmap: allow memihash computation to be continued

Hi Junio,

Quoted 27 lines · Junio C Hamano
Quoted 11 lines · Johannes Schindelin
hashmap.c +3 -0
index b10b642229c..061b7d61da6 100644
@@ -50,6 +50,20 @@ unsigned int memihash(const void *buf, size_t len)
 	return hash;
 }
 
+/* Incoporate another chunk of data into a memihash computation. */
+unsigned int memihash_continue(unsigned int hash,
+			       const void *buf, size_t len)

hashmap.c unsigned int memihash(const void *buf, size_t len) · line 65

Quoted 10 lines
hashmap.c +10 -0
+{
+	const unsigned char *p = buf;
+	while (len--) {
+		unsigned int c = *p++;
+		if (c >= 'a' && c <= 'z')
+			c -= 'a' - 'A';
+		hash = (hash * FNV32_PRIME) ^ c;
+	}
+	return hash;
+}

This makes me wonder if we want to reduce the duplication (primarily to avoid risking the loop body to go out of sync) by doing:

Quoted 7 lines
	unsigned int memihash(const void *buf, size_t len)
	{
		return memihash_continue(buf, len, FNV32_BASE);
	}                

If an extra call level really matters, its "inline" equivalent in the header would probably be good.

Well, the hashing is supposed to be as fast as possible, so I would like to avoid that extra call level. However, the end result is not so pretty because FNV32_BASE needs to be made public (OTOH it removes more lines than it adds):

-- snipsnap --

hashmap.c +0 -14
index 061b7d61da6..470a0832688 100644
@@ -4,7 +4,6 @@
 #include "cache.h"
 #include "hashmap.h"
 
-#define FNV32_BASE ((unsigned int) 0x811c9dc5)
 #define FNV32_PRIME ((unsigned int) 0x01000193)
 
 unsigned int strhash(const char *str)
@@ -37,19 +36,6 @@ unsigned int memhash(const void *buf, size_t len)
 	return hash;
 }
 
-unsigned int memihash(const void *buf, size_t len)
-{
-	unsigned int hash = FNV32_BASE;
-	unsigned char *ucbuf = (unsigned char *) buf;
-	while (len--) {
-		unsigned int c = *ucbuf++;
-		if (c >= 'a' && c <= 'z')
-			c -= 'a' - 'A';
-		hash = (hash * FNV32_PRIME) ^ c;
-	}
-	return hash;
-}
-
 /* Incoporate another chunk of data into a memihash computation. */
 unsigned int memihash_continue(unsigned int hash,
 			       const void *buf, size_t len)
hashmap.h +6 -1
index 78e14dfde71..a1a8fd7dc54 100644
@@ -8,12 +8,17 @@
 
 /* FNV-1 functions */
 
+#define FNV32_BASE ((unsigned int) 0x811c9dc5)
+
 extern unsigned int strhash(const char *buf);
 extern unsigned int strihash(const char *buf);
 extern unsigned int memhash(const void *buf, size_t len);
-extern unsigned int memihash(const void *buf, size_t len);
 extern unsigned int memihash_continue(unsigned int hash_seed,
 				      const void *buf, size_t len);
+static inline unsigned int memihash(const void *buf, size_t len)
+{
+	return memihash_continue(FNV32_BASE, buf, len);
+}
 
 static inline unsigned int sha1hash(const unsigned char *sha1)
 {
#5 lore raw

Re: [PATCH 2/5] hashmap: allow memihash computation to be continued

Quoted 7 lines · Johannes Schindelin
Quoted 2 lines

If an extra call level really matters, its "inline" equivalent in the header would probably be good.

Well, the hashing is supposed to be as fast as possible, so I would like to avoid that extra call level. However, the end result is not so pretty because FNV32_BASE needs to be made public (OTOH it removes more lines than it adds):

I think our usual answer is "can we measure the difference to demonstrate that the overhead for an extra call matter?"

As two functions sit next to each other in a single file, the code duplication does not bother me _that_ much. A single liner

    /* keep implementations of these two in sync */

in front of these two functions would not hurt, but whoever attempts to come up with a better hash needs to stare at this file carefully anyway, so lack of such carefulness probably wouldn't be too big an issue, either.

But the above 8 lines are something we need to worry about after we definitely know that we MUST have two independent functions that are supposed to be kept in sync; a patch that makes us worry them before we know is a premature optimization, and that bothers me even more than the actual code duplication that can drift apart.

#6 lore raw

PATCH 3/5 name-hash: precompute hash values during preload-index

In reply to Johannes Schindelin

From: Jeff Hostetler <[email protected]>

Precompute the istate.name_hash and istate.dir_hash values for each cache-entry during the preload-index phase.

Move the expensive memihash() calculations from lazy_init_name_hash() to the multi-threaded preload-index phase.

---
 cache.h         |  6 ++++++
 name-hash.c     | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 preload-index.c |  2 ++
 read-cache.c    |  3 +++
 4 files changed, 66 insertions(+), 2 deletions(-)
cache.h +6 -0
index 61fc86e6d71..56f7c97cdbe 100644
@@ -173,6 +173,10 @@ struct cache_entry {
 	unsigned int ce_flags;
 	unsigned int ce_namelen;
 	unsigned int index;	/* for link extension */
+	struct {
+		unsigned initialized:1, root_entry:1;
+		unsigned int name, dir;
+	} precomputed_hash;
 	struct object_id oid;
 	char name[FLEX_ARRAY]; /* more */
 };
@@ -229,6 +233,8 @@ struct cache_entry {
 #error "CE_EXTENDED_FLAGS out of range"
 #endif
 
+void precompute_istate_hashes(struct cache_entry *ce);
+
 /* Forward structure decls */
 struct pathspec;
 struct child_process;
name-hash.c +55 -2

81 lines not on this page · raw message

preload-index.c +2 -0
index c1fe3a3ef9c..602737f9d0f 100644
@@ -47,6 +47,8 @@ static void *preload_thread(void *_data)
 		struct cache_entry *ce = *cep++;
 		struct stat st;
 
+		precompute_istate_hashes(ce);
+
 		if (ce_stage(ce))
 			continue;
 		if (S_ISGITLINK(ce->ce_mode))
read-cache.c +3 -0
index 9054369dd0c..1a25c345441 100644
@@ -73,6 +73,7 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n
 	copy_cache_entry(new, old);
 	new->ce_flags &= ~CE_HASHED;
 	new->ce_namelen = namelen;
+	new->precomputed_hash.initialized = 0;
 	new->index = 0;
 	memcpy(new->name, new_name, namelen + 1);
 
@@ -614,6 +615,7 @@ static struct cache_entry *create_alias_ce(struct index_state *istate,
 	new = xcalloc(1, cache_entry_size(len));
 	memcpy(new->name, alias->name, len);
 	copy_cache_entry(new, ce);
+	new->precomputed_hash.initialized = 0;
 	save_or_free_index_entry(istate, ce);
 	return new;
 }
@@ -1446,6 +1448,7 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on
 	ce->ce_stat_data.sd_size  = get_be32(&ondisk->size);
 	ce->ce_flags = flags & ~CE_NAMEMASK;
 	ce->ce_namelen = len;
+	ce->precomputed_hash.initialized = 0;
 	ce->index = 0;
 	hashcpy(ce->oid.hash, ondisk->sha1);
 	memcpy(ce->name, name, len);
Signature · 1 line
2.11.1.windows.1
#7 lore raw

Re: [PATCH 3/5] name-hash: precompute hash values during preload-index

Quoted 25 lines · Johannes Schindelin
name-hash.c +20 -0
+void precompute_istate_hashes(struct cache_entry *ce)
+{
+	int namelen = ce_namelen(ce);
+
+	while (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))
+		namelen--;
+
+	if (namelen <= 0) {
+		ce->precomputed_hash.name = memihash(ce->name, ce_namelen(ce));
+		ce->precomputed_hash.root_entry = 1;
+	} else {
+		namelen--;
+		ce->precomputed_hash.dir = memihash(ce->name, namelen);
+		ce->precomputed_hash.name = memihash_continue(
+			ce->precomputed_hash.dir, ce->name + namelen,
+			ce_namelen(ce) - namelen);
+		ce->precomputed_hash.root_entry = 0;
+	}
+	ce->precomputed_hash.initialized = 1;
+}
preload-index.c +0 -0
index c1fe3a3ef9c..602737f9d0f 100644

preload-index.c static void *preload_thread(void *_data) · line 51

Quoted 5 lines
preload-index.c +2 -0
@@ -47,6 +47,8 @@ static void *preload_thread(void *_data)
 		struct cache_entry *ce = *cep++;
 		struct stat st;
 
+		precompute_istate_hashes(ce);
+

The fact that each preload_thread() still walks the index in-order makes me wonder if it may allow us to further optimize the "dir" part of the hash by passing the previous ce for which we already precomputed hash values. While the loop is iterating over the paths in the same directory, .dir component from the previous ce can be reused and .name component can "continue", no?

It's possible that you already tried such an optimization and rejected it after finding that the cost of comparison of pathnames to tell if ce and previous ce are still in the same directory is more than unconditionally memihash() the directory part, and I am in no way saying that I found a missed optimization opportunity you must pursue. I am just being curious.

#8 lore raw

RE: [PATCH 3/5] name-hash: precompute hash values during preload-index

From: Junio C Hamano [mailto:[email protected]] On Behalf Of Junio C Hamano

Quoted 8 lines

The fact that each preload_thread() still walks the index in-order makes me wonder if it may allow us to further optimize the "dir" part of the hash by passing the previous ce for which we already precomputed hash values. While the loop is iterating over the paths in the same directory, .dir component from the previous ce can be reused and .name component can "continue", no?

Quoted 6 lines

It's possible that you already tried such an optimization and rejected it after finding that the cost of comparison of pathnames to tell if ce and previous ce are still in the same directory is more than unconditionally memihash() the directory part, and I am in no way saying that I found a missed optimization opportunity you must pursue. I am just being curious.

I looked at doing this, but I didn't think the complexity and overhead to forward search for peers at the current level didn't warrant the limited gains. (I was just looking at the complexity of clear_ce_flags_1() in unpack-trees.c and how hard it has to look to find the end of the current directory and the effect that that has on the recursion and it felt like too much work for the potential gain.)

Whereas remembering the previous one was basically free. Granted, it only helps us for adjacent files in the index, so it's not perfect, but gives us the best bang for the buck.

Jeff

#9 lore raw

Re: [PATCH 3/5] name-hash: precompute hash values during preload-index

Quoted 2 lines · Jeff Hostetler

I looked at doing this, but I didn't think the complexity and overhead to forward search for peers at the current level didn't warrant the limited gains.

It seems that I wasn't clear what I meant. I didn't mean anything complex like what you said.

Just something simple, like this on top of yours, that passes and compares with only the previous one. I do not know if that gives any gain, though ;-).

 cache.h         |  2 +-
 name-hash.c     | 11 +++++++++--
 preload-index.c |  4 +++-
 3 files changed, 13 insertions(+), 4 deletions(-)
cache.h +1 -1
index 390aa803df..bd2980f6e3 100644
@@ -233,7 +233,7 @@ struct cache_entry {
 #error "CE_EXTENDED_FLAGS out of range"
 #endif
 
-void precompute_istate_hashes(struct cache_entry *ce);
+void precompute_istate_hashes(struct cache_entry *ce, struct cache_entry *prev);
 
 /* Forward structure decls */
 struct pathspec;
name-hash.c +9 -2
index f95054f44c..5e09b79170 100644
@@ -300,7 +300,7 @@ void free_name_hash(struct index_state *istate)
  * non-skip-worktree items (since status should not observe skipped items), but
  * because lazy_init_name_hash() hashes everything, we force it here.
  */
-void precompute_istate_hashes(struct cache_entry *ce)
+void precompute_istate_hashes(struct cache_entry *ce, struct cache_entry *prev)
 {
 	int namelen = ce_namelen(ce);
 
@@ -312,7 +312,14 @@ void precompute_istate_hashes(struct cache_entry *ce)
 		ce->precomputed_hash.root_entry = 1;
 	} else {
 		namelen--;
-		ce->precomputed_hash.dir = memihash(ce->name, namelen);
+
+		if (prev && 
+		    prev->precomputed_hash.initialized &&
+		    namelen <= ce_namelen(prev) &&
+		    !memcmp(ce->name, prev->name, namelen))
+			ce->precomputed_hash.dir = prev->precomputed_hash.dir;
+		else
+			ce->precomputed_hash.dir = memihash(ce->name, namelen);
 		ce->precomputed_hash.name = memihash_continue(
 			ce->precomputed_hash.dir, ce->name + namelen,
 			ce_namelen(ce) - namelen);
preload-index.c +3 -1
index 602737f9d0..784378ffac 100644
@@ -37,6 +37,7 @@ static void *preload_thread(void *_data)
 	struct thread_data *p = _data;
 	struct index_state *index = p->index;
 	struct cache_entry **cep = index->cache + p->offset;
+	struct cache_entry *previous = NULL;
 	struct cache_def cache = CACHE_DEF_INIT;
 
 	nr = p->nr;
@@ -47,7 +48,8 @@ static void *preload_thread(void *_data)
 		struct cache_entry *ce = *cep++;
 		struct stat st;
 
-		precompute_istate_hashes(ce);
+		precompute_istate_hashes(ce, previous);
+		previous = ce;
 
 		if (ce_stage(ce))
 			continue;
Quoted 10 lines

(I was just looking at the complexity of clear_ce_flags_1() in unpack-trees.c and how hard it has to look to find the end of the current directory and the effect that that has on the recursion and it felt like too much work for the potential gain.)

Whereas remembering the previous one was basically free. Granted, it only helps us for adjacent files in the index, so it's not perfect, but gives us the best bang for the buck.

Jeff

#10 lore raw

PATCH 4/5 name-hash: specify initial size for istate.dir_hash table

In reply to Johannes Schindelin

From: Jeff Hostetler <[email protected]>

Specify an initial size for the istate.dir_hash hash map matching the size of the istate.name_hash.

Previously hashmap_init() was given 0, causing a 64 bucket hashmap to be created. When working with very large repositories, this would cause numerous rehash() calls to realloc and rebalance the hashmap. This is especially true when the worktree is deep, with many directories containing a only a few files each.

---
 name-hash.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
name-hash.c +2 -1
index 49eb84846df..8f8336cc868 100644
@@ -143,7 +143,8 @@ static void lazy_init_name_hash(struct index_state *istate)
 		return;
 	hashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp,
 			istate->cache_nr);
-	hashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp, 0);
+	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]);
 	istate->name_hash_initialized = 1;
Signature · 1 line
2.11.1.windows.1
#11 lore raw

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

In reply to Johannes Schindelin

From: Jeff Hostetler <[email protected]>

Teach hash_dir_entry() to remember the previously found dir_entry during lazy_init_name_hash() iteration. This is a performance optimization. Since items in the index array are sorted by full pathname, adjacent items are likely to be in the same directory. This can save memihash() computations and hash map lookups.

---
 name-hash.c | 50 ++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 36 insertions(+), 14 deletions(-)
name-hash.c +36 -14
index 8f8336cc868..f95054f44cb 100644
@@ -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)
Signature · 1 line
2.11.1.windows.1
#12 lore raw
In reply to Johannes Schindelin
Quoted 9 lines · Johannes Schindelin

On Windows, calls to memihash() and maintaining the istate.name_hash and istate.dir_hash HashMaps take significant time on very large repositories. This series of changes reduces the overall time taken for various operations by reducing the number calls to memihash(), moving some of them into multi-threaded code, and etc.

Note: one commenter in https://github.com/git-for-windows/git/pull/964
pointed out that memihash() only handles ASCII correctly. That is true. And fixing this is outside the purview of this patch series.

Out of curiosity, do you have numbers? Bonus points if the speedup can be shown via a t/perf script.

We have a read-cache perf-test already, but I suspect you'd want something more like "git status" or "ls-files -o" that calls into read_directory().

-Peff

#13 lore raw
Quoted 11 lines · Jeff King
Quoted 9 lines · Johannes Schindelin

On Windows, calls to memihash() and maintaining the istate.name_hash and istate.dir_hash HashMaps take significant time on very large repositories. This series of changes reduces the overall time taken for various operations by reducing the number calls to memihash(), moving some of them into multi-threaded code, and etc.

Note: one commenter in https://github.com/git-for-windows/git/pull/964
pointed out that memihash() only handles ASCII correctly. That is true. And fixing this is outside the purview of this patch series.

Quoted 6 lines

Out of curiosity, do you have numbers? Bonus points if the speedup can be shown via a t/perf script.

We have a read-cache perf-test already, but I suspect you'd want something more like "git status" or "ls-files -o" that calls into read_directory().

I have some informal numbers in a spreadsheet. I was seeing a 8-9% speed up on a status on my gigantic repo.

I'll try to put together a before/after perf-test to better demonstrate this.

Jeff

#14 lore raw
Quoted 5 lines · Jeff Hostetler

I have some informal numbers in a spreadsheet. I was seeing a 8-9% speed up on a status on my gigantic repo.

I'll try to put together a before/after perf-test to better demonstrate this.

Thanks. What I'm mostly curious about is how much each individual step buys. Sometimes when doing a long optimization series, I find that some of the optimizations make other ones somewhat redundant (e.g., if patch 2 causes us to call the optimized code from patch 3 less often).

-Peff

#15 lore raw
Quoted 5 lines · Jeff King
Quoted 3 lines · Jeff Hostetler

I have some informal numbers in a spreadsheet. I was seeing a 8-9% speed up on a status on my gigantic repo.

Quoted 7 lines
Quoted 2 lines

I'll try to put together a before/after perf-test to better demonstrate this.

Thanks. What I'm mostly curious about is how much each individual step buys. Sometimes when doing a long optimization series, I find that some of the optimizations make other ones somewhat redundant (e.g., if patch 2 causes us to call the optimized code from patch 3 less often).

I am curious too.

To me 1/5 (reduction of redundant calls), 4/5 (correctly size the hash that would grow to a known size anyway) and 5/5 (take advantage of the fact that adjacent cache entries are often in the same directory) look like no brainers to take, regardless of the others (including themselves).

It is not clear to me if 3/5 (preload-index uses available cores to compute hashes) is an unconditional win (an operation that is pathspec limited may need hashes for only a small fraction of the index---would it still be a win to compute the hash for all entries upon loading the index, even if we are using otherwise-idel cores?).

Of course 2/5 is a prerequisite step for 3/5 and 5/5, so if we want either of the latter two, we cannot avoid it.

#16 lore raw

From: Junio C Hamano [mailto:[email protected]] On Behalf Of Junio C Hamano

Quoted 14 lines
Quoted 5 lines · Jeff King
Quoted 3 lines · Jeff Hostetler

I have some informal numbers in a spreadsheet. I was seeing a 8-9% speed up on a status on my gigantic repo.

Quoted 7 lines
Quoted 2 lines

I'll try to put together a before/after perf-test to better demonstrate this.

Thanks. What I'm mostly curious about is how much each individual step buys. Sometimes when doing a long optimization series, I find that some of the optimizations make other ones somewhat redundant (e.g., if patch 2 causes us to call the optimized code from patch 3 less often).

Quoted 7 lines

I am curious too.

To me 1/5 (reduction of redundant calls), 4/5 (correctly size the hash that would grow to a known size anyway) and 5/5 (take advantage of the fact that adjacent cache entries are often in the same directory) look like no brainers to take, regardless of the others (including themselves).

agreed.

Quoted 5 lines

It is not clear to me if 3/5 (preload-index uses available cores to compute hashes) is an unconditional win (an operation that is pathspec limited may need hashes for only a small fraction of the index---would it still be a win to compute the hash for all entries upon loading the index, even if we are using otherwise-idel cores?).

I'm not sure about pathspec cases. What I was seeing was that during the call to lazy_name_init_hash() was taking 30% of the time in "git status" and 40% in "git add <one_file>". (Again this was on my giant repo with a 450MB index).

Quoted 2 lines

Of course 2/5 is a prerequisite step for 3/5 and 5/5, so if we want either of the latter two, we cannot avoid it.

jeff

#17 lore raw
In reply to Jeff Hostetler
Quoted 2 lines · Jeff Hostetler

I'll try to put together a before/after perf-test to better demonstrate this.

I didn't pick up the series while watching these exchanges, as I didn't know how quick your turnaround would be, but now a few days have passed. Just to make sure we won't forget this topic, I'll pick up these 5 patches in the meantime.

Thanks.

#18 lore raw
Quoted 9 lines · Junio C Hamano
Quoted 2 lines · Jeff Hostetler

I'll try to put together a before/after perf-test to better demonstrate this.

I didn't pick up the series while watching these exchanges, as I didn't know how quick your turnaround would be, but now a few days have passed. Just to make sure we won't forget this topic, I'll pick up these 5 patches in the meantime.

Yeah, to be clear my question was not an objection, but mostly curiosity and interest.

-Peff

#19 lore raw
Quoted 7 lines · Jeff King
Quoted 5 lines · Junio C Hamano
Quoted 2 lines · Jeff Hostetler

I'll try to put together a before/after perf-test to better demonstrate this.

Quoted 7 lines
Quoted 4 lines

I didn't pick up the series while watching these exchanges, as I didn't know how quick your turnaround would be, but now a few days have passed. Just to make sure we won't forget this topic, I'll pick up these 5 patches in the meantime.

Yeah, to be clear my question was not an objection, but mostly curiosity and interest.

Yes, it was very clear that it wasn't an objection.

But the other Jeff sounded like a follow-up was to follow shortly if not imminent so I decided to allocate my time on other topics still only on the list first while waiting to see what happens.

#20 lore raw
Quoted 14 lines
Quoted 12 lines · Jeff King
Quoted 9 lines · Junio C Hamano
Quoted 2 lines · Jeff Hostetler

I'll try to put together a before/after perf-test to better demonstrate this.

I didn't pick up the series while watching these exchanges, as I didn't know how quick your turnaround would be, but now a few days have passed. Just to make sure we won't forget this topic, I'll pick up these 5 patches in the meantime.

Quoted 8 lines
Quoted 2 lines

Yeah, to be clear my question was not an objection, but mostly curiosity and interest.

Yes, it was very clear that it wasn't an objection.

But the other Jeff sounded like a follow-up was to follow shortly if not imminent so I decided to allocate my time on other topics still only on the list first while waiting to see what happens.

Sorry, I was out of the office for a family emergency on Thursday and Friday. Add to that the long weekend, and I won't get back around to this until Tuesday or Wednesday at the earliest.

Jeff

#21 lore raw
Quoted 7 lines · Jeff Hostetler
Quoted 3 lines

But the other Jeff sounded like a follow-up was to follow shortly if not imminent so I decided to allocate my time on other topics still only on the list first while waiting to see what happens.

Sorry, I was out of the office for a family emergency on Thursday and Friday. Add to that the long weekend, and I won't get back around to this until Tuesday or Wednesday at the earliest.

The open source process makes progress at the pace of its participants, and it is expected that some topics come fast while others don't.

Hope things are all OK for you and your family now.

Thanks.

#22 lore raw
In reply to Jeff Hostetler
Quoted 19 lines · Jeff Hostetler
Quoted 11 lines · Jeff King
Quoted 9 lines · Johannes Schindelin

On Windows, calls to memihash() and maintaining the istate.name_hash and istate.dir_hash HashMaps take significant time on very large repositories. This series of changes reduces the overall time taken for various operations by reducing the number calls to memihash(), moving some of them into multi-threaded code, and etc.

Note: one commenter in https://github.com/git-for-windows/git/pull/964
pointed out that memihash() only handles ASCII correctly. That is true. And fixing this is outside the purview of this patch series.

Quoted 6 lines

Out of curiosity, do you have numbers? Bonus points if the speedup can be shown via a t/perf script.

We have a read-cache perf-test already, but I suspect you'd want something more like "git status" or "ls-files -o" that calls into read_directory().

Quoted 5 lines

I have some informal numbers in a spreadsheet. I was seeing a 8-9% speed up on a status on my gigantic repo.

I'll try to put together a before/after perf-test to better demonstrate this.

Ping? I do not think there is anything wrong with the changes from correctness point of view, but as the series is about performance, it somewhat feels pointless to merge to 'next' without mentioning the actual numbers.

It might be sufficient to mention the rough numbers in the log messages, if additions to t/perf/ are too cumbersome to arrange.

#23 lore raw

Sorry, $DAYJOB got in the way (again).

This is still on my short-list of things to take care of. I should have something for you next week.

Thanks again,
Jeff

-----Original Message-----
From: Junio C Hamano [mailto:[email protected]]
Sent: Thursday, March 2, 2017 4:12 PM
To: Jeff Hostetler <[email protected]>
Cc: Jeff King <[email protected]>; Johannes Schindelin <[email protected]>; [email protected]; Jeff Hostetler <[email protected]>
Subject: Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

Quoted 19 lines · Jeff Hostetler
Quoted 11 lines · Jeff King
Quoted 9 lines · Johannes Schindelin

On Windows, calls to memihash() and maintaining the istate.name_hash and istate.dir_hash HashMaps take significant time on very large repositories. This series of changes reduces the overall time taken for various operations by reducing the number calls to memihash(), moving some of them into multi-threaded code, and etc.

Note: one commenter in https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fgit-for-windows%2Fgit%2Fpull%2F964&data=02%7C01%7CJeff.Hostetler%40microsoft.com%7C1d493f3031f74657f29308d461b0be80%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636240859121403139&sdata=16RQH1%2BrDonsanClb3%2Fwue7pcy9l7cUq9lDJenqCgbE%3D&reserved=0
pointed out that memihash() only handles ASCII correctly. That is true.
And fixing this is outside the purview of this patch series.

Quoted 6 lines

Out of curiosity, do you have numbers? Bonus points if the speedup can be shown via a t/perf script.

We have a read-cache perf-test already, but I suspect you'd want something more like "git status" or "ls-files -o" that calls into read_directory().

Quoted 5 lines

I have some informal numbers in a spreadsheet. I was seeing a 8-9% speed up on a status on my gigantic repo.

I'll try to put together a before/after perf-test to better demonstrate this.

Ping? I do not think there is anything wrong with the changes from correctness point of view, but as the series is about performance, it somewhat feels pointless to merge to 'next' without mentioning the actual numbers.

It might be sufficient to mention the rough numbers in the log messages, if additions to t/perf/ are too cumbersome to arrange.

#24 lore raw
Quoted 4 lines · Jeff Hostetler

Sorry, $DAYJOB got in the way (again).

This is still on my short-list of things to take care of. I should have something for you next week.

That's perfectly OK. I just wanted a newer articule in my newsreader I can bookmark so that I won't forget ;-) No hurries.