{"thread":{"id":"45137","subject":"[PATCH 5/5] name-hash: remember previous dir_entry during lazy_init_name_hash","startedAt":"2017-02-14T11:33:20Z","lastAt":"2017-03-02T21:44:49Z","messageCount":25,"participants":["Johannes Schindelin","Jeff King","Jeff Hostetler","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"311533","messageId":"ce9f344b4d4de06320d5914b8f2cc2eaf0fcd923.1487071883.git.johannes.schindelin@gmx.de","threadId":"45137","inReplyTo":"cover.1487071883.git.johannes.schindelin@gmx.de","subject":"[PATCH 5/5] name-hash: remember previous dir_entry during lazy_init_name_hash","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-02-14T11:32:38Z","receivedAt":"2017-02-14T11:33:20Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Jeff Hostetler \n\nTeach hash_dir_entry() to remember the previously found dir_entry during\nlazy_init_name_hash() iteration. This is a performance optimization.\nSince items in the index array are sorted by full pathname, adjacent\nitems are likely to be in the same directory. This can save memihash()\ncomputations and hash map lookups.\n\nSigned-off-by: Jeff Hostetler \nSigned-off-by: Johannes Schindelin \n---\n name-hash.c | 50 ++++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 36 insertions(+), 14 deletions(-)\n\ndiff --git a/name-hash.c b/name-hash.c\nindex 8f8336cc868..f95054f44cb 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -39,7 +39,8 @@ static struct dir_entry *find_dir_entry(struct index_state *istate,\n }\n \n static struct dir_entry *hash_dir_entry(struct index_state *istate,\n-\t\tstruct cache_entry *ce, int namelen)\n+\t\tstruct cache_entry *ce, int namelen,\n+\t\tstruct dir_entry **previous_dir)\n {\n \t/*\n \t * Throw each directory component in the hash for quick lookup\n@@ -63,11 +64,24 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \tnamelen--;\n \n \t/* lookup existing entry for that directory */\n-\tif (ce->precomputed_hash.initialized && orig_namelen == ce_namelen(ce))\n-\t\thash = ce->precomputed_hash.dir;\n-\telse\n-\t\thash = memihash(ce->name, namelen);\n-\tdir = find_dir_entry_1(istate, ce->name, namelen, hash);\n+\tif (previous_dir && *previous_dir\n+\t && namelen == (*previous_dir)->namelen\n+\t && memcmp(ce->name, (*previous_dir)->name, namelen) == 0) {\n+\t\t/*\n+\t\t * When our caller is sequentially iterating through the index,\n+\t\t * items in the same directory will be sequential, and therefore\n+\t\t * refer to the same dir_entry.\n+\t\t */\n+\t\tdir = *previous_dir;\n+\t} else {\n+\t\tif (ce->precomputed_hash.initialized &&\n+\t\t orig_namelen == ce_namelen(ce))\n+\t\t\thash = ce->precomputed_hash.dir;\n+\t\telse\n+\t\t\thash = memihash(ce->name, namelen);\n+\t\tdir = find_dir_entry_1(istate, ce->name, namelen, hash);\n+\t}\n+\n \tif (!dir) {\n \t\t/* not found, create it and add to hash table */\n \t\tFLEX_ALLOC_MEM(dir, name, ce->name, namelen);\n@@ -76,15 +90,21 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \t\thashmap_add(&istate->dir_hash, dir);\n \n \t\t/* recursively add missing parent directories */\n-\t\tdir->parent = hash_dir_entry(istate, ce, namelen);\n+\t\tdir->parent = hash_dir_entry(istate, ce, namelen, NULL);\n \t}\n+\n+\tif (previous_dir)\n+\t\t*previous_dir = dir;\n+\n \treturn dir;\n }\n \n-static void add_dir_entry(struct index_state *istate, struct cache_entry *ce)\n+static void add_dir_entry(struct index_state *istate, struct cache_entry *ce,\n+\t\t\t struct dir_entry **previous_dir)\n {\n \t/* Add reference to the directory entry (and parents if 0). */\n-\tstruct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));\n+\tstruct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce),\n+\t\t\t\t\t previous_dir);\n \twhile (dir && !(dir->nr++))\n \t\tdir = dir->parent;\n }\n@@ -95,7 +115,7 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)\n \t * Release reference to the directory entry. If 0, remove and continue\n \t * with parent directory.\n \t */\n-\tstruct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));\n+\tstruct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce), NULL);\n \twhile (dir && !(--dir->nr)) {\n \t\tstruct dir_entry *parent = dir->parent;\n \t\thashmap_remove(&istate->dir_hash, dir, NULL);\n@@ -104,7 +124,8 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)\n \t}\n }\n \n-static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n+static void hash_index_entry(struct index_state *istate, struct cache_entry *ce,\n+\t\t\t struct dir_entry **previous_dir)\n {\n \tunsigned int h;\n \n@@ -121,7 +142,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n \thashmap_add(&istate->name_hash, ce);\n \n \tif (ignore_case)\n-\t\tadd_dir_entry(istate, ce);\n+\t\tadd_dir_entry(istate, ce, previous_dir);\n }\n \n static int cache_entry_cmp(const struct cache_entry *ce1,\n@@ -137,6 +158,7 @@ static int cache_entry_cmp(const struct cache_entry *ce1,\n \n static void lazy_init_name_hash(struct index_state *istate)\n {\n+\tstruct dir_entry *previous_dir = NULL;\n \tint nr;\n \n \tif (istate->name_hash_initialized)\n@@ -146,14 +168,14 @@ static void lazy_init_name_hash(struct index_state *istate)\n \thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp,\n \t\t\tistate->cache_nr);\n \tfor (nr = 0; nr < istate->cache_nr; nr++)\n-\t\thash_index_entry(istate, istate->cache[nr]);\n+\t\thash_index_entry(istate, istate->cache[nr], &previous_dir);\n \tistate->name_hash_initialized = 1;\n }\n \n void add_name_hash(struct index_state *istate, struct cache_entry *ce)\n {\n \tif (istate->name_hash_initialized)\n-\t\thash_index_entry(istate, ce);\n+\t\thash_index_entry(istate, ce, NULL);\n }\n \n void remove_name_hash(struct index_state *istate, struct cache_entry *ce)\n-- \n2.11.1.windows.1\n"},{"id":"311534","messageId":"8621305c69898e012720d4fe66d42b096f053073.1487071883.git.johannes.schindelin@gmx.de","threadId":"45137","inReplyTo":"cover.1487071883.git.johannes.schindelin@gmx.de","subject":"[PATCH 3/5] name-hash: precompute hash values during preload-index","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-02-14T11:32:18Z","receivedAt":"2017-02-14T11:33:24Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Jeff Hostetler \n\nPrecompute the istate.name_hash and istate.dir_hash values\nfor each cache-entry during the preload-index phase.\n\nMove the expensive memihash() calculations from lazy_init_name_hash()\nto the multi-threaded preload-index phase.\n\nSigned-off-by: Jeff Hostetler \nSigned-off-by: Johannes Schindelin \n---\n cache.h | 6 ++++++\n name-hash.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--\n preload-index.c | 2 ++\n read-cache.c | 3 +++\n 4 files changed, 66 insertions(+), 2 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 61fc86e6d71..56f7c97cdbe 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -173,6 +173,10 @@ struct cache_entry {\n \tunsigned int ce_flags;\n \tunsigned int ce_namelen;\n \tunsigned int index;\t/* for link extension */\n+\tstruct {\n+\t\tunsigned initialized:1, root_entry:1;\n+\t\tunsigned int name, dir;\n+\t} precomputed_hash;\n \tstruct object_id oid;\n \tchar name[FLEX_ARRAY]; /* more */\n };\n@@ -229,6 +233,8 @@ struct cache_entry {\n #error \"CE_EXTENDED_FLAGS out of range\"\n #endif\n \n+void precompute_istate_hashes(struct cache_entry *ce);\n+\n /* Forward structure decls */\n struct pathspec;\n struct child_process;\ndiff --git a/name-hash.c b/name-hash.c\nindex ad0bc0cef73..49eb84846df 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -50,6 +50,10 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \t */\n \tstruct dir_entry *dir;\n \tunsigned int hash;\n+\tint orig_namelen = namelen;\n+\n+\tif (ce->precomputed_hash.initialized && ce->precomputed_hash.root_entry)\n+\t\treturn NULL; /* item does not have a parent directory */\n \n \t/* get length of parent directory */\n \twhile (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))\n@@ -59,7 +63,10 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \tnamelen--;\n \n \t/* lookup existing entry for that directory */\n-\thash = memihash(ce->name, namelen);\n+\tif (ce->precomputed_hash.initialized && orig_namelen == ce_namelen(ce))\n+\t\thash = ce->precomputed_hash.dir;\n+\telse\n+\t\thash = memihash(ce->name, namelen);\n \tdir = find_dir_entry_1(istate, ce->name, namelen, hash);\n \tif (!dir) {\n \t\t/* not found, create it and add to hash table */\n@@ -99,10 +106,18 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)\n \n static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n {\n+\tunsigned int h;\n+\n \tif (ce->ce_flags & CE_HASHED)\n \t\treturn;\n \tce->ce_flags |= CE_HASHED;\n-\thashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));\n+\n+\tif (ce->precomputed_hash.initialized)\n+\t\th = ce->precomputed_hash.name;\n+\telse\n+\t\th = memihash(ce->name, ce_namelen(ce));\n+\n+\thashmap_entry_init(ce, h);\n \thashmap_add(&istate->name_hash, ce);\n \n \tif (ignore_case)\n@@ -244,3 +259,41 @@ void free_name_hash(struct index_state *istate)\n \thashmap_free(&istate->name_hash, 0);\n \thashmap_free(&istate->dir_hash, 1);\n }\n+\n+/*\n+ * Precompute the hash values for this cache_entry\n+ * for use in the istate.name_hash and istate.dir_hash.\n+ *\n+ * If the item is in the root directory, just compute the hash value (for\n+ * istate.name_hash) on the full path.\n+ *\n+ * If the item is in a subdirectory, first compute the hash value for the\n+ * immediate parent directory (for istate.dir_hash) and then the hash value for\n+ * the full path by continuing the computation.\n+ *\n+ * Note that these hashes will be used by wt_status_collect_untracked() as it\n+ * scans the worktree and maps observed paths back to the index (optionally\n+ * ignoring case). Technically, we only *NEED* to precompute this for\n+ * non-skip-worktree items (since status should not observe skipped items), but\n+ * because lazy_init_name_hash() hashes everything, we force it here.\n+ */\n+void precompute_istate_hashes(struct cache_entry *ce)\n+{\n+\tint namelen = ce_namelen(ce);\n+\n+\twhile (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))\n+\t\tnamelen--;\n+\n+\tif (namelen <= 0) {\n+\t\tce->precomputed_hash.name = memihash(ce->name, ce_namelen(ce));\n+\t\tce->precomputed_hash.root_entry = 1;\n+\t} else {\n+\t\tnamelen--;\n+\t\tce->precomputed_hash.dir = memihash(ce->name, namelen);\n+\t\tce->precomputed_hash.name = memihash_continue(\n+\t\t\tce->precomputed_hash.dir, ce->name + namelen,\n+\t\t\tce_namelen(ce) - namelen);\n+\t\tce->precomputed_hash.root_entry = 0;\n+\t}\n+\tce->precomputed_hash.initialized = 1;\n+}\ndiff --git a/preload-index.c b/preload-index.c\nindex c1fe3a3ef9c..602737f9d0f 100644\n--- a/preload-index.c\n+++ b/preload-index.c\n@@ -47,6 +47,8 @@ static void *preload_thread(void *_data)\n \t\tstruct cache_entry *ce = *cep++;\n \t\tstruct stat st;\n \n+\t\tprecompute_istate_hashes(ce);\n+\n \t\tif (ce_stage(ce))\n \t\t\tcontinue;\n \t\tif (S_ISGITLINK(ce->ce_mode))\ndiff --git a/read-cache.c b/read-cache.c\nindex 9054369dd0c..1a25c345441 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -73,6 +73,7 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n\n \tcopy_cache_entry(new, old);\n \tnew->ce_flags &= ~CE_HASHED;\n \tnew->ce_namelen = namelen;\n+\tnew->precomputed_hash.initialized = 0;\n \tnew->index = 0;\n \tmemcpy(new->name, new_name, namelen + 1);\n \n@@ -614,6 +615,7 @@ static struct cache_entry *create_alias_ce(struct index_state *istate,\n \tnew = xcalloc(1, cache_entry_size(len));\n \tmemcpy(new->name, alias->name, len);\n \tcopy_cache_entry(new, ce);\n+\tnew->precomputed_hash.initialized = 0;\n \tsave_or_free_index_entry(istate, ce);\n \treturn new;\n }\n@@ -1446,6 +1448,7 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n \tce->ce_stat_data.sd_size = get_be32(&ondisk->size);\n \tce->ce_flags = flags & ~CE_NAMEMASK;\n \tce->ce_namelen = len;\n+\tce->precomputed_hash.initialized = 0;\n \tce->index = 0;\n \thashcpy(ce->oid.hash, ondisk->sha1);\n \tmemcpy(ce->name, name, len);\n-- \n2.11.1.windows.1\n\n\n"},{"id":"311535","messageId":"cover.1487071883.git.johannes.schindelin@gmx.de","threadId":"45137","inReplyTo":null,"subject":"[PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-02-14T11:31:46Z","receivedAt":"2017-02-14T11:33:26Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"On Windows, calls to memihash() and maintaining the istate.name_hash and\nistate.dir_hash HashMaps take significant time on very large\nrepositories. This series of changes reduces the overall time taken for\nvarious operations by reducing the number calls to memihash(), moving\nsome of them into multi-threaded code, and etc.\n\nNote: one commenter in https://github.com/git-for-windows/git/pull/964\npointed out that memihash() only handles ASCII correctly. That is true.\nAnd fixing this is outside the purview of this patch series.\n\n[jes: renamed and reformatted a few places, and replaced global\nconstants by 1-bit fields, in the hopes to make the contribution a\nsmoother ride.]\n\n\nJeff Hostetler (5):\n name-hash: eliminate duplicate memihash call\n hashmap: allow memihash computation to be continued\n name-hash: precompute hash values during preload-index\n name-hash: specify initial size for istate.dir_hash table\n name-hash: remember previous dir_entry during lazy_init_name_hash\n\n cache.h | 6 +++\n hashmap.c | 14 +++++++\n hashmap.h | 2 +\n name-hash.c | 116 ++++++++++++++++++++++++++++++++++++++++++++++++--------\n preload-index.c | 2 +\n read-cache.c | 3 ++\n 6 files changed, 127 insertions(+), 16 deletions(-)\n\n\nbase-commit: 5588dbffbd61e4906e453808c6ad32f792fea521\nPublished-As: https://github.com/dscho/git/releases/tag/memihash-perf-v1\nFetch-It-Via: git fetch https://github.com/dscho/git memihash-perf-v1\n\n-- \n2.11.1.windows.1\n\n"},{"id":"311536","messageId":"7fb6e739dde4dd733524708bae57f0e6e75f61c9.1487071883.git.johannes.schindelin@gmx.de","threadId":"45137","inReplyTo":"cover.1487071883.git.johannes.schindelin@gmx.de","subject":"[PATCH 1/5] name-hash: eliminate duplicate memihash call","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-02-14T11:31:57Z","receivedAt":"2017-02-14T11:33:30Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Jeff Hostetler \n\nThe existing code called memihash() to pass to the find_dir_entry()\nfunction, and if not found, called memihash() again to pass to the\nhashmap_add() function. Remove that duplicate memihash() call in\nhash_dir_entry().\n\nSigned-off-by: Jeff Hostetler \nSigned-off-by: Johannes Schindelin \n---\n name-hash.c | 18 +++++++++++++-----\n 1 file changed, 13 insertions(+), 5 deletions(-)\n\ndiff --git a/name-hash.c b/name-hash.c\nindex 6d9f23e9325..ad0bc0cef73 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -23,15 +23,21 @@ static int dir_entry_cmp(const struct dir_entry *e1,\n \t\t\tname ? name : e2->name, e1->namelen);\n }\n \n-static struct dir_entry *find_dir_entry(struct index_state *istate,\n-\t\tconst char *name, unsigned int namelen)\n+static struct dir_entry *find_dir_entry_1(struct index_state *istate,\n+\t\tconst char *name, unsigned int namelen, unsigned int hash)\n {\n \tstruct dir_entry key;\n-\thashmap_entry_init(&key, memihash(name, namelen));\n+\thashmap_entry_init(&key, hash);\n \tkey.namelen = namelen;\n \treturn hashmap_get(&istate->dir_hash, &key, name);\n }\n \n+static struct dir_entry *find_dir_entry(struct index_state *istate,\n+\t\tconst char *name, unsigned int namelen)\n+{\n+\treturn find_dir_entry_1(istate, name, namelen, memihash(name, namelen));\n+}\n+\n static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \t\tstruct cache_entry *ce, int namelen)\n {\n@@ -43,6 +49,7 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \t * in index_state.name_hash (as ordinary cache_entries).\n \t */\n \tstruct dir_entry *dir;\n+\tunsigned int hash;\n \n \t/* get length of parent directory */\n \twhile (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))\n@@ -52,11 +59,12 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \tnamelen--;\n \n \t/* lookup existing entry for that directory */\n-\tdir = find_dir_entry(istate, ce->name, namelen);\n+\thash = memihash(ce->name, namelen);\n+\tdir = find_dir_entry_1(istate, ce->name, namelen, hash);\n \tif (!dir) {\n \t\t/* not found, create it and add to hash table */\n \t\tFLEX_ALLOC_MEM(dir, name, ce->name, namelen);\n-\t\thashmap_entry_init(dir, memihash(ce->name, namelen));\n+\t\thashmap_entry_init(dir, hash);\n \t\tdir->namelen = namelen;\n \t\thashmap_add(&istate->dir_hash, dir);\n \n-- \n2.11.1.windows.1\n\n\n"},{"id":"311537","messageId":"bd4893f86c4484fc36480848bf2d0905d961e022.1487071883.git.johannes.schindelin@gmx.de","threadId":"45137","inReplyTo":"cover.1487071883.git.johannes.schindelin@gmx.de","subject":"[PATCH 2/5] hashmap: allow memihash computation to be continued","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-02-14T11:32:07Z","receivedAt":"2017-02-14T11:33:31Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Jeff Hostetler \n\nThere are times when we compute the hash on\na full path and then the hash on just the path to the parent\ndirectory. This can be expensive on large repositories.\n\nWith the new memihash_continue() function, we can hash the parent\ndirectory first, and reuse that computed hash for all directory\nentries.\n\nSigned-off-by: Jeff Hostetler \nSigned-off-by: Johannes Schindelin \n---\n hashmap.c | 14 ++++++++++++++\n hashmap.h | 2 ++\n 2 files changed, 16 insertions(+)\n\ndiff --git a/hashmap.c b/hashmap.c\nindex b10b642229c..061b7d61da6 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -50,6 +50,20 @@ unsigned int memihash(const void *buf, size_t len)\n \treturn hash;\n }\n \n+/* Incoporate another chunk of data into a memihash computation. */\n+unsigned int memihash_continue(unsigned int hash,\n+\t\t\t const void *buf, size_t len)\n+{\n+\tconst unsigned char *p = buf;\n+\twhile (len--) {\n+\t\tunsigned int c = *p++;\n+\t\tif (c >= 'a' && c <= 'z')\n+\t\t\tc -= 'a' - 'A';\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t}\n+\treturn hash;\n+}\n+\n #define HASHMAP_INITIAL_SIZE 64\n /* grow / shrink by 2^2 */\n #define HASHMAP_RESIZE_BITS 2\ndiff --git a/hashmap.h b/hashmap.h\nindex ab7958ae333..78e14dfde71 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -12,6 +12,8 @@ extern unsigned int strhash(const char *buf);\n extern unsigned int strihash(const char *buf);\n extern unsigned int memhash(const void *buf, size_t len);\n extern unsigned int memihash(const void *buf, size_t len);\n+extern unsigned int memihash_continue(unsigned int hash_seed,\n+\t\t\t\t const void *buf, size_t len);\n \n static inline unsigned int sha1hash(const unsigned char *sha1)\n {\n-- \n2.11.1.windows.1\n\n\n"},{"id":"311538","messageId":"b30c0a47b84c063cefb7a8164dd766e251433605.1487071883.git.johannes.schindelin@gmx.de","threadId":"45137","inReplyTo":"cover.1487071883.git.johannes.schindelin@gmx.de","subject":"[PATCH 4/5] name-hash: specify initial size for istate.dir_hash table","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-02-14T11:32:30Z","receivedAt":"2017-02-14T11:33:34Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Jeff Hostetler \n\nSpecify an initial size for the istate.dir_hash hash map matching the\nsize of the istate.name_hash.\n\nPreviously hashmap_init() was given 0, causing a 64 bucket hashmap to be\ncreated. When working with very large repositories, this would cause\nnumerous rehash() calls to realloc and rebalance the hashmap. This is\nespecially true when the worktree is deep, with many directories\ncontaining a only a few files each.\n\nSigned-off-by: Jeff Hostetler \nSigned-off-by: Johannes Schindelin \n---\n name-hash.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/name-hash.c b/name-hash.c\nindex 49eb84846df..8f8336cc868 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -143,7 +143,8 @@ static void lazy_init_name_hash(struct index_state *istate)\n \t\treturn;\n \thashmap_init(&istate->name_hash, (hashmap_cmp_fn) cache_entry_cmp,\n \t\t\tistate->cache_nr);\n-\thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp, 0);\n+\thashmap_init(&istate->dir_hash, (hashmap_cmp_fn) dir_entry_cmp,\n+\t\t\tistate->cache_nr);\n \tfor (nr = 0; nr < istate->cache_nr; nr++)\n \t\thash_index_entry(istate, istate->cache[nr]);\n \tistate->name_hash_initialized = 1;\n-- \n2.11.1.windows.1\n\n\n"},{"id":"311593","messageId":"20170214220332.753i4tgclm62er4f@sigill.intra.peff.net","threadId":"45137","inReplyTo":"cover.1487071883.git.johannes.schindelin@gmx.de","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-02-14T22:03:32Z","receivedAt":"2017-02-14T22:03:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 14, 2017 at 12:31:46PM +0100, Johannes Schindelin wrote:\n\n> On Windows, calls to memihash() and maintaining the istate.name_hash and\n> istate.dir_hash HashMaps take significant time on very large\n> repositories. This series of changes reduces the overall time taken for\n> various operations by reducing the number calls to memihash(), moving\n> some of them into multi-threaded code, and etc.\n> \n> Note: one commenter in https://github.com/git-for-windows/git/pull/964\n> pointed out that memihash() only handles ASCII correctly. That is true.\n> And fixing this is outside the purview of this patch series.\n\nOut of curiosity, do you have numbers? Bonus points if the speedup can\nbe shown via a t/perf script.\n\nWe have a read-cache perf-test already, but I suspect you'd want\nsomething more like \"git status\" or \"ls-files -o\" that calls into\nread_directory().\n\n-Peff\n"},{"id":"311651","messageId":"16b1259c-4cdc-8f4d-db47-d724386a3d2b@jeffhostetler.com","threadId":"45137","inReplyTo":"20170214220332.753i4tgclm62er4f@sigill.intra.peff.net","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-02-15T14:27:53Z","receivedAt":"2017-02-15T14:27:59Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 2/14/2017 5:03 PM, Jeff King wrote:\n> On Tue, Feb 14, 2017 at 12:31:46PM +0100, Johannes Schindelin wrote:\n>\n>> On Windows, calls to memihash() and maintaining the istate.name_hash and\n>> istate.dir_hash HashMaps take significant time on very large\n>> repositories. This series of changes reduces the overall time taken for\n>> various operations by reducing the number calls to memihash(), moving\n>> some of them into multi-threaded code, and etc.\n>>\n>> Note: one commenter in https://github.com/git-for-windows/git/pull/964\n>> pointed out that memihash() only handles ASCII correctly. That is true.\n>> And fixing this is outside the purview of this patch series.\n> Out of curiosity, do you have numbers? Bonus points if the speedup can\n> be shown via a t/perf script.\n>\n> We have a read-cache perf-test already, but I suspect you'd want\n> something more like \"git status\" or \"ls-files -o\" that calls into\n> read_directory().\n\nI have some informal numbers in a spreadsheet. I was seeing\na 8-9% speed up on a status on my gigantic repo.\n\nI'll try to put together a before/after perf-test to better demonstrate \nthis.\n\nJeff\n\n"},{"id":"311654","messageId":"20170215164416.tekykkzhm6qlj2h2@sigill.intra.peff.net","threadId":"45137","inReplyTo":"16b1259c-4cdc-8f4d-db47-d724386a3d2b@jeffhostetler.com","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-02-15T16:44:16Z","receivedAt":"2017-02-15T16:44:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Feb 15, 2017 at 09:27:53AM -0500, Jeff Hostetler wrote:\n\n> I have some informal numbers in a spreadsheet. I was seeing\n> a 8-9% speed up on a status on my gigantic repo.\n> \n> I'll try to put together a before/after perf-test to better\n> demonstrate this.\n\nThanks. What I'm mostly curious about is how much each individual step\nbuys. Sometimes when doing a long optimization series, I find that some\nof the optimizations make other ones somewhat redundant (e.g., if patch\n2 causes us to call the optimized code from patch 3 less often).\n\n-Peff\n"},{"id":"312025","messageId":"xmqq7f4onjrs.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"bd4893f86c4484fc36480848bf2d0905d961e022.1487071883.git.johannes.schindelin@gmx.de","subject":"Re: [PATCH 2/5] hashmap: allow memihash computation to be continued","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-18T05:35:35Z","receivedAt":"2017-02-18T05:35:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> diff --git a/hashmap.c b/hashmap.c\n> index b10b642229c..061b7d61da6 100644\n> --- a/hashmap.c\n> +++ b/hashmap.c\n> @@ -50,6 +50,20 @@ unsigned int memihash(const void *buf, size_t len)\n> \treturn hash;\n> }\n> \n> +/* Incoporate another chunk of data into a memihash computation. */\n> +unsigned int memihash_continue(unsigned int hash,\n> +\t\t\t const void *buf, size_t len)\n> +{\n> +\tconst unsigned char *p = buf;\n> +\twhile (len--) {\n> +\t\tunsigned int c = *p++;\n> +\t\tif (c >= 'a' && c <= 'z')\n> +\t\t\tc -= 'a' - 'A';\n> +\t\thash = (hash * FNV32_PRIME) ^ c;\n> +\t}\n> +\treturn hash;\n> +}\n\nThis makes me wonder if we want to reduce the duplication (primarily\nto avoid risking the loop body to go out of sync) by doing:\n\n\tunsigned int memihash(const void *buf, size_t len)\n\t{\n\t\treturn memihash_continue(buf, len, FNV32_BASE);\n\t} \n\nIf an extra call level really matters, its \"inline\" equivalent in\nthe header would probably be good.\n"},{"id":"312026","messageId":"xmqq37fcnj7v.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"8621305c69898e012720d4fe66d42b096f053073.1487071883.git.johannes.schindelin@gmx.de","subject":"Re: [PATCH 3/5] name-hash: precompute hash values during preload-index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-18T05:47:32Z","receivedAt":"2017-02-18T05:56:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> +void precompute_istate_hashes(struct cache_entry *ce)\n> +{\n> +\tint namelen = ce_namelen(ce);\n> +\n> +\twhile (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))\n> +\t\tnamelen--;\n> +\n> +\tif (namelen <= 0) {\n> +\t\tce->precomputed_hash.name = memihash(ce->name, ce_namelen(ce));\n> +\t\tce->precomputed_hash.root_entry = 1;\n> +\t} else {\n> +\t\tnamelen--;\n> +\t\tce->precomputed_hash.dir = memihash(ce->name, namelen);\n> +\t\tce->precomputed_hash.name = memihash_continue(\n> +\t\t\tce->precomputed_hash.dir, ce->name + namelen,\n> +\t\t\tce_namelen(ce) - namelen);\n> +\t\tce->precomputed_hash.root_entry = 0;\n> +\t}\n> +\tce->precomputed_hash.initialized = 1;\n> +}\n> diff --git a/preload-index.c b/preload-index.c\n> index c1fe3a3ef9c..602737f9d0f 100644\n> --- a/preload-index.c\n> +++ b/preload-index.c\n> @@ -47,6 +47,8 @@ static void *preload_thread(void *_data)\n> \t\tstruct cache_entry *ce = *cep++;\n> \t\tstruct stat st;\n> \n> +\t\tprecompute_istate_hashes(ce);\n> +\n\nThe fact that each preload_thread() still walks the index in-order\nmakes me wonder if it may allow us to further optimize the \"dir\"\npart of the hash by passing the previous ce for which we already\nprecomputed hash values. While the loop is iterating over the paths\nin the same directory, .dir component from the previous ce can be\nreused and .name component can \"continue\", no?\n\nIt's possible that you already tried such an optimization and\nrejected it after finding that the cost of comparison of pathnames\nto tell if ce and previous ce are still in the same directory is\nmore than unconditionally memihash() the directory part, and I am in\nno way saying that I found a missed optimization opportunity you\nmust pursue. I am just being curious.\n\n"},{"id":"312027","messageId":"xmqqvas8m499.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"20170215164416.tekykkzhm6qlj2h2@sigill.intra.peff.net","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-18T05:56:02Z","receivedAt":"2017-02-18T05:56:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Wed, Feb 15, 2017 at 09:27:53AM -0500, Jeff Hostetler wrote:\n>\n>> I have some informal numbers in a spreadsheet. I was seeing\n>> a 8-9% speed up on a status on my gigantic repo.\n>> \n>> I'll try to put together a before/after perf-test to better\n>> demonstrate this.\n>\n> Thanks. What I'm mostly curious about is how much each individual step\n> buys. Sometimes when doing a long optimization series, I find that some\n> of the optimizations make other ones somewhat redundant (e.g., if patch\n> 2 causes us to call the optimized code from patch 3 less often).\n\nI am curious too.\n\nTo me 1/5 (reduction of redundant calls), 4/5 (correctly size the\nhash that would grow to a known size anyway) and 5/5 (take advantage\nof the fact that adjacent cache entries are often in the same\ndirectory) look like no brainers to take, regardless of the others\n(including themselves).\n\nIt is not clear to me if 3/5 (preload-index uses available cores to\ncompute hashes) is an unconditional win (an operation that is\npathspec limited may need hashes for only a small fraction of the\nindex---would it still be a win to compute the hash for all entries\nupon loading the index, even if we are using otherwise-idel cores?).\n\nOf course 2/5 is a prerequisite step for 3/5 and 5/5, so if we want\neither of the latter two, we cannot avoid it.\n"},{"id":"312028","messageId":"xmqqo9y0m45e.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"16b1259c-4cdc-8f4d-db47-d724386a3d2b@jeffhostetler.com","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-18T05:58:21Z","receivedAt":"2017-02-18T05:58:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff Hostetler writes:\n\n> I'll try to put together a before/after perf-test to better\n> demonstrate this.\n\nI didn't pick up the series while watching these exchanges, as I\ndidn't know how quick your turnaround would be, but now a few days\nhave passed. Just to make sure we won't forget this topic, I'll\npick up these 5 patches in the meantime.\n\nThanks.\n"},{"id":"312029","messageId":"20170218062943.j2llxuuylqs2qemy@sigill.intra.peff.net","threadId":"45137","inReplyTo":"xmqqo9y0m45e.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-02-18T06:29:43Z","receivedAt":"2017-02-18T06:33:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Feb 17, 2017 at 09:58:21PM -0800, Junio C Hamano wrote:\n\n> Jeff Hostetler writes:\n> \n> > I'll try to put together a before/after perf-test to better\n> > demonstrate this.\n> \n> I didn't pick up the series while watching these exchanges, as I\n> didn't know how quick your turnaround would be, but now a few days\n> have passed. Just to make sure we won't forget this topic, I'll\n> pick up these 5 patches in the meantime.\n\nYeah, to be clear my question was not an objection, but mostly\ncuriosity and interest.\n\n-Peff\n"},{"id":"312056","messageId":"xmqqk28nmdi4.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"20170218062943.j2llxuuylqs2qemy@sigill.intra.peff.net","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-18T20:48:35Z","receivedAt":"2017-02-18T21:14:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Feb 17, 2017 at 09:58:21PM -0800, Junio C Hamano wrote:\n>\n>> Jeff Hostetler writes:\n>> \n>> > I'll try to put together a before/after perf-test to better\n>> > demonstrate this.\n>> \n>> I didn't pick up the series while watching these exchanges, as I\n>> didn't know how quick your turnaround would be, but now a few days\n>> have passed. Just to make sure we won't forget this topic, I'll\n>> pick up these 5 patches in the meantime.\n>\n> Yeah, to be clear my question was not an objection, but mostly\n> curiosity and interest.\n\nYes, it was very clear that it wasn't an objection.\n\nBut the other Jeff sounded like a follow-up was to follow shortly if\nnot imminent so I decided to allocate my time on other topics still\nonly on the list first while waiting to see what happens.\n\n"},{"id":"312061","messageId":"MWHPR03MB2958D975B3B3022D6BC9AFBB8A5C0@MWHPR03MB2958.namprd03.prod.outlook.com","threadId":"45137","inReplyTo":"xmqqk28nmdi4.fsf@gitster.mtv.corp.google.com","subject":"RE: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Jeff Hostetler","fromEmail":"jeff.hostetler@microsoft.com","sentAt":"2017-02-18T23:52:20Z","receivedAt":"2017-02-18T23:53:05Z","isPatch":true,"sender":{"key":"jeff.hostetler@microsoft.com","avatar":"https://gravatar.com/avatar/c08ca15525534971284f8687bc24245899c4c7b6eb83f292fedbd6056c085d3b?d=mp&s=160"},"body":"> Jeff King writes:\n> \n>> On Fri, Feb 17, 2017 at 09:58:21PM -0800, Junio C Hamano wrote:\n>>\n>>> Jeff Hostetler writes:\n>>> \n>>> > I'll try to put together a before/after perf-test to better\n>>> > demonstrate this.\n>>> \n>>> I didn't pick up the series while watching these exchanges, as I\n>>> didn't know how quick your turnaround would be, but now a few days\n>>> have passed. Just to make sure we won't forget this topic, I'll\n>>> pick up these 5 patches in the meantime.\n>>\n>> Yeah, to be clear my question was not an objection, but mostly\n>> curiosity and interest.\n>\n> Yes, it was very clear that it wasn't an objection.\n> \n> But the other Jeff sounded like a follow-up was to follow shortly if\n> not imminent so I decided to allocate my time on other topics still\n> only on the list first while waiting to see what happens.\n\nSorry, I was out of the office for a family emergency on Thursday\nand Friday. Add to that the long weekend, and I won't get back around\nto this until Tuesday or Wednesday at the earliest.\n\nJeff\n\n\n\n \n"},{"id":"312062","messageId":"MWHPR03MB29582CB216B01C0A825817A08A5F0@MWHPR03MB2958.namprd03.prod.outlook.com","threadId":"45137","inReplyTo":"xmqqvas8m499.fsf@gitster.mtv.corp.google.com","subject":"RE: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Jeff Hostetler","fromEmail":"jeff.hostetler@microsoft.com","sentAt":"2017-02-19T00:02:29Z","receivedAt":"2017-02-19T00:04:12Z","isPatch":true,"sender":{"key":"jeff.hostetler@microsoft.com","avatar":"https://gravatar.com/avatar/c08ca15525534971284f8687bc24245899c4c7b6eb83f292fedbd6056c085d3b?d=mp&s=160"},"body":"\n\nFrom: Junio C Hamano [mailto:jch2355@gmail.com] On Behalf Of Junio C Hamano\n> Jeff King writes:\n>> On Wed, Feb 15, 2017 at 09:27:53AM -0500, Jeff Hostetler wrote:\n>>\n>>> I have some informal numbers in a spreadsheet. I was seeing\n>>> a 8-9% speed up on a status on my gigantic repo.\n>>> \n>>> I'll try to put together a before/after perf-test to better\n>>> demonstrate this.\n>>\n>> Thanks. What I'm mostly curious about is how much each individual step\n>> buys. Sometimes when doing a long optimization series, I find that some\n>> of the optimizations make other ones somewhat redundant (e.g., if patch\n>> 2 causes us to call the optimized code from patch 3 less often).\n>\n> I am curious too.\n>\n> To me 1/5 (reduction of redundant calls), 4/5 (correctly size the\n> hash that would grow to a known size anyway) and 5/5 (take advantage\n> of the fact that adjacent cache entries are often in the same\n> directory) look like no brainers to take, regardless of the others\n> (including themselves). \n\nagreed.\n\n> It is not clear to me if 3/5 (preload-index uses available cores to\n> compute hashes) is an unconditional win (an operation that is\n> pathspec limited may need hashes for only a small fraction of the\n> index---would it still be a win to compute the hash for all entries\n> upon loading the index, even if we are using otherwise-idel cores?).\n\nI'm not sure about pathspec cases. What I was seeing was that during\nthe call to lazy_name_init_hash() was taking 30% of the time in\n\"git status\" and 40% in \"git add \". (Again this was on my\ngiant repo with a 450MB index).\n \n> Of course 2/5 is a prerequisite step for 3/5 and 5/5, so if we want\n> either of the latter two, we cannot avoid it.\n\njeff\n\n"},{"id":"312064","messageId":"MWHPR03MB295845950BB87BA9479E973E8A5F0@MWHPR03MB2958.namprd03.prod.outlook.com","threadId":"45137","inReplyTo":"xmqq37fcnj7v.fsf@gitster.mtv.corp.google.com","subject":"RE: [PATCH 3/5] name-hash: precompute hash values during preload-index","fromName":"Jeff Hostetler","fromEmail":"jeff.hostetler@microsoft.com","sentAt":"2017-02-19T00:19:58Z","receivedAt":"2017-02-19T00:20:24Z","isPatch":true,"sender":{"key":"jeff.hostetler@microsoft.com","avatar":"https://gravatar.com/avatar/c08ca15525534971284f8687bc24245899c4c7b6eb83f292fedbd6056c085d3b?d=mp&s=160"},"body":"\n\nFrom: Junio C Hamano [mailto:jch2355@gmail.com] On Behalf Of Junio C Hamano\n> \n> The fact that each preload_thread() still walks the index in-order\n> makes me wonder if it may allow us to further optimize the \"dir\"\n> part of the hash by passing the previous ce for which we already\n> precomputed hash values. While the loop is iterating over the paths\n> in the same directory, .dir component from the previous ce can be\n> reused and .name component can \"continue\", no?\n> \n> It's possible that you already tried such an optimization and\n> rejected it after finding that the cost of comparison of pathnames\n> to tell if ce and previous ce are still in the same directory is\n> more than unconditionally memihash() the directory part, and I am in\n> no way saying that I found a missed optimization opportunity you\n> must pursue. I am just being curious.\n\nI looked at doing this, but I didn't think the complexity and overhead to\nforward search for peers at the current level didn't warrant the limited gains.\n(I was just looking at the complexity of clear_ce_flags_1() in unpack-trees.c\nand how hard it has to look to find the end of the current directory and the\neffect that that has on the recursion and it felt like too much work for the\npotential gain.)\n\nWhereas remembering the previous one was basically free. Granted, it only\nhelps us for adjacent files in the index, so it's not perfect, but gives us the\nbest bang for the buck.\n\nJeff\n\n"},{"id":"312093","messageId":"xmqqwpcllujg.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"MWHPR03MB2958D975B3B3022D6BC9AFBB8A5C0@MWHPR03MB2958.namprd03.prod.outlook.com","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-19T21:50:27Z","receivedAt":"2017-02-19T21:51:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff Hostetler writes:\n\n>> But the other Jeff sounded like a follow-up was to follow shortly if\n>> not imminent so I decided to allocate my time on other topics still\n>> only on the list first while waiting to see what happens.\n>\n> Sorry, I was out of the office for a family emergency on Thursday\n> and Friday. Add to that the long weekend, and I won't get back around\n> to this until Tuesday or Wednesday at the earliest.\n\nThe open source process makes progress at the pace of its\nparticipants, and it is expected that some topics come fast while\nothers don't.\n\nHope things are all OK for you and your family now.\n\nThanks.\n\n"},{"id":"312094","messageId":"xmqq1sutn9cf.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"MWHPR03MB295845950BB87BA9479E973E8A5F0@MWHPR03MB2958.namprd03.prod.outlook.com","subject":"Re: [PATCH 3/5] name-hash: precompute hash values during preload-index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-19T21:45:20Z","receivedAt":"2017-02-19T21:54:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff Hostetler writes:\n\n> I looked at doing this, but I didn't think the complexity and overhead to\n> forward search for peers at the current level didn't warrant the limited gains.\n\nIt seems that I wasn't clear what I meant. I didn't mean anything\ncomplex like what you said.\n\nJust something simple, like this on top of yours, that passes and\ncompares with only the previous one. I do not know if that gives\nany gain, though ;-).\n\n cache.h | 2 +-\n name-hash.c | 11 +++++++++--\n preload-index.c | 4 +++-\n 3 files changed, 13 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 390aa803df..bd2980f6e3 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -233,7 +233,7 @@ struct cache_entry {\n #error \"CE_EXTENDED_FLAGS out of range\"\n #endif\n \n-void precompute_istate_hashes(struct cache_entry *ce);\n+void precompute_istate_hashes(struct cache_entry *ce, struct cache_entry *prev);\n \n /* Forward structure decls */\n struct pathspec;\ndiff --git a/name-hash.c b/name-hash.c\nindex f95054f44c..5e09b79170 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -300,7 +300,7 @@ void free_name_hash(struct index_state *istate)\n * non-skip-worktree items (since status should not observe skipped items), but\n * because lazy_init_name_hash() hashes everything, we force it here.\n */\n-void precompute_istate_hashes(struct cache_entry *ce)\n+void precompute_istate_hashes(struct cache_entry *ce, struct cache_entry *prev)\n {\n \tint namelen = ce_namelen(ce);\n \n@@ -312,7 +312,14 @@ void precompute_istate_hashes(struct cache_entry *ce)\n \t\tce->precomputed_hash.root_entry = 1;\n \t} else {\n \t\tnamelen--;\n-\t\tce->precomputed_hash.dir = memihash(ce->name, namelen);\n+\n+\t\tif (prev && \n+\t\t prev->precomputed_hash.initialized &&\n+\t\t namelen <= ce_namelen(prev) &&\n+\t\t !memcmp(ce->name, prev->name, namelen))\n+\t\t\tce->precomputed_hash.dir = prev->precomputed_hash.dir;\n+\t\telse\n+\t\t\tce->precomputed_hash.dir = memihash(ce->name, namelen);\n \t\tce->precomputed_hash.name = memihash_continue(\n \t\t\tce->precomputed_hash.dir, ce->name + namelen,\n \t\t\tce_namelen(ce) - namelen);\ndiff --git a/preload-index.c b/preload-index.c\nindex 602737f9d0..784378ffac 100644\n--- a/preload-index.c\n+++ b/preload-index.c\n@@ -37,6 +37,7 @@ static void *preload_thread(void *_data)\n \tstruct thread_data *p = _data;\n \tstruct index_state *index = p->index;\n \tstruct cache_entry **cep = index->cache + p->offset;\n+\tstruct cache_entry *previous = NULL;\n \tstruct cache_def cache = CACHE_DEF_INIT;\n \n \tnr = p->nr;\n@@ -47,7 +48,8 @@ static void *preload_thread(void *_data)\n \t\tstruct cache_entry *ce = *cep++;\n \t\tstruct stat st;\n \n-\t\tprecompute_istate_hashes(ce);\n+\t\tprecompute_istate_hashes(ce, previous);\n+\t\tprevious = ce;\n \n \t\tif (ce_stage(ce))\n \t\t\tcontinue;\n\n\n\n\n> (I was just looking at the complexity of clear_ce_flags_1() in unpack-trees.c\n> and how hard it has to look to find the end of the current directory and the\n> effect that that has on the recursion and it felt like too much work for the\n> potential gain.)\n>\n> Whereas remembering the previous one was basically free. Granted, it only\n> helps us for adjacent files in the index, so it's not perfect, but gives us the\n> best bang for the buck.\n>\n> Jeff\n"},{"id":"312149","messageId":"alpine.DEB.2.20.1702201342020.3496@virtualbox","threadId":"45137","inReplyTo":"xmqq7f4onjrs.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 2/5] hashmap: allow memihash computation to be continued","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-02-20T12:43:38Z","receivedAt":"2017-02-20T12:44:17Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Fri, 17 Feb 2017, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > diff --git a/hashmap.c b/hashmap.c\n> > index b10b642229c..061b7d61da6 100644\n> > --- a/hashmap.c\n> > +++ b/hashmap.c\n> > @@ -50,6 +50,20 @@ unsigned int memihash(const void *buf, size_t len)\n> > \treturn hash;\n> > }\n> > \n> > +/* Incoporate another chunk of data into a memihash computation. */\n> > +unsigned int memihash_continue(unsigned int hash,\n> > +\t\t\t const void *buf, size_t len)\n> > +{\n> > +\tconst unsigned char *p = buf;\n> > +\twhile (len--) {\n> > +\t\tunsigned int c = *p++;\n> > +\t\tif (c >= 'a' && c <= 'z')\n> > +\t\t\tc -= 'a' - 'A';\n> > +\t\thash = (hash * FNV32_PRIME) ^ c;\n> > +\t}\n> > +\treturn hash;\n> > +}\n> \n> This makes me wonder if we want to reduce the duplication (primarily\n> to avoid risking the loop body to go out of sync) by doing:\n> \n> \tunsigned int memihash(const void *buf, size_t len)\n> \t{\n> \t\treturn memihash_continue(buf, len, FNV32_BASE);\n> \t} \n> \n> If an extra call level really matters, its \"inline\" equivalent in\n> the header would probably be good.\n\nWell, the hashing is supposed to be as fast as possible, so I would like\nto avoid that extra call level. However, the end result is not so pretty\nbecause FNV32_BASE needs to be made public (OTOH it removes more lines\nthan it adds):\n\n-- snipsnap --\ndiff --git a/hashmap.c b/hashmap.c\nindex 061b7d61da6..470a0832688 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -4,7 +4,6 @@\n #include \"cache.h\"\n #include \"hashmap.h\"\n \n-#define FNV32_BASE ((unsigned int) 0x811c9dc5)\n #define FNV32_PRIME ((unsigned int) 0x01000193)\n \n unsigned int strhash(const char *str)\n@@ -37,19 +36,6 @@ unsigned int memhash(const void *buf, size_t len)\n \treturn hash;\n }\n \n-unsigned int memihash(const void *buf, size_t len)\n-{\n-\tunsigned int hash = FNV32_BASE;\n-\tunsigned char *ucbuf = (unsigned char *) buf;\n-\twhile (len--) {\n-\t\tunsigned int c = *ucbuf++;\n-\t\tif (c >= 'a' && c <= 'z')\n-\t\t\tc -= 'a' - 'A';\n-\t\thash = (hash * FNV32_PRIME) ^ c;\n-\t}\n-\treturn hash;\n-}\n-\n /* Incoporate another chunk of data into a memihash computation. */\n unsigned int memihash_continue(unsigned int hash,\n \t\t\t const void *buf, size_t len)\ndiff --git a/hashmap.h b/hashmap.h\nindex 78e14dfde71..a1a8fd7dc54 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -8,12 +8,17 @@\n \n /* FNV-1 functions */\n \n+#define FNV32_BASE ((unsigned int) 0x811c9dc5)\n+\n extern unsigned int strhash(const char *buf);\n extern unsigned int strihash(const char *buf);\n extern unsigned int memhash(const void *buf, size_t len);\n-extern unsigned int memihash(const void *buf, size_t len);\n extern unsigned int memihash_continue(unsigned int hash_seed,\n \t\t\t\t const void *buf, size_t len);\n+static inline unsigned int memihash(const void *buf, size_t len)\n+{\n+\treturn memihash_continue(FNV32_BASE, buf, len);\n+}\n \n static inline unsigned int sha1hash(const unsigned char *sha1)\n {\n"},{"id":"312163","messageId":"xmqqwpckip5c.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"alpine.DEB.2.20.1702201342020.3496@virtualbox","subject":"Re: [PATCH 2/5] hashmap: allow memihash computation to be continued","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-02-20T20:27:27Z","receivedAt":"2017-02-20T20:27:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n>> If an extra call level really matters, its \"inline\" equivalent in\n>> the header would probably be good.\n>\n> Well, the hashing is supposed to be as fast as possible, so I would like\n> to avoid that extra call level. However, the end result is not so pretty\n> because FNV32_BASE needs to be made public (OTOH it removes more lines\n> than it adds):\n\nI think our usual answer is \"can we measure the difference to\ndemonstrate that the overhead for an extra call matter?\"\n\nAs two functions sit next to each other in a single file, the code\nduplication does not bother me _that_ much. A single liner \n\n /* keep implementations of these two in sync */\n\nin front of these two functions would not hurt, but whoever attempts\nto come up with a better hash needs to stare at this file carefully\nanyway, so lack of such carefulness probably wouldn't be too big an\nissue, either.\n\nBut the above 8 lines are something we need to worry about after we\ndefinitely know that we MUST have two independent functions that are\nsupposed to be kept in sync; a patch that makes us worry them before\nwe know is a premature optimization, and that bothers me even more\nthan the actual code duplication that can drift apart.\n\n"},{"id":"313100","messageId":"xmqqfuivbcz0.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"16b1259c-4cdc-8f4d-db47-d724386a3d2b@jeffhostetler.com","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-02T21:11:47Z","receivedAt":"2017-03-02T21:12:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff Hostetler writes:\n\n> On 2/14/2017 5:03 PM, Jeff King wrote:\n>> On Tue, Feb 14, 2017 at 12:31:46PM +0100, Johannes Schindelin wrote:\n>>\n>>> On Windows, calls to memihash() and maintaining the istate.name_hash and\n>>> istate.dir_hash HashMaps take significant time on very large\n>>> repositories. This series of changes reduces the overall time taken for\n>>> various operations by reducing the number calls to memihash(), moving\n>>> some of them into multi-threaded code, and etc.\n>>>\n>>> Note: one commenter in https://github.com/git-for-windows/git/pull/964\n>>> pointed out that memihash() only handles ASCII correctly. That is true.\n>>> And fixing this is outside the purview of this patch series.\n>> Out of curiosity, do you have numbers? Bonus points if the speedup can\n>> be shown via a t/perf script.\n>>\n>> We have a read-cache perf-test already, but I suspect you'd want\n>> something more like \"git status\" or \"ls-files -o\" that calls into\n>> read_directory().\n>\n> I have some informal numbers in a spreadsheet. I was seeing\n> a 8-9% speed up on a status on my gigantic repo.\n>\n> I'll try to put together a before/after perf-test to better\n> demonstrate this.\n\nPing? I do not think there is anything wrong with the changes from\ncorrectness point of view, but as the series is about performance,\nit somewhat feels pointless to merge to 'next' without mentioning\nthe actual numbers. \n\nIt might be sufficient to mention the rough numbers in the log\nmessages, if additions to t/perf/ are too cumbersome to arrange.\n\n\n"},{"id":"313102","messageId":"MWHPR03MB29581B0EDDEDCA7D51EC396F8A280@MWHPR03MB2958.namprd03.prod.outlook.com","threadId":"45137","inReplyTo":"xmqqfuivbcz0.fsf@gitster.mtv.corp.google.com","subject":"RE: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Jeff Hostetler","fromEmail":"jeff.hostetler@microsoft.com","sentAt":"2017-03-02T21:18:41Z","receivedAt":"2017-03-02T21:21:34Z","isPatch":true,"sender":{"key":"jeff.hostetler@microsoft.com","avatar":"https://gravatar.com/avatar/c08ca15525534971284f8687bc24245899c4c7b6eb83f292fedbd6056c085d3b?d=mp&s=160"},"body":"Sorry, $DAYJOB got in the way (again).\n\nThis is still on my short-list of things to take care of.\nI should have something for you next week.\n\nThanks again,\nJeff\n\n\n-----Original Message-----\nFrom: Junio C Hamano [mailto:gitster@pobox.com] \nSent: Thursday, March 2, 2017 4:12 PM\nTo: Jeff Hostetler \nCc: Jeff King ; Johannes Schindelin ; git@vger.kernel.org; Jeff Hostetler \nSubject: Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area\n\nJeff Hostetler writes:\n\n> On 2/14/2017 5:03 PM, Jeff King wrote:\n>> On Tue, Feb 14, 2017 at 12:31:46PM +0100, Johannes Schindelin wrote:\n>>\n>>> On Windows, calls to memihash() and maintaining the istate.name_hash and\n>>> istate.dir_hash HashMaps take significant time on very large\n>>> repositories. This series of changes reduces the overall time taken for\n>>> various operations by reducing the number calls to memihash(), moving\n>>> some of them into multi-threaded code, and etc.\n>>>\n>>> 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\n>>> pointed out that memihash() only handles ASCII correctly. That is true.\n>>> And fixing this is outside the purview of this patch series.\n>> Out of curiosity, do you have numbers? Bonus points if the speedup can\n>> be shown via a t/perf script.\n>>\n>> We have a read-cache perf-test already, but I suspect you'd want\n>> something more like \"git status\" or \"ls-files -o\" that calls into\n>> read_directory().\n>\n> I have some informal numbers in a spreadsheet. I was seeing\n> a 8-9% speed up on a status on my gigantic repo.\n>\n> I'll try to put together a before/after perf-test to better\n> demonstrate this.\n\nPing? I do not think there is anything wrong with the changes from\ncorrectness point of view, but as the series is about performance,\nit somewhat feels pointless to merge to 'next' without mentioning\nthe actual numbers. \n\nIt might be sufficient to mention the rough numbers in the log\nmessages, if additions to t/perf/ are too cumbersome to arrange.\n\n\n"},{"id":"313104","messageId":"xmqq7f47bbn3.fsf@gitster.mtv.corp.google.com","threadId":"45137","inReplyTo":"MWHPR03MB29581B0EDDEDCA7D51EC396F8A280@MWHPR03MB2958.namprd03.prod.outlook.com","subject":"Re: [PATCH 0/5] A series of performance enhancements in the memihash and name-cache area","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-02T21:40:32Z","receivedAt":"2017-03-02T21:44:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff Hostetler writes:\n\n> Sorry, $DAYJOB got in the way (again).\n>\n> This is still on my short-list of things to take care of.\n> I should have something for you next week.\n\nThat's perfectly OK. I just wanted a newer articule in my\nnewsreader I can bookmark so that I won't forget ;-) No hurries.\n\n"}]}