{"thread":{"id":"45479","subject":"[PATCH v2 0/7] thread lazy_init_name_hash","startedAt":"2017-03-23T13:47:30Z","lastAt":"2017-04-06T13:53:43Z","messageCount":20,"participants":["git@jeffhostetler.com","Ramsay Jones","Stefan Beller","Junio C Hamano","Jeff Hostetler","Duy Nguyen"],"isPatch":true,"patchVersion":2,"patchTotal":7},"messages":[{"id":"315065","messageId":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","threadId":"45479","inReplyTo":null,"subject":"[PATCH v2 0/7] thread lazy_init_name_hash","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-23T13:46:58Z","receivedAt":"2017-03-23T13:47:30Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nVersion 2 of this patch series addresses the coding\nstyle issues, compile errors in non-threaded builds,\nand updated API documentation.\n\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) with an 8 (logical)\ncore machine, we reduced the runtime of lazy_init_name_hash()\nfrom 1.4 to 0.27 seconds.\n\nThis patch series replaces my earlier\n * jh/memihash-opt (2017-02-17) 5 commits\npatch series. This series is an improvement over the\noriginal proposal because it completely isolates the changes\nin name name-hash.c (rather than having parts in preload-index.c)\nand eliminates the need to update/invalidate precomputed hash\nvalues as cache_entries are changed.\n\n\nJeff Hostetler (7):\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 hashmap: document memihash_cont, hashmap_disallow_rehash api\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 Documentation/technical/api-hashmap.txt | 22 ++\n Makefile | 1 +\n cache.h | 1 +\n hashmap.c | 29 +-\n hashmap.h | 25 ++\n name-hash.c | 495 +++++++++++++++++++++++++++++++-\n t/helper/test-lazy-init-name-hash.c | 264 +++++++++++++++++\n t/perf/p0004-lazy-init-name-hash.sh | 19 ++\n 8 files changed, 847 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":"315066","messageId":"1490276825-41544-3-git-send-email-git@jeffhostetler.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH v2 2/7] hashmap: allow memihash computation to be continued","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-23T13:47:00Z","receivedAt":"2017-03-23T13:47:32Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \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 \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..93793cb 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":"315067","messageId":"1490276825-41544-7-git-send-email-git@jeffhostetler.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH v2 6/7] name-hash: add test-lazy-init-name-hash","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-23T13:47:04Z","receivedAt":"2017-03-23T13:47:33Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \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 \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..0769e17\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;\n+static int multi;\n+static int count = 1;\n+static int dump;\n+static int perf;\n+static int analyze;\n+static int analyze_step;\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":"315068","messageId":"1490276825-41544-2-git-send-email-git@jeffhostetler.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH v2 1/7] name-hash: specify initial size for istate.dir_hash table","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-23T13:46:59Z","receivedAt":"2017-03-23T13:47:35Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \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 \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":"315069","messageId":"1490276825-41544-8-git-send-email-git@jeffhostetler.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH v2 7/7] name-hash: add perf test for lazy_init_name_hash","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-23T13:47:05Z","receivedAt":"2017-03-23T13:47:36Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \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 \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":"315070","messageId":"1490276825-41544-6-git-send-email-git@jeffhostetler.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH v2 5/7] name-hash: perf improvement for lazy_init_name_hash","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-23T13:47:03Z","receivedAt":"2017-03-23T13:47:38Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \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 \n---\n name-hash.c | 492 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 485 insertions(+), 7 deletions(-)\n\ndiff --git a/name-hash.c b/name-hash.c\nindex 3f7722a..71ef07e 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,493 @@ 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+static int lazy_try_threaded = 1;\n+static int lazy_nr_dir_threads;\n+\n+#ifdef NO_PTHREADS\n+\n+static inline int lookup_lazy_params(struct index_state *istate)\n {\n-\tint nr;\n+\treturn 0;\n+}\n+\n+static inline void threaded_lazy_init_name_hash(\n+\tstruct index_state *istate)\n+{\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 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":"315071","messageId":"1490276825-41544-4-git-send-email-git@jeffhostetler.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH v2 3/7] hashmap: Add disallow_rehash setting","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-23T13:47:01Z","receivedAt":"2017-03-23T13:47:41Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \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 \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 93793cb..7d1044e 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":"315072","messageId":"1490276825-41544-5-git-send-email-git@jeffhostetler.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"[PATCH v2 4/7] hashmap: document memihash_cont, hashmap_disallow_rehash api","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-23T13:47:02Z","receivedAt":"2017-03-23T13:47:43Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nDocument memihash_cont() and hashmap_disallow_rehash()\nin Documentation/technical/api-hashmap.txt.\n\nSigned-off-by: Jeff Hostetler \n---\n Documentation/technical/api-hashmap.txt | 22 ++++++++++++++++++++++\n 1 file changed, 22 insertions(+)\n\ndiff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt\nindex a3f020c..ccc634b 100644\n--- a/Documentation/technical/api-hashmap.txt\n+++ b/Documentation/technical/api-hashmap.txt\n@@ -21,6 +21,9 @@ that the hashmap is initialized. It may also be useful for statistical purposes\n `cmpfn` stores the comparison function specified in `hashmap_init()`. In\n advanced scenarios, it may be useful to change this, e.g. to switch between\n case-sensitive and case-insensitive lookup.\n++\n+When `disallow_rehash` is set, automatic rehashes are prevented during inserts\n+and deletes.\n \n `struct hashmap_entry`::\n \n@@ -57,6 +60,7 @@ Functions\n `unsigned int strihash(const char *buf)`::\n `unsigned int memhash(const void *buf, size_t len)`::\n `unsigned int memihash(const void *buf, size_t len)`::\n+`unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)`::\n \n \tReady-to-use hash functions for strings, using the FNV-1 algorithm (see\n \thttp://www.isthe.com/chongo/tech/comp/fnv).\n@@ -65,6 +69,9 @@ Functions\n `memihash` operate on arbitrary-length memory.\n +\n `strihash` and `memihash` are case insensitive versions.\n++\n+`memihash_cont` is a variant of `memihash` that allows a computation to be\n+continued with another chunk of data.\n \n `unsigned int sha1hash(const unsigned char *sha1)`::\n \n@@ -184,6 +191,21 @@ passed to `hashmap_cmp_fn` to decide whether the entry matches the key.\n +\n Returns the removed entry, or NULL if not found.\n \n+`void hashmap_disallow_rehash(struct hashmap *map, unsigned value)`::\n+\n+\tDisallow/allow automatic rehashing of the hashmap during inserts\n+\tand deletes.\n++\n+This is useful if the caller knows that the hashmap will be accessed\n+by multiple threads.\n++\n+The caller is still responsible for any necessary locking; this simply\n+prevents unexpected rehashing. The caller is also responsible for properly\n+sizing the initial hashmap to ensure good performance.\n++\n+A call to allow rehashing does not force a rehash; that might happen\n+with the next insert or delete.\n+\n `void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`::\n `void *hashmap_iter_next(struct hashmap_iter *iter)`::\n `void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`::\n-- \n2.7.4\n\n"},{"id":"315079","messageId":"e987714e-473f-cad1-159b-18459ffeb241@ramsayjones.plus.com","threadId":"45479","inReplyTo":"1490276825-41544-6-git-send-email-git@jeffhostetler.com","subject":"Re: [PATCH v2 5/7] name-hash: perf improvement for lazy_init_name_hash","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2017-03-23T15:25:44Z","receivedAt":"2017-03-23T15:25:56Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 23/03/17 13:47, git@jeffhostetler.com wrote:\n> From: Jeff Hostetler \n> \n[snip]\n\n> \n> diff --git a/name-hash.c b/name-hash.c\n> index 3f7722a..71ef07e 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,493 @@ 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> +static int lazy_try_threaded = 1;\n> +static int lazy_nr_dir_threads;\n> +\n> +#ifdef NO_PTHREADS\n> +\n> +static inline int lookup_lazy_params(struct index_state *istate)\n> {\n> -\tint nr;\n> +\treturn 0;\n> +}\n> +\n> +static inline void threaded_lazy_init_name_hash(\n> +\tstruct index_state *istate)\n> +{\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 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\nsparse complains about 'Using plain integer as a NULL pointer', (the\nreturn from strchr() is NULL, if '/' is not found) so maybe:\n\n+\tassert((parent != NULL) ^ (strchr(prefix->buf, '/') == NULL));\n\n\nATB,\nRamsay Jones\n"},{"id":"315080","messageId":"a823a9e1-2355-e348-3408-2021cee78001@ramsayjones.plus.com","threadId":"45479","inReplyTo":"1490276825-41544-7-git-send-email-git@jeffhostetler.com","subject":"Re: [PATCH v2 6/7] name-hash: add test-lazy-init-name-hash","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2017-03-23T15:29:25Z","receivedAt":"2017-03-23T15:29:33Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 23/03/17 13:47, git@jeffhostetler.com wrote:\n> From: Jeff Hostetler \n> \n> Add t/helper/test-lazy-init-name-hash.c test code\n> to demonstrate performance times for lazy_init_name_hash()\n> using the original single-threaded and the new multi-threaded\n> code paths.\n> \n> Includes a --dump option to dump the created hashmaps to\n> stdout. You can use this to run both code paths and\n> confirm that they generate the same hashmaps.\n> \n> Includes a --analyze option to analyze performance of both\n> code paths over a range of index sizes to help you find a\n> lower bound for the LAZY_THREAD_COST in name-hash.c.\n> For example, passing \"-a 4000\" will set \"istate.cache_nr\"\n> to 4000 and then try the multi-threaded code -- probably\n> giving 2 threads with 2000 entries each. It will then\n> run both the single-threaded (1x4000) and the multi-threaded\n> (2x2000) and compare the times. It will then repeat the\n> test with 8000, 12000, and etc. so that you can see the\n> cross over.\n> \n> Signed-off-by: Jeff Hostetler \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> \n> diff --git a/Makefile b/Makefile\n> index 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\n> diff --git a/cache.h b/cache.h\n> index 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);\n> diff --git a/t/helper/test-lazy-init-name-hash.c b/t/helper/test-lazy-init-name-hash.c\n> new file mode 100644\n> index 0000000..0769e17\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;\n> +static int multi;\n> +static int count = 1;\n> +static int dump;\n> +static int perf;\n> +static int analyze;\n> +static int analyze_step;\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\nstatic void dump_run(void)\n\n[again, sparse complains ...]\n\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\nstatic uint64_t time_runs(int try_threaded)\n\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\nstatic void analyze_run(void)\n\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\nATB,\nRamsay Jones\n\n"},{"id":"315127","messageId":"CAGZ79kZKri4jsnGCWhpV_WjSef5DxSwMTxYOour9kjzTWOFcxA@mail.gmail.com","threadId":"45479","inReplyTo":"e987714e-473f-cad1-159b-18459ffeb241@ramsayjones.plus.com","subject":"Re: [PATCH v2 5/7] name-hash: perf improvement for lazy_init_name_hash","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-03-23T17:45:07Z","receivedAt":"2017-03-23T17:45:12Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Mar 23, 2017 at 8:25 AM, Ramsay Jones\n wrote:\n>> +static struct dir_entry *hash_dir_entry_with_parent_and_prefix(\n>> + struct index_state *istate,\n>> + struct dir_entry *parent,\n>> + struct strbuf *prefix)\n>> +{\n>> + struct dir_entry *dir;\n>> + unsigned int hash;\n>> + int lock_nr;\n>> +\n>> + /*\n>> + * Either we have a parent directory and path with slash(es)\n>> + * or the directory is an immediate child of the root directory.\n>> + */\n>> + assert((parent != NULL) ^ (strchr(prefix->buf, '/') == 0));\n>\n> sparse complains about 'Using plain integer as a NULL pointer', (the\n> return from strchr() is NULL, if '/' is not found) so maybe:\n>\n> + assert((parent != NULL) ^ (strchr(prefix->buf, '/') == NULL));\n>\n\nAlso this seems part of the actual shipped code, not testing code.\nIn that case we prefer\n\n if ()\n die(\"BUG: \");\n\nThis is because asserts may be omitted by the compiler,\nwhen compiled with NDEBUG.\n\nHowever it is preferable to have these error checking code\nin the shipped product, as opposed to users running into\nthat edge case and reporting an error which is totally non-obvious.\n\nThanks,\nStefan\n"},{"id":"315130","messageId":"xmqqh92jev8d.fsf@gitster.mtv.corp.google.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"Re: [PATCH v2 0/7] thread lazy_init_name_hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-23T17:52:34Z","receivedAt":"2017-03-23T17:52:52Z","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 \n>\n> Version 2 of this patch series addresses the coding\n> style issues, compile errors in non-threaded builds,\n> and updated API documentation.\n>\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) with an 8 (logical)\n> core machine, we reduced the runtime of lazy_init_name_hash()\n> from 1.4 to 0.27 seconds.\n>\n> This patch series replaces my earlier\n> * jh/memihash-opt (2017-02-17) 5 commits\n> patch series. This series is an improvement over the\n> original proposal because it completely isolates the changes\n> in name name-hash.c (rather than having parts in preload-index.c)\n> and eliminates the need to update/invalidate precomputed hash\n> values as cache_entries are changed.\n\nHaving the above helps readers by giving them what to expect to see\nto prepare them before they dive into the patches ;-)\n\nThe API document update in 4/7 is a nice addition and it comes at\nthe right spot in the series, just after API enhancement is done. I\ngave a quick reading on it twice, and all looked reasonable. Nicely\ndone.\n\nI queued the sparse things Ramsay pointed out in the form of\n\"SQUASH???\" immediately that follows your original patch while\napplying the series, so please check what I push out (when it\nhappens) and if there is no further change needed, just tell me to\nactually squash them in, if you think these SQUASH??? patches are\ngood. That way we do not have to have another reroll only to fix\nthese up ;-)\n\nI'll need to re-read \"name-hash: perf improvement for lazy_init_name_hash\"\nlater again to convince myself, but during my initial read (from the\nlast round) I didn't spot anything wrong there.\n\nThanks.\n"},{"id":"315242","messageId":"89375f59-8716-3ddc-b163-5669452273c5@jeffhostetler.com","threadId":"45479","inReplyTo":"CAGZ79kZKri4jsnGCWhpV_WjSef5DxSwMTxYOour9kjzTWOFcxA@mail.gmail.com","subject":"Re: [PATCH v2 5/7] name-hash: perf improvement for lazy_init_name_hash","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-24T12:36:06Z","receivedAt":"2017-03-24T12:36:13Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/23/2017 1:45 PM, Stefan Beller wrote:\n> On Thu, Mar 23, 2017 at 8:25 AM, Ramsay Jones\n> wrote:\n>>> + /*\n>>> + * Either we have a parent directory and path with slash(es)\n>>> + * or the directory is an immediate child of the root directory.\n>>> + */\n>>> + assert((parent != NULL) ^ (strchr(prefix->buf, '/') == 0));\n>>\n>\n> Also this seems part of the actual shipped code, not testing code.\n> In that case we prefer\n>\n> if ()\n> die(\"BUG: \");\n>\n> This is because asserts may be omitted by the compiler,\n> when compiled with NDEBUG.\n\nI mainly wrote that for myself while testing. Now that I'm\npast that, I'm comfortable removing it completely or converting\nit to an actual if-die.\n\nJeff\n"},{"id":"315244","messageId":"5f29c3d9-0de5-385e-fda1-fb4380c7bc17@jeffhostetler.com","threadId":"45479","inReplyTo":"xmqqh92jev8d.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2 0/7] thread lazy_init_name_hash","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-24T12:39:52Z","receivedAt":"2017-03-24T12:39:59Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/23/2017 1:52 PM, Junio C Hamano wrote:\n> The API document update in 4/7 is a nice addition and it comes at\n> the right spot in the series, just after API enhancement is done. I\n> gave a quick reading on it twice, and all looked reasonable. Nicely\n> done.\n\nThanks.\n\n> I queued the sparse things Ramsay pointed out in the form of\n> \"SQUASH???\" immediately that follows your original patch while\n> applying the series, so please check what I push out (when it\n> happens) and if there is no further change needed, just tell me to\n> actually squash them in, if you think these SQUASH??? patches are\n> good. That way we do not have to have another reroll only to fix\n> these up ;-)\n\nThe squashes look fine.\n\nWRT the assert() in name-hash.c, Stefan suggested converting it\nto an if-!-die form in an earlier message in this thread. I'm OK\nwith that or with removing the assert completely.\n\n> I'll need to re-read \"name-hash: perf improvement for lazy_init_name_hash\"\n> later again to convince myself, but during my initial read (from the\n> last round) I didn't spot anything wrong there.\n>\n> Thanks.\n>\n\nThanks,\nJeff\n"},{"id":"315269","messageId":"CAGZ79kZU2Gzq7Qv7+UJSeu9gMai6A3vZB+cg8Lcu-7FUZ1-w1A@mail.gmail.com","threadId":"45479","inReplyTo":"5f29c3d9-0de5-385e-fda1-fb4380c7bc17@jeffhostetler.com","subject":"Re: [PATCH v2 0/7] thread lazy_init_name_hash","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-03-24T16:36:44Z","receivedAt":"2017-03-24T16:36:53Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Mar 24, 2017 at 5:39 AM, Jeff Hostetler wrote:\n> WRT the assert() in name-hash.c, Stefan suggested converting it\n> to an if-!-die form in an earlier message in this thread. I'm OK\n> with that or with removing the assert completely.\n\nI think removing them completely sounds even better.\n\nThanks,\nStefan\n"},{"id":"315287","messageId":"xmqq4lyi8t7o.fsf@gitster.mtv.corp.google.com","threadId":"45479","inReplyTo":"5f29c3d9-0de5-385e-fda1-fb4380c7bc17@jeffhostetler.com","subject":"Re: [PATCH v2 0/7] thread lazy_init_name_hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-24T17:44:59Z","receivedAt":"2017-03-24T17:48:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff Hostetler writes:\n\n> WRT the assert() in name-hash.c, Stefan suggested converting it\n> to an if-!-die form in an earlier message in this thread. I'm OK\n> with that or with removing the assert completely.\n\nI actually am OK with leaving things as they are ;-)\n"},{"id":"315527","messageId":"xmqqinmu1n8o.fsf@gitster.mtv.corp.google.com","threadId":"45479","inReplyTo":"1490276825-41544-6-git-send-email-git@jeffhostetler.com","subject":"Re: [PATCH v2 5/7] name-hash: perf improvement for lazy_init_name_hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-03-27T20:24:55Z","receivedAt":"2017-03-27T20:25:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"git@jeffhostetler.com writes:\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\nGood thinking is very well explained in the in-code comment.\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\nDying at this low level in the callchain in a worker thread made me\nfeel a little bit nervous, but even if we arrange to return to the\ncaller without doing extra computation, we would want to detect and\nabort when the cache entries are not sorted anyway, so this hsould\nbe OK.\n\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\nThe varilable \"rc\" (return code?) is a lot more than return code; it\ntells how many entries we processed and signals the caller that it\nstill needs to sweep the remainder if we didn't reach k_end. The\ncaller of this function calls the variable to receive this\n\"processed\", so I didn't find it too confusing while reading the\ncode top-down, though.\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\nAt first I was worried by this early return (i.e. we chop the entire\nactive_nr entries into lazy_nr_dir_threads and hand each of them a\nrange [k_start, k_end)---stopping before a thread reaches the end of\nthe range it is responsible for will leave gaps), but then realized\nthat this early return \"we are done with the entries in the same\ndirectory\" kicks in only for recursive invocation of this function,\nwhich makes it correct and perfectly fine.\n\nI also briefly wondered if it is worth wiggling the boundary of\nranges for adjacent workers to align with directory boundaries, as\nthe last round of hashes done by a worker and the first round of\nhashes done by another worker adjacent to it will be hashing for the\nsame parent directory, but I think that would be counter-productive\nand think your \"almost even\" distribution would be a lot more\nsensible. After all, when distribution of paths is skewed, a single\ndirectory may have disproportionally more (leaf) entries than the\nremainder of the index and in such a case, we would want multiple\nworkers to share the load of hashing them, even if that means they\nmay have to hash the same leading path independently.\n\nNicely done. Let's have this in 'next' and then in 'master'\nsoonish.\n\nThanks.\n"},{"id":"315531","messageId":"122907b4-e689-c436-18df-27664186a8ce@jeffhostetler.com","threadId":"45479","inReplyTo":"xmqqinmu1n8o.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2 5/7] name-hash: perf improvement for lazy_init_name_hash","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-03-27T20:50:40Z","receivedAt":"2017-03-27T20:51:08Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/27/2017 4:24 PM, Junio C Hamano wrote:\n> git@jeffhostetler.com writes:\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> Good thinking is very well explained in the in-code comment.\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>\n> Dying at this low level in the callchain in a worker thread made me\n> feel a little bit nervous, but even if we arrange to return to the\n> caller without doing extra computation, we would want to detect and\n> abort when the cache entries are not sorted anyway, so this hsould\n> be OK.\n\nyeah, i wasn't sure if there was any need to complicate things\nreturning this error. the index is sorted before we get here,\nso this should never happen.\n\n>\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> The varilable \"rc\" (return code?) is a lot more than return code; it\n> tells how many entries we processed and signals the caller that it\n> still needs to sweep the remainder if we didn't reach k_end. The\n> caller of this function calls the variable to receive this\n> \"processed\", so I didn't find it too confusing while reading the\n> code top-down, though.\n\nThe \"rc\" variable came from clear_ce_flags_dir(). I stole the\ndiving logic from it and clear_ce_flags_1(), so I tried to keep\nthe same name here.\n\n(And that reminds me, the linear search in clead_ce_flags_dir()\ncould be sped up with a variation of the binary search I put in\nhere. But that's for another day.)\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> At first I was worried by this early return (i.e. we chop the entire\n> active_nr entries into lazy_nr_dir_threads and hand each of them a\n> range [k_start, k_end)---stopping before a thread reaches the end of\n> the range it is responsible for will leave gaps), but then realized\n> that this early return \"we are done with the entries in the same\n> directory\" kicks in only for recursive invocation of this function,\n> which makes it correct and perfectly fine.\n>\n> I also briefly wondered if it is worth wiggling the boundary of\n> ranges for adjacent workers to align with directory boundaries, as\n> the last round of hashes done by a worker and the first round of\n> hashes done by another worker adjacent to it will be hashing for the\n> same parent directory, but I think that would be counter-productive\n> and think your \"almost even\" distribution would be a lot more\n> sensible. After all, when distribution of paths is skewed, a single\n> directory may have disproportionally more (leaf) entries than the\n> remainder of the index and in such a case, we would want multiple\n> workers to share the load of hashing them, even if that means they\n> may have to hash the same leading path independently.\n\nI thought about various options along this, but yeah the work to\nfind the end of the directory would have to be done before the\nthreads started or each thread would have to tweak their endpoints\nand that might be more expensive than just repeating a few\ndirectory component calculations along the boundaries (and much\nmore complicated).\n\n>\n> Nicely done. Let's have this in 'next' and then in 'master'\n> soonish.\n>\n> Thanks.\n>\n\nThanks\nJeff\n"},{"id":"316254","messageId":"CACsJy8CCb+i3xjtEY=6_dWCGw8VJHT1Mo5973YmQ-6xpTd=z=g@mail.gmail.com","threadId":"45479","inReplyTo":"1490276825-41544-1-git-send-email-git@jeffhostetler.com","subject":"Re: [PATCH v2 0/7] thread lazy_init_name_hash","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2017-04-06T02:22:29Z","receivedAt":"2017-04-06T02:23:06Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Mar 23, 2017 at 8:46 PM, wrote:\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\nIf sha1 verification in the index file can now be optionally skipped,\nI wonder if you would have faster startup time by storing hashes in\nthe index as an extension. I have never tried it (though I planned to\nhave some sort of caching for this) but I would guess loading hashes\nwould cost less than 0.27 seconds, hopefully closer to 0.05 seconds.\n-- \nDuy\n"},{"id":"316276","messageId":"c89de108-916e-49a1-934c-0fb5d8901f3a@jeffhostetler.com","threadId":"45479","inReplyTo":"CACsJy8CCb+i3xjtEY=6_dWCGw8VJHT1Mo5973YmQ-6xpTd=z=g@mail.gmail.com","subject":"Re: [PATCH v2 0/7] thread lazy_init_name_hash","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T13:53:14Z","receivedAt":"2017-04-06T13:53:43Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/5/2017 10:22 PM, Duy Nguyen wrote:\n> On Thu, Mar 23, 2017 at 8:46 PM, wrote:\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> If sha1 verification in the index file can now be optionally skipped,\n> I wonder if you would have faster startup time by storing hashes in\n> the index as an extension. I have never tried it (though I planned to\n> have some sort of caching for this) but I would guess loading hashes\n> would cost less than 0.27 seconds, hopefully closer to 0.05 seconds.\n>\n\nI've thought about doing that, but haven't gotten around to\nactually trying it yet. It's on my TODO list though.\n\nThanks\nJeff\n"}]}