{"thread":{"id":"45467","subject":"[PATCH 3/6] hashmap: Add disallow_rehash setting","startedAt":"2017-03-22T17:15:10Z","lastAt":"2017-03-22T21:30:04Z","messageCount":14,"participants":["git@jeffhostetler.com","Stefan Beller","Jeff Hostetler","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"314921","messageId":"1490202865-31325-4-git-send-email-git@jeffhostetler.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH 3/6] hashmap: Add disallow_rehash setting","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T17:14:22Z","receivedAt":"2017-03-22T17:15:10Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nTeach hashmap to allow rehashes to be suppressed.\nThis is useful when hashmaps are accessed by multiple\nthreads.  It still requires the caller to properly\nmanage their locking.  This just prevents unexpected\nrehashing during inserts and deletes.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n hashmap.c | 12 +++++++++++-\n hashmap.h | 24 ++++++++++++++++++++++++\n 2 files changed, 35 insertions(+), 1 deletion(-)\n\ndiff --git a/hashmap.c b/hashmap.c\nindex 505e63f..37dfc37 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -104,11 +104,19 @@ static inline unsigned int bucket(const struct hashmap *map,\n \treturn key->hash & (map->tablesize - 1);\n }\n \n+int hashmap_bucket(const struct hashmap *map, unsigned int hash)\n+{\n+\treturn hash & (map->tablesize - 1);\n+}\n+\n static void rehash(struct hashmap *map, unsigned int newsize)\n {\n \tunsigned int i, oldsize = map->tablesize;\n \tstruct hashmap_entry **oldtable = map->table;\n \n+\tif (map->disallow_rehash)\n+\t\treturn;\n+\n \talloc_table(map, newsize);\n \tfor (i = 0; i < oldsize; i++) {\n \t\tstruct hashmap_entry *e = oldtable[i];\n@@ -141,7 +149,9 @@ void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function,\n \t\tsize_t initial_size)\n {\n \tunsigned int size = HASHMAP_INITIAL_SIZE;\n-\tmap->size = 0;\n+\n+\tmemset(map, 0, sizeof(*map));\n+\n \tmap->cmpfn = equals_function ? equals_function : always_equal;\n \n \t/* calculate initial table size and allocate the table */\ndiff --git a/hashmap.h b/hashmap.h\nindex 45eda69..de6022a 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -39,6 +39,7 @@ struct hashmap {\n \tstruct hashmap_entry **table;\n \thashmap_cmp_fn cmpfn;\n \tunsigned int size, tablesize, grow_at, shrink_at;\n+\tunsigned disallow_rehash : 1;\n };\n \n struct hashmap_iter {\n@@ -77,6 +78,29 @@ static inline void *hashmap_get_from_hash(const struct hashmap *map,\n \treturn hashmap_get(map, &key, keydata);\n }\n \n+int hashmap_bucket(const struct hashmap *map, unsigned int hash);\n+\n+/*\n+ * Disallow/allow rehashing of the hashmap.\n+ * This is useful if the caller knows that the hashmap\n+ * needs multi-threaded access.  The caller is still\n+ * required to guard/lock searches and inserts in a\n+ * manner appropriate to their usage.  This simply\n+ * prevents the table from being unexpectedly re-mapped.\n+ *\n+ * If is up to the caller to ensure that the hashmap is\n+ * initialized to a reasonable size to prevent poor\n+ * performance.\n+ *\n+ * When value=1, prevent future rehashes on adds and deleted.\n+ * When value=0, allow future rehahses.  This DOES NOT force\n+ * a rehash now.\n+ */\n+static inline void hashmap_disallow_rehash(struct hashmap *map, unsigned value)\n+{\n+\tmap->disallow_rehash = value;\n+}\n+\n /* hashmap_iter functions */\n \n extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter);\n-- \n2.7.4\n\n"},{"id":"314922","messageId":"1490202865-31325-5-git-send-email-git@jeffhostetler.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH 4/6] name-hash: perf improvement for lazy_init_name_hash","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T17:14:23Z","receivedAt":"2017-03-22T17:15:43Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nImprove performance of lazy_init_name_hash() when\nignore_case is set.  Teach name-hash to build the\nistate.name_hash and istate.dir_hash simultaneously\nusing a forward-diving technique on the pathname\nof the index_entry, rather than adding name_hash\nentries and then searching backwards in the pathname\nfor parent directories.\n\nThis borrows algorithm ideas from clear_ce_flags_{1,dir}.\n\nMultiple threads are used with the new algorithm to\nspeed hashmap construction.\n\nThis new code path is only used when threads are present\n(a compiler settings) and when the index is large enough\nto warrant the pthread complexity.\n\nThe code in clear_ce_flags_dir() uses a linear search to\nfind the adjacent index entries with the same prefix; a\nbinary search is used here handle_range_dir() to further\nspeed things up.\n\nThe size of LAZY_THREAD_COST was determined from rough\nanalysis using:\n    t/helper/test-lazy-init-name-hash --analyze\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n name-hash.c | 487 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 480 insertions(+), 7 deletions(-)\n\ndiff --git a/name-hash.c b/name-hash.c\nindex 3f7722a..a582650 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__hash(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__hash(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@@ -112,21 +118,488 @@ static int cache_entry_cmp(const struct cache_entry *ce1,\n \treturn remove ? !(ce1 == ce2) : 0;\n }\n \n-static void lazy_init_name_hash(struct index_state *istate)\n+\n+#ifdef NO_PTHREADS\n+\n+static int lookup_lazy_params(struct index_state *istate)\n {\n-\tint nr;\n+\treturn 0;\n+}\n+\n+#else\n+\n+#include \"thread-utils.h\"\n+\n+/*\n+ * Set a minimum number of cache_entries that we will handle per\n+ * thread and use that to decide how many threads to run (upto\n+ * the number on the system).\n+ *\n+ * For guidance setting the lower per-thread bound, see:\n+ *     t/helper/test-lazy-init-name-hash --analyze\n+ */\n+#define LAZY_THREAD_COST (2000)\n+\n+/*\n+ * We use n mutexes to guard n partitions of the \"istate->dir_hash\"\n+ * hashtable.  Since \"find\" and \"insert\" operations will hash to a\n+ * particular bucket and modify/search a single chain, we can say\n+ * that \"all chains mod n\" are guarded by the same mutex -- rather\n+ * than having a single mutex to guard the entire table.  (This does\n+ * require that we disable \"rehashing\" on the hashtable.)\n+ *\n+ * So, a larger value here decreases the probability of a collision\n+ * and the time that each thread must wait for the mutex.\n+ */\n+#define LAZY_MAX_MUTEX   (32)\n+\n+static int lazy_try_threaded = 1;\n+static int lazy_nr_dir_threads = 0;\n+static pthread_mutex_t *lazy_dir_mutex_array;\n+\n+/*\n+ * An array of lazy_entry items is used by the n threads in\n+ * the directory parse (first) phase to (lock-free) store the\n+ * intermediate results.  These values are then referenced by\n+ * the 2 threads in the second phase.\n+ */\n+struct lazy_entry {\n+\tstruct dir_entry *dir;\n+\tunsigned int hash_dir;\n+\tunsigned int hash_name;\n+};\n+\n+/*\n+ * Decide if we want to use threads (if available) to load\n+ * the hash tables.  We set \"lazy_nr_dir_threads\" to zero when\n+ * it is not worth it.\n+ */\n+static int lookup_lazy_params(struct index_state *istate)\n+{\n+\tint nr_cpus;\n+\n+\tlazy_nr_dir_threads = 0;\n+\n+\tif (!lazy_try_threaded)\n+\t\treturn 0;\n+\n+\t/*\n+\t * If we are respecting case, just use the original\n+\t * code to build the \"istate->name_hash\".  We don't\n+\t * need the complexity here.\n+\t */\n+\tif (!ignore_case)\n+\t\treturn 0;\n+\n+\tnr_cpus = online_cpus();\n+\tif (nr_cpus < 2)\n+\t\treturn 0;\n+\n+\tif (istate->cache_nr < 2 * LAZY_THREAD_COST)\n+\t\treturn 0;\n+\n+\tif (istate->cache_nr < nr_cpus * LAZY_THREAD_COST)\n+\t\tnr_cpus = istate->cache_nr / LAZY_THREAD_COST;\n+\tlazy_nr_dir_threads = nr_cpus;\n+\treturn lazy_nr_dir_threads;\n+}\n+\n+/*\n+ * Initialize n mutexes for use when searching and inserting\n+ * into \"istate->dir_hash\".  All \"dir\" threads are trying\n+ * to insert partial pathnames into the hash as they iterate\n+ * over their portions of the index, so lock contention is\n+ * high.\n+ *\n+ * However, the hashmap is going to put items into bucket\n+ * chains based on their hash values.  Use that to create n\n+ * mutexes and lock on mutex[bucket(hash) % n].  This will\n+ * decrease the collision rate by (hopefully) by a factor of n.\n+ */\n+static void init_dir_mutex(void)\n+{\n+\tint j;\n+\n+\tlazy_dir_mutex_array = xcalloc(LAZY_MAX_MUTEX, sizeof(pthread_mutex_t));\n+\n+\tfor (j = 0; j < LAZY_MAX_MUTEX; j++)\n+\t\tinit_recursive_mutex(&lazy_dir_mutex_array[j]);\n+}\n+\n+static void cleanup_dir_mutex(void)\n+{\n+\tint j;\n+\n+\tfor (j = 0; j < LAZY_MAX_MUTEX; j++)\n+\t\tpthread_mutex_destroy(&lazy_dir_mutex_array[j]);\n+\n+\tfree(lazy_dir_mutex_array);\n+}\n+\n+static void lock_dir_mutex(int j)\n+{\n+\tpthread_mutex_lock(&lazy_dir_mutex_array[j]);\n+}\n+\n+static void unlock_dir_mutex(int j)\n+{\n+\tpthread_mutex_unlock(&lazy_dir_mutex_array[j]);\n+}\n+\n+static inline int compute_dir_lock_nr(\n+\tconst struct hashmap *map,\n+\tunsigned int hash)\n+{\n+\treturn hashmap_bucket(map, hash) % LAZY_MAX_MUTEX;\n+}\n+\n+static struct dir_entry *hash_dir_entry_with_parent_and_prefix(\n+\tstruct index_state *istate,\n+\tstruct dir_entry *parent,\n+\tstruct strbuf *prefix)\n+{\n+\tstruct dir_entry *dir;\n+\tunsigned int hash;\n+\tint lock_nr;\n+\n+\t/*\n+\t * Either we have a parent directory and path with slash(es)\n+\t * or the directory is an immediate child of the root directory.\n+\t */\n+\tassert((parent != NULL) ^ (strchr(prefix->buf, '/') == 0));\n+\n+\tif (parent)\n+\t\thash = memihash_cont(parent->ent.hash,\n+\t\t\tprefix->buf + parent->namelen,\n+\t\t\tprefix->len - parent->namelen);\n+\telse\n+\t\thash = memihash(prefix->buf, prefix->len);\n \n+\tlock_nr = compute_dir_lock_nr(&istate->dir_hash, hash);\n+\tlock_dir_mutex(lock_nr);\n+\n+\tdir = find_dir_entry__hash(istate, prefix->buf, prefix->len, hash);\n+\tif (!dir) {\n+\t\tFLEX_ALLOC_MEM(dir, name, prefix->buf, prefix->len);\n+\t\thashmap_entry_init(dir, hash);\n+\t\tdir->namelen = prefix->len;\n+\t\tdir->parent = parent;\n+\t\thashmap_add(&istate->dir_hash, dir);\n+\n+\t\tif (parent) {\n+\t\t\tunlock_dir_mutex(lock_nr);\n+\n+\t\t\t/* All I really need here is an InterlockedIncrement(&(parent->nr)) */\n+\t\t\tlock_nr = compute_dir_lock_nr(&istate->dir_hash, parent->ent.hash);\n+\t\t\tlock_dir_mutex(lock_nr);\n+\t\t\tparent->nr++;\n+\t\t}\n+\t}\n+\n+\tunlock_dir_mutex(lock_nr);\n+\n+\treturn dir;\n+}\n+\n+/*\n+ * handle_range_1() and handle_range_dir() are derived from\n+ * clear_ce_flags_1() and clear_ce_flags_dir() in unpack-trees.c\n+ * and handle the iteration over the entire array of index entries.\n+ * They use recursion for adjacent entries in the same parent\n+ * directory.\n+ */\n+static int handle_range_1(\n+\tstruct index_state *istate,\n+\tint k_start,\n+\tint k_end,\n+\tstruct dir_entry *parent,\n+\tstruct strbuf *prefix,\n+\tstruct lazy_entry *lazy_entries);\n+\n+static int handle_range_dir(\n+\tstruct index_state *istate,\n+\tint k_start,\n+\tint k_end,\n+\tstruct dir_entry *parent,\n+\tstruct strbuf *prefix,\n+\tstruct lazy_entry *lazy_entries,\n+\tstruct dir_entry **dir_new_out)\n+{\n+\tint rc, k;\n+\tint input_prefix_len = prefix->len;\n+\tstruct dir_entry *dir_new;\n+\n+\tdir_new = hash_dir_entry_with_parent_and_prefix(istate, parent, prefix);\n+\n+\tstrbuf_addch(prefix, '/');\n+\n+\t/*\n+\t * Scan forward in the index array for index entries having the same\n+\t * path prefix (that are also in this directory).\n+\t */\n+\tif (strncmp(istate->cache[k_start + 1]->name, prefix->buf, prefix->len) > 0)\n+\t\tk = k_start + 1;\n+\telse if (strncmp(istate->cache[k_end - 1]->name, prefix->buf, prefix->len) == 0)\n+\t\tk = k_end;\n+\telse {\n+\t\tint begin = k_start;\n+\t\tint end = k_end;\n+\t\twhile (begin < end) {\n+\t\t\tint mid = (begin + end) >> 1;\n+\t\t\tint cmp = strncmp(istate->cache[mid]->name, prefix->buf, prefix->len);\n+\t\t\tif (cmp == 0) /* mid has same prefix; look in second part */\n+\t\t\t\tbegin = mid + 1;\n+\t\t\telse if (cmp > 0) /* mid is past group; look in first part */\n+\t\t\t\tend = mid;\n+\t\t\telse\n+\t\t\t\tdie(\"cache entry out of order\");\n+\t\t}\n+\t\tk = begin;\n+\t}\n+\n+\t/*\n+\t * Recurse and process what we can of this subset [k_start, k).\n+\t */\n+\trc = handle_range_1(istate, k_start, k, dir_new, prefix, lazy_entries);\n+\n+\tstrbuf_setlen(prefix, input_prefix_len);\n+\n+\t*dir_new_out = dir_new;\n+\treturn rc;\n+}\n+\n+static int handle_range_1(\n+\tstruct index_state *istate,\n+\tint k_start,\n+\tint k_end,\n+\tstruct dir_entry *parent,\n+\tstruct strbuf *prefix,\n+\tstruct lazy_entry *lazy_entries)\n+{\n+\tint input_prefix_len = prefix->len;\n+\tint k = k_start;\n+\n+\twhile (k < k_end) {\n+\t\tstruct cache_entry *ce_k = istate->cache[k];\n+\t\tconst char *name, *slash;\n+\n+\t\tif (prefix->len && strncmp(ce_k->name, prefix->buf, prefix->len))\n+\t\t\tbreak;\n+\n+\t\tname = ce_k->name + prefix->len;\n+\t\tslash = strchr(name, '/');\n+\n+\t\tif (slash) {\n+\t\t\tint len = slash - name;\n+\t\t\tint processed;\n+\t\t\tstruct dir_entry *dir_new;\n+\n+\t\t\tstrbuf_add(prefix, name, len);\n+\t\t\tprocessed = handle_range_dir(istate, k, k_end, parent, prefix, lazy_entries, &dir_new);\n+\t\t\tif (processed) {\n+\t\t\t\tk += processed;\n+\t\t\t\tstrbuf_setlen(prefix, input_prefix_len);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\tstrbuf_addch(prefix, '/');\n+\t\t\tprocessed = handle_range_1(istate, k, k_end, dir_new, prefix, lazy_entries);\n+\t\t\tk += processed;\n+\t\t\tstrbuf_setlen(prefix, input_prefix_len);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/*\n+\t\t * It is too expensive to take a lock to insert \"ce_k\"\n+\t\t * into \"istate->name_hash\" and increment the ref-count\n+\t\t * on the \"parent\" dir.  So we defer actually updating\n+\t\t * permanent data structures until phase 2 (where we\n+\t\t * can change the locking requirements) and simply\n+\t\t * accumulate our current results into the lazy_entries\n+\t\t * data array).\n+\t\t *\n+\t\t * We do not need to lock the lazy_entries array because\n+\t\t * we have exclusive access to the cells in the range\n+\t\t * [k_start,k_end) that this thread was given.\n+\t\t */\n+\t\tlazy_entries[k].dir = parent;\n+\t\tif (parent) {\n+\t\t\tlazy_entries[k].hash_name = memihash_cont(\n+\t\t\t\tparent->ent.hash,\n+\t\t\t\tce_k->name + parent->namelen,\n+\t\t\t\tce_namelen(ce_k) - parent->namelen);\n+\t\t\tlazy_entries[k].hash_dir = parent->ent.hash;\n+\t\t} else {\n+\t\t\tlazy_entries[k].hash_name = memihash(ce_k->name, ce_namelen(ce_k));\n+\t\t}\n+\n+\t\tk++;\n+\t}\n+\n+\treturn k - k_start;\n+}\n+\n+struct lazy_dir_thread_data {\n+\tpthread_t pthread;\n+\tstruct index_state *istate;\n+\tstruct lazy_entry *lazy_entries;\n+\tint k_start;\n+\tint k_end;\n+};\n+\n+static void *lazy_dir_thread_proc(void *_data)\n+{\n+\tstruct lazy_dir_thread_data *d = _data;\n+\tstruct strbuf prefix = STRBUF_INIT;\n+\thandle_range_1(d->istate, d->k_start, d->k_end, NULL, &prefix, d->lazy_entries);\n+\tstrbuf_release(&prefix);\n+\treturn NULL;\n+}\n+\n+struct lazy_name_thread_data {\n+\tpthread_t pthread;\n+\tstruct index_state *istate;\n+\tstruct lazy_entry *lazy_entries;\n+};\n+\n+static void *lazy_name_thread_proc(void *_data)\n+{\n+\tstruct lazy_name_thread_data *d = _data;\n+\tint k;\n+\n+\tfor (k = 0; k < d->istate->cache_nr; k++) {\n+\t\tstruct cache_entry *ce_k = d->istate->cache[k];\n+\t\tce_k->ce_flags |= CE_HASHED;\n+\t\thashmap_entry_init(ce_k, d->lazy_entries[k].hash_name);\n+\t\thashmap_add(&d->istate->name_hash, ce_k);\n+\t}\n+\n+\treturn NULL;\n+}\n+\n+static inline void lazy_update_dir_ref_counts(\n+\tstruct index_state *istate,\n+\tstruct lazy_entry *lazy_entries)\n+{\n+\tint k;\n+\n+\tfor (k = 0; k < istate->cache_nr; k++) {\n+\t\tif (lazy_entries[k].dir)\n+\t\t\tlazy_entries[k].dir->nr++;\n+\t}\n+}\n+\n+static void threaded_lazy_init_name_hash(\n+\tstruct index_state *istate)\n+{\n+\tint nr_each;\n+\tint k_start;\n+\tint t;\n+\tstruct lazy_entry *lazy_entries;\n+\tstruct lazy_dir_thread_data *td_dir;\n+\tstruct lazy_name_thread_data *td_name;\n+\n+\tk_start = 0;\n+\tnr_each = DIV_ROUND_UP(istate->cache_nr, lazy_nr_dir_threads);\n+\n+\tlazy_entries = xcalloc(istate->cache_nr, sizeof(struct lazy_entry));\n+\ttd_dir = xcalloc(lazy_nr_dir_threads, sizeof(struct lazy_dir_thread_data));\n+\ttd_name = xcalloc(1, sizeof(struct lazy_name_thread_data));\n+\n+\tinit_dir_mutex();\n+\n+\t/*\n+\t * Phase 1:\n+\t * Build \"istate->dir_hash\" using n \"dir\" threads (and a read-only index).\n+\t */\n+\tfor (t = 0; t < lazy_nr_dir_threads; t++) {\n+\t\tstruct lazy_dir_thread_data *td_dir_t = td_dir + t;\n+\t\ttd_dir_t->istate = istate;\n+\t\ttd_dir_t->lazy_entries = lazy_entries;\n+\t\ttd_dir_t->k_start = k_start;\n+\t\tk_start += nr_each;\n+\t\tif (k_start > istate->cache_nr)\n+\t\t\tk_start = istate->cache_nr;\n+\t\ttd_dir_t->k_end = k_start;\n+\t\tif (pthread_create(&td_dir_t->pthread, NULL, lazy_dir_thread_proc, td_dir_t))\n+\t\t\tdie(\"unable to create lazy_dir_thread\");\n+\t}\n+\tfor (t = 0; t < lazy_nr_dir_threads; t++) {\n+\t\tstruct lazy_dir_thread_data *td_dir_t = td_dir + t;\n+\t\tif (pthread_join(td_dir_t->pthread, NULL))\n+\t\t\tdie(\"unable to join lazy_dir_thread\");\n+\t}\n+\n+\t/*\n+\t * Phase 2:\n+\t * Iterate over all index entries and add them to the \"istate->name_hash\"\n+\t * using a single \"name\" background thread.\n+\t * (Testing showed it wasn't worth running more than 1 thread for this.)\n+\t *\n+\t * Meanwhile, finish updating the parent directory ref-counts for each\n+\t * index entry using the current thread.  (This step is very fast and\n+\t * doesn't need threading.)\n+\t */\n+\ttd_name->istate = istate;\n+\ttd_name->lazy_entries = lazy_entries;\n+\tif (pthread_create(&td_name->pthread, NULL, lazy_name_thread_proc, td_name))\n+\t\tdie(\"unable to create lazy_name_thread\");\n+\n+\tlazy_update_dir_ref_counts(istate, lazy_entries);\n+\n+\tif (pthread_join(td_name->pthread, NULL))\n+\t\tdie(\"unable to join lazy_name_thread\");\n+\n+\tcleanup_dir_mutex();\n+\n+\tfree(td_name);\n+\tfree(td_dir);\n+\tfree(lazy_entries);\n+}\n+\n+#endif\n+\n+static void lazy_init_name_hash(struct index_state *istate)\n+{\n \tif (istate->name_hash_initialized)\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,\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+\n+\tif (lookup_lazy_params(istate)) {\n+\t\thashmap_disallow_rehash(&istate->dir_hash, 1);\n+\t\tthreaded_lazy_init_name_hash(istate);\n+\t\thashmap_disallow_rehash(&istate->dir_hash, 0);\n+\t} else {\n+\t\tint nr;\n+\t\tfor (nr = 0; nr < istate->cache_nr; nr++)\n+\t\t\thash_index_entry(istate, istate->cache[nr]);\n+\t}\n+\n \tistate->name_hash_initialized = 1;\n }\n \n+/*\n+ * A test routine for t/helper/ sources.\n+ *\n+ * Returns the number of threads used or 0 when\n+ * the non-threaded code path was used.\n+ *\n+ * Requesting threading WILL NOT override guards\n+ * in lookup_lazy_params().\n+ */\n+int test_lazy_init_name_hash(struct index_state *istate, int try_threaded)\n+{\n+\tlazy_nr_dir_threads = 0;\n+\tlazy_try_threaded = try_threaded;\n+\n+\tlazy_init_name_hash(istate);\n+\n+\treturn lazy_nr_dir_threads;\n+}\n+\n void add_name_hash(struct index_state *istate, struct cache_entry *ce)\n {\n \tif (istate->name_hash_initialized)\n-- \n2.7.4\n\n"},{"id":"314923","messageId":"1490202865-31325-2-git-send-email-git@jeffhostetler.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH 1/6] name-hash: specify initial size for istate.dir_hash table","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T17:14:20Z","receivedAt":"2017-03-22T17:15:44Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nSpecify an initial size for the istate.dir_hash HashMap matching\nthe size of the istate.name_hash.\n\nPreviously hashmap_init() was given 0, causing a 64 bucket\nhashmap to be created.  When working with very large\nrepositories, this would cause numerous rehash() calls to\nrealloc and rebalance the hashmap. This is especially true\nwhen the worktree is deep, with many directories containing\na few files.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\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 6d9f23e..3f7722a 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -120,7 +120,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.7.4\n\n"},{"id":"314924","messageId":"1490202865-31325-3-git-send-email-git@jeffhostetler.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH 2/6] hashmap: allow memihash computation to be continued","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T17:14:21Z","receivedAt":"2017-03-22T17:15:57Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nAdd variant of memihash() to allow the hash computation to\nbe continued.  There 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 this, we can hash the parent directory first. And then\ncontinue the computation to include the \"/filename\".\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n hashmap.c | 17 +++++++++++++++++\n hashmap.h |  1 +\n 2 files changed, 18 insertions(+)\n\ndiff --git a/hashmap.c b/hashmap.c\nindex b10b642..505e63f 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -50,6 +50,23 @@ unsigned int memihash(const void *buf, size_t len)\n \treturn hash;\n }\n \n+/*\n+ * Incoporate another chunk of data into a memihash\n+ * computation.\n+ */ \n+unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)\n+{\n+\tunsigned int hash = hash_seed;\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 #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 ab7958a..45eda69 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -12,6 +12,7 @@ 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_cont(unsigned int hash_seed, const void *buf, size_t len);\n \n static inline unsigned int sha1hash(const unsigned char *sha1)\n {\n-- \n2.7.4\n\n"},{"id":"314925","messageId":"1490202865-31325-7-git-send-email-git@jeffhostetler.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH 6/6] name-hash: add perf test for lazy_init_name_hash","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T17:14:25Z","receivedAt":"2017-03-22T17:15:59Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nCreated t/perf/p0004-lazy-init-name-hash.sh test\nto demonstrate correctness and performance gains\nwith the multithreaded version of lazy_init_name_hash().\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n t/perf/p0004-lazy-init-name-hash.sh | 19 +++++++++++++++++++\n 1 file changed, 19 insertions(+)\n create mode 100644 t/perf/p0004-lazy-init-name-hash.sh\n\ndiff --git a/t/perf/p0004-lazy-init-name-hash.sh b/t/perf/p0004-lazy-init-name-hash.sh\nnew file mode 100644\nindex 0000000..5afa8c8\n--- /dev/null\n+++ b/t/perf/p0004-lazy-init-name-hash.sh\n@@ -0,0 +1,19 @@\n+#!/bin/sh\n+\n+test_description='Tests multi-threaded lazy_init_name_hash'\n+. ./perf-lib.sh\n+\n+test_perf_large_repo\n+test_checkout_worktree\n+\n+test_expect_success 'verify both methods build the same hashmaps' '\n+\t$GIT_BUILD_DIR/t/helper/test-lazy-init-name-hash$X --dump --single | sort >out.single &&\n+\t$GIT_BUILD_DIR/t/helper/test-lazy-init-name-hash$X --dump --multi  | sort >out.multi  &&\n+\ttest_cmp out.single out.multi\n+'\n+\n+test_expect_success 'multithreaded should be faster' '\n+\t$GIT_BUILD_DIR/t/helper/test-lazy-init-name-hash$X --perf >out.perf\n+'\n+\n+test_done\n-- \n2.7.4\n\n"},{"id":"314926","messageId":"1490202865-31325-6-git-send-email-git@jeffhostetler.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH 5/6] name-hash: add test-lazy-init-name-hash","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T17:14:24Z","receivedAt":"2017-03-22T17:16:10Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nAdd t/helper/test-lazy-init-name-hash.c test code\nto demonstrate performance times for lazy_init_name_hash()\nusing the original single-threaded and the new multi-threaded\ncode paths.\n\nIncludes a --dump option to dump the created hashmaps to\nstdout.  You can use this to run both code paths and\nconfirm that they generate the same hashmaps.\n\nIncludes a --analyze option to analyze performance of both\ncode paths over a range of index sizes to help you find a\nlower bound for the LAZY_THREAD_COST in name-hash.c.\nFor example, passing \"-a 4000\" will set \"istate.cache_nr\"\nto 4000 and then try the multi-threaded code -- probably\ngiving 2 threads with 2000 entries each.  It will then\nrun both the single-threaded (1x4000) and the multi-threaded\n(2x2000) and compare the times.  It will then repeat the\ntest with 8000, 12000, and etc. so that you can see the\ncross over.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n Makefile                            |   1 +\n cache.h                             |   1 +\n t/helper/test-lazy-init-name-hash.c | 264 ++++++++++++++++++++++++++++++++++++\n 3 files changed, 266 insertions(+)\n create mode 100644 t/helper/test-lazy-init-name-hash.c\n\ndiff --git a/Makefile b/Makefile\nindex 9ec6065..5fb46c8 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -616,6 +616,7 @@ TEST_PROGRAMS_NEED_X += test-fake-ssh\n TEST_PROGRAMS_NEED_X += test-genrandom\n TEST_PROGRAMS_NEED_X += test-hashmap\n TEST_PROGRAMS_NEED_X += test-index-version\n+TEST_PROGRAMS_NEED_X += test-lazy-init-name-hash\n TEST_PROGRAMS_NEED_X += test-line-buffer\n TEST_PROGRAMS_NEED_X += test-match-trees\n TEST_PROGRAMS_NEED_X += test-mergesort\ndiff --git a/cache.h b/cache.h\nindex 80b6372..6a72f6a 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -343,6 +343,7 @@ struct index_state {\n extern struct index_state the_index;\n \n /* Name hashing */\n+extern int test_lazy_init_name_hash(struct index_state *istate, int try_threaded);\n extern void add_name_hash(struct index_state *istate, struct cache_entry *ce);\n extern void remove_name_hash(struct index_state *istate, struct cache_entry *ce);\n extern void free_name_hash(struct index_state *istate);\ndiff --git a/t/helper/test-lazy-init-name-hash.c b/t/helper/test-lazy-init-name-hash.c\nnew file mode 100644\nindex 0000000..435837b\n--- /dev/null\n+++ b/t/helper/test-lazy-init-name-hash.c\n@@ -0,0 +1,264 @@\n+#include \"cache.h\"\n+#include \"parse-options.h\"\n+\n+static int single = 0;\n+static int multi = 0;\n+static int count = 1;\n+static int dump = 0;\n+static int perf = 0;\n+static int analyze = 0;\n+static int analyze_step = 0;\n+\n+/*\n+ * Dump the contents of the \"dir\" and \"name\" hash tables to stdout.\n+ * If you sort the result, you can compare it with the other type\n+ * mode and verify that both single and multi produce the same set.\n+ */\n+void dump_run(void)\n+{\n+\tstruct hashmap_iter iter_dir;\n+\tstruct hashmap_iter iter_cache;\n+\n+\t/* Stolen from name-hash.c */\n+\tstruct dir_entry {\n+\t\tstruct hashmap_entry ent;\n+\t\tstruct dir_entry *parent;\n+\t\tint nr;\n+\t\tunsigned int namelen;\n+\t\tchar name[FLEX_ARRAY];\n+\t};\n+\n+\tstruct dir_entry *dir;\n+\tstruct cache_entry *ce;\n+\n+\tread_cache();\n+\tif (single) {\n+\t\ttest_lazy_init_name_hash(&the_index, 0);\n+\t} else {\n+\t\tint nr_threads_used = test_lazy_init_name_hash(&the_index, 1);\n+\t\tif (!nr_threads_used)\n+\t\t\tdie(\"non-threaded code path used\");\n+\t}\n+\n+\tdir = hashmap_iter_first(&the_index.dir_hash, &iter_dir);\n+\twhile (dir) {\n+\t\tprintf(\"dir %08x %7d %s\\n\", dir->ent.hash, dir->nr, dir->name);\n+\t\tdir = hashmap_iter_next(&iter_dir);\n+\t}\n+\n+\tce = hashmap_iter_first(&the_index.name_hash, &iter_cache);\n+\twhile (ce) {\n+\t\tprintf(\"name %08x %s\\n\", ce->ent.hash, ce->name);\n+\t\tce = hashmap_iter_next(&iter_cache);\n+\t}\n+\n+\tdiscard_cache();\n+}\n+\n+/*\n+ * Run the single or multi threaded version \"count\" times and\n+ * report on the time taken.\n+ */\n+uint64_t time_runs(int try_threaded)\n+{\n+\tuint64_t t0, t1, t2;\n+\tuint64_t sum = 0;\n+\tuint64_t avg;\n+\tint nr_threads_used;\n+\tint i;\n+\n+\tfor (i = 0; i < count; i++) {\n+\t\tt0 = getnanotime();\n+\t\tread_cache();\n+\t\tt1 = getnanotime();\n+\t\tnr_threads_used = test_lazy_init_name_hash(&the_index, try_threaded);\n+\t\tt2 = getnanotime();\n+\n+\t\tsum += (t2 - t1);\n+\n+\t\tif (try_threaded && !nr_threads_used)\n+\t\t\tdie(\"non-threaded code path used\");\n+\n+\t\tif (nr_threads_used)\n+\t\t\tprintf(\"%f %f %d multi %d\\n\",\n+\t\t\t\t   ((double)(t1 - t0))/1000000000,\n+\t\t\t\t   ((double)(t2 - t1))/1000000000,\n+\t\t\t\t   the_index.cache_nr,\n+\t\t\t\t   nr_threads_used);\n+\t\telse\n+\t\t\tprintf(\"%f %f %d single\\n\",\n+\t\t\t\t   ((double)(t1 - t0))/1000000000,\n+\t\t\t\t   ((double)(t2 - t1))/1000000000,\n+\t\t\t\t   the_index.cache_nr);\n+\t\tfflush(stdout);\n+\n+\t\tdiscard_cache();\n+\t}\n+\n+\tavg = sum / count;\n+\tif (count > 1)\n+\t\tprintf(\"avg %f %s\\n\",\n+\t\t\t   (double)avg/1000000000,\n+\t\t\t   (try_threaded) ? \"multi\" : \"single\");\n+\n+\treturn avg;\n+}\n+\n+/*\n+ * Try a series of runs varying the \"istate->cache_nr\" and\n+ * try to find a good value for the multi-threaded criteria.\n+ */\n+void analyze_run(void)\n+{\n+\tuint64_t t1s, t1m, t2s, t2m;\n+\tint cache_nr_limit;\n+\tint nr_threads_used;\n+\tint i;\n+\tint nr;\n+\n+\tread_cache();\n+\tcache_nr_limit = the_index.cache_nr;\n+\tdiscard_cache();\n+\n+\tnr = analyze;\n+\twhile (1) {\n+\t\tuint64_t sum_single = 0;\n+\t\tuint64_t sum_multi = 0;\n+\t\tuint64_t avg_single;\n+\t\tuint64_t avg_multi;\n+\n+\t\tif (nr > cache_nr_limit)\n+\t\t\tnr = cache_nr_limit;\n+\n+\t\tfor (i = 0; i < count; i++) {\n+\t\t\tread_cache();\n+\t\t\tthe_index.cache_nr = nr; /* cheap truncate of index */\n+\t\t\tt1s = getnanotime();\n+\t\t\ttest_lazy_init_name_hash(&the_index, 0);\n+\t\t\tt2s = getnanotime();\n+\t\t\tsum_single += (t2s - t1s);\n+\t\t\tthe_index.cache_nr = cache_nr_limit;\n+\t\t\tdiscard_cache();\n+\n+\t\t\tread_cache();\n+\t\t\tthe_index.cache_nr = nr; /* cheap truncate of index */\n+\t\t\tt1m = getnanotime();\n+\t\t\tnr_threads_used = test_lazy_init_name_hash(&the_index, 1);\n+\t\t\tt2m = getnanotime();\n+\t\t\tsum_multi += (t2m - t1m);\n+\t\t\tthe_index.cache_nr = cache_nr_limit;\n+\t\t\tdiscard_cache();\n+\n+\t\t\tif (!nr_threads_used)\n+\t\t\t\tprintf(\"    [size %8d] [single %f]   non-threaded code path used\\n\",\n+\t\t\t\t\t   nr, ((double)(t2s - t1s))/1000000000);\n+\t\t\telse \n+\t\t\t\tprintf(\"    [size %8d] [single %f] %c [multi %f %d]\\n\",\n+\t\t\t\t\t   nr,\n+\t\t\t\t\t   ((double)(t2s - t1s))/1000000000,\n+\t\t\t\t\t   (((t2s - t1s) < (t2m - t1m)) ? '<' : '>'),\n+\t\t\t\t\t   ((double)(t2m - t1m))/1000000000,\n+\t\t\t\t\t   nr_threads_used);\n+\t\t\tfflush(stdout);\n+\t\t}\n+\t\tif (count > 1) {\n+\t\t\tavg_single = sum_single / count;\n+\t\t\tavg_multi = sum_multi / count;\n+\t\t\tif (!nr_threads_used)\n+\t\t\t\tprintf(\"avg [size %8d] [single %f]\\n\",\n+\t\t\t\t\t   nr,\n+\t\t\t\t\t   (double)avg_single/1000000000);\n+\t\t\telse\n+\t\t\t\tprintf(\"avg [size %8d] [single %f] %c [multi %f %d]\\n\",\n+\t\t\t\t\t   nr,\n+\t\t\t\t\t   (double)avg_single/1000000000,\n+\t\t\t\t\t   (avg_single < avg_multi ? '<' : '>'),\n+\t\t\t\t\t   (double)avg_multi/1000000000,\n+\t\t\t\t\t   nr_threads_used);\n+\t\t\tfflush(stdout);\n+\t\t}\n+\n+\t\tif (nr >= cache_nr_limit)\n+\t\t\treturn;\n+\t\tnr += analyze_step;\n+\t}\n+}\n+\n+int cmd_main(int argc, const char **argv)\n+{\n+\tconst char *usage[] = {\n+\t\t\"test-lazy-init-name-hash -d (-s | -m)\",\n+\t\t\"test-lazy-init-name-hash -p [-c c]\",\n+\t\t\"test-lazy-init-name-hash -a a [--step s] [-c c]\",\n+\t\t\"test-lazy-init-name-hash (-s | -m) [-c c]\",\n+\t\t\"test-lazy-init-name-hash -s -m [-c c]\",\n+\t\tNULL\n+\t};\n+\tstruct option options[] = {\n+\t\tOPT_BOOL('s', \"single\", &single, \"run single-threaded code\"),\n+\t\tOPT_BOOL('m', \"multi\", &multi, \"run multi-threaded code\"),\n+\t\tOPT_INTEGER('c', \"count\", &count, \"number of passes\"),\n+\t\tOPT_BOOL('d', \"dump\", &dump, \"dump hash tables\"),\n+\t\tOPT_BOOL('p', \"perf\", &perf, \"compare single vs multi\"),\n+\t\tOPT_INTEGER('a', \"analyze\", &analyze, \"analyze different multi sizes\"),\n+\t\tOPT_INTEGER(0, \"step\", &analyze_step, \"analyze step factor\"),\n+\t\tOPT_END(),\n+\t};\n+\tconst char *prefix;\n+\tuint64_t avg_single, avg_multi;\n+\n+\tprefix = setup_git_directory();\n+\n+\targc = parse_options(argc, argv, prefix, options, usage, 0);\n+\n+\t/*\n+\t * istate->dir_hash is only created when ignore_case is set.\n+\t */\n+\tignore_case = 1;\n+\n+\tif (dump) {\n+\t\tif (perf || analyze > 0)\n+\t\t\tdie(\"cannot combine dump, perf, or analyze\");\n+\t\tif (count > 1)\n+\t\t\tdie(\"count not valid with dump\");\n+\t\tif (single && multi)\n+\t\t\tdie(\"cannot use both single and multi with dump\");\n+\t\tif (!single && !multi)\n+\t\t\tdie(\"dump requires either single or multi\");\n+\t\tdump_run();\n+\t\treturn 0;\n+\t}\n+\n+\tif (perf) {\n+\t\tif (analyze > 0)\n+\t\t\tdie(\"cannot combine dump, perf, or analyze\");\n+\t\tif (single || multi)\n+\t\t\tdie(\"cannot use single or multi with perf\");\n+\t\tavg_single = time_runs(0);\n+\t\tavg_multi = time_runs(1);\n+\t\tif (avg_multi > avg_single)\n+\t\t\tdie(\"multi is slower\");\n+\t\treturn 0;\n+\t}\n+\n+\tif (analyze) {\n+\t\tif (analyze < 500)\n+\t\t\tdie(\"analyze must be at least 500\");\n+\t\tif (!analyze_step)\n+\t\t\tanalyze_step = analyze;\n+\t\tif (single || multi)\n+\t\t\tdie(\"cannot use single or multi with analyze\");\n+\t\tanalyze_run();\n+\t\treturn 0;\n+\t}\n+\n+\tif (!single && !multi)\n+\t\tdie(\"require either -s or -m or both\");\n+\n+\tif (single)\n+\t\ttime_runs(0);\n+\tif (multi)\n+\t\ttime_runs(1);\n+\n+\treturn 0;\n+}\n-- \n2.7.4\n\n"},{"id":"314927","messageId":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","threadId":"45467","inReplyTo":null,"subject":"[PATCH 0/6] thread lazy_init_name_hash","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T17:14:19Z","receivedAt":"2017-03-22T17:16:21Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nThis patch series is a performance optimization for\nlazy_init_name_hash() in name-hash.c on very large\nrepositories.\n\nThis change allows lazy_init_name_hash() to optionally\nuse multiple threads when building the the_index.dir_hash\nand the_index.name_hash hashmaps.  The original code path\nhas been preserved and is used when the repo is small or\nthe system does not have sufficient CPUs.\n\nA helper command (t/helper/test-lazy-init-name-hash) was\ncreated to demonstrate performance differences and validate\noutput.  For example, use the '-p' option to compare both\ncode paths on a large repo.\n\nDuring our testing on the Windows source tree (3.1M\nfiles, 500K folders, 450MB index), this change reduced\nthe runtime of lazy_init_name_hash() from 1.4 to 0.27\nseconds.\n\nThis patch series replaces my earlier\n     * jh/memihash-opt (2017-02-17) 5 commits\npatch series.\n\nJeff Hostetler (6):\n  name-hash: specify initial size for istate.dir_hash table\n  hashmap: allow memihash computation to be continued\n  hashmap: Add disallow_rehash setting\n  name-hash: perf improvement for lazy_init_name_hash\n  name-hash: add test-lazy-init-name-hash\n  name-hash: add perf test for lazy_init_name_hash\n\n Makefile                            |   1 +\n cache.h                             |   1 +\n hashmap.c                           |  29 ++-\n hashmap.h                           |  25 ++\n name-hash.c                         | 490 +++++++++++++++++++++++++++++++++++-\n t/helper/test-lazy-init-name-hash.c | 264 +++++++++++++++++++\n t/perf/p0004-lazy-init-name-hash.sh |  19 ++\n 7 files changed, 820 insertions(+), 9 deletions(-)\n create mode 100644 t/helper/test-lazy-init-name-hash.c\n create mode 100644 t/perf/p0004-lazy-init-name-hash.sh\n\n-- \n2.7.4\n\n"},{"id":"314934","messageId":"CAGZ79kYh0eP-dzpX58SrSRJGEr9iyOb0Q3vizsvxE81kzddwxQ@mail.gmail.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"Re: [PATCH 0/6] thread lazy_init_name_hash","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-03-22T18:02:31Z","receivedAt":"2017-03-22T18:02:36Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Mar 22, 2017 at 10:14 AM,  <git@jeffhostetler.com> wrote:\n>\n> During our testing on the Windows source tree (3.1M\n> files, 500K folders, 450MB index), this change reduced\n> the runtime of lazy_init_name_hash() from 1.4 to 0.27\n> seconds.\n\nThis sounds promising. :)\nA fast skim over the code makes me like the code.\n\n>  hashmap.c                           |  29 ++-\n>  hashmap.h                           |  25 ++\n\nCould you add some documentation to\nDocumentation/technical/api-hashmap.txt ?\n(Bonus points for migrating the documentation inline,\nc.f. discussion surrounding [1])\n\n[1] https://public-inbox.org/git/20141212212800.GA27451@peff.net/\n\n>  name-hash.c                         | 490 +++++++++++++++++++++++++++++++++++-\n\nAFAICT the new threading is all implicit in name-hash and we do not expose\nits functionality or tuning knobs outside the testing helper, such that we do\nnot need API documentation here, but only enough code comments to\nunderstand the code for maintainability?\n\nThanks,\nStefan\n"},{"id":"314946","messageId":"90a7b4fa-67bf-6501-1da6-97883d7cde4a@jeffhostetler.com","threadId":"45467","inReplyTo":"CAGZ79kYh0eP-dzpX58SrSRJGEr9iyOb0Q3vizsvxE81kzddwxQ@mail.gmail.com","subject":"Re: [PATCH 0/6] thread lazy_init_name_hash","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T19:22:09Z","receivedAt":"2017-03-22T19:22:20Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/22/2017 2:02 PM, Stefan Beller wrote:\n> On Wed, Mar 22, 2017 at 10:14 AM,  <git@jeffhostetler.com> wrote:\n>>\n>> During our testing on the Windows source tree (3.1M\n>> files, 500K folders, 450MB index), this change reduced\n>> the runtime of lazy_init_name_hash() from 1.4 to 0.27\n>> seconds.\n>\n> This sounds promising. :)\n> A fast skim over the code makes me like the code.\n\nI forgot to mention that this was on an 8 (logical) core machine.\n\n>\n>>  hashmap.c                           |  29 ++-\n>>  hashmap.h                           |  25 ++\n>\n> Could you add some documentation to\n> Documentation/technical/api-hashmap.txt ?\n\nWill do. Thanks.\n\n> (Bonus points for migrating the documentation inline,\n> c.f. discussion surrounding [1])\n>\n> [1] https://public-inbox.org/git/20141212212800.GA27451@peff.net/\n\nI'd like to save this for a separate effort.\n\n>\n>>  name-hash.c                         | 490 +++++++++++++++++++++++++++++++++++-\n>\n> AFAICT the new threading is all implicit in name-hash and we do not expose\n> its functionality or tuning knobs outside the testing helper, such that we do\n> not need API documentation here, but only enough code comments to\n> understand the code for maintainability?\n\nYes, my goal was to just make it transparent to all callers.\nEspecially since the main lazy_init_name_hash() function is static\nand not visible anyway.\n\nJeff\n\n"},{"id":"314950","messageId":"xmqqshm5je4d.fsf@gitster.mtv.corp.google.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"Re: [PATCH 0/6] thread lazy_init_name_hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-22T19:38:42Z","receivedAt":"2017-03-22T19:42:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"git@jeffhostetler.com writes:\n\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n>\n> This patch series is a performance optimization for\n> lazy_init_name_hash() in name-hash.c on very large\n> repositories.\n>\n> This change allows lazy_init_name_hash() to optionally\n> use multiple threads when building the the_index.dir_hash\n> and the_index.name_hash hashmaps.  The original code path\n> has been preserved and is used when the repo is small or\n> the system does not have sufficient CPUs.\n>\n> A helper command (t/helper/test-lazy-init-name-hash) was\n> created to demonstrate performance differences and validate\n> output.  For example, use the '-p' option to compare both\n> code paths on a large repo.\n>\n> During our testing on the Windows source tree (3.1M\n> files, 500K folders, 450MB index), this change reduced\n> the runtime of lazy_init_name_hash() from 1.4 to 0.27\n> seconds.\n>\n> This patch series replaces my earlier\n>      * jh/memihash-opt (2017-02-17) 5 commits\n> patch series.\n\nAhh.  I was scratching my head trying to remember why some of these\nlook so familiar.  [PATCH v2 ...] would have helped.\n\nThank you for an update.\n\n>\n> Jeff Hostetler (6):\n>   name-hash: specify initial size for istate.dir_hash table\n>   hashmap: allow memihash computation to be continued\n>   hashmap: Add disallow_rehash setting\n>   name-hash: perf improvement for lazy_init_name_hash\n>   name-hash: add test-lazy-init-name-hash\n>   name-hash: add perf test for lazy_init_name_hash\n>\n>  Makefile                            |   1 +\n>  cache.h                             |   1 +\n>  hashmap.c                           |  29 ++-\n>  hashmap.h                           |  25 ++\n>  name-hash.c                         | 490 +++++++++++++++++++++++++++++++++++-\n>  t/helper/test-lazy-init-name-hash.c | 264 +++++++++++++++++++\n>  t/perf/p0004-lazy-init-name-hash.sh |  19 ++\n>  7 files changed, 820 insertions(+), 9 deletions(-)\n>  create mode 100644 t/helper/test-lazy-init-name-hash.c\n>  create mode 100644 t/perf/p0004-lazy-init-name-hash.sh\n"},{"id":"314962","messageId":"xmqqa88djbbb.fsf@gitster.mtv.corp.google.com","threadId":"45467","inReplyTo":"1490202865-31325-1-git-send-email-git@jeffhostetler.com","subject":"Re: [PATCH 0/6] thread lazy_init_name_hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-22T20:39:20Z","receivedAt":"2017-03-22T20:39:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Just FYI before I start reading each patch carefully...\n\nSubject: [PATCH 2/6] hashmap: allow memihash computation to be continued\nERROR: trailing whitespace\n#28: FILE: hashmap.c:56:\n+ */ $\n\ntotal: 1 errors, 0 warnings, 30 lines checked\n------------------------------------------------\nSubject: [PATCH 4/6] name-hash: perf improvement for lazy_init_name_hash\nERROR: space required after that ',' (ctx:VxV)\n#57: FILE: name-hash.c:38:\n+\treturn find_dir_entry__hash(istate, name, namelen, memihash(name,namelen));\n \t                                                                ^\n\nERROR: do not initialise statics to 0 or NULL\n#105: FILE: name-hash.c:157:\n+static int lazy_nr_dir_threads = 0;\n\ntotal: 2 errors, 0 warnings, 516 lines checked\n------------------------------------------------\nSubject: [PATCH 5/6] name-hash: add test-lazy-init-name-hash\nERROR: do not initialise statics to 0 or NULL\n#64: FILE: t/helper/test-lazy-init-name-hash.c:4:\n+static int single = 0;\n\nERROR: do not initialise statics to 0 or NULL\n#65: FILE: t/helper/test-lazy-init-name-hash.c:5:\n+static int multi = 0;\n\nERROR: do not initialise statics to 0 or NULL\n#67: FILE: t/helper/test-lazy-init-name-hash.c:7:\n+static int dump = 0;\n\nERROR: do not initialise statics to 0 or NULL\n#68: FILE: t/helper/test-lazy-init-name-hash.c:8:\n+static int perf = 0;\n\nERROR: do not initialise statics to 0 or NULL\n#69: FILE: t/helper/test-lazy-init-name-hash.c:9:\n+static int analyze = 0;\n\nERROR: do not initialise statics to 0 or NULL\n#70: FILE: t/helper/test-lazy-init-name-hash.c:10:\n+static int analyze_step = 0;\n\nERROR: trailing whitespace\n#215: FILE: t/helper/test-lazy-init-name-hash.c:155:\n+^I^I^Ielse $\n\ntotal: 7 errors, 0 warnings, 278 lines checked\n------------------------------------------------\n"},{"id":"314963","messageId":"xmqq60j1jalv.fsf@gitster.mtv.corp.google.com","threadId":"45467","inReplyTo":"xmqqshm5je4d.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 0/6] thread lazy_init_name_hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-22T20:54:36Z","receivedAt":"2017-03-22T20:54:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n>> This patch series replaces my earlier\n>>      * jh/memihash-opt (2017-02-17) 5 commits\n>> patch series.\n>\n> Ahh.  I was scratching my head trying to remember why some of these\n> look so familiar.  [PATCH v2 ...] would have helped.\n>\n> Thank you for an update.\n\nOne notable difference I noticed since the previous round is that\nthis no longer adds precomputed hash to \"struct cache_entry\".  As\nyou are aiming to manage an index with a large number of entries,\nthis is a welcome change that makes sense.\n\n$ make NO_PTHREADS=NoThanks name-hash.o\n    CC name-hash.o\nname-hash.c: In function 'lazy_init_name_hash':\nname-hash.c:573:3: error: implicit declaration of function 'threaded_lazy_init_name_hash' [-Werror=implicit-function-declaration]\n   threaded_lazy_init_name_hash(istate);\n   ^\nname-hash.c: In function 'test_lazy_init_name_hash':\nname-hash.c:595:2: error: 'lazy_nr_dir_threads' undeclared (first use in this function)\n  lazy_nr_dir_threads = 0;\n  ^\nname-hash.c:595:2: note: each undeclared identifier is reported only once for each function it appears in\nname-hash.c:596:2: error: 'lazy_try_threaded' undeclared (first use in this function)\n  lazy_try_threaded = try_threaded;\n  ^\nname-hash.c:601:1: error: control reaches end of non-void function [-Werror=return-type]\n }\n ^\ncc1: all warnings being treated as errors\nmake: *** [name-hash.o] Error 1\n\nstill has to be addressed.  Perhaps squash pieces of these into\nappropriate patches in the series?\n\n name-hash.c | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/name-hash.c b/name-hash.c\nindex a5826505e0..725ac22886 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -118,9 +118,16 @@ static int cache_entry_cmp(const struct cache_entry *ce1,\n \treturn remove ? !(ce1 == ce2) : 0;\n }\n \n+static int lazy_try_threaded = 1;\n+static int lazy_nr_dir_threads = 0;\n \n #ifdef NO_PTHREADS\n \n+static void threaded_lazy_init_name_hash(struct index_state *istate)\n+{\n+\t; /* nothing */\n+}\n+\n static int lookup_lazy_params(struct index_state *istate)\n {\n \treturn 0;\n@@ -153,8 +160,6 @@ static int lookup_lazy_params(struct index_state *istate)\n  */\n #define LAZY_MAX_MUTEX   (32)\n \n-static int lazy_try_threaded = 1;\n-static int lazy_nr_dir_threads = 0;\n static pthread_mutex_t *lazy_dir_mutex_array;\n \n /*\n"},{"id":"314965","messageId":"1a23fa5d-3b80-ca47-fcaa-56f794699aab@jeffhostetler.com","threadId":"45467","inReplyTo":"xmqq60j1jalv.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 0/6] thread lazy_init_name_hash","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-22T21:04:49Z","receivedAt":"2017-03-22T21:06:25Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/22/2017 4:54 PM, Junio C Hamano wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n>\n>>> This patch series replaces my earlier\n>>>      * jh/memihash-opt (2017-02-17) 5 commits\n>>> patch series.\n>>\n>> Ahh.  I was scratching my head trying to remember why some of these\n>> look so familiar.  [PATCH v2 ...] would have helped.\n>>\n>> Thank you for an update.\n>\n> One notable difference I noticed since the previous round is that\n> this no longer adds precomputed hash to \"struct cache_entry\".  As\n> you are aiming to manage an index with a large number of entries,\n> this is a welcome change that makes sense.\n\nYes, this completely isolates the changes inside the name-hash.c\ncode.  And it eliminates the need to update/invalidate the precomputed\nhash values as entries are changed.\n\n>\n> $ make NO_PTHREADS=NoThanks name-hash.o\n>     CC name-hash.o\n> name-hash.c: In function 'lazy_init_name_hash':\n> ...\n> still has to be addressed.  Perhaps squash pieces of these into\n> appropriate patches in the series?\n> ...\n\nWill do. I wasn't sure how you specified non-threaded builds.\n\nThanks,\nJeff\n\n\n"},{"id":"314974","messageId":"xmqqk27hhuei.fsf@gitster.mtv.corp.google.com","threadId":"45467","inReplyTo":"1a23fa5d-3b80-ca47-fcaa-56f794699aab@jeffhostetler.com","subject":"Re: [PATCH 0/6] thread lazy_init_name_hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-22T21:29:57Z","receivedAt":"2017-03-22T21:30:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff Hostetler <git@jeffhostetler.com> writes:\n\n> On 3/22/2017 4:54 PM, Junio C Hamano wrote:\n>>>\n>>> Thank you for an update.\n>>\n>> One notable difference I noticed since the previous round is that\n>> this no longer adds precomputed hash to \"struct cache_entry\".  As\n>> you are aiming to manage an index with a large number of entries,\n>> this is a welcome change that makes sense.\n>\n> Yes, this completely isolates the changes inside the name-hash.c\n> code.  And it eliminates the need to update/invalidate the precomputed\n> hash values as entries are changed.\n\nThanks.  Having a summary like that for differences since the last\nround in the cover letter would help during the review, but this is\nan example that lack of such a summary would be one way to make sure\nthat reviewer(s) are paying attention ;-)\n\n"}]}