[PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[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.

[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

-- 
2.11.1.windows.1

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

[Johannes Schindelin]

From: Jeff Hostetler <jeffhost@microsoft.com>

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().

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

diff --git a/name-hash.c b/name-hash.c
index 6d9f23e9325..ad0bc0cef73 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -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);
 
-- 
2.11.1.windows.1

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

[Johannes Schindelin]

From: Jeff Hostetler <jeffhost@microsoft.com>

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.

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 hashmap.c | 14 ++++++++++++++
 hashmap.h |  2 ++
 2 files changed, 16 insertions(+)

diff --git a/hashmap.c b/hashmap.c
index b10b642229c..061b7d61da6 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -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
diff --git a/hashmap.h b/hashmap.h
index ab7958ae333..78e14dfde71 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -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)
 {
-- 
2.11.1.windows.1

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

[Johannes Schindelin]

From: Jeff Hostetler <jeffhost@microsoft.com>

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.

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 cache.h         |  6 ++++++
 name-hash.c     | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 preload-index.c |  2 ++
 read-cache.c    |  3 +++
 4 files changed, 66 insertions(+), 2 deletions(-)

diff --git a/cache.h b/cache.h
index 61fc86e6d71..56f7c97cdbe 100644
--- a/cache.h
+++ b/cache.h
@@ -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;
diff --git a/name-hash.c b/name-hash.c
index ad0bc0cef73..49eb84846df 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -50,6 +50,10 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 	 */
 	struct dir_entry *dir;
 	unsigned int hash;
+	int orig_namelen = namelen;
+
+	if (ce->precomputed_hash.initialized && ce->precomputed_hash.root_entry)
+		return NULL; /* item does not have a parent directory */
 
 	/* get length of parent directory */
 	while (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))
@@ -59,7 +63,10 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 	namelen--;
 
 	/* lookup existing entry for that directory */
-	hash = memihash(ce->name, namelen);
+	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 */
@@ -99,10 +106,18 @@ 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)
 {
+	unsigned int h;
+
 	if (ce->ce_flags & CE_HASHED)
 		return;
 	ce->ce_flags |= CE_HASHED;
-	hashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));
+
+	if (ce->precomputed_hash.initialized)
+		h = ce->precomputed_hash.name;
+	else
+		h = memihash(ce->name, ce_namelen(ce));
+
+	hashmap_entry_init(ce, h);
 	hashmap_add(&istate->name_hash, ce);
 
 	if (ignore_case)
@@ -244,3 +259,41 @@ void free_name_hash(struct index_state *istate)
 	hashmap_free(&istate->name_hash, 0);
 	hashmap_free(&istate->dir_hash, 1);
 }
