{"thread":{"id":"22267","subject":"[PATCH v3] Threaded grep","startedAt":"2010-01-18T10:33:34Z","lastAt":"2010-01-25T22:47:30Z","messageCount":10,"participants":["Fredrik Kuivinen","Johannes Sixt","Linus Torvalds"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"132028","messageId":"20100118103334.GA17361@fredrik-laptop","threadId":"22267","inReplyTo":null,"subject":"[PATCH v3] Threaded grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-01-18T10:33:34Z","receivedAt":"2010-01-18T10:33:34Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Make git grep use threads when it is available.\n\nThe results below are best of five runs in the Linux repository (on a\nbox with two cores).\n\nWith the patch:\n\ngit grep qwerty\n1.58user 0.55system 0:01.16elapsed 183%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+800outputs (0major+5774minor)pagefaults 0swaps\n\nWithout:\n\ngit grep qwerty\n1.59user 0.43system 0:02.02elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+800outputs (0major+3716minor)pagefaults 0swaps\n\n\nAnd with a pattern with quite a few matches:\n\nWith the patch:\n\n$ /usr/bin/time git grep void\n5.61user 0.56system 0:03.44elapsed 179%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+800outputs (0major+5587minor)pagefaults 0swaps\n\nWithout:\n\n$ /usr/bin/time git grep void\n5.36user 0.51system 0:05.87elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+800outputs (0major+3693minor)pagefaults 0swaps\n\nIn either case we gain about 40% by the threading.\n\nSigned-off-by: Fredrik Kuivinen <frekui@gmail.com>\n---\n\nThe patch has been rebased on top of next and I believe that it is now\nready for inclusion. It is time to decide if the added code complexity\nis worth the increased performance.\n\n builtin-grep.c |  325 +++++++++++++++++++++++++++++++++++++++++++++++++++++---\n grep.c         |  104 +++++++++++++++---\n grep.h         |    6 +\n 3 files changed, 400 insertions(+), 35 deletions(-)\n\ndiff --git a/builtin-grep.c b/builtin-grep.c\nindex 24ae1ce..dc07e9e 100644\n--- a/builtin-grep.c\n+++ b/builtin-grep.c\n@@ -15,11 +15,257 @@\n #include \"grep.h\"\n #include \"quote.h\"\n \n+#ifndef NO_PTHREADS\n+#include \"thread-utils.h\"\n+#include <pthread.h>\n+#endif\n+\n static char const * const grep_usage[] = {\n \t\"git grep [options] [-e] <pattern> [<rev>...] [[--] path...]\",\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+\n+static void* load_file(const char *filename, size_t *sz);\n+\n+enum work_type {WORK_BUF, WORK_FILE};\n+\n+/* We use one producer thread and number_of_threads consumer\n+   threads. The producer adds struct work_items to 'todo' and the\n+   consumers pick work items from the same array. */\n+struct work_item\n+{\n+\tenum work_type type;\n+\tchar *name;\n+\n+\t/* if type == WORK_BUF, then 'buf' points to a buffer of size\n+\t   'size' otherwise type == WORK_FILE and 'buf' is a NUL\n+\t   terminated filename. */\n+\tchar *buf;\n+\tsize_t size;\n+\tchar done;\n+\tstruct strbuf out;\n+};\n+\n+/* In the range [todo_done, todo_start) in 'todo' we have work_items\n+   that have been or are processed by a consumer thread. We haven't\n+   written the result for these to stdout yet.\n+\n+   The work_items in [todo_start, todo_end) are waiting to be picked\n+   up by a consumer thread.\n+\n+   The ranges are modulo TODO_SIZE.\n+*/\n+#define TODO_SIZE 128\n+static struct work_item todo[TODO_SIZE];\n+static int todo_start = 0;\n+static int todo_end = 0;\n+static int todo_done = 0;\n+\n+/* Has all work items been added? */\n+static int all_work_added = 0;\n+\n+/* This lock protects all the variables above. */\n+static pthread_mutex_t grep_lock = PTHREAD_MUTEX_INITIALIZER;\n+\n+/* Signalled when a new work_item is added to todo. */\n+static pthread_cond_t cond_add = PTHREAD_COND_INITIALIZER;\n+\n+/* Signalled when the result from one work_item is written to\n+   stdout. */\n+static pthread_cond_t cond_write = PTHREAD_COND_INITIALIZER;\n+\n+/* Signalled when we are finished with everything. */\n+static pthread_cond_t cond_result = PTHREAD_COND_INITIALIZER;\n+\n+static void add_work(enum work_type type, char *name, char *buf, size_t size)\n+{\n+\tpthread_mutex_lock(&grep_lock);\n+\n+\twhile ((todo_end+1) % ARRAY_SIZE(todo) == todo_done) {\n+\t\tpthread_cond_wait(&cond_write, &grep_lock);\n+\t}\n+\n+\ttodo[todo_end].type = type;\n+\ttodo[todo_end].name = name;\n+\ttodo[todo_end].buf = buf;\n+\ttodo[todo_end].size = size;\n+\ttodo[todo_end].done = 0;\n+\tstrbuf_reset(&todo[todo_end].out);\n+\ttodo_end = (todo_end + 1) % ARRAY_SIZE(todo);\n+\n+\tpthread_mutex_unlock(&grep_lock);\n+\tpthread_cond_signal(&cond_add);\n+}\n+\n+static struct work_item* get_work()\n+{\n+\tstruct work_item* ret;\n+\n+\tpthread_mutex_lock(&grep_lock);\n+\twhile (todo_start == todo_end && !all_work_added) {\n+\t\tpthread_cond_wait(&cond_add, &grep_lock);\n+\t}\n+\n+\tif (todo_start == todo_end && all_work_added) {\n+\t\tret = NULL;\n+\t} else {\n+\t\tret = &todo[todo_start];\n+\t\ttodo_start = (todo_start + 1) % ARRAY_SIZE(todo);\n+\t}\n+\tpthread_mutex_unlock(&grep_lock);\n+\treturn ret;\n+}\n+\n+/* This function takes ownership of 'name' and 'buf'. They will be\n+   deallocated with free. */\n+static int grep_buffer_async(struct grep_opt *opt, char *name, char *buf,\n+\t\t\t     size_t size)\n+{\n+\tadd_work(WORK_BUF, name, buf, size);\n+\treturn 0;\n+}\n+\n+static int grep_file_async(struct grep_opt *opt, char *name,\n+\t\t\t   const char *filename)\n+{\n+\tadd_work(WORK_FILE, name, (char*) filename, 0);\n+\treturn 0;\n+}\n+\n+static void work_done(struct work_item *w)\n+{\n+\tint old_done;\n+\n+\tpthread_mutex_lock(&grep_lock);\n+\tw->done = 1;\n+\told_done = todo_done;\n+\tfor(; todo[todo_done].done && todo_done != todo_start;\n+\t    todo_done = (todo_done+1) % ARRAY_SIZE(todo)) {\n+\t\tw = &todo[todo_done];\n+\t\twrite_or_die(1, w->out.buf, w->out.len);\n+\t\tif (w->type == WORK_BUF)\n+\t\t\tfree(w->buf);\n+\n+\t\tfree(w->name);\n+\t}\n+\n+\tif (old_done != todo_done)\n+\t\tpthread_cond_signal(&cond_write);\n+\n+\tif (all_work_added && todo_done == todo_end)\n+\t\tpthread_cond_signal(&cond_result);\n+\n+\tpthread_mutex_unlock(&grep_lock);\n+}\n+\n+static void* run(void *arg)\n+{\n+\tint hit = 0;\n+\tstruct grep_opt *opt = arg;\n+\n+\twhile (1) {\n+\t\tstruct work_item *w = get_work();\n+\t\tif (!w)\n+\t\t\tbreak;\n+\n+\t\topt->output_priv = w;\n+\t\tif (w->type == WORK_BUF) {\n+\t\t\thit |= grep_buffer(opt, w->name, w->buf, w->size);\n+\t\t} else {\n+\t\t\tsize_t sz;\n+\t\t\tvoid* data = load_file(w->buf, &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}\n+\n+\t\twork_done(w);\n+\t}\n+\n+\treturn (void*) (intptr_t) hit;\n+}\n+\n+static void strbuf_out(struct grep_opt *opt, const void *buf, size_t size)\n+{\n+\tstruct work_item *w = opt->output_priv;\n+\tstrbuf_add(&w->out, buf, size);\n+}\n+\n+static void start_threads(struct grep_opt *opt)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < ARRAY_SIZE(todo); i++) {\n+\t\tstrbuf_init(&todo[i].out, 0);\n+\t}\n+\n+\tfor (i = 0; i < ARRAY_SIZE(threads); i++) {\n+\t\tstruct grep_opt *o = grep_opt_dup(opt);\n+\t\to->output = strbuf_out;\n+\t\tcompile_grep_patterns(o);\n+\t\tint err = pthread_create(&threads[i], NULL, run, o);\n+\n+\t\tif (err)\n+\t\t\tdie(\"grep: failed to create thread: %s\", strerror(err));\n+\t}\n+}\n+#endif /* !NO_PTHREADS */\n+\n+#ifndef NO_PTHREADS\n+static int wait_all()\n+{\n+\tint hit = 0;\n+\tint i;\n+\n+\tpthread_mutex_lock(&grep_lock);\n+\tall_work_added = 1;\n+\n+\t/* Wait until all work is done. */\n+\twhile (todo_done != todo_end)\n+\t\tpthread_cond_wait(&cond_result, &grep_lock);\n+\n+\t/* Wake up all the consumer threads so they can see that there\n+\t   is no more work to do. */\n+\tpthread_cond_broadcast(&cond_add);\n+\tpthread_mutex_unlock(&grep_lock);\n+\n+\tfor (i = 0; i < ARRAY_SIZE(threads); i++) {\n+\t\tvoid *h;\n+\t\tpthread_join(threads[i], &h);\n+\t\thit |= (int) (intptr_t) h;\n+\t}\n+\n+\treturn hit;\n+}\n+#else\n+static int wait_all()\n+{\n+\treturn 0;\n+}\n+#endif\n+\n+static int grep_buffer_internal(struct grep_opt *opt, char *name, char *buf,\n+\t\t\t\tsize_t size)\n+{\n+#ifndef NO_PTHREADS\n+\tif (use_threads)\n+\t\treturn grep_buffer_async(opt, name, buf, size);\n+#endif\n+\t{\n+\t\tint hit = grep_buffer(opt, name, buf, size);\n+\t\tfree(name);\n+\t\tfree(buf);\n+\t\treturn hit;\n+\t}\n+}\n+\n static int grep_config(const char *var, const char *value, void *cb)\n {\n \tstruct grep_opt *opt = cb;\n@@ -159,21 +405,21 @@ static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1, const char\n \tif (opt->relative && opt->prefix_length) {\n \t\tquote_path_relative(name + tree_name_len, -1, &pathbuf, opt->prefix);\n \t\tstrbuf_insert(&pathbuf, 0, name, tree_name_len);\n-\t\tname = pathbuf.buf;\n+\t} else {\n+\t\tstrbuf_addstr(&pathbuf, name);\n \t}\n-\thit = grep_buffer(opt, name, data, size);\n-\tstrbuf_release(&pathbuf);\n-\tfree(data);\n+\n+\thit = grep_buffer_internal(opt, strbuf_detach(&pathbuf, NULL),\n+\t\t\t\t   data, size);\n+\n \treturn hit;\n }\n \n-static int grep_file(struct grep_opt *opt, const char *filename)\n+static void* load_file(const char *filename, size_t *sz)\n {\n \tstruct stat st;\n+\tchar* data;\n \tint i;\n-\tchar *data;\n-\tsize_t sz;\n-\tstruct strbuf buf = STRBUF_INIT;\n \n \tif (lstat(filename, &st) < 0) {\n \terr_ret:\n@@ -183,24 +429,47 @@ static int grep_file(struct grep_opt *opt, const char *filename)\n \t}\n \tif (!S_ISREG(st.st_mode))\n \t\treturn 0;\n-\tsz = xsize_t(st.st_size);\n+\t*sz = xsize_t(st.st_size);\n \ti = open(filename, O_RDONLY);\n \tif (i < 0)\n \t\tgoto err_ret;\n-\tdata = xmalloc(sz + 1);\n-\tif (st.st_size != read_in_full(i, data, sz)) {\n+\tdata = xmalloc(*sz + 1);\n+\tdata[*sz] = 0;\n+\tif (st.st_size != read_in_full(i, data, *sz)) {\n \t\terror(\"'%s': short read %s\", filename, strerror(errno));\n \t\tclose(i);\n \t\tfree(data);\n \t\treturn 0;\n \t}\n \tclose(i);\n+\treturn data;\n+}\n+\n+static int grep_file(struct grep_opt *opt, const char *filename)\n+{\n+\tchar *data;\n+\tsize_t sz;\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tchar *name;\n+\n \tif (opt->relative && opt->prefix_length)\n-\t\tfilename = quote_path_relative(filename, -1, &buf, opt->prefix);\n-\ti = grep_buffer(opt, filename, data, sz);\n-\tstrbuf_release(&buf);\n-\tfree(data);\n-\treturn i;\n+\t\tquote_path_relative(filename, -1, &buf, opt->prefix);\n+\telse\n+\t\tstrbuf_addstr(&buf, filename);\n+\tname = strbuf_detach(&buf, NULL);\n+\n+#ifndef NO_PTHREADS\n+\tif (use_threads) {\n+\t\treturn grep_file_async(opt, name, filename);\n+\t} else\n+#endif\n+\t{\n+\t\tdata = load_file(filename, &sz);\n+\t\tif (!data)\n+\t\t\treturn 0;\n+\n+\t\treturn grep_buffer_internal(opt, name, data, sz);\n+\t}\n }\n \n static int grep_cache(struct grep_opt *opt, const char **paths, int cached)\n@@ -546,6 +815,20 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t\topt.regflags |= REG_ICASE;\n \tif ((opt.regflags != REG_NEWLINE) && opt.fixed)\n \t\tdie(\"cannot mix --fixed-strings and regexp\");\n+\n+#ifndef NO_PTHREADS\n+\tif (!grep_threads_ok(&opt))\n+\t\tuse_threads = 0;\n+\n+\tif (online_cpus() == 1)\n+\t\tuse_threads = 0;\n+\n+\tif (use_threads)\n+\t\tstart_threads(&opt);\n+#else\n+\tuse_threads = 0;\n+#endif\n+\n \tcompile_grep_patterns(&opt);\n \n \t/* Check revs and then paths */\n@@ -583,9 +866,14 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t}\n \n \tif (!list.nr) {\n+\t\tint hit;\n \t\tif (!cached)\n \t\t\tsetup_work_tree();\n-\t\treturn !grep_cache(&opt, paths, cached);\n+\n+\t\thit = grep_cache(&opt, paths, cached);\n+\t\tif (use_threads)\n+\t\t\thit |= wait_all();\n+\t\treturn !hit;\n \t}\n \n \tif (cached)\n@@ -597,6 +885,9 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t\tif (grep_object(&opt, paths, real_obj, list.objects[i].name))\n \t\t\thit = 1;\n \t}\n+\n+\tif (use_threads)\n+\t\thit |= wait_all();\n \tfree_grep_patterns(&opt);\n \treturn !hit;\n }\ndiff --git a/grep.c b/grep.c\nindex 8e1f7de..05aab15 100644\n--- a/grep.c\n+++ b/grep.c\n@@ -29,6 +29,28 @@ void append_grep_pattern(struct grep_opt *opt, const char *pat,\n \tp->next = NULL;\n }\n \n+struct grep_opt* grep_opt_dup(const struct grep_opt *opt)\n+{\n+\tstruct grep_pat *pat;\n+\tstruct grep_opt *ret = xmalloc(sizeof(struct grep_opt));\n+\t*ret = *opt;\n+\n+\tret->pattern_list = NULL;\n+\tret->pattern_tail = &ret->pattern_list;\n+\n+\tfor(pat = opt->pattern_list; pat != NULL; pat = pat->next)\n+\t{\n+\t\tif(pat->token == GREP_PATTERN_HEAD)\n+\t\t\tappend_header_grep_pattern(ret, pat->field,\n+\t\t\t\t\t\t   pat->pattern);\n+\t\telse\n+\t\t\tappend_grep_pattern(ret, pat->pattern, pat->origin,\n+\t\t\t\t\t    pat->no, pat->token);\n+\t}\n+\n+\treturn ret;\n+}\n+\n static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)\n {\n \tint err;\n@@ -253,7 +275,8 @@ static int word_char(char ch)\n \n static void show_name(struct grep_opt *opt, const char *name)\n {\n-\tprintf(\"%s%c\", name, opt->null_following_name ? '\\0' : '\\n');\n+\topt->output(opt, name, strlen(name));\n+\topt->output(opt, opt->null_following_name ? \"\\0\" : \"\\n\", 1);\n }\n \n \n@@ -490,24 +513,32 @@ static void show_line(struct grep_opt *opt, char *bol, char *eol,\n \t\t      const char *name, unsigned lno, char sign)\n {\n \tint rest = eol - bol;\n+\tchar sign_str[1];\n \n+\tsign_str[0] = sign;\n \tif (opt->pre_context || opt->post_context) {\n \t\tif (opt->last_shown == 0) {\n \t\t\tif (opt->show_hunk_mark)\n-\t\t\t\tfputs(\"--\\n\", stdout);\n+\t\t\t\topt->output(opt, \"--\\n\", 3);\n \t\t\telse\n \t\t\t\topt->show_hunk_mark = 1;\n \t\t} else if (lno > opt->last_shown + 1)\n-\t\t\tfputs(\"--\\n\", stdout);\n+\t\t\topt->output(opt, \"--\\n\", 3);\n \t}\n \topt->last_shown = lno;\n \n \tif (opt->null_following_name)\n-\t\tsign = '\\0';\n-\tif (opt->pathname)\n-\t\tprintf(\"%s%c\", name, sign);\n-\tif (opt->linenum)\n-\t\tprintf(\"%d%c\", lno, sign);\n+\t\tsign_str[0] = '\\0';\n+\tif (opt->pathname) {\n+\t\topt->output(opt, name, strlen(name));\n+\t\topt->output(opt, sign_str, 1);\n+\t}\n+\tif (opt->linenum) {\n+\t\tchar buf[32];\n+\t\tsnprintf(buf, sizeof(buf), \"%d\", lno);\n+\t\topt->output(opt, buf, strlen(buf));\n+\t\topt->output(opt, sign_str, 1);\n+\t}\n \tif (opt->color) {\n \t\tregmatch_t match;\n \t\tenum grep_context ctx = GREP_CONTEXT_BODY;\n@@ -518,18 +549,22 @@ static void show_line(struct grep_opt *opt, char *bol, char *eol,\n \t\twhile (next_match(opt, bol, eol, ctx, &match, eflags)) {\n \t\t\tif (match.rm_so == match.rm_eo)\n \t\t\t\tbreak;\n-\t\t\tprintf(\"%.*s%s%.*s%s\",\n-\t\t\t       (int)match.rm_so, bol,\n-\t\t\t       opt->color_match,\n-\t\t\t       (int)(match.rm_eo - match.rm_so), bol + match.rm_so,\n-\t\t\t       GIT_COLOR_RESET);\n+\n+\t\t\topt->output(opt, bol, match.rm_so);\n+\t\t\topt->output(opt, opt->color_match,\n+\t\t\t\tstrlen(opt->color_match));\n+\t\t\topt->output(opt, bol + match.rm_so,\n+\t\t\t\t(int)(match.rm_eo - match.rm_so));\n+\t\t\topt->output(opt, GIT_COLOR_RESET,\n+\t\t\t\t    strlen(GIT_COLOR_RESET));\n \t\t\tbol += match.rm_eo;\n \t\t\trest -= match.rm_eo;\n \t\t\teflags = REG_NOTBOL;\n \t\t}\n \t\t*eol = ch;\n \t}\n-\tprintf(\"%.*s\\n\", rest, bol);\n+\topt->output(opt, bol, rest);\n+\topt->output(opt, \"\\n\", 1);\n }\n \n static int match_funcname(struct grep_opt *opt, char *bol, char *eol)\n@@ -667,6 +702,30 @@ 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+\tif (opt->funcname && !opt->unmatch_name_only && !opt->status_only &&\n+\t    !opt->name_only)\n+\t\treturn 0;\n+\n+\t/* If we are showing hunk marks, we should not do it for the\n+\t   first match. The synchronization problem we get for this\n+\t   constraint is not yet solved, so we disable threading in\n+\t   this case. */\n+\tif (opt->pre_context || opt->post_context)\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+}\n+\n static int grep_buffer_1(struct grep_opt *opt, const char *name,\n \t\t\t char *buf, unsigned long size, int collect_hits)\n {\n@@ -682,6 +741,9 @@ static int grep_buffer_1(struct grep_opt *opt, const char *name,\n \n \topt->last_shown = 0;\n \n+\tif (!opt->output)\n+\t\topt->output = std_output;\n+\n \tif (buffer_is_binary(buf, size)) {\n \t\tswitch (opt->binary) {\n \t\tcase GREP_BINARY_DEFAULT:\n@@ -754,7 +816,9 @@ static int grep_buffer_1(struct grep_opt *opt, const char *name,\n \t\t\tif (opt->status_only)\n \t\t\t\treturn 1;\n \t\t\tif (binary_match_only) {\n-\t\t\t\tprintf(\"Binary file %s matches\\n\", name);\n+\t\t\t\topt->output(opt, \"Binary file \", 12);\n+\t\t\t\topt->output(opt, name, strlen(name));\n+\t\t\t\topt->output(opt, \" matches\\n\", 9);\n \t\t\t\treturn 1;\n \t\t\t}\n \t\t\tif (opt->name_only) {\n@@ -810,9 +874,13 @@ static int grep_buffer_1(struct grep_opt *opt, const char *name,\n \t * which feels mostly useless but sometimes useful.  Maybe\n \t * make it another option?  For now suppress them.\n \t */\n-\tif (opt->count && count)\n-\t\tprintf(\"%s%c%u\\n\", name,\n-\t\t       opt->null_following_name ? '\\0' : ':', count);\n+\tif (opt->count && count) {\n+\t\tchar buf[32];\n+\t\topt->output(opt, name, strlen(name));\n+\t\tsnprintf(buf, sizeof(buf), \"%c%u\\n\",\n+\t\t\topt->null_following_name ? '\\0' : ':', count);\n+\t\topt->output(opt, buf, strlen(buf));\n+\t}\n \treturn !!last_hit;\n }\n \ndiff --git a/grep.h b/grep.h\nindex 0c61b00..6517909 100644\n--- a/grep.h\n+++ b/grep.h\n@@ -91,6 +91,9 @@ struct grep_opt {\n \tunsigned last_shown;\n \tint show_hunk_mark;\n \tvoid *priv;\n+\n+\tvoid (*output)(struct grep_opt*, const void* data, size_t size);\n+\tvoid *output_priv;\n };\n \n extern void append_grep_pattern(struct grep_opt *opt, const char *pat, const char *origin, int no, enum grep_pat_token t);\n@@ -99,4 +102,7 @@ extern void compile_grep_patterns(struct grep_opt *opt);\n extern void free_grep_patterns(struct grep_opt *opt);\n extern int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size);\n \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 #endif\n"},{"id":"132029","messageId":"4B5441D7.40503@viscovery.net","threadId":"22267","inReplyTo":"20100118103334.GA17361@fredrik-laptop","subject":"Re: [PATCH v3] Threaded grep","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2010-01-18T11:11:19Z","receivedAt":"2010-01-18T11:11:19Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Fredrik Kuivinen schrieb:\n> The patch has been rebased on top of next and I believe that it is now\n> ready for inclusion. It is time to decide if the added code complexity\n> is worth the increased performance.\n\nI also have to add a few nits to make this play better on Windows.\n\n> +/* This lock protects all the variables above. */\n> +static pthread_mutex_t grep_lock = PTHREAD_MUTEX_INITIALIZER;\n> +\n> +/* Signalled when a new work_item is added to todo. */\n> +static pthread_cond_t cond_add = PTHREAD_COND_INITIALIZER;\n> +\n> +/* Signalled when the result from one work_item is written to\n> +   stdout. */\n> +static pthread_cond_t cond_write = PTHREAD_COND_INITIALIZER;\n> +\n> +/* Signalled when we are finished with everything. */\n> +static pthread_cond_t cond_result = PTHREAD_COND_INITIALIZER;\n\nPlease do not use PTHREAD_MUTEX_INITIALIZER nor PTHREAD_COND_INITIALIZER;\ncall pthread_mutex_init and pthread_cond_init (and the corresponding\n*_destroy!!) from the code.\n\n> +static void add_work(enum work_type type, char *name, char *buf, size_t size)\n> +{\n> +...\n> +\tpthread_mutex_unlock(&grep_lock);\n> +\tpthread_cond_signal(&cond_add);\n\nPlease swap these two lines, so that pthread_cond_signal() is called while\nthe lock is held.\n\n> +\t/* Wake up all the consumer threads so they can see that there\n> +\t   is no more work to do. */\n> +\tpthread_cond_broadcast(&cond_add);\n> +\tpthread_mutex_unlock(&grep_lock);\n\nOuch! We do not have pthread_cond_broadcast() on Windows, yet. This\nshouldn't be a stopper for this patch, though. Perhaps Andrzej (cc:ed) can\nimplement it?\n\n-- Hannes\n"},{"id":"132031","messageId":"4c8ef71001180528h6182ef4l8a617fd038bd7318@mail.gmail.com","threadId":"22267","inReplyTo":"4B5441D7.40503@viscovery.net","subject":"Re: [PATCH v3] Threaded grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-01-18T13:28:26Z","receivedAt":"2010-01-18T13:28:26Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Mon, Jan 18, 2010 at 12:11, Johannes Sixt <j.sixt@viscovery.net> wrote:\n> Fredrik Kuivinen schrieb:\n>> +/* This lock protects all the variables above. */\n>> +static pthread_mutex_t grep_lock = PTHREAD_MUTEX_INITIALIZER;\n>> +\n>> +/* Signalled when a new work_item is added to todo. */\n>> +static pthread_cond_t cond_add = PTHREAD_COND_INITIALIZER;\n>> +\n>> +/* Signalled when the result from one work_item is written to\n>> +   stdout. */\n>> +static pthread_cond_t cond_write = PTHREAD_COND_INITIALIZER;\n>> +\n>> +/* Signalled when we are finished with everything. */\n>> +static pthread_cond_t cond_result = PTHREAD_COND_INITIALIZER;\n>\n> Please do not use PTHREAD_MUTEX_INITIALIZER nor PTHREAD_COND_INITIALIZER;\n> call pthread_mutex_init and pthread_cond_init (and the corresponding\n> *_destroy!!) from the code.\n\nOk. Will fix.\n\n>> +static void add_work(enum work_type type, char *name, char *buf, size_t size)\n>> +{\n>> +...\n>> +     pthread_mutex_unlock(&grep_lock);\n>> +     pthread_cond_signal(&cond_add);\n>\n> Please swap these two lines, so that pthread_cond_signal() is called while\n> the lock is held.\n\nMay I ask why? (just curious)\n\n\nThanks for your comments.\n\n- Fredrik\n"},{"id":"132032","messageId":"4B546608.4010503@viscovery.net","threadId":"22267","inReplyTo":"4c8ef71001180528h6182ef4l8a617fd038bd7318@mail.gmail.com","subject":"Re: [PATCH v3] Threaded grep","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2010-01-18T13:45:44Z","receivedAt":"2010-01-18T13:45:44Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Fredrik Kuivinen schrieb:\n> On Mon, Jan 18, 2010 at 12:11, Johannes Sixt <j.sixt@viscovery.net> wrote:\n>> Fredrik Kuivinen schrieb:\n>>> +     pthread_mutex_unlock(&grep_lock);\n>>> +     pthread_cond_signal(&cond_add);\n>> Please swap these two lines, so that pthread_cond_signal() is called while\n>> the lock is held.\n> \n> May I ask why? (just curious)\n\nBecause our pthreads_cond_* functions on Windows are not POSIXly correct\nand work reliably only when pthread_cond_signal() is called while the\nmutex is held.\n\n-- Hannes\n"},{"id":"132042","messageId":"alpine.LFD.2.00.1001180947140.13231@localhost.localdomain","threadId":"22267","inReplyTo":"20100118103334.GA17361@fredrik-laptop","subject":"Re: [PATCH v3] Threaded grep","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2010-01-18T18:05:19Z","receivedAt":"2010-01-18T18:05:19Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 18 Jan 2010, Fredrik Kuivinen wrote:\n>\n> Make git grep use threads when it is available.\n\nOk, this is much better.\n\nOn my machine (4 cores with HT, so 8 threads total), I get the \nfollowing:\n\n [ Note: the --no-ext-grep is because I'm comparing with a git that has \n  the original grep optimization, but hasn't removed the external grep \n  functionality yet. I just used the same command line when then comparing \n  to next+your patch, so don't mind it.\n\n  Also, the three examples are chosen to be: \"trivial single match\", \n  \"regex single match\", and \"trivial lots of matches\" ]\n\nBefore (all best-of-five), with the non-threaded internal grep:\n\n - git grep --no-ext-grep qwerty\n\n\treal\t0m0.311s\n\tuser\t0m0.164s\n\tsys\t0m0.144s\n\n - git grep --no-ext-grep qwerty.*as\n\n\treal\t0m0.555s\n\tuser\t0m0.416s\n\tsys\t0m0.132s\n\n - git grep --no-ext-grep function\n\n\treal\t0m0.461s\n\tuser\t0m0.276s\n\tsys\t0m0.180s\n\nAfter, with threading:\n\n - git grep --no-ext-grep qwerty\n\n\treal\t0m0.152s\n\tuser\t0m0.788s\n\tsys\t0m0.212s\n\n - git grep --no-ext-grep qwerty.*as\n\n\treal\t0m0.148s\n\tuser\t0m0.724s\n\tsys\t0m0.284s\n\n - git grep --no-ext-grep function\n\n\treal\t0m0.241s\n\tuser\t0m1.436s\n\tsys\t0m0.216s\n\nso now it's a clear win in all cases. And as you'd expect, the \"complex \ncase with single output\" is the one that wins most, since it's the one \nthat should have the most CPU usage, with the least synchronization.\n\nThat said, it still does waste quite a bit of time doing this, and while \nit almost doubles performance in the last case too, it does so at the cost \nof quite a bit of overhead.\n\n(Some overhead is natural, especially since I have HT. Running two threads \non the same core does _not_ give double the performance, so the CPU time \nalmost doubling - because the threads themselves run slower - is not \nunexpected. It's when the CPU time more than quadruples that I suspect \nthat it could be improved a bit).\n\n\t\tLinus\n"},{"id":"132059","messageId":"4c8ef71001181612l72ec73ecmae709fbb475752b0@mail.gmail.com","threadId":"22267","inReplyTo":"7vmy0bhxn1.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3] Threaded grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-01-19T00:12:40Z","receivedAt":"2010-01-19T00:12:40Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"[I am adding git@vger to the Cc list as this may be interesting to\nothers as well.]\n\nOn Mon, Jan 18, 2010 at 23:10, Junio C Hamano <gitster@pobox.com> wrote:\n> Fredrik Kuivinen <frekui@gmail.com> writes:\n>\n>> diff --git a/builtin-grep.c b/builtin-grep.c\n>> index 24ae1ce..dc07e9e 100644\n>> --- a/builtin-grep.c\n>> +++ b/builtin-grep.c\n>> @@ -15,11 +15,257 @@\n>>  #include \"grep.h\"\n>>  #include \"quote.h\"\n>>\n>> +#ifndef NO_PTHREADS\n>> +#include \"thread-utils.h\"\n>> +#include <pthread.h>\n>> +#endif\n>> +\n>>  static char const * const grep_usage[] = {\n>>       \"git grep [options] [-e] <pattern> [<rev>...] [[--] path...]\",\n>>       NULL\n>>  };\n>>\n>> +static int use_threads = 1;\n>> +\n>> +#ifndef NO_PTHREADS\n>> +#define THREADS 8\n>> +static pthread_t threads[THREADS];\n>\n> I had to wonder why builtin-pack-objects.c doesn't have an array like\n> this.  It uses an array of structure each of which bundles per-thread\n> work item data and pthread_t.  Would an arrangement like that make it\n> easier to read for this patch as well?\n\nFrom a cursory look at builtin-pack-objects.c I think it depends on\nhow you structure the work you are about to do.\n\nIn builtin-pack-objects.c the work seems to be divided evenly among\nthe threads at the start. When some thread don't have anything to do\nit then steals work from some other thread.\n\nIn the current patch we instead add work to a FIFO from one thread and\nthen the consumer threads pick work from the FIFO. I think the current\nstructure suits the FIFO style quite well.\n\n>> +static void* load_file(const char *filename, size_t *sz);\n>\n> Style: asterisks stick to identifiers, not types.  There are other\n> places with the same issue in the patch, e.g.\n>> +static struct work_item* get_work()\n> that I'll omit from the rest of my comments.\n\nWill fix. I looked carefully at the arguments, but forgot the return types.\n\n>> +enum work_type {WORK_BUF, WORK_FILE};\n>> +\n>> +/* We use one producer thread and number_of_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> Style:\n>\n>        /*\n>         * We write multi line comments\n>         * like this.\n>         */\n\nWill fix.\n\n>> +#define TODO_SIZE 128\n>\n> How was this size tuned?  Can everybody (from teeny machines to beefy\n> ones) use the same setting?\n\nI simply increased it until I didn't see any more significant\nperformance improvements on two the boxes I have access to. As I only\nhave access to two boxes, it can most certainly be better tuned for\nboxes with significantly different characteristics. However, I think\nthat 128 is reasonable in the sense that it gives a nice improvement\nfor everyone with more than one core.\n\n>> +static struct work_item todo[TODO_SIZE];\n>> +static int todo_start = 0;\n>\n> We try not to explicitly initialize statics to 0 and let BSS segment\n> take care of them.\n\nWill fix.\n\n>> +/* This lock protects all the variables above. */\n>> +static pthread_mutex_t grep_lock = PTHREAD_MUTEX_INITIALIZER;\n>\n> J6t had comments on these initializers; do they also apply to\n> builtin-pack-objects.c?\n\nI believe so, but I do not know. Johannes?\n\n>> +/* This function takes ownership of 'name' and 'buf'. They will be\n>> +   deallocated with free. */\n>> +static int grep_buffer_async(struct grep_opt *opt, char *name, char *buf,\n>> +                          size_t size)\n>> +{\n>> +     add_work(WORK_BUF, name, buf, size);\n>> +     return 0;\n>> +}\n>> +\n>> +static int grep_file_async(struct grep_opt *opt, char *name,\n>> +                        const char *filename)\n>> +{\n>> +     add_work(WORK_FILE, name, (char*) filename, 0);\n>> +     return 0;\n>> +}\n>\n> If I am reading the code correctly, it seems that you read quite many\n> blobs in core and queue them in todo[] (up to the size limit of the\n> array), and the worker bees in run() consumes them.  Shouldn't the\n> rate of feeding blobs be limited in some way (other than just having a\n> fixed TODO_SIZE, but somehow linked to the rate the worker bees finish\n> their work) to avoid wasting memory like this?  One approach might be\n> to queue only the blob SHA-1 not the data in work item queue just like\n> you queue only the filename not the contents, and have the worker bee\n> to read the blob into memory.\n\nHm, yes that would be an improvement. One just have serialize the\ncalls to read_sha1_file (as I don't think read_sha1_file safely can be\ncalled simultaneously from multiple threads).\n\n>> ...\n>> +static int grep_buffer_internal(struct grep_opt *opt, char *name, char *buf,\n>> +                             size_t size)\n>> +{\n>> +#ifndef NO_PTHREADS\n>> +     if (use_threads)\n>> +             return grep_buffer_async(opt, name, buf, size);\n>> +#endif\n>> +     {\n>> +             int hit = grep_buffer(opt, name, buf, size);\n>> +             free(name);\n>> +             free(buf);\n>> +             return hit;\n>> +     }\n>> +}\n>> +\n>>  static int grep_config(const char *var, const char *value, void *cb)\n>>  {\n>>       struct grep_opt *opt = cb;\n>> @@ -159,21 +405,21 @@ static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1, const char\n>>       if (opt->relative && opt->prefix_length) {\n>>               quote_path_relative(name + tree_name_len, -1, &pathbuf, opt->prefix);\n>>               strbuf_insert(&pathbuf, 0, name, tree_name_len);\n>> -             name = pathbuf.buf;\n>> +     } else {\n>> +             strbuf_addstr(&pathbuf, name);\n>>       }\n>> -     hit = grep_buffer(opt, name, data, size);\n>> -     strbuf_release(&pathbuf);\n>> -     free(data);\n>> +\n>> +     hit = grep_buffer_internal(opt, strbuf_detach(&pathbuf, NULL),\n>> +                                data, size);\n>> +\n>>       return hit;\n>>  }\n>\n> This is quite a puzzling code.  Your grep_buffer_internal() returns\n> the return value from grep_buffer_async() which always return 0 but\n> then that 0 is returned to the caller as \"we didn't see any hit\".\n> What happens if we start optimizing for a case where the end user is\n> interested only in one bit of information \"does it find anything, or\n> is there absolutely no hits?\" and wanted to add an early return\n> codepath to grep_tree() and grep_cache() so that we say \"Ah, we have\n> seen a hit, so we don't have to look in others\"?\n>\n> IOW, this patch makes the variable \"hit\" meaningless and confuses the\n> readers.  This actually is the point that most worries me from longer\n> term maintenance point of view.\n\nThe idea was to keep the current calling conventions as much as\npossible, so that grep_cache and grep_tree could stay nearly\nunchanged. So hit = 1 now means \"we found something\" and hit = 0 means\n\"we didn't find anything right now, but we may find something later\nfor this entry\". The early return you sketched above will still\nproduce correct results, but it will not be an optimization for the\nthreaded code.\n\nWith the patch the return value from grep_file and grep_sha1 has to be\nORed with the return value from wait_all to determine if we found\nsomething.\n\n> How is the order of output controlled by the way?  I see you are\n> keeping more than one threads from doing write_or_die() of the\n> accumulated output at the same time with a mutex in work_done(), but\n> if we have large files whose names come near the beginning and then a\n> small file whose name come later in the input, we should defer the\n> output of hits from the later smaller one before the earlier larger\n> ones even if the worker bee assigned to the smaller one finishes while\n> the other worker bees are still searching in the larger ones; it is\n> not obvious to me where you are guaranteeing that ordering.\n\nThe output order is controlled by todo_done, todo_start, and work_item::done.\n\nThe rule is that the range [todo_done, todo_start) (modulo\nARRAY_SIZE(todo)) in \"todo\" contains work_items have been or are\nprocessed by a consumer thread. If a particular work_item has been\nprocessed, then .done = 1 and otherwise .done = 0. When a work_item is\nmarked as done in \"work_done\" we traverse a prefix of the range\n[todo_done, todo_start): we stop as soon as .done = 0. We then set\ntodo_done to the first work_item with .done = 0.\n\nIn your example todo_done = 0 and todo_start = 2. todo[0] represents a\nlarge file and todo[1] represents a small file. If the small file gets\ndone first we set todo[1].done to 1 in work_done. As todo_done = 0 and\ntodo[0].done = 0 we will not write any output now. When work_done is\ncalled for todo[0], we set todo[0].done to 1. We will then write the\noutput for todo[0] (as todo_done = 0 and todo[0].done = 1) and after\nthat we write the output for todo[1].\n\nIn the current patch the mutex grep_lock is held when the output is\nwritten. I'm guessing that this unnecessary serialization is the cause\nof the waste of CPU time Linus is seeing. (Strangely enough I haven't\nobserved this phenomena on the boxes I have tested it on.)\n\n> I am wondering if this can somehow be made into a change with alot\n> smaller inpact, in spirit similar to \"preloading\".  The higher level\n> loop may walk the input (be it cache, tree, or directory), issuing one\n> grep_file() or grep_sha1() at a time just like the existing code, but\n> the thread-aware code adds \"priming\" phase that (1) populates a \"work\n> queue\" with a very small memory footprint, and that (2) starts more\n> than one underlying grep on different files and blobs (up to the\n> number of threads you are allowed, like your \"#define THREADS 8\"), and\n> that (3) upon completion of one \"work queue\" item, the work queue item\n> is marked with its result.\n>\n> Then grep_file() and grep_sha1() _may_ notice that the work queue item\n> hasn't completed, and would wait in such a case, or just emits the\n> output produced earlier (could be much earlier) by the worker bee.\n>\n> The low-memory-footprint work queue could be implemented as a lazy\n> one, and may be very different depending on how the input is created.\n> If we are grepping in the index, it could be a small array of <array\n> index in active_cache[], done-bit, result-bit, result-strbuf> with a\n> single integer that is a pointer into the index to indicate up to\n> which index entry the work queue has been populated.\n\nI will have to think about this a bit more. It's getting late here.\n\n- Fredrik\n"},{"id":"132081","messageId":"4B555934.9060106@viscovery.net","threadId":"22267","inReplyTo":"4c8ef71001181612l72ec73ecmae709fbb475752b0@mail.gmail.com","subject":"Re: [PATCH v3] Threaded grep","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2010-01-19T07:03:16Z","receivedAt":"2010-01-19T07:03:16Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Fredrik Kuivinen schrieb:\n> On Mon, Jan 18, 2010 at 23:10, Junio C Hamano <gitster@pobox.com> wrote:\n>> Fredrik Kuivinen <frekui@gmail.com> writes:\n>>> +/* This lock protects all the variables above. */\n>>> +static pthread_mutex_t grep_lock = PTHREAD_MUTEX_INITIALIZER;\n>> J6t had comments on these initializers; do they also apply to\n>> builtin-pack-objects.c?\n> \n> I believe so, but I do not know. Johannes?\n\n44626dc (MSVC: Windows-native implementation for subset of Pthreads API)\nthat is currently queued in pu makes the necessary adjustments to\nbuiltin-pack-objects.c.\n\n-- Hannes\n"},{"id":"132086","messageId":"20100119073454.GA15575@fredrik-laptop","threadId":"22267","inReplyTo":"alpine.LFD.2.00.1001180947140.13231@localhost.localdomain","subject":"Re: [PATCH v3] Threaded grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-01-19T07:34:54Z","receivedAt":"2010-01-19T07:34:54Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Mon, Jan 18, 2010 at 10:05:19AM -0800, Linus Torvalds wrote:\n> On my machine (4 cores with HT, so 8 threads total), I get the \n> following:\n> \n>  [ Note: the --no-ext-grep is because I'm comparing with a git that has \n>   the original grep optimization, but hasn't removed the external grep \n>   functionality yet. I just used the same command line when then comparing \n>   to next+your patch, so don't mind it.\n> \n>   Also, the three examples are chosen to be: \"trivial single match\", \n>   \"regex single match\", and \"trivial lots of matches\" ]\n\n\nYou may be testing slightly different things: next has 885d211 (grep:\nrip out pessimization to use fixmatch()) and bbc09c2 (grep: rip out\nsupport for external grep) was added before. So next+patch uses\nregexec and the version with support for external greps uses\nstrstr. IIRC strstr was a bit faster than regexec on your\nbox. However, this only explains a small part of the results you are\nseeing.\n\n> \n> Before (all best-of-five), with the non-threaded internal grep:\n> \n>  - git grep --no-ext-grep qwerty\n> \n> \treal\t0m0.311s\n> \tuser\t0m0.164s\n> \tsys\t0m0.144s\n> \n>  - git grep --no-ext-grep qwerty.*as\n> \n> \treal\t0m0.555s\n> \tuser\t0m0.416s\n> \tsys\t0m0.132s\n> \n>  - git grep --no-ext-grep function\n> \n> \treal\t0m0.461s\n> \tuser\t0m0.276s\n> \tsys\t0m0.180s\n> \n> After, with threading:\n> \n>  - git grep --no-ext-grep qwerty\n> \n> \treal\t0m0.152s\n> \tuser\t0m0.788s\n> \tsys\t0m0.212s\n> \n>  - git grep --no-ext-grep qwerty.*as\n> \n> \treal\t0m0.148s\n> \tuser\t0m0.724s\n> \tsys\t0m0.284s\n> \n>  - git grep --no-ext-grep function\n> \n> \treal\t0m0.241s\n> \tuser\t0m1.436s\n> \tsys\t0m0.216s\n> \n> so now it's a clear win in all cases. And as you'd expect, the \"complex \n> case with single output\" is the one that wins most, since it's the one \n> that should have the most CPU usage, with the least synchronization.\n> \n> That said, it still does waste quite a bit of time doing this, and while \n> it almost doubles performance in the last case too, it does so at the cost \n> of quite a bit of overhead.\n> \n> (Some overhead is natural, especially since I have HT. Running two threads \n> on the same core does _not_ give double the performance, so the CPU time \n> almost doubling - because the threads themselves run slower - is not \n> unexpected. It's when the CPU time more than quadruples that I suspect \n> that it could be improved a bit).\n\n\nI haven't seen this overhead during my tests. But I'm _guessing_ that\nthe problem is that the mutex grep_lock is held while the result is\nwritten to stdout. So when we are writing, no significant amount of\nwork can be done by any thread. Here is a patch to fix this (applies\non to of v3).\n\n\n\ndiff --git a/builtin-grep.c b/builtin-grep.c\nindex 8fca7a6..422b0ec 100644\n--- a/builtin-grep.c\n+++ b/builtin-grep.c\n@@ -139,21 +139,48 @@ static int grep_file_async(struct grep_opt *opt, char *name,\n \treturn 0;\n }\n \n+/* Mark the work_item as done. The function guarantees that w->done is\n+ * set to 1 and that if w is included in a prefix of the range\n+ * [todo_done, todo_start) where each work_item has .done == 1, then\n+ * w->out will eventually be written to stdout. The writing is done\n+ * either by this thread or by the thread which has set 'writing' to\n+ * 1.\n+ */\n static void work_done(struct work_item *w)\n {\n-\tint old_done;\n+\t/* 1 if there is a thread which is writing data to stdout and\n+\t   0 otherwise. */\n+\tstatic int writing = 0;\n+\tint old_done, write_idx, write_to;\n \n \tpthread_mutex_lock(&grep_lock);\n \tw->done = 1;\n \told_done = todo_done;\n-\tfor(; todo[todo_done].done && todo_done != todo_start;\n-\t    todo_done = (todo_done+1) % ARRAY_SIZE(todo)) {\n-\t\tw = &todo[todo_done];\n-\t\twrite_or_die(1, w->out.buf, w->out.len);\n-\t\tif (w->type == WORK_BUF)\n-\t\t\tfree(w->buf);\n-\n-\t\tfree(w->name);\n+\n+\t/* We need a loop here if todo_start is changed while we write\n+\t * some data. */\n+\twhile (!writing && todo[todo_done].done && todo_done != todo_start) {\n+\t\twrite_idx = todo_done;\n+\t\twrite_to = todo_start;\n+\t\twriting = 1;\n+\n+\t\t/* Unlock the mutex while we write the data. This is\n+\t\t * safe as writing == 1 and hence there is at most one\n+\t\t * thread which writes data at any time. */\n+\t\tpthread_mutex_unlock(&grep_lock);\n+\t\tfor(; todo[write_idx].done && write_idx != write_to;\n+\t\t    write_idx = (write_idx+1) % ARRAY_SIZE(todo)) {\n+\t\t\tw = &todo[write_idx];\n+\t\t\twrite_or_die(1, w->out.buf, w->out.len);\n+\t\t\tif (w->type == WORK_BUF)\n+\t\t\t\tfree(w->buf);\n+\t\t\n+\t\t\tfree(w->name);\n+\t\t}\n+\n+\t\tpthread_mutex_lock(&grep_lock);\n+\t\twriting = 0;\n+\t\ttodo_done = write_idx;\n \t}\n \n \tif (old_done != todo_done)\n"},{"id":"132112","messageId":"alpine.LFD.2.00.1001190728300.13231@localhost.localdomain","threadId":"22267","inReplyTo":"20100119073454.GA15575@fredrik-laptop","subject":"Re: [PATCH v3] Threaded grep","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2010-01-19T15:41:43Z","receivedAt":"2010-01-19T15:41:43Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 19 Jan 2010, Fredrik Kuivinen wrote:\n> > \n> >  - git grep --no-ext-grep function\n> > \n> > \treal\t0m0.241s\n> > \tuser\t0m1.436s\n> > \tsys\t0m0.216s\n> \n> I haven't seen this overhead during my tests. But I'm _guessing_ that\n> the problem is that the mutex grep_lock is held while the result is\n> written to stdout. So when we are writing, no significant amount of\n> work can be done by any thread. Here is a patch to fix this (applies\n> on to of v3).\n\nNo, I get basically the same timings with this patch:\n\n\treal\t0m0.239s\n\tuser\t0m1.372s\n\tsys\t0m0.280s\n\n(that _may_ be a slight real improvement, but it's more likely that the \nchanging in user/sys time is just noise).\n\nBut I do think that you're right that there's a difference in my timings, \nand I am comparing to the one that uses strstr(). Your patches didn't have \na \"disable threads\" option that I could see, so I just compared against my \nold numbers. \n\nSo I guess a better example is to use a \"complex\" grep pattern like \n'function.*a' which also gets a lot of hits, and the threaded case does \nlook much better in comparison. Pre-threaded:\n\n\treal\t0m0.921s\n\tuser\t0m0.728s\n\tsys\t0m0.184s\n\nso it's less than 2x the CPU time, and a 3.85x real-time improvement. And \nthat \"less than 2x the CPU time\" is the factor I'd expect from HT.\n\nIt's also worth noting that at least _some_ versions of glibc would \nactually use different versions of subroutines for the threaded vs \nnon-threaded case, ie they'd avoid locking overhead when they know they \naren't running with threads. So things like stdio actually got slower when \nyou did any pthreads things, because suddenly glibc knew that it needed to \ndo locking around the functions.\n\n\t\t\tLinus\n"},{"id":"132643","messageId":"4c8ef71001251447m18a0e7c0y71db3972d0ca1152@mail.gmail.com","threadId":"22267","inReplyTo":"4c8ef71001181612l72ec73ecmae709fbb475752b0@mail.gmail.com","subject":"Re: [PATCH v3] Threaded grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-01-25T22:47:30Z","receivedAt":"2010-01-25T22:47:30Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Tue, Jan 19, 2010 at 01:12, Fredrik Kuivinen <frekui@gmail.com> wrote:\n> On Mon, Jan 18, 2010 at 23:10, Junio C Hamano <gitster@pobox.com> wrote:\n>>\n>> I am wondering if this can somehow be made into a change with alot\n>> smaller inpact, in spirit similar to \"preloading\".  The higher level\n>> loop may walk the input (be it cache, tree, or directory), issuing one\n>> grep_file() or grep_sha1() at a time just like the existing code, but\n>> the thread-aware code adds \"priming\" phase that (1) populates a \"work\n>> queue\" with a very small memory footprint, and that (2) starts more\n>> than one underlying grep on different files and blobs (up to the\n>> number of threads you are allowed, like your \"#define THREADS 8\"), and\n>> that (3) upon completion of one \"work queue\" item, the work queue item\n>> is marked with its result.\n>>\n>> Then grep_file() and grep_sha1() _may_ notice that the work queue item\n>> hasn't completed, and would wait in such a case, or just emits the\n>> output produced earlier (could be much earlier) by the worker bee.\n>>\n>> The low-memory-footprint work queue could be implemented as a lazy\n>> one, and may be very different depending on how the input is created.\n>> If we are grepping in the index, it could be a small array of <array\n>> index in active_cache[], done-bit, result-bit, result-strbuf> with a\n>> single integer that is a pointer into the index to indicate up to\n>> which index entry the work queue has been populated.\n>\n> I will have to think about this a bit more. It's getting late here.\n\nI will be sending v4 of the patch in a couple of minutes, but I want\nto comment on this first.\n\nSure, it is probably possible to structure the code as you suggest.\nHowever, I am not so sure that it will be a significantly smaller\nchange. I find the approach taken in the patch to be quite nice as the\nthreaded and non-threaded cases are fairly similar. There is a block\nof code which deals with the threading, but that part is mostly\nself-contained. In v4 I have not changed the overall approach to the\nproblem.\n\n- Fredrik\n"}]}