A series of performance enhancements in the memihash and name-cache area
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
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
@@ -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
PATCH 2/5 hashmap: allow memihash computation to be continued
In reply to Johannes SchindelinFrom: 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
@@ -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
@@ -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
Re: [PATCH 2/5] hashmap: allow memihash computation to be continued
Quoted 11 lines · Johannes Schindelin
hashmap.c +3
-0@@ -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.
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@@ -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
@@ -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
@@ -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
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_BASEneeds 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.
PATCH 3/5 name-hash: precompute hash values during preload-index
In reply to Johannes SchindelinFrom: 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
@@ -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
@@ -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
@@ -73,6 +73,7 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_ncopy_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
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
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.
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
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
@@ -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
@@ -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
@@ -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()inunpack-trees.cand 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
PATCH 4/5 name-hash: specify initial size for istate.dir_hash table
In reply to Johannes SchindelinFrom: 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
@@ -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
PATCH 5/5 name-hash: remember previous dir_entry during lazy_init_name_hash
In reply to Johannes SchindelinFrom: 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
@@ -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
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 tomemihash(), 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 thatmemihash()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
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 tomemihash(), 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 thatmemihash()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
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
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.
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
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.
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
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.
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
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.
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 tomemihash(), 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 thatmemihash()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.
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 tomemihash(), 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 thatmemihash()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.
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.