{"thread":{"id":"29068","subject":"[PATCH v2 2/3] grep: enable threading with -p and -W using lazy attribute lookup","startedAt":"2011-12-02T13:07:45Z","lastAt":"2011-12-25T03:32:27Z","messageCount":35,"participants":["Thomas Rast","René Scharfe","Jeff King","Eric Herman","J. Bruce Fields","Pete Wyckoff","Ævar Arnfjörð Bjarmason","Nguyen Thai Ngoc Duy"],"isPatch":true,"patchVersion":2,"patchTotal":3},"messages":[{"id":"180245","messageId":"cover.1322830368.git.trast@student.ethz.ch","threadId":"29068","inReplyTo":"201111291507.04754.trast@student.ethz.ch","subject":"[PATCH v2 0/3] grep multithreading and scaling","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-02T13:07:45Z","receivedAt":"2011-12-02T13:07:45Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"[Eric, I measured some numbers that may be interesting to the\ndiscussion about b2924dc. See below.]\n\nThis round wraps up the original patch I posted, plus the draft patch\nI posted inline the other day with René's review taken into account.\nI also added a patch that rips out threading in the non-worktree case;\nread on for the reasoning.\n\nRené Scharfe wrote:\n> Hmm, why are [gitattributes lookups] that expensive?\n> \n> callgrind tells me that userdiff_find_by_path() contributes only 0.18%\n> to the total cost with your first patch. Timings in my virtual machine\n> are very volatile, but it seems that here the difference is in the\n> system time while user is basically the same for all combinations of\n> patches.\n\nWell, turns out I was measuring something completely stupid. I had\n\n git grep --cached -W INITRAMFS_ROOT_UID\n\nwhere I put the --cached originally because that makes it independent\nof the worktree (which in the very first measurements I still had\nwiped, as I tend to do for this repo; I checked it out again after\nthat). This in fact gives me (~/g/git-grep --cached\nINITRAMFS_ROOT_UID, leaving aside -W; best of 10):\n\n THREADS=8: 2.88user 0.21system 0:02.94elapsed\n THREADS=4: 2.89user 0.29system 0:02.99elapsed\n THREADS=2: 2.83user 0.36system 0:02.87elapsed\n NO_PTHREADS: 2.16user 0.08system 0:02.25elapsed\n\nUhuh. Doesn't scale so well after all. But removing the --cached, as\nmost people probably would:\n\n THREADS=8: 0.19user 0.32system 0:00.16elapsed\n THREADS=4: 0.16user 0.34system 0:00.17elapsed\n THREADS=2: 0.18user 0.32system 0:00.26elapsed\n NO_PTHREADS: 0.12user 0.17system 0:00.31elapsed\n\nSo I conclude that during any grep that cannot use the worktree,\nhaving any threads hurts.\n\nIn addition, during a grep that *can* use the worktree, THREADS=8\nstill helps somewhat on my dual-core i7, though it goes downhill from\nthere (12 is again as fast as 4; I verified these details using\nbest-of-50 timings, and it is reproducible.)\n\nI have also run timings on a 2*6-core workstation running OS X, where\nperformance is best at 5 cores:\n\n 2 threads: 0.96 real 0.41 user 1.27 sys\n 3 threads: 0.68 real 0.41 user 1.30 sys\n 4 threads: 0.54 real 0.43 user 1.63 sys\n 5 threads: 0.50 real 0.41 user 1.51 sys\n 6 threads: 0.54 real 0.43 user 1.63 sys\n 7 threads: 0.86 real 0.49 user 1.93 sys\n 8 threads: 0.98 real 0.51 user 2.07 sys\n\nI kid you not. That's best-of-50 and rather stable. It's on the same\ntree as the Linux machine too, except for the problem that the OS X FS\nis set to case-insensitive and thus cannot represent the tree exactly.\nSo from git's POV, there are unstaged changes.\n\nSadly I do not have access to a Linux box having more than 2 physical\ncores. If you have one, please run some tests :-)\n\nSo based on my measurements, I would suggest that unless we have\nevidence of it scaling beyond 8 cores on some machine, b2924dc (grep:\ndetect number of CPUs for thread spawning) be dropped. For now I'm\nignoring the problem that on OS X it doesn't even scale to 8; I'd\nrather check how it fares on Linux first.\n\nI added a third patch on top that disables threading in any case that\ndoes not hit the worktree. I wonder if I missed something or if it\nreally is that simple. The neat part is that it's also a reduction in\ncode required, and at the same time avoids any issues 2/3 might have\nwith a future attributes-from-trees implementation.\n\nWith this I get\n\n worktree, 8 threads: 0.15user 0.37system 0:00.17elapsed\n --cached, 8 threads: 2.18user 0.07system 0:02.27elapsed\n\nOf course, we could probably gain a huge boost if the read_sha1\nmachinery could be made threaded, so that it can unpack several\nobjects at a time. In addition, I can well imagine that there are\ncombinations of delta density, object size, and luck where it pays off\nto grep in parallel. Do we care?\n\nNow I really should do something else than fretting over the\nsub-second performance of git-grep...\n\n\nThomas Rast (3):\n grep: load funcname patterns for -W\n grep: enable threading with -p and -W using lazy attribute lookup\n grep: disable threading in all but worktree case\n\n builtin/grep.c | 153 ++++++++++++++++--------------------------------------\n grep.c | 73 ++++++++++++++++----------\n grep.h | 7 +++\n t/t7810-grep.sh | 14 +++++\n 4 files changed, 112 insertions(+), 135 deletions(-)\n\n-- \n1.7.8.rc4.388.ge53ab\n"},{"id":"180244","messageId":"5e3bcf651b31b299ca411296e6e7c4d11f6ae617.1322830368.git.trast@student.ethz.ch","threadId":"29068","inReplyTo":"cover.1322830368.git.trast@student.ethz.ch","subject":"[PATCH v2 1/3] grep: load funcname patterns for -W","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-02T13:07:46Z","receivedAt":"2011-12-02T13:07:46Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"git-grep avoids loading the funcname patterns unless they are needed.\nba8ea74 (grep: add option to show whole function as context,\n2011-08-01) forgot to extend this test also to the new funcbody\nfeature. Do so.\n\nThe catch is that we also have to disable threading when using\nuserdiff, as explained in grep_threads_ok(). So we must be careful to\nintroduce the same test there.\n---\n grep.c | 7 ++++---\n t/t7810-grep.sh | 14 ++++++++++++++\n 2 files changed, 18 insertions(+), 3 deletions(-)\n\ndiff --git a/grep.c b/grep.c\nindex b29d09c..7a070e9 100644\n--- a/grep.c\n+++ b/grep.c\n@@ -948,8 +948,8 @@ int grep_threads_ok(const struct grep_opt *opt)\n \t * machinery in grep_buffer_1. The attribute code is not\n \t * thread safe, so we disable the use of threads.\n \t */\n-\tif (opt->funcname && !opt->unmatch_name_only && !opt->status_only &&\n-\t !opt->name_only)\n+\tif ((opt->funcname || opt->funcbody)\n+\t && !opt->unmatch_name_only && !opt->status_only && !opt->name_only)\n \t\treturn 0;\n \n \treturn 1;\n@@ -1008,7 +1008,8 @@ static int grep_buffer_1(struct grep_opt *opt, const char *name,\n \t}\n \n \tmemset(&xecfg, 0, sizeof(xecfg));\n-\tif (opt->funcname && !opt->unmatch_name_only && !opt->status_only &&\n+\tif ((opt->funcname || opt->funcbody)\n+\t && !opt->unmatch_name_only && !opt->status_only &&\n \t !opt->name_only && !binary_match_only && !collect_hits) {\n \t\tstruct userdiff_driver *drv = userdiff_find_by_path(name);\n \t\tif (drv && drv->funcname.pattern) {\ndiff --git a/t/t7810-grep.sh b/t/t7810-grep.sh\nindex 81263b7..7ba5b16 100755\n--- a/t/t7810-grep.sh\n+++ b/t/t7810-grep.sh\n@@ -523,6 +523,20 @@ test_expect_success 'grep -W' '\n \ttest_cmp expected actual\n '\n \n+cat >expected <.gitattributes &&\n+\tgit grep -W return >actual &&\n+\ttest_cmp expected actual\n+'\n+\n test_expect_success 'grep from a subdirectory to search wider area (1)' '\n \tmkdir -p s &&\n \t(\n-- \n1.7.8.rc4.388.ge53ab\n"},{"id":"180243","messageId":"9fd6c51b18accc532f556af0c2539ed9f97a93e5.1322830368.git.trast@student.ethz.ch","threadId":"29068","inReplyTo":"cover.1322830368.git.trast@student.ethz.ch","subject":"[PATCH v2 2/3] grep: enable threading with -p and -W using lazy attribute lookup","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-02T13:07:47Z","receivedAt":"2011-12-02T13:07:47Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Lazily load the userdiff attributes in match_funcname(). Use a\nseparate mutex around this loading to protect the (not thread-safe)\nattributes machinery. This lets us re-enable threading with -p and\n-W while reducing the overhead caused by looking up attributes.\n\nSigned-off-by: Thomas Rast \n---\n builtin/grep.c | 10 +++++++-\n grep.c | 74 ++++++++++++++++++++++++++++++++++----------------------\n grep.h | 7 +++++\n 3 files changed, 61 insertions(+), 30 deletions(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 988ea1d..65b1ffe 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -256,6 +256,7 @@ static void start_threads(struct grep_opt *opt)\n \n \tpthread_mutex_init(&grep_mutex, NULL);\n \tpthread_mutex_init(&read_sha1_mutex, NULL);\n+\tpthread_mutex_init(&grep_attr_mutex, NULL);\n \tpthread_cond_init(&cond_add, NULL);\n \tpthread_cond_init(&cond_write, NULL);\n \tpthread_cond_init(&cond_result, NULL);\n@@ -303,6 +304,7 @@ static int wait_all(void)\n \n \tpthread_mutex_destroy(&grep_mutex);\n \tpthread_mutex_destroy(&read_sha1_mutex);\n+\tpthread_mutex_destroy(&grep_attr_mutex);\n \tpthread_cond_destroy(&cond_add);\n \tpthread_cond_destroy(&cond_write);\n \tpthread_cond_destroy(&cond_result);\n@@ -1002,9 +1004,15 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t\topt.regflags |= REG_ICASE;\n \n #ifndef NO_PTHREADS\n-\tif (online_cpus() == 1 || !grep_threads_ok(&opt))\n+\tif (online_cpus() == 1)\n \t\tuse_threads = 0;\n+#else\n+\tuse_threads = 0;\n+#endif\n \n+\topt.use_threads = use_threads;\n+\n+#ifndef NO_PTHREADS\n \tif (use_threads) {\n \t\tif (opt.pre_context || opt.post_context || opt.file_break ||\n \t\t opt.funcbody)\ndiff --git a/grep.c b/grep.c\nindex 7a070e9..4dd7da2 100644\n--- a/grep.c\n+++ b/grep.c\n@@ -2,6 +2,7 @@\n #include \"grep.h\"\n #include \"userdiff.h\"\n #include \"xdiff-interface.h\"\n+#include \"thread-utils.h\"\n \n void append_header_grep_pattern(struct grep_opt *opt, enum grep_header_field field, const char *pat)\n {\n@@ -806,10 +807,46 @@ static void show_line(struct grep_opt *opt, char *bol, char *eol,\n \topt->output(opt, \"\\n\", 1);\n }\n \n-static int match_funcname(struct grep_opt *opt, char *bol, char *eol)\n+#ifndef NO_PTHREADS\n+/*\n+ * This lock protects access to the gitattributes machinery, which is\n+ * not thread-safe.\n+ */\n+pthread_mutex_t grep_attr_mutex;\n+\n+static inline void grep_attr_lock(struct grep_opt *opt)\n+{\n+\tif (opt->use_threads)\n+\t\tpthread_mutex_lock(&grep_attr_mutex);\n+}\n+\n+static inline void grep_attr_unlock(struct grep_opt *opt)\n+{\n+\tif (opt->use_threads)\n+\t\tpthread_mutex_unlock(&grep_attr_mutex);\n+}\n+#else\n+#define grep_attr_lock(opt)\n+#define grep_attr_unlock(opt)\n+#endif\n+\n+static int match_funcname(struct grep_opt *opt, const char *name, char *bol, char *eol)\n {\n \txdemitconf_t *xecfg = opt->priv;\n-\tif (xecfg && xecfg->find_func) {\n+\tif (xecfg && !xecfg->find_func) {\n+\t\tstruct userdiff_driver *drv;\n+\t\tgrep_attr_lock(opt);\n+\t\tdrv = userdiff_find_by_path(name);\n+\t\tgrep_attr_unlock(opt);\n+\t\tif (drv && drv->funcname.pattern) {\n+\t\t\tconst struct userdiff_funcname *pe = &drv->funcname;\n+\t\t\txdiff_set_find_func(xecfg, pe->pattern, pe->cflags);\n+\t\t} else {\n+\t\t\txecfg = opt->priv = NULL;\n+\t\t}\n+\t}\n+\n+\tif (xecfg) {\n \t\tchar buf[1];\n \t\treturn xecfg->find_func(bol, eol - bol, buf, 1,\n \t\t\t\t\txecfg->find_func_priv) >= 0;\n@@ -835,7 +872,7 @@ static void show_funcname_line(struct grep_opt *opt, const char *name,\n \t\tif (lno <= opt->last_shown)\n \t\t\tbreak;\n \n-\t\tif (match_funcname(opt, bol, eol)) {\n+\t\tif (match_funcname(opt, name, bol, eol)) {\n \t\t\tshow_line(opt, bol, eol, name, lno, '=');\n \t\t\tbreak;\n \t\t}\n@@ -848,7 +885,7 @@ static void show_pre_context(struct grep_opt *opt, const char *name, char *buf,\n \tunsigned cur = lno, from = 1, funcname_lno = 0;\n \tint funcname_needed = !!opt->funcname;\n \n-\tif (opt->funcbody && !match_funcname(opt, bol, end))\n+\tif (opt->funcbody && !match_funcname(opt, name, bol, end))\n \t\tfuncname_needed = 2;\n \n \tif (opt->pre_context < lno)\n@@ -864,7 +901,7 @@ static void show_pre_context(struct grep_opt *opt, const char *name, char *buf,\n \t\twhile (bol > buf && bol[-1] != '\\n')\n \t\t\tbol--;\n \t\tcur--;\n-\t\tif (funcname_needed && match_funcname(opt, bol, eol)) {\n+\t\tif (funcname_needed && match_funcname(opt, name, bol, eol)) {\n \t\t\tfuncname_lno = cur;\n \t\t\tfuncname_needed = 0;\n \t\t}\n@@ -942,19 +979,6 @@ static int look_ahead(struct grep_opt *opt,\n \treturn 0;\n }\n \n-int grep_threads_ok(const struct grep_opt *opt)\n-{\n-\t/* If this condition is true, then we may use the attribute\n-\t * machinery in grep_buffer_1. The attribute code is not\n-\t * thread safe, so we disable the use of threads.\n-\t */\n-\tif ((opt->funcname || opt->funcbody)\n-\t && !opt->unmatch_name_only && !opt->status_only && !opt->name_only)\n-\t\treturn 0;\n-\n-\treturn 1;\n-}\n-\n static void std_output(struct grep_opt *opt, const void *buf, size_t size)\n {\n \tfwrite(buf, size, 1, stdout);\n@@ -1008,16 +1032,8 @@ static int grep_buffer_1(struct grep_opt *opt, const char *name,\n \t}\n \n \tmemset(&xecfg, 0, sizeof(xecfg));\n-\tif ((opt->funcname || opt->funcbody)\n-\t && !opt->unmatch_name_only && !opt->status_only &&\n-\t !opt->name_only && !binary_match_only && !collect_hits) {\n-\t\tstruct userdiff_driver *drv = userdiff_find_by_path(name);\n-\t\tif (drv && drv->funcname.pattern) {\n-\t\t\tconst struct userdiff_funcname *pe = &drv->funcname;\n-\t\t\txdiff_set_find_func(&xecfg, pe->pattern, pe->cflags);\n-\t\t\topt->priv = &xecfg;\n-\t\t}\n-\t}\n+\topt->priv = &xecfg;\n+\n \ttry_lookahead = should_lookahead(opt);\n \n \twhile (left) {\n@@ -1093,7 +1109,7 @@ static int grep_buffer_1(struct grep_opt *opt, const char *name,\n \t\t\t\tshow_function = 1;\n \t\t\tgoto next_line;\n \t\t}\n-\t\tif (show_function && match_funcname(opt, bol, eol))\n+\t\tif (show_function && match_funcname(opt, name, bol, eol))\n \t\t\tshow_function = 0;\n \t\tif (show_function ||\n \t\t (last_hit && lno <= last_hit + opt->post_context)) {\ndiff --git a/grep.h b/grep.h\nindex a652800..15d227c 100644\n--- a/grep.h\n+++ b/grep.h\n@@ -115,6 +115,7 @@ struct grep_opt {\n \tint show_hunk_mark;\n \tint file_break;\n \tint heading;\n+\tint use_threads;\n \tvoid *priv;\n \n \tvoid (*output)(struct grep_opt *opt, const void *data, size_t size);\n@@ -131,4 +132,10 @@ struct grep_opt {\n extern struct grep_opt *grep_opt_dup(const struct grep_opt *opt);\n extern int grep_threads_ok(const struct grep_opt *opt);\n \n+#ifndef NO_PTHREADS\n+/* Mutex used around access to the attributes machinery if\n+ * opt->use_threads. Must be initialized/destroyed by callers! */\n+extern pthread_mutex_t grep_attr_mutex;\n+#endif\n+\n #endif\n-- \n1.7.8.rc4.388.ge53ab\n"},{"id":"180246","messageId":"5328add8b32f83b4cdbd2e66283f77c125ec127a.1322830368.git.trast@student.ethz.ch","threadId":"29068","inReplyTo":"cover.1322830368.git.trast@student.ethz.ch","subject":"[PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-02T13:07:48Z","receivedAt":"2011-12-02T13:07:48Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Measuring grep performance showed that in all but the worktree case\n(as opposed to --cached, or ), threading\nactually slows things down. For example, on my dual-core\nhyperthreaded i7 in a linux-2.6.git at v2.6.37-rc2, I got:\n\nThreads worktree case | --cached case\n--------------------------------------------------------------------------\n8 (default) | 2.17user 0.15sys 0:02.20real | 0.11user 0.26sys 0:00.11real\n4 | 2.06user 0.17sys 0:02.08real | 0.11user 0.26sys 0:00.12real\n2 | 2.02user 0.25sys 0:02.08real | 0.15user 0.37sys 0:00.28real\nNO_PTHREADS | 1.57user 0.05sys 0:01.64real | 0.09user 0.12sys 0:00.22real\n\nI conjecture that this is caused by contention on read_sha1_mutex.\n\nSo disable threading entirely when not scanning the worktree, to get\nthe NO_PTHREADS performance in that case. This obsoletes all code\nrelated to grep_sha1_async. The thread startup must be delayed until\nafter all arguments have been parsed, but this does not have a\nmeasurable effect.\n---\n builtin/grep.c | 157 ++++++++++++++++----------------------------------------\n 1 files changed, 44 insertions(+), 113 deletions(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 65b1ffe..edf6a31 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -34,21 +34,13 @@\n \t\t const char *name);\n static void *load_file(const char *filename, size_t *sz);\n \n-enum work_type {WORK_SHA1, WORK_FILE};\n-\n /* We use one producer thread and THREADS consumer\n * threads. The producer adds struct work_items to 'todo' and the\n * consumers pick work items from the same array.\n */\n struct work_item {\n-\tenum work_type type;\n \tchar *name;\n-\n-\t/* if type == WORK_SHA1, then 'identifier' is a SHA1,\n-\t * otherwise type == WORK_FILE, and 'identifier' is a NUL\n-\t * terminated filename.\n-\t */\n-\tvoid *identifier;\n+\tchar *filename;\n \tchar done;\n \tstruct strbuf out;\n };\n@@ -86,21 +78,6 @@ static inline void grep_unlock(void)\n \t\tpthread_mutex_unlock(&grep_mutex);\n }\n \n-/* Used to serialize calls to read_sha1_file. */\n-static pthread_mutex_t read_sha1_mutex;\n-\n-static inline void read_sha1_lock(void)\n-{\n-\tif (use_threads)\n-\t\tpthread_mutex_lock(&read_sha1_mutex);\n-}\n-\n-static inline void read_sha1_unlock(void)\n-{\n-\tif (use_threads)\n-\t\tpthread_mutex_unlock(&read_sha1_mutex);\n-}\n-\n /* Signalled when a new work_item is added to todo. */\n static pthread_cond_t cond_add;\n \n@@ -114,7 +91,7 @@ static inline void read_sha1_unlock(void)\n \n static int skip_first_line;\n \n-static void add_work(enum work_type type, char *name, void *id)\n+static void add_work(char *name, char *filename)\n {\n \tgrep_lock();\n \n@@ -122,9 +99,8 @@ static void add_work(enum work_type type, char *name, void *id)\n \t\tpthread_cond_wait(&cond_write, &grep_mutex);\n \t}\n \n-\ttodo[todo_end].type = type;\n \ttodo[todo_end].name = name;\n-\ttodo[todo_end].identifier = id;\n+\ttodo[todo_end].filename = filename;\n \ttodo[todo_end].done = 0;\n \tstrbuf_reset(&todo[todo_end].out);\n \ttodo_end = (todo_end + 1) % ARRAY_SIZE(todo);\n@@ -152,19 +128,10 @@ static void add_work(enum work_type type, char *name, void *id)\n \treturn ret;\n }\n \n-static void grep_sha1_async(struct grep_opt *opt, char *name,\n-\t\t\t const unsigned char *sha1)\n-{\n-\tunsigned char *s;\n-\ts = xmalloc(20);\n-\tmemcpy(s, sha1, 20);\n-\tadd_work(WORK_SHA1, name, s);\n-}\n-\n static void grep_file_async(struct grep_opt *opt, char *name,\n \t\t\t const char *filename)\n {\n-\tadd_work(WORK_FILE, name, xstrdup(filename));\n+\tadd_work(name, xstrdup(filename));\n }\n \n static void work_done(struct work_item *w)\n@@ -194,7 +161,7 @@ static void work_done(struct work_item *w)\n \t\t\twrite_or_die(1, p, len);\n \t\t}\n \t\tfree(w->name);\n-\t\tfree(w->identifier);\n+\t\tfree(w->filename);\n \t}\n \n \tif (old_done != todo_done)\n@@ -213,29 +180,18 @@ static void work_done(struct work_item *w)\n \n \twhile (1) {\n \t\tstruct work_item *w = get_work();\n+\t\tsize_t sz;\n+\t\tvoid* data;\n+\n \t\tif (!w)\n \t\t\tbreak;\n \n \t\topt->output_priv = w;\n-\t\tif (w->type == WORK_SHA1) {\n-\t\t\tunsigned long sz;\n-\t\t\tvoid* data = load_sha1(w->identifier, &sz, w->name);\n-\n-\t\t\tif (data) {\n-\t\t\t\thit |= grep_buffer(opt, w->name, data, sz);\n-\t\t\t\tfree(data);\n-\t\t\t}\n-\t\t} else if (w->type == WORK_FILE) {\n-\t\t\tsize_t sz;\n-\t\t\tvoid* data = load_file(w->identifier, &sz);\n-\t\t\tif (data) {\n-\t\t\t\thit |= grep_buffer(opt, w->name, data, sz);\n-\t\t\t\tfree(data);\n-\t\t\t}\n-\t\t} else {\n-\t\t\tassert(0);\n+\t\tdata = load_file(w->filename, &sz);\n+\t\tif (data) {\n+\t\t\thit |= grep_buffer(opt, w->name, data, sz);\n+\t\t\tfree(data);\n \t\t}\n-\n \t\twork_done(w);\n \t}\n \tfree_grep_patterns(arg);\n@@ -255,7 +211,6 @@ static void start_threads(struct grep_opt *opt)\n \tint i;\n \n \tpthread_mutex_init(&grep_mutex, NULL);\n-\tpthread_mutex_init(&read_sha1_mutex, NULL);\n \tpthread_mutex_init(&grep_attr_mutex, NULL);\n \tpthread_cond_init(&cond_add, NULL);\n \tpthread_cond_init(&cond_write, NULL);\n@@ -303,7 +258,6 @@ static int wait_all(void)\n \t}\n \n \tpthread_mutex_destroy(&grep_mutex);\n-\tpthread_mutex_destroy(&read_sha1_mutex);\n \tpthread_mutex_destroy(&grep_attr_mutex);\n \tpthread_cond_destroy(&cond_add);\n \tpthread_cond_destroy(&cond_write);\n@@ -312,9 +266,6 @@ static int wait_all(void)\n \treturn hit;\n }\n #else /* !NO_PTHREADS */\n-#define read_sha1_lock()\n-#define read_sha1_unlock()\n-\n static int wait_all(void)\n {\n \treturn 0;\n@@ -371,21 +322,11 @@ static int grep_config(const char *var, const char *value, void *cb)\n \treturn 0;\n }\n \n-static void *lock_and_read_sha1_file(const unsigned char *sha1, enum object_type *type, unsigned long *size)\n-{\n-\tvoid *data;\n-\n-\tread_sha1_lock();\n-\tdata = read_sha1_file(sha1, type, size);\n-\tread_sha1_unlock();\n-\treturn data;\n-}\n-\n static void *load_sha1(const unsigned char *sha1, unsigned long *size,\n \t\t const char *name)\n {\n \tenum object_type type;\n-\tvoid *data = lock_and_read_sha1_file(sha1, &type, size);\n+\tvoid *data = read_sha1_file(sha1, &type, size);\n \n \tif (!data)\n \t\terror(_(\"'%s': unable to read %s\"), name, sha1_to_hex(sha1));\n@@ -398,6 +339,9 @@ static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1,\n {\n \tstruct strbuf pathbuf = STRBUF_INIT;\n \tchar *name;\n+\tint hit;\n+\tunsigned long sz;\n+\tvoid *data;\n \n \tif (opt->relative && opt->prefix_length) {\n \t\tquote_path_relative(filename + tree_name_len, -1, &pathbuf,\n@@ -409,25 +353,15 @@ static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1,\n \n \tname = strbuf_detach(&pathbuf, NULL);\n \n-#ifndef NO_PTHREADS\n-\tif (use_threads) {\n-\t\tgrep_sha1_async(opt, name, sha1);\n-\t\treturn 0;\n-\t} else\n-#endif\n-\t{\n-\t\tint hit;\n-\t\tunsigned long sz;\n-\t\tvoid *data = load_sha1(sha1, &sz, name);\n-\t\tif (!data)\n-\t\t\thit = 0;\n-\t\telse\n-\t\t\thit = grep_buffer(opt, name, data, sz);\n+\tdata = load_sha1(sha1, &sz, name);\n+\tif (!data)\n+\t\thit = 0;\n+\telse\n+\t\thit = grep_buffer(opt, name, data, sz);\n \n-\t\tfree(data);\n-\t\tfree(name);\n-\t\treturn hit;\n-\t}\n+\tfree(data);\n+\tfree(name);\n+\treturn hit;\n }\n \n static void *load_file(const char *filename, size_t *sz)\n@@ -586,7 +520,7 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,\n \t\t\tvoid *data;\n \t\t\tunsigned long size;\n \n-\t\t\tdata = lock_and_read_sha1_file(entry.sha1, &type, &size);\n+\t\t\tdata = read_sha1_file(entry.sha1, &type, &size);\n \t\t\tif (!data)\n \t\t\t\tdie(_(\"unable to read tree (%s)\"),\n \t\t\t\t sha1_to_hex(entry.sha1));\n@@ -616,10 +550,8 @@ static int grep_object(struct grep_opt *opt, const struct pathspec *pathspec,\n \t\tstruct strbuf base;\n \t\tint hit, len;\n \n-\t\tread_sha1_lock();\n \t\tdata = read_object_with_reference(obj->sha1, tree_type,\n \t\t\t\t\t\t &size, NULL);\n-\t\tread_sha1_unlock();\n \n \t\tif (!data)\n \t\t\tdie(_(\"unable to read tree (%s)\"), sha1_to_hex(obj->sha1));\n@@ -1003,26 +935,6 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \tif (!opt.fixed && opt.ignore_case)\n \t\topt.regflags |= REG_ICASE;\n \n-#ifndef NO_PTHREADS\n-\tif (online_cpus() == 1)\n-\t\tuse_threads = 0;\n-#else\n-\tuse_threads = 0;\n-#endif\n-\n-\topt.use_threads = use_threads;\n-\n-#ifndef NO_PTHREADS\n-\tif (use_threads) {\n-\t\tif (opt.pre_context || opt.post_context || opt.file_break ||\n-\t\t opt.funcbody)\n-\t\t\tskip_first_line = 1;\n-\t\tstart_threads(&opt);\n-\t}\n-#else\n-\tuse_threads = 0;\n-#endif\n-\n \tcompile_grep_patterns(&opt);\n \n \t/* Check revs and then paths */\n@@ -1044,6 +956,25 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t\tbreak;\n \t}\n \n+#ifndef NO_PTHREADS\n+\tif (online_cpus() == 1 || cached || list.nr)\n+\t\tuse_threads = 0;\n+#else\n+\tuse_threads = 0;\n+#endif\n+\n+\topt.use_threads = use_threads;\n+\n+#ifndef NO_PTHREADS\n+\tif (use_threads) {\n+\t\topt.use_threads = use_threads;\n+\t\tif (opt.pre_context || opt.post_context || opt.file_break ||\n+\t\t opt.funcbody)\n+\t\t\tskip_first_line = 1;\n+\t\tstart_threads(&opt);\n+\t}\n+#endif\n+\n \t/* The rest are paths */\n \tif (!seen_dashdash) {\n \t\tint j;\n-- \n1.7.8.rc4.388.ge53ab\n"},{"id":"180252","messageId":"4ED8F9AE.8030605@lsrfire.ath.cx","threadId":"29068","inReplyTo":"5328add8b32f83b4cdbd2e66283f77c125ec127a.1322830368.git.trast@student.ethz.ch","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-02T16:15:42Z","receivedAt":"2011-12-02T16:15:42Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 02.12.2011 14:07, schrieb Thomas Rast:\n> Measuring grep performance showed that in all but the worktree case\n> (as opposed to --cached, or), threading\n> actually slows things down. For example, on my dual-core\n> hyperthreaded i7 in a linux-2.6.git at v2.6.37-rc2, I got:\n>\n> Threads worktree case | --cached case\n> --------------------------------------------------------------------------\n> 8 (default) | 2.17user 0.15sys 0:02.20real | 0.11user 0.26sys 0:00.11real\n> 4 | 2.06user 0.17sys 0:02.08real | 0.11user 0.26sys 0:00.12real\n> 2 | 2.02user 0.25sys 0:02.08real | 0.15user 0.37sys 0:00.28real\n> NO_PTHREADS | 1.57user 0.05sys 0:01.64real | 0.09user 0.12sys 0:00.22real\n\nAre the columns mixed up?\n\n> I conjecture that this is caused by contention on read_sha1_mutex.\n\nYeah, and I wonder why we need to have this lock in the first place. In \ntheory, multiple readers shouldn't have to affect each other at all, \nright? The lock could be pushed down into read_sha1_file(), or a \nthread-safe variant of the function added.\n\nIn pratice, however, the code in sha1_file.c etc. scares me. ;-)\n\n> So disable threading entirely when not scanning the worktree, to get\n> the NO_PTHREADS performance in that case. This obsoletes all code\n> related to grep_sha1_async. The thread startup must be delayed until\n> after all arguments have been parsed, but this does not have a\n> measurable effect.\n\nThis is a bit radical. I think the underlying issue that \nread_sha1_file() is not thread-safe can be solved eventually and then \nwe'd need to readd that code.\n\nHow about adding a parameter to control the number of threads \n(--threads?) instead that defaults to eight (or five) for the worktree \nand one for the rest? That would also make benchmarking easier.\n\nRené\n\nPS: Patches one and three missed a signoff.\n"},{"id":"180259","messageId":"20111202173400.GC23447@sigill.intra.peff.net","threadId":"29068","inReplyTo":"cover.1322830368.git.trast@student.ethz.ch","subject":"Re: [PATCH v2 0/3] grep multithreading and scaling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-02T17:34:00Z","receivedAt":"2011-12-02T17:34:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 02, 2011 at 02:07:45PM +0100, Thomas Rast wrote:\n\n> where I put the --cached originally because that makes it independent\n> of the worktree (which in the very first measurements I still had\n> wiped, as I tend to do for this repo; I checked it out again after\n> that). This in fact gives me (~/g/git-grep --cached\n> INITRAMFS_ROOT_UID, leaving aside -W; best of 10):\n> \n> THREADS=8: 2.88user 0.21system 0:02.94elapsed\n> THREADS=4: 2.89user 0.29system 0:02.99elapsed\n> THREADS=2: 2.83user 0.36system 0:02.87elapsed\n> NO_PTHREADS: 2.16user 0.08system 0:02.25elapsed\n> \n> Uhuh. Doesn't scale so well after all. But removing the --cached, as\n> most people probably would:\n> \n> THREADS=8: 0.19user 0.32system 0:00.16elapsed\n> THREADS=4: 0.16user 0.34system 0:00.17elapsed\n> THREADS=2: 0.18user 0.32system 0:00.26elapsed\n> NO_PTHREADS: 0.12user 0.17system 0:00.31elapsed\n> \n> So I conclude that during any grep that cannot use the worktree,\n> having any threads hurts.\n\nWow, that's horrible. Leaving aside the parallelism, it's just terrible\nthat reading from the cache is 20 times slower than the worktree. I get\nsimilar results on my quad-core machine.\n\nA quick perf run shows most of the time is spent inflating objects. The\ndiff code has a sneaky trick to re-use worktree files when we know they\nare stat-clean (in diff's case it is to avoid writing a tempfile). I\nwonder if we should use the same trick here.\n\nIt would hurt the cold cache case, though, as the compressed versions\nrequire fewer disk accesses, of course.\n\n-Peff\n\nPS I suspect your timings are somewhat affected by the simplicity of the\n regex you are asking for. The time to inflate the blobs dominates,\n because the search is just a memmem(). On my quad-core w/\n hyperthreading (i.e., 8 apparent cores):\n\n [no caching, simple regex; we get some parallelism, but the regex\n task is just not that intensive]\n $ /usr/bin/time git grep INITRAMFS_ROOT_UID >/dev/null\n 0.42user 0.45system 0:00.15elapsed 578%CPU\n\n [no caching, harder regex; we get much higher CPU utilization]\n $ /usr/bin/time git grep 'a.*b' >/dev/null\n 14.68user 0.50system 0:02.00elapsed 758%CPU\n\n [with caching, simple regex; we get almost _no_ parallelism because\n all of our time is spent deflating under a lock, and the regex task\n takes very little time]\n $ /usr/bin/time git grep --cached INITRAMFS_ROOT_UID >/dev/null\n 7.64user 0.41system 0:07.61elapsed 105%CPU\n\n [with caching, harder regex; not as much parallelism as we hoped for,\n but still much more than before. Because there is actually work to\n parallelize in the regex]\n $ /usr/bin/time git grep --cached 'a.*b' >/dev/null\n 23.46user 0.47system 0:08.42elapsed 284%CPU\n\n So I think there is value in parallelizing even --cached greps. But\n we could do so much better if blob inflation could be done in\n parallel.\n"},{"id":"180266","messageId":"4ED92EE4.7030404@freesa.org","threadId":"29068","inReplyTo":"cover.1322830368.git.trast@student.ethz.ch","subject":"Re: [PATCH v2 0/3] grep multithreading and scaling","fromName":"Eric Herman","fromEmail":"eric@freesa.org","sentAt":"2011-12-02T20:02:44Z","receivedAt":"2011-12-02T20:02:44Z","isPatch":true,"sender":{"key":"eric@freesa.org","avatar":null},"body":"Hello Thomas,\n\nThanks for the work and the great info.\nSome of the numbers are quite surprising.\n\nI do, indeed, have a machine with more cores, but I have been either \nbusy with out-of-town guests or generally plain lazy in the last couple \nof weeks. I intend to set aside some time to do some benchmarking this \nweekend.\n\nI'll let you know what I find.\n\nCheers,\n -Eric\n\n\n\n-- \nhttp://www.freesa.org/ -- mobile: +31 620719662\naim: ericigps -- skype: eric_herman -- jabber: eric.herman@gmail.com\n"},{"id":"180305","messageId":"201112051002.22138.trast@student.ethz.ch","threadId":"29068","inReplyTo":"4ED8F9AE.8030605@lsrfire.ath.cx","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-05T09:02:21Z","receivedAt":"2011-12-05T09:02:21Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"René Scharfe wrote:\n> Am 02.12.2011 14:07, schrieb Thomas Rast:\n> > Measuring grep performance showed that in all but the worktree case\n> > (as opposed to --cached, or), threading\n> > actually slows things down. For example, on my dual-core\n> > hyperthreaded i7 in a linux-2.6.git at v2.6.37-rc2, I got:\n> >\n> > Threads worktree case | --cached case\n> > --------------------------------------------------------------------------\n> > 8 (default) | 2.17user 0.15sys 0:02.20real | 0.11user 0.26sys 0:00.11real\n> > 4 | 2.06user 0.17sys 0:02.08real | 0.11user 0.26sys 0:00.12real\n> > 2 | 2.02user 0.25sys 0:02.08real | 0.15user 0.37sys 0:00.28real\n> > NO_PTHREADS | 1.57user 0.05sys 0:01.64real | 0.09user 0.12sys 0:00.22real\n> \n> Are the columns mixed up?\n\nIndeed, sorry.\n\nIn case you were wondering why this table is different from the\nnumbers given in the cover letter: I noticed at some point that I had\nan incomplete checkout (apparently 'git checkout -- .' is really not\nthe same as 'git reset --hard'... sigh). Then I saw that while the\nnumbers were different, the conclusion was not, so I forgot to update\nit.\n\n> This is a bit radical. I think the underlying issue that \n> read_sha1_file() is not thread-safe can be solved eventually and then \n> we'd need to readd that code.\n\nI'm also scared of sha1_file.c, especially when it gets down to\npackfiles. But perhaps it wouldn't be *too* hard to do it in parallel\niff the object can be read from the loose object store.\n\n> PS: Patches one and three missed a signoff.\n\nOops, thanks, turns out I had a misconfigured alias ...\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"180306","messageId":"201112051038.16423.trast@student.ethz.ch","threadId":"29068","inReplyTo":"20111202173400.GC23447@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/3] grep multithreading and scaling","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-05T09:38:16Z","receivedAt":"2011-12-05T09:38:16Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King wrote:\n> \n> A quick perf run shows most of the time is spent inflating objects. The\n> diff code has a sneaky trick to re-use worktree files when we know they\n> are stat-clean (in diff's case it is to avoid writing a tempfile). I\n> wonder if we should use the same trick here.\n> \n> It would hurt the cold cache case, though, as the compressed versions\n> require fewer disk accesses, of course.\n\nI just found out that on Linux, there's mincore() that can tell us\n(racily, but who cares) whether a given file mapping is in memory. If\nyou would like to try it, see the source at the end, but I'm getting\nthings such as\n\n # in a random collection of files, none of which I have accessed lately\n $ ls -l\n -rw-r--r-- 1 thomas users 116534 Jul 4 2010 IMG_4884.JPG\n -rw-r--r-- 1 thomas users 7278081 Aug 25 2010 remoteserverrepo.zip\n $ ./mincore IMG_4884.JPG \n 00000000000000000000000000000\n $ cat IMG_4884.JPG > /dev/null \n $ ./mincore IMG_4884.JPG \n 11111111111111111111111111111\n $ ./mincore remoteserverrepo.zip \n 0000000000000000000000[...]\n $ head -10 remoteserverrepo.zip >/dev/null\n $ ./mincore remoteserverrepo.zip \n 1111000000000000000000[...]\n\nSo that looks fairly promising, and the order would then be:\n\n- if stat-clean, and we have mincore(), and it tells us we can do it\n cheaply: grab file from tree\n\n- if it's a loose object: decompress it\n\n- if stat-clean: grab file from tree\n\n- access packs as usual\n\n> PS I suspect your timings are somewhat affected by the simplicity of the\n> regex you are asking for. The time to inflate the blobs dominates,\n> because the search is just a memmem(). On my quad-core w/\n> hyperthreading (i.e., 8 apparent cores):\n> \n> $ /usr/bin/time git grep INITRAMFS_ROOT_UID >/dev/null\n> 0.42user 0.45system 0:00.15elapsed 578%CPU\n> $ /usr/bin/time git grep 'a.*b' >/dev/null\n> 14.68user 0.50system 0:02.00elapsed 758%CPU\n> $ /usr/bin/time git grep --cached INITRAMFS_ROOT_UID >/dev/null\n> 7.64user 0.41system 0:07.61elapsed 105%CPU\n> $ /usr/bin/time git grep --cached 'a.*b' >/dev/null\n> 23.46user 0.47system 0:08.42elapsed 284%CPU\n> \n> So I think there is value in parallelizing even --cached greps. But\n> we could do so much better if blob inflation could be done in\n> parallel.\n\nOk, I see, I missed that part. Perhaps the heuristic should then be\n\"if the regex boils down to memmem, disable threading\", but let's see\nwhat loose object decompression in parallel can give us.\n\n\n---- 8< ---- mincore.c ---- 8< ----\n#include \n#include \n#include \n#include \n#include \n#include \n#include \n\nvoid die(const char *s)\n{\n\tperror(s);\n\texit(1);\n}\n\nint main (int argc, char *argv[])\n{\n\tvoid *mem;\n\tsize_t len;\n\tstruct stat st;\n\tint fd;\n\tunsigned char *vec;\n\tint vsize;\n\tint i;\n\tsize_t page = sysconf(_SC_PAGESIZE);\n\n\tif (argc != 2) {\n\t\tfprintf(stderr, \"usage: %s \\n\", argv[0]);\n\t\texit(2);\n\t}\n\n\tfd = open(argv[1], O_RDONLY);\n\tif (fd == -1)\n\t\tdie(\"open failed\");\n\tif (fstat(fd, &st) == -1)\n\t\tdie(\"fstat failed\");\n\tmem = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);\n\tif (mem == (void*) -1)\n\t\tdie(\"mmap failed\");\n\n\tvsize = (st.st_size+page-1)/page;\n\tvec = malloc(vsize);\n\tif (!vec)\n\t\tdie(\"malloc failed\");\n\tif (mincore(mem, st.st_size, vec) == -1)\n\t\tdie(\"mincore failed\");\n\tfor (i = 0; i < vsize; i++)\n\t\tprintf(\"%d\", (int) vec[i]);\n\tprintf(\"\\n\");\n\treturn 0;\n}\n\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"180314","messageId":"201112052116.48106.trast@student.ethz.ch","threadId":"29068","inReplyTo":"201112051038.16423.trast@student.ethz.ch","subject":"Re: [PATCH v2 0/3] grep multithreading and scaling","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-05T20:16:47Z","receivedAt":"2011-12-05T20:16:47Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Rast wrote:\n> \n> I just found out that on Linux, there's mincore() that can tell us\n> (racily, but who cares) whether a given file mapping is in memory.\n[...]\n> So that looks fairly promising, and the order would then be:\n> \n> - if stat-clean, and we have mincore(), and it tells us we can do it\n> cheaply: grab file from tree\n> \n> - if it's a loose object: decompress it\n> \n> - if stat-clean: grab file from tree\n> \n> - access packs as usual\n\nJust a small note, I tried two things:\n\n* the simpler option of grabbing a loose object if it exists and is\n mincore() turns out to massively slow down 'git log HEAD', probably\n because only very few of these objects are loose in the first place\n\n* doing this only under grep's use_threads, and dropping the lock\n around unpack_sha1_file() [i.e., zlib decompression] still results\n in a git-grep that is slower than without this, though not much\n\nSo no improvement here. Will have to look into the worktree trick\nthough.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"180327","messageId":"20111206004012.GA12760@sigill.intra.peff.net","threadId":"29068","inReplyTo":"201112051038.16423.trast@student.ethz.ch","subject":"Re: [PATCH v2 0/3] grep multithreading and scaling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-06T00:40:12Z","receivedAt":"2011-12-06T00:40:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 05, 2011 at 10:38:16AM +0100, Thomas Rast wrote:\n\n> I just found out that on Linux, there's mincore() that can tell us\n> (racily, but who cares) whether a given file mapping is in memory. If\n> you would like to try it, see the source at the end, but I'm getting\n> things such as\n\nNeat, I didn't know about mincore.\n\n> So that looks fairly promising, and the order would then be:\n> \n> - if stat-clean, and we have mincore(), and it tells us we can do it\n> cheaply: grab file from tree\n> \n> - if it's a loose object: decompress it\n> \n> - if stat-clean: grab file from tree\n> \n> - access packs as usual\n\nI don't think your third one makes sense. If the working tree file isn't\nstat clean, then either:\n\n 1. the pack file is in cache, and it's way faster than faulting in the\n working tree file from disk\n\n 2. the pack file is not in cache, and it's a toss-up whether it is\n faster to fault in the smaller compressed pack-file version and\n uncompress it, or to fault in the larger on-disk version. The\n exact result will depend on the ratio of CPU to disk speed, the\n quality of your filesystem, and the size and contents of your file.\n\n And possibly on the exact delta chains you have. Though this\n optimization only happens when the file is in the index, which\n usually means it's recent, which means it will tend to be at the\n head of the delta chain.\n\nSo it probably just makes sense to grab the working tree file only if\nmincore() tells us we have all (or most) of it, and otherwise go to the\npackfile.\n\n> Ok, I see, I missed that part. Perhaps the heuristic should then be\n> \"if the regex boils down to memmem, disable threading\", but let's see\n> what loose object decompression in parallel can give us.\n\nYeah. I'd really rather have parallel object decompression than some\ncomplex Linux-only mincore optimization (even though that optimization\n_could_ yield extra savings on top of properly threading, if the blob\nretrieval is threaded, I think I'll care less about how much CPU time it\ntakes).\n\n-Peff\n"},{"id":"180425","messageId":"4EDE9BBA.2010409@lsrfire.ath.cx","threadId":"29068","inReplyTo":"4ED8F9AE.8030605@lsrfire.ath.cx","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-06T22:48:26Z","receivedAt":"2011-12-06T22:48:26Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 02.12.2011 17:15, schrieb René Scharfe:\n> How about adding a parameter to control the number of threads \n> (--threads?) instead that defaults to eight (or five) for the worktree \n> and one for the rest? That would also make benchmarking easier.\n\nLike this:\n\n-- >8 --\nSubject: grep: add parameter --threads\n\nAllow the number of threads to be specified by the user. This makes\nbenchmarking the performance impact of different numbers of threads\nmuch easier.\n\nMove the code for thread handling after argument parsing. This allows\nto change the default number of threads based on the kind of search\n(worktree etc.) later on.\n\nSigned-off-by: Rene Scharfe \n---\nApplies on top of your second patch.\n\n Documentation/git-grep.txt | 4 ++\n builtin/grep.c | 75 +++++++++++++++++++++++--------------------\n 2 files changed, 44 insertions(+), 35 deletions(-)\n\ndiff --git a/Documentation/git-grep.txt b/Documentation/git-grep.txt\nindex 15d6711..47ac188 100644\n--- a/Documentation/git-grep.txt\n+++ b/Documentation/git-grep.txt\n@@ -227,6 +227,10 @@ OPTIONS\n \tDo not output matched lines; instead, exit with status 0 when\n \tthere is a match and with non-zero status when there isn't.\n \n+--threads ::\n+\tRun search threads in parallel. Default is 8. This option\n+\tis ignored if git was built without support for POSIX threads.\n+\n ...::\n \tInstead of searching tracked files in the working tree, search\n \tblobs in the given trees.\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 65b1ffe..0bda900 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -24,11 +24,10 @@ static char const * const grep_usage[] = {\n \tNULL\n };\n \n-static int use_threads = 1;\n-\n #ifndef NO_PTHREADS\n #define THREADS 8\n-static pthread_t threads[THREADS];\n+static pthread_t *threads;\n+static int nr_threads = -1;\n \n static void *load_sha1(const unsigned char *sha1, unsigned long *size,\n \t\t const char *name);\n@@ -76,13 +75,13 @@ static pthread_mutex_t grep_mutex;\n \n static inline void grep_lock(void)\n {\n-\tif (use_threads)\n+\tif (nr_threads > 0)\n \t\tpthread_mutex_lock(&grep_mutex);\n }\n \n static inline void grep_unlock(void)\n {\n-\tif (use_threads)\n+\tif (nr_threads > 0)\n \t\tpthread_mutex_unlock(&grep_mutex);\n }\n \n@@ -91,13 +90,13 @@ static pthread_mutex_t read_sha1_mutex;\n \n static inline void read_sha1_lock(void)\n {\n-\tif (use_threads)\n+\tif (nr_threads > 0)\n \t\tpthread_mutex_lock(&read_sha1_mutex);\n }\n \n static inline void read_sha1_unlock(void)\n {\n-\tif (use_threads)\n+\tif (nr_threads > 0)\n \t\tpthread_mutex_unlock(&read_sha1_mutex);\n }\n \n@@ -254,6 +253,8 @@ static void start_threads(struct grep_opt *opt)\n {\n \tint i;\n \n+\tthreads = xcalloc(nr_threads, sizeof(pthread_t));\n+\n \tpthread_mutex_init(&grep_mutex, NULL);\n \tpthread_mutex_init(&read_sha1_mutex, NULL);\n \tpthread_mutex_init(&grep_attr_mutex, NULL);\n@@ -265,7 +266,7 @@ static void start_threads(struct grep_opt *opt)\n \t\tstrbuf_init(&todo[i].out, 0);\n \t}\n \n-\tfor (i = 0; i < ARRAY_SIZE(threads); i++) {\n+\tfor (i = 0; i < nr_threads; i++) {\n \t\tint err;\n \t\tstruct grep_opt *o = grep_opt_dup(opt);\n \t\to->output = strbuf_out;\n@@ -296,7 +297,7 @@ static int wait_all(void)\n \tpthread_cond_broadcast(&cond_add);\n \tgrep_unlock();\n \n-\tfor (i = 0; i < ARRAY_SIZE(threads); i++) {\n+\tfor (i = 0; i < nr_threads; i++) {\n \t\tvoid *h;\n \t\tpthread_join(threads[i], &h);\n \t\thit |= (int) (intptr_t) h;\n@@ -309,6 +310,8 @@ static int wait_all(void)\n \tpthread_cond_destroy(&cond_write);\n \tpthread_cond_destroy(&cond_result);\n \n+\tfree(threads);\n+\n \treturn hit;\n }\n #else /* !NO_PTHREADS */\n@@ -410,7 +413,7 @@ static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1,\n \tname = strbuf_detach(&pathbuf, NULL);\n \n #ifndef NO_PTHREADS\n-\tif (use_threads) {\n+\tif (nr_threads > 0) {\n \t\tgrep_sha1_async(opt, name, sha1);\n \t\treturn 0;\n \t} else\n@@ -472,7 +475,7 @@ static int grep_file(struct grep_opt *opt, const char *filename)\n \tname = strbuf_detach(&buf, NULL);\n \n #ifndef NO_PTHREADS\n-\tif (use_threads) {\n+\tif (nr_threads > 0) {\n \t\tgrep_file_async(opt, name, filename);\n \t\treturn 0;\n \t} else\n@@ -895,6 +898,13 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t\t\tPARSE_OPT_OPTARG, NULL, (intptr_t)default_pager },\n \t\tOPT_BOOLEAN(0, \"ext-grep\", &external_grep_allowed__ignored,\n \t\t\t \"allow calling of grep(1) (ignored by this build)\"),\n+#ifdef NO_PTHREADS\n+\t\tOPT_INTEGER(0, \"threads\", &nr_threads,\n+\t\t\t\"handle files in parallel (ignored by this build)\"),\n+#else\n+\t\tOPT_INTEGER(0, \"threads\", &nr_threads,\n+\t\t\t\"handle files in parallel\"),\n+#endif\n \t\t{ OPTION_CALLBACK, 0, \"help-all\", &options, NULL, \"show usage\",\n \t\t PARSE_OPT_HIDDEN | PARSE_OPT_NOARG, help_callback },\n \t\tOPT_END()\n@@ -995,7 +1005,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t\topt.output_priv = &path_list;\n \t\topt.output = append_path;\n \t\tstring_list_append(&path_list, show_in_pager);\n-\t\tuse_threads = 0;\n+\t\tnr_threads = 0;\n \t}\n \n \tif (!opt.pattern_list)\n@@ -1003,28 +1013,6 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \tif (!opt.fixed && opt.ignore_case)\n \t\topt.regflags |= REG_ICASE;\n \n-#ifndef NO_PTHREADS\n-\tif (online_cpus() == 1)\n-\t\tuse_threads = 0;\n-#else\n-\tuse_threads = 0;\n-#endif\n-\n-\topt.use_threads = use_threads;\n-\n-#ifndef NO_PTHREADS\n-\tif (use_threads) {\n-\t\tif (opt.pre_context || opt.post_context || opt.file_break ||\n-\t\t opt.funcbody)\n-\t\t\tskip_first_line = 1;\n-\t\tstart_threads(&opt);\n-\t}\n-#else\n-\tuse_threads = 0;\n-#endif\n-\n-\tcompile_grep_patterns(&opt);\n-\n \t/* Check revs and then paths */\n \tfor (i = 0; i < argc; i++) {\n \t\tconst char *arg = argv[i];\n@@ -1056,6 +1044,23 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \tpathspec.max_depth = opt.max_depth;\n \tpathspec.recursive = 1;\n \n+#ifdef NO_PTHREADS\n+\tnr_threads = 0;\n+#else\n+\tif (nr_threads == -1)\n+\t\tnr_threads = (online_cpus() > 1) ? THREADS : 0;\n+\n+\tif (nr_threads > 0) {\n+\t\topt.use_threads = 1;\n+\t\tif (opt.pre_context || opt.post_context || opt.file_break ||\n+\t\t opt.funcbody)\n+\t\t\tskip_first_line = 1;\n+\t\tstart_threads(&opt);\n+\t}\n+#endif\n+\n+\tcompile_grep_patterns(&opt);\n+\n \tif (show_in_pager && (cached || list.nr))\n \t\tdie(_(\"--open-files-in-pager only works on the worktree\"));\n \n@@ -1100,7 +1105,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t\thit = grep_objects(&opt, &pathspec, &list);\n \t}\n \n-\tif (use_threads)\n+\tif (nr_threads > 0)\n \t\thit |= wait_all();\n \tif (hit && show_in_pager)\n \t\trun_pager(&opt, prefix);\n-- \n1.7.8\n"},{"id":"180428","messageId":"4EDE9ED1.8010502@lsrfire.ath.cx","threadId":"29068","inReplyTo":"4EDE9BBA.2010409@lsrfire.ath.cx","subject":"[PATCH 4/2] grep: turn off threading for non-worktree","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-06T23:01:37Z","receivedAt":"2011-12-06T23:01:37Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Reading of git objects needs to be protected by an exclusive lock\nand cannot be parallelized. Searching the read buffers can be done\nin parallel, but for simple expressions threading is a net loss due\nto its overhead, as measured by Thomas. Turn it off unless we're\nsearching in the worktree.\n\nOnce the object store can be read safely by multiple threads in\nparallel this patch should be reverted.\n\nSigned-off-by: Rene Scharfe \n---\nGoes on top of my earlier patch. Could use a better commit message\nwith your (cleaned up) performance numbers.\n\n Documentation/git-grep.txt | 5 +++--\n builtin/grep.c | 2 +-\n 2 files changed, 4 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/git-grep.txt b/Documentation/git-grep.txt\nindex 47ac188..e981a9b 100644\n--- a/Documentation/git-grep.txt\n+++ b/Documentation/git-grep.txt\n@@ -228,8 +228,9 @@ OPTIONS\n \tthere is a match and with non-zero status when there isn't.\n \n --threads ::\n-\tRun search threads in parallel. Default is 8. This option\n-\tis ignored if git was built without support for POSIX threads.\n+\tRun search threads in parallel. Default is 8 when searching\n+\tthe worktree and 0 otherwise. This option is ignored if git was\n+\tbuilt without support for POSIX threads.\n \n ...::\n \tInstead of searching tracked files in the working tree, search\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 0bda900..f698642 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -1048,7 +1048,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \tnr_threads = 0;\n #else\n \tif (nr_threads == -1)\n-\t\tnr_threads = (online_cpus() > 1) ? THREADS : 0;\n+\t\tnr_threads = (online_cpus() > 1 && !list.nr) ? THREADS : 0;\n \n \tif (nr_threads > 0) {\n \t\topt.use_threads = 1;\n-- \n1.7.8\n"},{"id":"180445","messageId":"20111207042431.GA10765@sigill.intra.peff.net","threadId":"29068","inReplyTo":"4EDE9BBA.2010409@lsrfire.ath.cx","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-07T04:24:31Z","receivedAt":"2011-12-07T04:24:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 06, 2011 at 11:48:26PM +0100, René Scharfe wrote:\n\n> #ifndef NO_PTHREADS\n> -\tif (use_threads) {\n> +\tif (nr_threads > 0) {\n> \t\tgrep_sha1_async(opt, name, sha1);\n> \t\treturn 0;\n> \t} else\n\nShould this be \"if (nr_threads > 1)\"?\n\nAs a user, I would do:\n\n git grep --threads=1 ...\n\nif I wanted a single-threaded process. Instead, we actually spawn a\nsub-thread and do all of the locking, which has a measurable cost:\n\n $ time git grep --threads=0 SIMPLE HEAD >/dev/null\n real 0m2.994s\n user 0m2.932s\n sys 0m0.060s\n\n $ time git grep --threads=1 SIMPLE HEAD >/dev/null\n real 0m3.407s\n user 0m3.392s\n sys 0m0.140s\n\nShould --threads=1 be equivalent to --threads=0?\n\n-Peff\n"},{"id":"180446","messageId":"20111207044242.GB10765@sigill.intra.peff.net","threadId":"29068","inReplyTo":"4EDE9ED1.8010502@lsrfire.ath.cx","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-07T04:42:42Z","receivedAt":"2011-12-07T04:42:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 07, 2011 at 12:01:37AM +0100, René Scharfe wrote:\n\n> Reading of git objects needs to be protected by an exclusive lock\n> and cannot be parallelized. Searching the read buffers can be done\n> in parallel, but for simple expressions threading is a net loss due\n> to its overhead, as measured by Thomas. Turn it off unless we're\n> searching in the worktree.\n\nBased on my earlier numbers, I was going to complain that we should\nalso be checking the \"simple expressions\" assumption here, as time spent\nin the actual regex might be important.\n\nHowever, after trying to repeat my experiment, I think the numbers I\nposted earlier were misleading. For example, using my \"more complex\"\nregex of 'a.*b':\n\n $ time git grep --threads=8 'a.*b' HEAD >/dev/null\n real 0m8.655s\n user 0m23.817s\n sys 0m0.480s\n\nLook at that sweet, sweet parallelism. It's a quad-core with\nhyperthreading, so we're not getting the 8x speedup we might hope for\n(presumably due to lock contention on extracting blobs), but hey, 3x\nisn't bad. Except, wait:\n\n $ time git grep --threads=0 'a.*b' HEAD >/dev/null\n real 0m7.651s\n user 0m7.600s\n sys 0m0.048s\n\nWe can get 1x on a single core, but the total time is lower! This\nprocessor is an i7 with \"turbo boost\", which means it clocks higher in\nsingle-core mode than when multiple cores are active. So the numbers I\nposted earlier were misleading. Yes, we got parallelism, but at the cost\nof knocking the clock speed down for a net loss.\n\nThe sweet spot for me seems to be:\n\n $ time git grep --threads=2 'a.*b' HEAD >/dev/null\n real 0m6.303s\n user 0m11.129s\n sys 0m0.220s\n\nI'd be curious to see results from somebody with a quad-core (or more)\nwithout turbo boost; I suspect that threading may have more benefit\nthere, even though we have some lock contention for blobs.\n\n> --- a/builtin/grep.c\n> +++ b/builtin/grep.c\n> @@ -1048,7 +1048,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n> \tnr_threads = 0;\n> #else\n> \tif (nr_threads == -1)\n> -\t\tnr_threads = (online_cpus() > 1) ? THREADS : 0;\n> +\t\tnr_threads = (online_cpus() > 1 && !list.nr) ? THREADS : 0;\n> \n> \tif (nr_threads > 0) {\n> \t\topt.use_threads = 1;\n\nThis doesn't kick in for \"--cached\", which has the same performance\ncharacteristics as grepping a tree. I think you want to add \"&& !cached\" to\nthe conditional.\n\n-Peff\n"},{"id":"180465","messageId":"201112070911.08079.trast@student.ethz.ch","threadId":"29068","inReplyTo":"4EDE9BBA.2010409@lsrfire.ath.cx","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-07T08:11:07Z","receivedAt":"2011-12-07T08:11:07Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"René Scharfe wrote:\n> Am 02.12.2011 17:15, schrieb René Scharfe:\n> > How about adding a parameter to control the number of threads \n> > (--threads?) instead that defaults to eight (or five) for the worktree \n> > and one for the rest? That would also make benchmarking easier.\n> \n> Like this:\n> \n> -- >8 --\n> Subject: grep: add parameter --threads\n> \n> Allow the number of threads to be specified by the user. This makes\n> benchmarking the performance impact of different numbers of threads\n> much easier.\n\nSounds good, though in the end we would also want to have a config\nvariable for the poor OS X users who have to tune their threads\n*down*... :-)\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"180466","messageId":"201112070912.54766.trast@student.ethz.ch","threadId":"29068","inReplyTo":"4EDE9ED1.8010502@lsrfire.ath.cx","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-07T08:12:54Z","receivedAt":"2011-12-07T08:12:54Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"René Scharfe wrote:\n> diff --git a/Documentation/git-grep.txt b/Documentation/git-grep.txt\n> index 47ac188..e981a9b 100644\n> --- a/Documentation/git-grep.txt\n> +++ b/Documentation/git-grep.txt\n> @@ -228,8 +228,9 @@ OPTIONS\n> \tthere is a match and with non-zero status when there isn't.\n> \n> --threads ::\n> +\tRun search threads in parallel. Default is 8 when searching\n> +\tthe worktree and 0 otherwise. This option is ignored if git was\n> +\tbuilt without support for POSIX threads.\n[...]\n> -\t\tnr_threads = (online_cpus() > 1) ? THREADS : 0;\n> +\t\tnr_threads = (online_cpus() > 1 && !list.nr) ? THREADS : 0;\n\nIt would be more consistent to stick to the pack.threads convention\nwhere 0 means \"all of my cores\", so to disable threading the user\nwould set the number of threads to 1. Or were you trying to measure\nthe contention between the worker thread and the add_work() thread?\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"180494","messageId":"4EDF99BA.3040006@lsrfire.ath.cx","threadId":"29068","inReplyTo":"20111207042431.GA10765@sigill.intra.peff.net","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-07T16:52:10Z","receivedAt":"2011-12-07T16:52:10Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.12.2011 05:24, schrieb Jeff King:\n> On Tue, Dec 06, 2011 at 11:48:26PM +0100, René Scharfe wrote:\n> \n>> #ifndef NO_PTHREADS\n>> -\tif (use_threads) {\n>> +\tif (nr_threads > 0) {\n>> \t\tgrep_sha1_async(opt, name, sha1);\n>> \t\treturn 0;\n>> \t} else\n> \n> Should this be \"if (nr_threads > 1)\"?\n> \n> As a user, I would do:\n> \n> git grep --threads=1 ...\n> \n> if I wanted a single-threaded process. Instead, we actually spawn a\n> sub-thread and do all of the locking, which has a measurable cost:\n\nYes, the difference is measurable, and that's exactly how I like it to\nbe. :) A user can turn off threading with --threads=0 or (more\nintuitively) --no-threads. And we can quantify the overhead.\n\n> $ time git grep --threads=0 SIMPLE HEAD >/dev/null\n> real 0m2.994s\n> user 0m2.932s\n> sys 0m0.060s\n> \n> $ time git grep --threads=1 SIMPLE HEAD >/dev/null\n> real 0m3.407s\n> user 0m3.392s\n> sys 0m0.140s\n> \n> Should --threads=1 be equivalent to --threads=0?\n\nWe can do that if there's another way to calculate this difference, or\nif it is not useful to know. I find your results interesting at least,\nthough. :)\n\nRené\n"},{"id":"180496","messageId":"4EDF9A3B.607@lsrfire.ath.cx","threadId":"29068","inReplyTo":"201112070911.08079.trast@student.ethz.ch","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-07T16:54:19Z","receivedAt":"2011-12-07T16:54:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.12.2011 09:11, schrieb Thomas Rast:\n> René Scharfe wrote:\n>> Am 02.12.2011 17:15, schrieb René Scharfe:\n>>> How about adding a parameter to control the number of threads \n>>> (--threads?) instead that defaults to eight (or five) for the worktree \n>>> and one for the rest? That would also make benchmarking easier.\n>>\n>> Like this:\n>>\n>> -- >8 --\n>> Subject: grep: add parameter --threads\n>>\n>> Allow the number of threads to be specified by the user. This makes\n>> benchmarking the performance impact of different numbers of threads\n>> much easier.\n> \n> Sounds good, though in the end we would also want to have a config\n> variable for the poor OS X users who have to tune their threads\n> *down*... :-)\n\nWe could set different defaults for different platforms..\n\nRené\n"},{"id":"180497","messageId":"4EDF9BA0.2080204@lsrfire.ath.cx","threadId":"29068","inReplyTo":"201112070912.54766.trast@student.ethz.ch","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-07T17:00:16Z","receivedAt":"2011-12-07T17:00:16Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.12.2011 09:12, schrieb Thomas Rast:\n> René Scharfe wrote:\n>> diff --git a/Documentation/git-grep.txt b/Documentation/git-grep.txt\n>> index 47ac188..e981a9b 100644\n>> --- a/Documentation/git-grep.txt\n>> +++ b/Documentation/git-grep.txt\n>> @@ -228,8 +228,9 @@ OPTIONS\n>> \tthere is a match and with non-zero status when there isn't.\n>> \n>> --threads ::\n>> +\tRun search threads in parallel. Default is 8 when searching\n>> +\tthe worktree and 0 otherwise. This option is ignored if git was\n>> +\tbuilt without support for POSIX threads.\n> [...]\n>> -\t\tnr_threads = (online_cpus() > 1) ? THREADS : 0;\n>> +\t\tnr_threads = (online_cpus() > 1 && !list.nr) ? THREADS : 0;\n> \n> It would be more consistent to stick to the pack.threads convention\n> where 0 means \"all of my cores\", so to disable threading the user\n> would set the number of threads to 1. Or were you trying to measure\n> the contention between the worker thread and the add_work() thread?\n\nYes, indeed, the cost for the threading overhead does interest me. The\ndocumentation should perhaps mention --no-threads explicitly to avoid\nconfusion.\n\nCurrently there is no way to specify \"as many threads as there are\ncores\" here. Previous measurements indicated that it wasn't too useful,\nhowever, because I/O parallelism was beneficial even for machines with\nless than eight cores and more threads didn't pay off.\n\nRené\n"},{"id":"180498","messageId":"4EDF9E53.7090702@lsrfire.ath.cx","threadId":"29068","inReplyTo":"20111207044242.GB10765@sigill.intra.peff.net","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-07T17:11:47Z","receivedAt":"2011-12-07T17:11:47Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.12.2011 05:42, schrieb Jeff King:\n> On Wed, Dec 07, 2011 at 12:01:37AM +0100, René Scharfe wrote:\n> \n>> Reading of git objects needs to be protected by an exclusive lock\n>> and cannot be parallelized. Searching the read buffers can be done\n>> in parallel, but for simple expressions threading is a net loss due\n>> to its overhead, as measured by Thomas. Turn it off unless we're\n>> searching in the worktree.\n> \n> Based on my earlier numbers, I was going to complain that we should\n> also be checking the \"simple expressions\" assumption here, as time spent\n> in the actual regex might be important.\n> \n> However, after trying to repeat my experiment, I think the numbers I\n> posted earlier were misleading. For example, using my \"more complex\"\n> regex of 'a.*b':\n> \n> $ time git grep --threads=8 'a.*b' HEAD >/dev/null\n> real 0m8.655s\n> user 0m23.817s\n> sys 0m0.480s\n> \n> Look at that sweet, sweet parallelism. It's a quad-core with\n> hyperthreading, so we're not getting the 8x speedup we might hope for\n> (presumably due to lock contention on extracting blobs), but hey, 3x\n> isn't bad. Except, wait:\n> \n> $ time git grep --threads=0 'a.*b' HEAD >/dev/null\n> real 0m7.651s\n> user 0m7.600s\n> sys 0m0.048s\n> \n> We can get 1x on a single core, but the total time is lower! This\n> processor is an i7 with \"turbo boost\", which means it clocks higher in\n> single-core mode than when multiple cores are active. So the numbers I\n> posted earlier were misleading. Yes, we got parallelism, but at the cost\n> of knocking the clock speed down for a net loss.\n\nUgh, right, Turbo Boost complicates matters.\n\nI don't understand the multiplied user time in the threaded case,\nthough. Is it caused by busy-waiting? Thomas reported similar numbers\nearlier.\n\n> The sweet spot for me seems to be:\n> \n> $ time git grep --threads=2 'a.*b' HEAD >/dev/null\n> real 0m6.303s\n> user 0m11.129s\n> sys 0m0.220s\n> \n> I'd be curious to see results from somebody with a quad-core (or more)\n> without turbo boost; I suspect that threading may have more benefit\n> there, even though we have some lock contention for blobs.\n\nIt would be nice if we could come up with simple rules to calculate\ndefaults for the number of threads on a given run. Users shouldn't have\nto specify this option normally. And it would be good if these rules\ndidn't require a list of all CPUs known to git. :)\n\n>> --- a/builtin/grep.c\n>> +++ b/builtin/grep.c\n>> @@ -1048,7 +1048,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n>> \tnr_threads = 0;\n>> #else\n>> \tif (nr_threads == -1)\n>> -\t\tnr_threads = (online_cpus() > 1) ? THREADS : 0;\n>> +\t\tnr_threads = (online_cpus() > 1 && !list.nr) ? THREADS : 0;\n>> \n>> \tif (nr_threads > 0) {\n>> \t\topt.use_threads = 1;\n> \n> This doesn't kick in for \"--cached\", which has the same performance\n> characteristics as grepping a tree. I think you want to add \"&& !cached\" to\n> the conditional.\n\nOh, yes.\n\nRené\n"},{"id":"180502","messageId":"20111207181056.GA6124@sigill.intra.peff.net","threadId":"29068","inReplyTo":"4EDF99BA.3040006@lsrfire.ath.cx","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-07T18:10:56Z","receivedAt":"2011-12-07T18:10:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 07, 2011 at 05:52:10PM +0100, René Scharfe wrote:\n\n> > As a user, I would do:\n> > \n> > git grep --threads=1 ...\n> > \n> > if I wanted a single-threaded process. Instead, we actually spawn a\n> > sub-thread and do all of the locking, which has a measurable cost:\n> \n> Yes, the difference is measurable, and that's exactly how I like it to\n> be. :) A user can turn off threading with --threads=0 or (more\n> intuitively) --no-threads. And we can quantify the overhead.\n\nThat seems acceptable to me if --threads is for speed-testing, but a\nhorrible interface if it is meant for end users who just want git to be\nfast.\n\n-Peff\n"},{"id":"180504","messageId":"20111207182843.GB6124@sigill.intra.peff.net","threadId":"29068","inReplyTo":"4EDF9E53.7090702@lsrfire.ath.cx","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-07T18:28:43Z","receivedAt":"2011-12-07T18:28:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 07, 2011 at 06:11:47PM +0100, René Scharfe wrote:\n\n> > $ time git grep --threads=8 'a.*b' HEAD >/dev/null\n> > real 0m8.655s\n> > user 0m23.817s\n> > sys 0m0.480s\n> [...]\n>\n> Ugh, right, Turbo Boost complicates matters.\n> \n> I don't understand the multiplied user time in the threaded case,\n> though. Is it caused by busy-waiting? Thomas reported similar numbers\n> earlier.\n\nI think it's mostly the clock speed. This processor runs at 1.86GHz but\nboosts to 3.2GHz. So we'd expect just the actual work to take close to\ntwice as long. Plus it's a quad-core with hyperthreading, so 8 threads\nis going to mean two threads sharing each core, including cache (i.e.,\nhyperthreading a core does not let you double performance, even though\nit presents itself as an extra core).\n\nAnd then you have context switching and lock overhead. So I can believe\nthat it takes 3x the CPU time to accomplish the task. In an ideal world,\nit would be mitigated by having 8x the threads, but in this case, lock\ncontention brings us down to less than 3x, and it's a slight net loss.\n\n-Peff\n"},{"id":"180522","messageId":"20111207201105.GA22995@fieldses.org","threadId":"29068","inReplyTo":"20111207044242.GB10765@sigill.intra.peff.net","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"J. Bruce Fields","fromEmail":"bfields@fieldses.org","sentAt":"2011-12-07T20:11:05Z","receivedAt":"2011-12-07T20:11:05Z","isPatch":true,"sender":{"key":"bfields@citi.umich.edu","avatar":null},"body":"On Tue, Dec 06, 2011 at 11:42:42PM -0500, Jeff King wrote:\n> On Wed, Dec 07, 2011 at 12:01:37AM +0100, René Scharfe wrote:\n> \n> > Reading of git objects needs to be protected by an exclusive lock\n> > and cannot be parallelized. Searching the read buffers can be done\n> > in parallel, but for simple expressions threading is a net loss due\n> > to its overhead, as measured by Thomas. Turn it off unless we're\n> > searching in the worktree.\n> \n> Based on my earlier numbers, I was going to complain that we should\n> also be checking the \"simple expressions\" assumption here, as time spent\n> in the actual regex might be important.\n> \n> However, after trying to repeat my experiment, I think the numbers I\n> posted earlier were misleading. For example, using my \"more complex\"\n> regex of 'a.*b':\n> \n> $ time git grep --threads=8 'a.*b' HEAD >/dev/null\n> real 0m8.655s\n> user 0m23.817s\n> sys 0m0.480s\n\nDumb question (I missed the beginning of the conversation): what kind of\nstorage are you using, and is the data already cached?\n\nI seem to recall part of the motivation for the multithreading being\nNFS, where the goal isn't so much to keep CPU's busy as it is to keep\nthe network busy.\n\nProbably a bigger problem for something like \"git status\" which I think\nends up doing a series of stat's (which can each require a round trip to\nthe server in the NFS case), as it is a problem for something like\ngit-grep that's also doing reads.\n\nJust a plea for considering the IO cost as well when making these kinds\nof decisions....\n\n(Which maybe you already do, apologies again for just naively dropping\ninto the middle of a thread.)\n\n--b.\n\n> \n> Look at that sweet, sweet parallelism. It's a quad-core with\n> hyperthreading, so we're not getting the 8x speedup we might hope for\n> (presumably due to lock contention on extracting blobs), but hey, 3x\n> isn't bad. Except, wait:\n> \n> $ time git grep --threads=0 'a.*b' HEAD >/dev/null\n> real 0m7.651s\n> user 0m7.600s\n> sys 0m0.048s\n> \n> We can get 1x on a single core, but the total time is lower! This\n> processor is an i7 with \"turbo boost\", which means it clocks higher in\n> single-core mode than when multiple cores are active. So the numbers I\n> posted earlier were misleading. Yes, we got parallelism, but at the cost\n> of knocking the clock speed down for a net loss.\n> \n> The sweet spot for me seems to be:\n> \n> $ time git grep --threads=2 'a.*b' HEAD >/dev/null\n> real 0m6.303s\n> user 0m11.129s\n> sys 0m0.220s\n> \n> I'd be curious to see results from somebody with a quad-core (or more)\n> without turbo boost; I suspect that threading may have more benefit\n> there, even though we have some lock contention for blobs.\n> \n> > --- a/builtin/grep.c\n> > +++ b/builtin/grep.c\n> > @@ -1048,7 +1048,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n> > \tnr_threads = 0;\n> > #else\n> > \tif (nr_threads == -1)\n> > -\t\tnr_threads = (online_cpus() > 1) ? THREADS : 0;\n> > +\t\tnr_threads = (online_cpus() > 1 && !list.nr) ? THREADS : 0;\n> > \n> > \tif (nr_threads > 0) {\n> > \t\topt.use_threads = 1;\n> \n> This doesn't kick in for \"--cached\", which has the same performance\n> characteristics as grepping a tree. I think you want to add \"&& !cached\" to\n> the conditional.\n> \n> -Peff\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"180523","messageId":"20111207204530.GA20907@sigill.intra.peff.net","threadId":"29068","inReplyTo":"20111207201105.GA22995@fieldses.org","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-07T20:45:31Z","receivedAt":"2011-12-07T20:45:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 07, 2011 at 03:11:05PM -0500, J. Bruce Fields wrote:\n\n> > $ time git grep --threads=8 'a.*b' HEAD >/dev/null\n> > real 0m8.655s\n> > user 0m23.817s\n> > sys 0m0.480s\n> \n> Dumb question (I missed the beginning of the conversation): what kind of\n> storage are you using, and is the data already cached?\n\nSorry, I should have been clear: all of those numbers are with a warm\ncache. So this is measuring only CPU.\n\n> I seem to recall part of the motivation for the multithreading being\n> NFS, where the goal isn't so much to keep CPU's busy as it is to keep\n> the network busy.\n> \n> Probably a bigger problem for something like \"git status\" which I think\n> ends up doing a series of stat's (which can each require a round trip to\n> the server in the NFS case), as it is a problem for something like\n> git-grep that's also doing reads.\n> \n> Just a plea for considering the IO cost as well when making these kinds\n> of decisions....\n\nThis system has a decent-quality SSD, so the I/O timings are perhaps\nnot as interesting as they might otherwise be. But here are cold cache\nnumbers (each run after 'echo 3 >/proc/sys/vm/drop_caches'):\n\n HEAD, --threads=0: 4.956s\n HEAD, --threads=8: 9.917s\n working tree, --threads=0: 17.444s\n working tree, --threads=8: 6.462s\n\nSo when pulling from the object db, threads are still a huge loss\n(because the data is compressed, the SSD is fast, and we spend a lot of\nCPU time inflating; so it ends up close to the warm cache results). But\nfor the working tree, the I/O parallelism is a huge win.\n\nSo at least on my system, cold cache vs. warm cache leads to the same\nconclusion. \"git grep --threads=8 ... HEAD\" might still be a win on slow\ndisks or NFS, though.\n\n-Peff\n"},{"id":"180796","messageId":"20111210131305.GA13344@arf.padd.com","threadId":"29068","inReplyTo":"4EDF9BA0.2080204@lsrfire.ath.cx","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"Pete Wyckoff","fromEmail":"pw@padd.com","sentAt":"2011-12-10T13:13:05Z","receivedAt":"2011-12-10T13:13:05Z","isPatch":true,"sender":{"key":"pw@padd.com","avatar":null},"body":"rene.scharfe@lsrfire.ath.cx wrote on Wed, 07 Dec 2011 18:00 +0100:\n> Am 07.12.2011 09:12, schrieb Thomas Rast:\n> > René Scharfe wrote:\n> >> diff --git a/Documentation/git-grep.txt b/Documentation/git-grep.txt\n> >> index 47ac188..e981a9b 100644\n> >> --- a/Documentation/git-grep.txt\n> >> +++ b/Documentation/git-grep.txt\n> >> @@ -228,8 +228,9 @@ OPTIONS\n> >> \tthere is a match and with non-zero status when there isn't.\n> >> \n> >> --threads ::\n> >> +\tRun search threads in parallel. Default is 8 when searching\n> >> +\tthe worktree and 0 otherwise. This option is ignored if git was\n> >> +\tbuilt without support for POSIX threads.\n> > [...]\n> >> -\t\tnr_threads = (online_cpus() > 1) ? THREADS : 0;\n> >> +\t\tnr_threads = (online_cpus() > 1 && !list.nr) ? THREADS : 0;\n> > \n> > It would be more consistent to stick to the pack.threads convention\n> > where 0 means \"all of my cores\", so to disable threading the user\n> > would set the number of threads to 1. Or were you trying to measure\n> > the contention between the worker thread and the add_work() thread?\n> \n> Yes, indeed, the cost for the threading overhead does interest me. The\n> documentation should perhaps mention --no-threads explicitly to avoid\n> confusion.\n> \n> Currently there is no way to specify \"as many threads as there are\n> cores\" here. Previous measurements indicated that it wasn't too useful,\n> however, because I/O parallelism was beneficial even for machines with\n> less than eight cores and more threads didn't pay off.\n\nRight. Even for single CPU machines this is true, so the\nnr_threads calculation above should still use all 8 THREADS\nregardless of the number of online_cpus().\n\n\t\t-- Pete\n"},{"id":"180986","messageId":"4EE68215.2060609@lsrfire.ath.cx","threadId":"29068","inReplyTo":"20111210131305.GA13344@arf.padd.com","subject":"Re: [PATCH 4/2] grep: turn off threading for non-worktree","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-12T22:37:09Z","receivedAt":"2011-12-12T22:37:09Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 10.12.2011 14:13, schrieb Pete Wyckoff:\n> rene.scharfe@lsrfire.ath.cx wrote on Wed, 07 Dec 2011 18:00 +0100:\n>> Am 07.12.2011 09:12, schrieb Thomas Rast:\n>>> René Scharfe wrote:\n>>>> diff --git a/Documentation/git-grep.txt b/Documentation/git-grep.txt\n>>>> index 47ac188..e981a9b 100644\n>>>> --- a/Documentation/git-grep.txt\n>>>> +++ b/Documentation/git-grep.txt\n>>>> @@ -228,8 +228,9 @@ OPTIONS\n>>>> \tthere is a match and with non-zero status when there isn't.\n>>>>\n>>>> --threads::\n>>>> +\tRun search threads in parallel. Default is 8 when searching\n>>>> +\tthe worktree and 0 otherwise. This option is ignored if git was\n>>>> +\tbuilt without support for POSIX threads.\n>>> [...]\n>>>> -\t\tnr_threads = (online_cpus()> 1) ? THREADS : 0;\n>>>> +\t\tnr_threads = (online_cpus()> 1&& !list.nr) ? THREADS : 0;\n>>>\n>>> It would be more consistent to stick to the pack.threads convention\n>>> where 0 means \"all of my cores\", so to disable threading the user\n>>> would set the number of threads to 1. Or were you trying to measure\n>>> the contention between the worker thread and the add_work() thread?\n>>\n>> Yes, indeed, the cost for the threading overhead does interest me. The\n>> documentation should perhaps mention --no-threads explicitly to avoid\n>> confusion.\n>>\n>> Currently there is no way to specify \"as many threads as there are\n>> cores\" here. Previous measurements indicated that it wasn't too useful,\n>> however, because I/O parallelism was beneficial even for machines with\n>> less than eight cores and more threads didn't pay off.\n>\n> Right. Even for single CPU machines this is true, so the\n> nr_threads calculation above should still use all 8 THREADS\n> regardless of the number of online_cpus().\n\nThat makes sense. However, in a quick test with a simple regex against \na cache-warm Linux repo threading increased the runtime of git grep by \n30% on a single-core virtual machine. Let's keep that check until we \nunderstand this better..\n\nRené\n"},{"id":"181653","messageId":"CACBZZX6hboo4wu3fOs+CHnxsdmedxw72GFMVttQzmHzpcZbqoQ@mail.gmail.com","threadId":"29068","inReplyTo":"5328add8b32f83b4cdbd2e66283f77c125ec127a.1322830368.git.trast@student.ethz.ch","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-12-23T22:37:55Z","receivedAt":"2011-12-23T22:37:55Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Fri, Dec 2, 2011 at 14:07, Thomas Rast wrote:\n\n> I conjecture that this is caused by contention on\n> read_sha1_mutex. [...] So disable threading entirely when not\n> scanning the worktree\n\nWhy does git-grep even need to keep a mutex to call read_sha1_file()?\nIt's inherently a read-only operation isn't it? If the lock is needed\nbecause data is being shared between threads in sha1_file.c shouldn't\nwe tackle that instead of completely disabling threading?\n"},{"id":"181654","messageId":"87mxaihpiq.fsf@thomas.inf.ethz.ch","threadId":"29068","inReplyTo":"CACBZZX6hboo4wu3fOs+CHnxsdmedxw72GFMVttQzmHzpcZbqoQ@mail.gmail.com","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-12-23T22:49:49Z","receivedAt":"2011-12-23T22:49:49Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Ævar Arnfjörð Bjarmason writes:\n\n> On Fri, Dec 2, 2011 at 14:07, Thomas Rast wrote:\n>\n>> I conjecture that this is caused by contention on\n>> read_sha1_mutex. [...] So disable threading entirely when not\n>> scanning the worktree\n>\n> Why does git-grep even need to keep a mutex to call read_sha1_file()?\n> It's inherently a read-only operation isn't it? If the lock is needed\n> because data is being shared between threads in sha1_file.c shouldn't\n> we tackle that instead of completely disabling threading?\n\nThe problem is that all sorts of data is shared. See\n\n http://thread.gmane.org/gmane.comp.version-control.git/186618\n\nBut I need to go through it again, there are some races and double locks\nin the posted version.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"181657","messageId":"CACBZZX67WhcdhXdqOm8gZHW7C3YMbV2KzeytwjHwsnF=8-M_+w@mail.gmail.com","threadId":"29068","inReplyTo":"87mxaihpiq.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-12-24T01:39:11Z","receivedAt":"2011-12-24T01:39:11Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"2011/12/23 Thomas Rast :\n> Ævar Arnfjörð Bjarmason writes:\n>\n>> On Fri, Dec 2, 2011 at 14:07, Thomas Rast wrote:\n>>\n>>> I conjecture that this is caused by contention on\n>>> read_sha1_mutex. [...] So disable threading entirely when not\n>>> scanning the worktree\n>>\n>> Why does git-grep even need to keep a mutex to call read_sha1_file()?\n>> It's inherently a read-only operation isn't it? If the lock is needed\n>> because data is being shared between threads in sha1_file.c shouldn't\n>> we tackle that instead of completely disabling threading?\n>\n> The problem is that all sorts of data is shared.  See\n>\n>  http://thread.gmane.org/gmane.comp.version-control.git/186618\n>\n> But I need to go through it again, there are some races and double locks\n> in the posted version.\n\nI mentioned this on IRC, but I thought I'd bring it up here too.\n\nIs the expensive part of git-grep all the setup work, or the actual\ntraversal and searching? I'm guessing it's the latter.\n\nIn that case an easy way to do git-grep in parallel would be to simply\nspawn multiple sub-processes, e.g. if we had 1000 files and 4 cores:\n\n 1. Split the 1000 into 4 parts 250 each.\n 2. Spawn 4 processes as: git grep -- <250 files>\n 3. Aggregate all of the results in the parent process\n"},{"id":"181663","messageId":"20111224070715.GA32267@sigill.intra.peff.net","threadId":"29068","inReplyTo":"CACBZZX67WhcdhXdqOm8gZHW7C3YMbV2KzeytwjHwsnF=8-M_+w@mail.gmail.com","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-24T07:07:15Z","receivedAt":"2011-12-24T07:07:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 24, 2011 at 02:39:11AM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> Is the expensive part of git-grep all the setup work, or the actual\n> traversal and searching? I'm guessing it's the latter.\n> \n> In that case an easy way to do git-grep in parallel would be to simply\n> spawn multiple sub-processes, e.g. if we had 1000 files and 4 cores:\n> \n> 1. Split the 1000 into 4 parts 250 each.\n> 2. Spawn 4 processes as: git grep -- <250 files>\n> 3. Aggregate all of the results in the parent process\n\nThat's an interesting idea. The expense of the traversal and searching\ndepends on two things:\n\n - how complex is your regex?\n\n - are you reading from objects (which need zlib inflated) or disk?\n\nBut you should be able to approximate it by compiling with NO_PTHREADS\nand doing (assuming you have GNU xargs):\n\n # grep in working tree\n git ls-files | xargs -P 8 git grep \"$re\" --\n\n # grep tree-ish\n git ls-tree -r --name-only $tree | xargs -P 8 git grep \"$re\" $tree --\n\nI tried to get some timings for this, but ran across some quite\nsurprising results. Here's a simple grep of the linux-2.6 working tree,\nusing a single-threaded grep:\n\n $ time git grep SIMPLE >/dev/null\n real 0m0.439s\n user 0m0.272s\n sys 0m0.160s\n\nand then the same thing, via xargs, without even turning on\nparallelization. This should give us a measurement of the overhead for\ngoing through xargs at all. We'd expect it to be slower, but not too\nmuch so:\n\n $ time git ls-files | xargs git grep SIMPLE -- >/dev/null\n real 0m11.989s\n user 0m11.769s\n sys 0m0.268s\n\nTwenty-five times slower! Running 'perf' reports the culprit as pathspec\nmatching:\n\n + 63.23% git git [.] match_pathspec_depth\n + 28.60% git libc-2.13.so [.] __strncmp_sse42\n + 2.22% git git [.] strncmp@plt\n + 1.67% git git [.] kwsexec\n\nwhere the strncmps are called as part of match_pathspec_depth. So over\n90% of the CPU time is spent on matching the pathspecs, compared to less\nthan 2% actually grepping.\n\nWhich really makes me wonder if our pathspec matching could stand to be\nfaster. True, giving a bunch of single files is the least efficient way\nto use pathspecs, but that's pretty amazingly slow.\n\nThe case where we would most expect the setup cost to be drowned out is\nusing a more complex regex, grepping tree objects. There we have a\nbaseline of:\n\n $ time git grep 'a.*c' HEAD >/dev/null\n real 0m5.684s\n user 0m5.472s\n sys 0m0.196s\n\n $ time git ls-tree --name-only -r HEAD |\n xargs git grep 'a.*c' HEAD -- >/dev/null\n real 0m10.906s\n user 0m10.725s\n sys 0m0.240s\n\nHere, we still almost double our time. It looks like we don't use the\nsame pathspec matching code in this case. But we do waste a lot of extra\ntime zlib-inflating the trees in \"ls-tree\", only to do it separately in\n\"grep\".\n\nDoing it in parallel yields:\n\n $ time git ls-tree --name-only -r HEAD |\n xargs -n 4000 -P 8 git grep 'a.*c' HEAD -- >/dev/null\n real 0m3.573s\n user 0m21.885s\n sys 0m0.400s\n\nSo that does at least yield a real speedup, albeit only by about half,\ndespite using over six times as much CPU (though my numbers are skewed\nsomewhat, as this is a quad i7 with hyperthreading and turbo boost).\n\n-Peff\n"},{"id":"181664","messageId":"CACsJy8C1o_Ryf0QDJXz8xEqFYxprWx01AeNT4CC=3DwbAT1JFg@mail.gmail.com","threadId":"29068","inReplyTo":"20111224070715.GA32267@sigill.intra.peff.net","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-24T10:49:42Z","receivedAt":"2011-12-24T10:49:42Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Dec 24, 2011 at 2:07 PM, Jeff King wrote:\n> I tried to get some timings for this, but ran across some quite\n> surprising results. Here's a simple grep of the linux-2.6 working tree,\n> using a single-threaded grep:\n>\n>  $ time git grep SIMPLE >/dev/null\n>  real    0m0.439s\n>  user    0m0.272s\n>  sys     0m0.160s\n>\n> and then the same thing, via xargs, without even turning on\n> parallelization. This should give us a measurement of the overhead for\n> going through xargs at all. We'd expect it to be slower, but not too\n> much so:\n>\n>  $ time git ls-files | xargs git grep SIMPLE -- >/dev/null\n>  real    0m11.989s\n>  user    0m11.769s\n>  sys     0m0.268s\n>\n> Twenty-five times slower! Running 'perf' reports the culprit as pathspec\n> matching:\n>\n>  +  63.23%    git  git                 [.] match_pathspec_depth\n>  +  28.60%    git  libc-2.13.so        [.] __strncmp_sse42\n>  +   2.22%    git  git                 [.] strncmp@plt\n>  +   1.67%    git  git                 [.] kwsexec\n>\n> where the strncmps are called as part of match_pathspec_depth. So over\n> 90% of the CPU time is spent on matching the pathspecs, compared to less\n> than 2% actually grepping.\n>\n> Which really makes me wonder if our pathspec matching could stand to be\n> faster. True, giving a bunch of single files is the least efficient way\n> to use pathspecs, but that's pretty amazingly slow.\n\nWe could eliminate get_pathspec_depth() in grep_directory() when\nread_directory() learns to filter path properly using (and at the cost\nof) tree_entry_interesting(). The latter function has more\noptimizaions built in and should be faster than the former. This is a\ngood test case for my read_directory() rewrite. Thanks.\n\nget_pathspec_depth() can still use some optimizations though for\ngrep_cache() case.\n-- \nDuy\n"},{"id":"181665","messageId":"CACsJy8DbfE8r3KsxCnb30-sb3LUAAWapAKJUSJ1zBZme1FoMwg@mail.gmail.com","threadId":"29068","inReplyTo":"20111224070715.GA32267@sigill.intra.peff.net","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-24T10:55:14Z","receivedAt":"2011-12-24T10:55:14Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"(Sorry I replied without reading though the mail)\n\nOn Sat, Dec 24, 2011 at 2:07 PM, Jeff King wrote:\n> The case where we would most expect the setup cost to be drowned out is\n> using a more complex regex, grepping tree objects. There we have a\n> baseline of:\n>\n>  $ time git grep 'a.*c' HEAD >/dev/null\n>  real    0m5.684s\n>  user    0m5.472s\n>  sys     0m0.196s\n>\n>  $ time git ls-tree --name-only -r HEAD |\n>      xargs git grep 'a.*c' HEAD -- >/dev/null\n>  real    0m10.906s\n>  user    0m10.725s\n>  sys     0m0.240s\n>\n> Here, we still almost double our time. It looks like we don't use the\n> same pathspec matching code in this case. But we do waste a lot of extra\n> time zlib-inflating the trees in \"ls-tree\", only to do it separately in\n> \"grep\".\n\nI assume this is gree_tree(), we have another form of pathspec\nmatching here: tree_entry_interesting() and it's still a bunch of\nstrcmp inside. Does strcmp show up in perf report?\n-- \nDuy\n"},{"id":"181666","messageId":"20111224133847.GA6669@sigill.intra.peff.net","threadId":"29068","inReplyTo":"CACsJy8DbfE8r3KsxCnb30-sb3LUAAWapAKJUSJ1zBZme1FoMwg@mail.gmail.com","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-24T13:38:47Z","receivedAt":"2011-12-24T13:38:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 24, 2011 at 05:55:14PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Sat, Dec 24, 2011 at 2:07 PM, Jeff King wrote:\n> > The case where we would most expect the setup cost to be drowned out is\n> > using a more complex regex, grepping tree objects. There we have a\n> > baseline of:\n> >\n> >  $ time git grep 'a.*c' HEAD >/dev/null\n> >  real    0m5.684s\n> >  user    0m5.472s\n> >  sys     0m0.196s\n> >\n> >  $ time git ls-tree --name-only -r HEAD |\n> >      xargs git grep 'a.*c' HEAD -- >/dev/null\n> >  real    0m10.906s\n> >  user    0m10.725s\n> >  sys     0m0.240s\n> >\n> > Here, we still almost double our time. It looks like we don't use the\n> > same pathspec matching code in this case. But we do waste a lot of extra\n> > time zlib-inflating the trees in \"ls-tree\", only to do it separately in\n> > \"grep\".\n> \n> I assume this is gree_tree(), we have another form of pathspec\n> matching here: tree_entry_interesting() and it's still a bunch of\n> strcmp inside. Does strcmp show up in perf report?\n\nYes, but not nearly as high. The top of the report is:\n\n + 32.16% git libc-2.13.so [.] re_search_internal\n + 17.82% git libz.so.1.2.3.4 [.] 0xe986\n + 7.81% git git [.] look_ahead\n + 6.24% git libc-2.13.so [.] __strncmp_sse42\n + 4.08% git git [.] tree_entry_interesting\n + 3.27% git git [.] end_of_line\n + 2.63% git libz.so.1.2.3.4 [.] adler32\n + 1.93% git libz.so.1.2.3.4 [.] inflate\n\nwhere the strncmps are from[1]:\n\n - 6.24% git libc-2.13.so [.] __strncmp_sse42\n - __strncmp_sse42\n + 80.92% grep_tree\n + 19.08% tree_entry_interesting\n\nSo we're spending maybe 10% of our time on pathspecs, but most of it is\ngoing to zlib and the actual regex search.\n\n-Peff\n\n[1] Note that this is with -O2, so some of that is from inlined calls.\n"},{"id":"181683","messageId":"CACsJy8AU+a6bHa4qGX0eYgdnP6+PhP7q0pty+bHLBupwr9LCMw@mail.gmail.com","threadId":"29068","inReplyTo":"20111224070715.GA32267@sigill.intra.peff.net","subject":"Re: [PATCH v2 3/3] grep: disable threading in all but worktree case","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-25T03:32:27Z","receivedAt":"2011-12-25T03:32:27Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Dec 24, 2011 at 2:07 PM, Jeff King wrote:\n> The case where we would most expect the setup cost to be drowned out is\n> using a more complex regex, grepping tree objects. There we have a\n> baseline of:\n>\n>  $ time git grep 'a.*c' HEAD >/dev/null\n>  real    0m5.684s\n>  user    0m5.472s\n>  sys     0m0.196s\n>\n>  $ time git ls-tree --name-only -r HEAD |\n>      xargs git grep 'a.*c' HEAD -- >/dev/null\n>  real    0m10.906s\n>  user    0m10.725s\n>  sys     0m0.240s\n>\n> Here, we still almost double our time. It looks like we don't use the\n> same pathspec matching code in this case. But we do waste a lot of extra\n> time zlib-inflating the trees in \"ls-tree\", only to do it separately in\n> \"grep\".\n\nOr you could pass blob SHA-1 to git grep to avoid reinflating trees\n\n$ time git ls-tree -r HEAD|cut -c 13-52|xargs git grep 'a.*c' >/dev/null\n\nDoing it in parallel does not seem to save time for me though.\n-- \nDuy\n"}]}