+
+/*
+ * Precompute the hash values for this cache_entry
+ * for use in the istate.name_hash and istate.dir_hash.
+ *
+ * If the item is in the root directory, just compute the hash value (for
+ * istate.name_hash) on the full path.
+ *
+ * If the item is in a subdirectory, first compute the hash value for the
+ * immediate parent directory (for istate.dir_hash) and then the hash value for
+ * the full path by continuing the computation.
+ *
+ * Note that these hashes will be used by wt_status_collect_untracked() as it
+ * scans the worktree and maps observed paths back to the index (optionally
+ * ignoring case). Technically, we only *NEED* to precompute this for
+ * 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)
+{
+	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;
+}
diff --git a/preload-index.c b/preload-index.c
index c1fe3a3ef9c..602737f9d0f 100644
--- a/preload-index.c
+++ b/preload-index.c
@@ -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))
diff --git a/read-cache.c b/read-cache.c
index 9054369dd0c..1a25c345441 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -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);
-- 
2.11.1.windows.1

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

[Johannes Schindelin]

From: Jeff Hostetler <jeffhost@microsoft.com>

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.

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

diff --git a/name-hash.c b/name-hash.c
index 49eb84846df..8f8336cc868 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -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;
-- 
2.11.1.windows.1

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

[Johannes Schindelin]

From: Jeff Hostetler <jeffhost@microsoft.com>

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.

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

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Jeff King]

On Tue, Feb 14, 2017 at 12:31:46PM +0100, Johannes Schindelin wrote:

> 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

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Jeff Hostetler]

On 2/14/2017 5:03 PM, Jeff King wrote:
> On Tue, Feb 14, 2017 at 12:31:46PM +0100, Johannes Schindelin wrote:
>
>> 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().

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

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Jeff King]

On Wed, Feb 15, 2017 at 09:27:53AM -0500, Jeff Hostetler wrote:

> 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

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

[Junio C Hamano]

Johannes Schindelin <johannes.schindelin@gmx.de> writes:

> diff --git a/hashmap.c b/hashmap.c
> index b10b642229c..061b7d61da6 100644
> --- a/hashmap.c
> +++ b/hashmap.c
> @@ -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;
> +}

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.

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

[Junio C Hamano]

Johannes Schindelin <johannes.schindelin@gmx.de> writes:

> +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;
> +}
> diff --git a/preload-index.c b/preload-index.c
> index c1fe3a3ef9c..602737f9d0f 100644
> --- a/preload-index.c
> +++ b/preload-index.c
> @@ -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.

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Wed, Feb 15, 2017 at 09:27:53AM -0500, Jeff Hostetler wrote:
>
>> 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).

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.

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Junio C Hamano]

Jeff Hostetler <git@jeffhostetler.com> writes:

> 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.

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Jeff King]

On Fri, Feb 17, 2017 at 09:58:21PM -0800, Junio C Hamano wrote:

> Jeff Hostetler <git@jeffhostetler.com> writes:
> 
> > 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

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Fri, Feb 17, 2017 at 09:58:21PM -0800, Junio C Hamano wrote:
>
>> Jeff Hostetler <git@jeffhostetler.com> writes:
>> 
>> > 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.

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.

RE: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Jeff Hostetler]

> Jeff King <peff@peff.net> writes:
> 
>> On Fri, Feb 17, 2017 at 09:58:21PM -0800, Junio C Hamano wrote:
>>
>>> Jeff Hostetler <git@jeffhostetler.com> writes:
>>> 
>>> > 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.
>
> 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



 

RE: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Jeff Hostetler]

From: Junio C Hamano [mailto:jch2355@gmail.com] On Behalf Of Junio C Hamano
> Jeff King <peff@peff.net> writes:
>> On Wed, Feb 15, 2017 at 09:27:53AM -0500, Jeff Hostetler wrote:
>>
>>> 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).
>
> 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.

> 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).
 
> 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

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

[Jeff Hostetler]

From: Junio C Hamano [mailto:jch2355@gmail.com] On Behalf Of Junio C Hamano
> 
> 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.

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

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

[Junio C Hamano]

Jeff Hostetler <Jeff.Hostetler@microsoft.com> writes:

> 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(-)

diff --git a/cache.h b/cache.h
index 390aa803df..bd2980f6e3 100644
--- a/cache.h
+++ b/cache.h
@@ -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;
diff --git a/name-hash.c b/name-hash.c
index f95054f44c..5e09b79170 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -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);
diff --git a/preload-index.c b/preload-index.c
index 602737f9d0..784378ffac 100644
--- a/preload-index.c
+++ b/preload-index.c
@@ -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;




> (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

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Junio C Hamano]

Jeff Hostetler <Jeff.Hostetler@microsoft.com> writes:

>> 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.

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

[Johannes Schindelin]

Hi Junio,

On Fri, 17 Feb 2017, Junio C Hamano wrote:

> Johannes Schindelin <johannes.schindelin@gmx.de> writes:
> 
> > diff --git a/hashmap.c b/hashmap.c
> > index b10b642229c..061b7d61da6 100644
> > --- a/hashmap.c
> > +++ b/hashmap.c
> > @@ -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;
> > +}
> 
> 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.

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 --
diff --git a/hashmap.c b/hashmap.c
index 061b7d61da6..470a0832688 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -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)
diff --git a/hashmap.h b/hashmap.h
index 78e14dfde71..a1a8fd7dc54 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -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)
 {

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

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

>> 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.

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Junio C Hamano]

Jeff Hostetler <git@jeffhostetler.com> writes:

> On 2/14/2017 5:03 PM, Jeff King wrote:
>> On Tue, Feb 14, 2017 at 12:31:46PM +0100, Johannes Schindelin wrote:
>>
>>> 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().
>
> 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.

RE: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[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.

Thanks again,
Jeff


-----Original Message-----
From: Junio C Hamano [mailto:gitster@pobox.com] 
Sent: Thursday, March 2, 2017 4:12 PM
To: Jeff Hostetler <git@jeffhostetler.com>
Cc: Jeff King <peff@peff.net>; Johannes Schindelin <johannes.schindelin@gmx.de>; git@vger.kernel.org; Jeff Hostetler <Jeff.Hostetler@microsoft.com>
Subject: Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

Jeff Hostetler <git@jeffhostetler.com> writes:

> On 2/14/2017 5:03 PM, Jeff King wrote:
>> On Tue, Feb 14, 2017 at 12:31:46PM +0100, Johannes Schindelin wrote:
>>
>>> 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.
>> 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.

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.

Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area

[Junio C Hamano]

Jeff Hostetler <Jeff.Hostetler@microsoft.com> writes:

> 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.