{"thread":{"id":"22391","subject":"[PATCH v4] Threaded grep","startedAt":"2010-01-25T22:51:39Z","lastAt":"2010-01-26T17:48:36Z","messageCount":12,"participants":["Fredrik Kuivinen","Linus Torvalds","Junio C Hamano","Benjamin Kramer","Mike Hommey"],"isPatch":true,"patchVersion":4,"patchTotal":null},"messages":[{"id":"132644","messageId":"20100125225139.GA3048@fredrik-laptop","threadId":"22391","inReplyTo":null,"subject":"[PATCH v4] Threaded grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-01-25T22:51:39Z","receivedAt":"2010-01-25T22:51:39Z","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.\n\nAdditional changes since v3:\n\n* Fix some issues with Git's native pthreads implementation on\n  Windows (pthread_cond_broadcast is still used though).\n* Fix style issues.\n* When greping in a tree, allocate memory for the data buffer as\n  late as possible.\n* Return void from grep_sha1_async and grep_file_async instead of\n  always returning 0.\n\n builtin-grep.c |  394 ++++++++++++++++++++++++++++++++++++++++++++++++++++----\n grep.c         |  106 +++++++++++++--\n grep.h         |    6 +\n 3 files changed, 457 insertions(+), 49 deletions(-)\n\ndiff --git a/builtin-grep.c b/builtin-grep.c\nindex da854fa..252cb0b 100644\n--- a/builtin-grep.c\n+++ b/builtin-grep.c\n@@ -16,11 +16,270 @@\n #include \"quote.h\"\n #include \"dir.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_sha1(const unsigned char *sha1, unsigned long *size,\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+{\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 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;\n+static int todo_end;\n+static int todo_done;\n+\n+/* Has all work items been added? */\n+static int all_work_added;\n+\n+/* This lock protects all the variables above. */\n+static pthread_mutex_t grep_lock;\n+\n+/* Used to serialize calls to read_sha1_file. */\n+static pthread_mutex_t read_sha1_lock;\n+\n+/* Signalled when a new work_item is added to todo. */\n+static pthread_cond_t cond_add;\n+\n+/* Signalled when the result from one work_item is written to\n+ * stdout.\n+ */\n+static pthread_cond_t cond_write;\n+\n+/* Signalled when we are finished with everything. */\n+static pthread_cond_t cond_result;\n+\n+static void add_work(enum work_type type, char *name, void *id)\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].identifier = id;\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_cond_signal(&cond_add);\n+\tpthread_mutex_unlock(&grep_lock);\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+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+}\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\tfree(w->name);\n+\t\tfree(w->identifier);\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_SHA1) {\n+\t\t\tunsigned long sz;\n+\t\t\tvoid* data;\n+\n+\t\t\tpthread_mutex_lock(&read_sha1_lock);\n+\t\t\tdata = load_sha1(w->identifier, &sz, w->name);\n+\t\t\tpthread_mutex_unlock(&read_sha1_lock);\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\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+\tpthread_mutex_init(&grep_lock, NULL);\n+\tpthread_mutex_init(&read_sha1_lock, NULL);\n+\tpthread_cond_init(&cond_add, NULL);\n+\tpthread_cond_init(&cond_write, NULL);\n+\tpthread_cond_init(&cond_result, NULL);\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\tint err;\n+\t\tstruct grep_opt *o = grep_opt_dup(opt);\n+\t\to->output = strbuf_out;\n+\t\tcompile_grep_patterns(o);\n+\t\terr = pthread_create(&threads[i], NULL, run, o);\n+\n+\t\tif (err)\n+\t\t\tdie(\"grep: failed to create thread: %s\",\n+\t\t\t    strerror(err));\n+\t}\n+}\n+\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+\t */\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+\tpthread_mutex_destroy(&grep_lock);\n+\tpthread_mutex_destroy(&read_sha1_lock);\n+\tpthread_cond_destroy(&cond_add);\n+\tpthread_cond_destroy(&cond_write);\n+\tpthread_cond_destroy(&cond_result);\n+\n+\treturn hit;\n+}\n+#else /* !NO_PTHREADS */\n+static int wait_all()\n+{\n+\treturn 0;\n+}\n+#endif\n+\n static int grep_config(const char *var, const char *value, void *cb)\n {\n \tstruct grep_opt *opt = cb;\n@@ -144,37 +403,60 @@ static int pathspec_matches(const char **paths, const char *name, int max_depth)\n \treturn 0;\n }\n \n-static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1, const char *name, int tree_name_len)\n+static void *load_sha1(const unsigned char *sha1, unsigned long *size,\n+\t\t       const char *name)\n {\n-\tunsigned long size;\n-\tchar *data;\n \tenum object_type type;\n-\tint hit;\n-\tstruct strbuf pathbuf = STRBUF_INIT;\n+\tchar *data = read_sha1_file(sha1, &type, size);\n \n-\tdata = read_sha1_file(sha1, &type, &size);\n-\tif (!data) {\n+\tif (!data)\n \t\terror(\"'%s': unable to read %s\", name, sha1_to_hex(sha1));\n-\t\treturn 0;\n-\t}\n+\n+\treturn data;\n+}\n+\n+static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1,\n+\t\t     const char *filename, int tree_name_len)\n+{\n+\tstruct strbuf pathbuf = STRBUF_INIT;\n+\tchar *name;\n+\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\tquote_path_relative(filename + tree_name_len, -1, &pathbuf,\n+\t\t\t\t    opt->prefix);\n+\t\tstrbuf_insert(&pathbuf, 0, filename, tree_name_len);\n+\t} else {\n+\t\tstrbuf_addstr(&pathbuf, filename);\n+\t}\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+\n+\t\tfree(data);\n+\t\tfree(name);\n+\t\treturn hit;\n \t}\n-\thit = grep_buffer(opt, name, data, size);\n-\tstrbuf_release(&pathbuf);\n-\tfree(data);\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-\tint i;\n \tchar *data;\n-\tsize_t sz;\n-\tstruct strbuf buf = STRBUF_INIT;\n+\tint i;\n \n \tif (lstat(filename, &st) < 0) {\n \terr_ret:\n@@ -184,25 +466,52 @@ 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+\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-\tdata[sz] = 0;\n+\tdata[*sz] = 0;\n+\treturn data;\n+}\n+\n+static int grep_file(struct grep_opt *opt, const char *filename)\n+{\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\tgrep_file_async(opt, name, filename);\n+\t\treturn 0;\n+\t} else\n+#endif\n+\t{\n+\t\tint hit;\n+\t\tsize_t sz;\n+\t\tvoid *data = load_file(filename, &sz);\n+\t\tif (!data)\n+\t\t\thit = 0;\n+\t\telse\n+\t\t\thit = grep_buffer(opt, name, data, sz);\n+\n+\t\tfree(data);\n+\t\tfree(name);\n+\t\treturn hit;\n+\t}\n }\n \n static int grep_cache(struct grep_opt *opt, const char **paths, int cached)\n@@ -572,6 +881,17 @@ 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 (online_cpus() == 1 || !grep_threads_ok(&opt))\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@@ -609,17 +929,26 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t}\n \n \tif (!use_index) {\n+\t\tint hit;\n \t\tif (cached)\n \t\t\tdie(\"--cached cannot be used with --no-index.\");\n \t\tif (list.nr)\n \t\t\tdie(\"--no-index cannot be used with revs.\");\n-\t\treturn !grep_directory(&opt, paths);\n+\t\thit = grep_directory(&opt, paths);\n+\t\tif (use_threads)\n+\t\t\thit |= wait_all();\n+\t\treturn !hit;\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@@ -631,6 +960,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..d281a02 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\t    strlen(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,32 @@ 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->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+\t */\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 +743,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 +818,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 +876,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\t opt->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..9703087 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 *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":"132648","messageId":"alpine.LFD.2.00.1001251542100.3574@localhost.localdomain","threadId":"22391","inReplyTo":"20100125225139.GA3048@fredrik-laptop","subject":"Re: [PATCH v4] Threaded grep","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2010-01-25T23:59:56Z","receivedAt":"2010-01-25T23:59:56Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 25 Jan 2010, Fredrik Kuivinen wrote:\n> \n> The results below are best of five runs in the Linux repository (on a\n> box with two cores).\n> \n> git grep qwerty\n\nBefore:\n\n\treal\t0m0.531s\n\tuser\t0m0.412s\n\tsys\t0m0.112s\n\nAfter:\n\n\treal\t0m0.151s\n\tuser\t0m0.720s\n\tsys\t0m0.272s\n\n\n> $ /usr/bin/time git grep void\n\nBefore:\n\n\treal\t0m1.144s\n\tuser\t0m0.988s\n\tsys\t0m0.148s\n\nAfter:\n\treal\t0m0.290s\n\tuser\t0m1.732s\n\tsys\t0m0.232s\n\nSo it's helping a lot (~3.5x and ~3.9x) on this 4-core HT setup. \n\nI don't seem to ever get more than a 4x speedup, so my guess is that HT \nsimply isn't able to do much of anything with this load. \n\nThe profile for the threaded case says:\n\n    51.73%      git  libc-2.11.1.so                 [.] re_search_internal\n    11.47%      git  [kernel]                       [k] copy_user_generic_string\n     2.90%      git  libc-2.11.1.so                 [.] __strlen_sse2\n     2.66%      git  [kernel]                       [k] link_path_walk\n     2.55%      git  [kernel]                       [k] intel_pmu_enable_all\n     2.40%      git  [kernel]                       [k] __d_lookup\n     1.71%      git  libc-2.11.1.so                 [.] __GI___libc_malloc\n     1.55%      git  [kernel]                       [k] _raw_spin_lock\n     1.43%      git  [kernel]                       [k] sys_futex\n     1.30%      git  libc-2.11.1.so                 [.] __cfree\n     1.28%      git  [kernel]                       [k] intel_pmu_disable_all\n     1.25%      git  libc-2.11.1.so                 [.] __GI_memchr\n     1.14%      git  libc-2.11.1.so                 [.] _int_malloc\n     1.02%      git  [kernel]                       [k] effective_load\n\nand the only thing that makes me go \"eh?\" there is the strlen(). Why is \nthat so hot?  But locking doesn't seem to be the biggest issue, and in \ngeneral I think this is all pretty good. The 'effective_load' thing is the \nscheduler, so there's certainly some context switching going on, probably \nstill due to excessive synchronization, but it's equally clear that that \nis certainly not a dominant factor.\n\nOne potentially interesting data point is that if I make NR_THREADS be 16, \nperformance goes down, and I get more locking overhead. So NR_THREADS of 8 \nworks well on this machine.\n\nSo ack from me. The patch looks reasonably clean too, at least for \nsomething as complex as a multi-threaded grep.\n\nOne worry is, of course, whether all regex() implementations are \nthread-safe. Maybe there are broken libraries that have hidden global \nstate in them?\n\n\t\t\tLinus\n"},{"id":"132657","messageId":"7vpr4x1x20.fsf@alter.siamese.dyndns.org","threadId":"22391","inReplyTo":"20100125225139.GA3048@fredrik-laptop","subject":"Re: [PATCH v4] Threaded grep","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-01-26T01:20:39Z","receivedAt":"2010-01-26T01:20:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen <frekui@gmail.com> writes:\n\n> The patch has been rebased on top of next.\n>\n> Additional changes since v3:\n>\n> * Fix some issues with Git's native pthreads implementation on\n>   Windows (pthread_cond_broadcast is still used though).\n> * Fix style issues.\n> * When greping in a tree, allocate memory for the data buffer as\n>   late as possible.\n> * Return void from grep_sha1_async and grep_file_async instead of\n>   always returning 0.\n\nThanks; I've fixed up a few old-style declaration header and queued the\nresult to 'pu'.\n"},{"id":"132671","messageId":"20100126114303.GA1854@fredrik-laptop","threadId":"22391","inReplyTo":"7vpr4x1x20.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v4] Threaded grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-01-26T11:43:03Z","receivedAt":"2010-01-26T11:43:03Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Mon, Jan 25, 2010 at 05:20:39PM -0800, Junio C Hamano wrote:\n> Fredrik Kuivinen <frekui@gmail.com> writes:\n> \n> > The patch has been rebased on top of next.\n> >\n> > Additional changes since v3:\n> >\n> > * Fix some issues with Git's native pthreads implementation on\n> >   Windows (pthread_cond_broadcast is still used though).\n> > * Fix style issues.\n> > * When greping in a tree, allocate memory for the data buffer as\n> >   late as possible.\n> > * Return void from grep_sha1_async and grep_file_async instead of\n> >   always returning 0.\n> \n> Thanks; I've fixed up a few old-style declaration header and queued the\n> result to 'pu'.\n\nI just noticed that I forgot to take the read_sha1 lock in\ngrep_tree. The result is a race condition in read_sha1_file.\n\nHere is a patch to fix this. It applies on top of ae35c68 (Threaded\ngrep). Could you please squash it in? Let me know if you want me to\nresend the entire patch instead.\n\n(The only important thing is that we now take the read_sha1_mutex in\ngrep_tree. The rest is there just to make it self-consistent.)\n\n\n- Fredrik\n\n--- 8< ---\n\ndiff --git a/builtin-grep.c b/builtin-grep.c\nindex 7ecf222..6cc743d 100644\n--- a/builtin-grep.c\n+++ b/builtin-grep.c\n@@ -75,10 +75,15 @@ static int todo_done;\n static int all_work_added;\n \n /* This lock protects all the variables above. */\n-static pthread_mutex_t grep_lock;\n+static pthread_mutex_t grep_mutex;\n \n /* Used to serialize calls to read_sha1_file. */\n-static pthread_mutex_t read_sha1_lock;\n+static pthread_mutex_t read_sha1_mutex;\n+\n+#define grep_lock() pthread_mutex_lock(&grep_mutex)\n+#define grep_unlock() pthread_mutex_unlock(&grep_mutex)\n+#define read_sha1_lock() pthread_mutex_lock(&read_sha1_mutex)\n+#define read_sha1_unlock() pthread_mutex_unlock(&read_sha1_mutex)\n \n /* Signalled when a new work_item is added to todo. */\n static pthread_cond_t cond_add;\n@@ -93,10 +98,10 @@ static pthread_cond_t cond_result;\n \n static void add_work(enum work_type type, char *name, void *id)\n {\n-\tpthread_mutex_lock(&grep_lock);\n+\tgrep_lock();\n \n \twhile ((todo_end+1) % ARRAY_SIZE(todo) == todo_done) {\n-\t\tpthread_cond_wait(&cond_write, &grep_lock);\n+\t\tpthread_cond_wait(&cond_write, &grep_mutex);\n \t}\n \n \ttodo[todo_end].type = type;\n@@ -107,16 +112,16 @@ static void add_work(enum work_type type, char *name, void *id)\n \ttodo_end = (todo_end + 1) % ARRAY_SIZE(todo);\n \n \tpthread_cond_signal(&cond_add);\n-\tpthread_mutex_unlock(&grep_lock);\n+\tgrep_unlock();\n }\n \n static struct work_item *get_work(void)\n {\n \tstruct work_item *ret;\n \n-\tpthread_mutex_lock(&grep_lock);\n+\tgrep_lock();\n \twhile (todo_start == todo_end && !all_work_added) {\n-\t\tpthread_cond_wait(&cond_add, &grep_lock);\n+\t\tpthread_cond_wait(&cond_add, &grep_mutex);\n \t}\n \n \tif (todo_start == todo_end && all_work_added) {\n@@ -125,7 +130,7 @@ static struct work_item *get_work(void)\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+\tgrep_unlock();\n \treturn ret;\n }\n \n@@ -148,7 +153,7 @@ static void work_done(struct work_item *w)\n {\n \tint old_done;\n \n-\tpthread_mutex_lock(&grep_lock);\n+\tgrep_lock();\n \tw->done = 1;\n \told_done = todo_done;\n \tfor(; todo[todo_done].done && todo_done != todo_start;\n@@ -165,7 +170,7 @@ static void work_done(struct work_item *w)\n \tif (all_work_added && todo_done == todo_end)\n \t\tpthread_cond_signal(&cond_result);\n \n-\tpthread_mutex_unlock(&grep_lock);\n+\tgrep_unlock();\n }\n \n static void *run(void *arg)\n@@ -181,11 +186,7 @@ static void *run(void *arg)\n \t\topt->output_priv = w;\n \t\tif (w->type == WORK_SHA1) {\n \t\t\tunsigned long sz;\n-\t\t\tvoid* data;\n-\n-\t\t\tpthread_mutex_lock(&read_sha1_lock);\n-\t\t\tdata = load_sha1(w->identifier, &sz, w->name);\n-\t\t\tpthread_mutex_unlock(&read_sha1_lock);\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@@ -218,8 +219,8 @@ static void start_threads(struct grep_opt *opt)\n {\n \tint i;\n \n-\tpthread_mutex_init(&grep_lock, NULL);\n-\tpthread_mutex_init(&read_sha1_lock, NULL);\n+\tpthread_mutex_init(&grep_mutex, NULL);\n+\tpthread_mutex_init(&read_sha1_mutex, NULL);\n \tpthread_cond_init(&cond_add, NULL);\n \tpthread_cond_init(&cond_write, NULL);\n \tpthread_cond_init(&cond_result, NULL);\n@@ -246,18 +247,18 @@ static int wait_all(void)\n \tint hit = 0;\n \tint i;\n \n-\tpthread_mutex_lock(&grep_lock);\n+\tgrep_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+\t\tpthread_cond_wait(&cond_result, &grep_mutex);\n \n \t/* Wake up all the consumer threads so they can see that there\n \t * is no more work to do.\n \t */\n \tpthread_cond_broadcast(&cond_add);\n-\tpthread_mutex_unlock(&grep_lock);\n+\tgrep_unlock();\n \n \tfor (i = 0; i < ARRAY_SIZE(threads); i++) {\n \t\tvoid *h;\n@@ -265,8 +266,8 @@ static int wait_all(void)\n \t\thit |= (int) (intptr_t) h;\n \t}\n \n-\tpthread_mutex_destroy(&grep_lock);\n-\tpthread_mutex_destroy(&read_sha1_lock);\n+\tpthread_mutex_destroy(&grep_mutex);\n+\tpthread_mutex_destroy(&read_sha1_mutex);\n \tpthread_cond_destroy(&cond_add);\n \tpthread_cond_destroy(&cond_write);\n \tpthread_cond_destroy(&cond_result);\n@@ -274,6 +275,9 @@ 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@@ -407,7 +411,11 @@ static void *load_sha1(const unsigned char *sha1, unsigned long *size,\n \t\t       const char *name)\n {\n \tenum object_type type;\n-\tchar *data = read_sha1_file(sha1, &type, size);\n+\tchar *data;\n+\n+\tread_sha1_lock();\n+\tdata = read_sha1_file(sha1, &type, size);\n+\tread_sha1_unlock();\n \n \tif (!data)\n \t\terror(\"'%s': unable to read %s\", name, sha1_to_hex(sha1));\n@@ -596,7 +604,10 @@ static int grep_tree(struct grep_opt *opt, const char **paths,\n \t\t\tvoid *data;\n \t\t\tunsigned long size;\n \n+\t\t\tread_sha1_lock();\n \t\t\tdata = read_sha1_file(entry.sha1, &type, &size);\n+\t\t\tread_sha1_unlock();\n+\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"},{"id":"132672","messageId":"4c8ef71001260410l2afd2dbx17b6e216bd9e5d8@mail.gmail.com","threadId":"22391","inReplyTo":"alpine.LFD.2.00.1001251542100.3574@localhost.localdomain","subject":"Re: [PATCH v4] Threaded grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2010-01-26T12:10:50Z","receivedAt":"2010-01-26T12:10:50Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Tue, Jan 26, 2010 at 00:59, Linus Torvalds\n<torvalds@linux-foundation.org> wrote:\n> The profile for the threaded case says:\n>\n>    51.73%      git  libc-2.11.1.so                 [.] re_search_internal\n>    11.47%      git  [kernel]                       [k] copy_user_generic_string\n>     2.90%      git  libc-2.11.1.so                 [.] __strlen_sse2\n>     2.66%      git  [kernel]                       [k] link_path_walk\n>     2.55%      git  [kernel]                       [k] intel_pmu_enable_all\n>     2.40%      git  [kernel]                       [k] __d_lookup\n>     1.71%      git  libc-2.11.1.so                 [.] __GI___libc_malloc\n>     1.55%      git  [kernel]                       [k] _raw_spin_lock\n>     1.43%      git  [kernel]                       [k] sys_futex\n>     1.30%      git  libc-2.11.1.so                 [.] __cfree\n>     1.28%      git  [kernel]                       [k] intel_pmu_disable_all\n>     1.25%      git  libc-2.11.1.so                 [.] __GI_memchr\n>     1.14%      git  libc-2.11.1.so                 [.] _int_malloc\n>     1.02%      git  [kernel]                       [k] effective_load\n>\n> and the only thing that makes me go \"eh?\" there is the strlen(). Why is\n> that so hot?  But locking doesn't seem to be the biggest issue, and in\n> general I think this is all pretty good. The 'effective_load' thing is the\n> scheduler, so there's certainly some context switching going on, probably\n> still due to excessive synchronization, but it's equally clear that that\n> is certainly not a dominant factor.\n\nI see the strlen in my profiles as well, but I haven't figured out\nwhere it comes from. I get the following:\n\n    51.16%  git-grep  /lib/tls/i686/cmov/libc-2.10.1.so\n[.] 0x000000000b14c6\n    10.12%  git-grep  /lib/tls/i686/cmov/libc-2.10.1.so\n[.] __GI_strlen\n     9.27%  git-grep  [kernel]\n[k] __copy_to_user_ll\n     4.68%  git-grep  /lib/tls/i686/cmov/libc-2.10.1.so\n[.] __memchr\n     1.72%  git-grep  [kernel]\n[k] __d_lookup\n     1.18%  git-grep  /lib/i686/cmov/libcrypto.so.0.9.8\n[.] sha1_block_asm_data_order\n     1.11%  git-grep  [kernel]\n[k] __ticket_spin_lock\n     0.84%  git-grep  [vdso]\n[.] 0x00000000b6c422\n\nIf I use perf record -g I get\n\n    10.39%  git-grep  /lib/tls/i686/cmov/libc-2.10.1.so\n[.] __GI_strlen\n                |\n                |--99.05%-- look_ahead\n                |          grep_buffer_1\n                |          grep_buffer\n                |          run\n                |          start_thread\n                |          __clone\n                |\n                |--0.64%-- grep_file\n                |          grep_cache\n                |          cmd_grep\n                |          run_builtin\n                |          handle_internal_command\n                |          main\n                |          __libc_start_main\n                |          0x804ae81\n                 --0.32%-- [...]\n\nThis doesn't make much sense to me as look_ahead doesn't call strlen\n(I compiled git with -O0 to avoid any issues with inlined functions).\nBut I haven't used perf so much, so maybe I'm reading the output the\nwrong way.\n\n> One potentially interesting data point is that if I make NR_THREADS be 16,\n> performance goes down, and I get more locking overhead. So NR_THREADS of 8\n> works well on this machine.\n\nInteresting. I get the best results with 8 threads as well, but I only\nhave two cores.\n\n> One worry is, of course, whether all regex() implementations are\n> thread-safe. Maybe there are broken libraries that have hidden global\n> state in them?\n\nThat would certainly be a problem. A quick google search didn't show\nany known bugs. Of course, this doesn't tell us anything about the\nunknown ones.\n\n- Fredrik\n"},{"id":"132679","messageId":"alpine.LFD.2.00.1001260728260.3574@localhost.localdomain","threadId":"22391","inReplyTo":"4c8ef71001260410l2afd2dbx17b6e216bd9e5d8@mail.gmail.com","subject":"Re: [PATCH v4] Threaded grep","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2010-01-26T15:28:41Z","receivedAt":"2010-01-26T15:28:41Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOn Tue, 26 Jan 2010, Fredrik Kuivinen wrote:\n> \n> I see the strlen in my profiles as well, but I haven't figured out\n> where it comes from.\n\nLooks like this in gdb:\n\n#0  0x0000003e3687f2e0 in __strlen_sse2 () from /lib64/libc.so.6\n#1  0x0000003e368c04c5 in regexec@@GLIBC_2.3.4 () from /lib64/libc.so.6\n#2  0x000000000047677a in look_ahead (opt=<value optimized out>, \n    name=<value optimized out>, buf=<value optimized out>, \n    size=<value optimized out>, collect_hits=<value optimized out>)\n    at grep.c:679\n#3  grep_buffer_1 (opt=<value optimized out>, name=<value optimized out>, \n    buf=<value optimized out>, size=<value optimized out>, \n    collect_hits=<value optimized out>) at grep.c:790\n\nso it's sadly internal to regex. It would be nice if there was a \nnon-string interface to regexec (ie a \"buffer + length\" instead of a \nNUL-terminated string).\n\n> If I use perf record -g I get\n\nI suspect that libc isn't compiled with frame pointers, so call chains end \nup being unreliable.\n\n\t\tLinus\n"},{"id":"132694","messageId":"4B5F1894.4070509@googlemail.com","threadId":"22391","inReplyTo":"alpine.LFD.2.00.1001260728260.3574@localhost.localdomain","subject":"Re: [PATCH v4] Threaded grep","fromName":"Benjamin Kramer","fromEmail":"benny.kra@googlemail.com","sentAt":"2010-01-26T16:30:12Z","receivedAt":"2010-01-26T16:30:12Z","isPatch":true,"sender":{"key":"benny.kra@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/16542?v=4"},"body":"BSD and glibc have an extension to regexec which takes a buffer + length pair\ninstead of a NUL-terminated string. Since we already have the length\ncomputed this can save us a strlen call.\n---\n\nOn 26.01.10 16:28, Linus Torvalds wrote:\n> so it's sadly internal to regex. It would be nice if there was a \n> non-string interface to regexec (ie a \"buffer + length\" instead of a \n> NUL-terminated string).\n\nBSD and glibc have an \"REG_STARTEND\" flag to do that. I made a small\nPoC patch to use it if it's available but it didn't give any significant\nspeedup on my system.\n\n\n\n grep.c |    9 ++++++++-\n 1 files changed, 8 insertions(+), 1 deletions(-)\n\ndiff --git a/grep.c b/grep.c\nindex d281a02..60cce46 100644\n--- a/grep.c\n+++ b/grep.c\n@@ -675,8 +675,15 @@ static int look_ahead(struct grep_opt *opt,\n \n \t\tif (p->fixed)\n \t\t\thit = !fixmatch(p->pattern, bol, p->ignore_case, &m);\n-\t\telse\n+\t\telse {\n+#ifdef REG_STARTEND\n+\t\t\tm.rm_so = 0;\n+\t\t\tm.rm_eo = *left_p;\n+\t\t\thit = !regexec(&p->regexp, bol, 1, &m, REG_STARTEND);\n+#else\n \t\t\thit = !regexec(&p->regexp, bol, 1, &m, 0);\n+#endif\n+\t\t}\n \t\tif (!hit || m.rm_so < 0 || m.rm_eo < 0)\n \t\t\tcontinue;\n \t\tif (earliest < 0 || m.rm_so < earliest)\n--\n1.7.0.rc0.12.gc33c3\n"},{"id":"132695","messageId":"alpine.LFD.2.00.1001260836520.3574@localhost.localdomain","threadId":"22391","inReplyTo":"4B5F1894.4070509@googlemail.com","subject":"Re: [PATCH v4] Threaded grep","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2010-01-26T16:44:12Z","receivedAt":"2010-01-26T16:44:12Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 26 Jan 2010, Benjamin Kramer wrote:\n> \n> BSD and glibc have an \"REG_STARTEND\" flag to do that. I made a small\n> PoC patch to use it if it's available but it didn't give any significant\n> speedup on my system.\n\nGoodie.  It's noticeable for me. This is what I reported earlier:\n\n> > $ /usr/bin/time git grep void\n> \n> Before:\n> \n>         real    0m1.144s\n>         user    0m0.988s\n>         sys     0m0.148s\n> \n> After:\n>         real    0m0.290s\n>         user    0m1.732s\n>         sys     0m0.232s\n\nand with your patch I get\n\n\treal\t0m0.239s\n\tuser\t0m1.392s\n\tsys\t0m0.276s\n\nand the profile shows no strlen in it:\n\n    57.12%      git  libc-2.11.1.so                 [.] re_search_internal\n     5.59%      git  [kernel]                       [k] copy_user_generic_string\n     4.09%      git  [kernel]                       [k] _raw_spin_lock\n     2.57%      git  [kernel]                       [k] intel_pmu_enable_all\n     2.46%      git  [kernel]                       [k] __d_lookup\n     1.94%      git  libc-2.11.1.so                 [.] re_string_reconstruct\n     1.87%      git  [kernel]                       [k] kmem_cache_alloc\n     1.68%      git  libc-2.11.1.so                 [.] _int_free\n     1.53%      git  [kernel]                       [k] find_get_page\n     1.43%      git  [kernel]                       [k] update_curr\n     1.27%      git  libc-2.11.1.so                 [.] __GI___libc_malloc\n     1.17%      git  [kernel]                       [k] _atomic_dec_and_lock\n     1.00%      git  libc-2.11.1.so                 [.] __GI_memcpy\n\nSide note: the tailing end of the profiles aren't very stable, probably \nbecause the grep executes so quickly and in so many threads, so the \nfunctions in the one-percent range will move up and down the list \ndepending on just exactly where we happened to get profile hits. \nSimilarly, the raw_spin_lock numbers vary.\n\nBut the big picture is stable, and that 57% number (and the nonlock \ncopy_user_generic_string) is consistent. And your patch definitely helped \nboth actual performance and is visible in the profile: re_search_internal \nwent from ~52% to ~57%.\n\nSo ack on that patch. Looks like a good thing to do, and with the #ifdef, \nit looks like it should just automatically DTRT based on regexec \nimplementation.\n\n\t\tLinus\n"},{"id":"132696","messageId":"alpine.LFD.2.00.1001260846330.3574@localhost.localdomain","threadId":"22391","inReplyTo":"alpine.LFD.2.00.1001260836520.3574@localhost.localdomain","subject":"Re: [PATCH v4] Threaded grep","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2010-01-26T16:56:50Z","receivedAt":"2010-01-26T16:56:50Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 26 Jan 2010, Linus Torvalds wrote:\n>\n> Goodie.  It's noticeable for me. This is what I reported earlier:\n> \n> > > $ /usr/bin/time git grep void\n> > \n> > Before:\n> > \n> >         real    0m1.144s\n> > \n> > After:\n> >         real    0m0.290s\n> \n> and with your patch I get\n> \n> \treal\t0m0.239s\n\nBtw, I have to also say that this whole performance reduction _feels_ \ngood. It's very noticeable in normal use. \"git grep\" was always fast (it's \nbeen getting a bit slower as the kernel has grown, though), but it used to \nbe still a noticeable pause.\n\nNow it just -feels- very immediate. That quarter second is short enough \nthat I can see the pause, but I don't feel it. It's like the results just \n\"are there\" rather than get searched for.\n\nBut perhaps even more importantly, it's also noticeable for me in the \ncold-cache case. IOW, after I do\n\n\techo 3 > /proc/sys/vm/drop_caches\n\nthe threaded grep is able to do much better at reading the disk:\n\nBefore threading:\n\n\t[torvalds@nehalem linux]$ time git grep void > /dev/null \n\n\treal\t0m11.745s\n\tuser\t0m2.380s\n\tsys\t0m1.200s\n\nAfter:\n\n\t[torvalds@nehalem linux]$ time ~/git/git grep void > /dev/null \n\n\treal\t0m3.710s\n\tuser\t0m2.564s\n\tsys\t0m2.076s\n\nalthough it is worth noting that that machine has an Intel SSD, which is \nwhy it gets sped up so much by parallel IO (there's no seek penalty, and \nit is able to read multiple channels in parallel, so this gives much \nbetter IO patterns for it - with rotational media the numbers might be \nvery different).\n\nIOW, the whole threaded grep thing is a 4x performance improvement in \nhot-cache, and a 3x improvement in cold-cache.\n\nMajor good mojo.\n\n\t\tLinus\n"},{"id":"132697","messageId":"20100126171900.GA14092@glandium.org","threadId":"22391","inReplyTo":"alpine.LFD.2.00.1001260846330.3574@localhost.localdomain","subject":"Re: [PATCH v4] Threaded grep","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2010-01-26T17:19:00Z","receivedAt":"2010-01-26T17:19:00Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Tue, Jan 26, 2010 at 08:56:50AM -0800, Linus Torvalds wrote:\n<snip>\n> although it is worth noting that that machine has an Intel SSD, which is \n> why it gets sped up so much by parallel IO (there's no seek penalty, and \n> it is able to read multiple channels in parallel, so this gives much \n> better IO patterns for it - with rotational media the numbers might be \n> very different).\n\nFor rotational disks, using FIEMAP to get the position of the files on\ndisk to reorder how we read them could help.\n\nMike\n"},{"id":"132698","messageId":"7vaaw0234o.fsf@alter.siamese.dyndns.org","threadId":"22391","inReplyTo":"20100126114303.GA1854@fredrik-laptop","subject":"Re: [PATCH v4] Threaded grep","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-01-26T17:21:43Z","receivedAt":"2010-01-26T17:21:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen <frekui@gmail.com> writes:\n\n> I just noticed that I forgot to take the read_sha1 lock in\n> grep_tree. The result is a race condition in read_sha1_file.\n>\n> Here is a patch to fix this. It applies on top of ae35c68 (Threaded\n> grep). Could you please squash it in?\n\nThanks; will do.\n"},{"id":"132699","messageId":"4B5F2AF4.2090307@googlemail.com","threadId":"22391","inReplyTo":"alpine.LFD.2.00.1001260846330.3574@localhost.localdomain","subject":"[PATCH] grep: use REG_STARTEND (if available) to speed up regexec","fromName":"Benjamin Kramer","fromEmail":"benny.kra@googlemail.com","sentAt":"2010-01-26T17:48:36Z","receivedAt":"2010-01-26T17:48:36Z","isPatch":true,"sender":{"key":"benny.kra@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/16542?v=4"},"body":"BSD and glibc have an extension to regexec which takes a buffer + length pair\ninstead of a NUL-terminated string. Since we already have the length computed\nthis can save us a strlen call inside regexec.\n\nSigned-off-by: Benjamin Kramer <benny.kra@googlemail.com>\nAcked-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nResend of my previous patch with SOB and correct title.\n\n grep.c |    9 ++++++++-\n 1 files changed, 8 insertions(+), 1 deletions(-)\n\ndiff --git a/grep.c b/grep.c\nindex 8e1f7de..452c2cb 100644\n--- a/grep.c\n+++ b/grep.c\n@@ -640,8 +640,15 @@ static int look_ahead(struct grep_opt *opt,\n \n \t\tif (p->fixed)\n \t\t\thit = !fixmatch(p->pattern, bol, p->ignore_case, &m);\n-\t\telse\n+\t\telse {\n+#ifdef REG_STARTEND\n+\t\t\tm.rm_so = 0;\n+\t\t\tm.rm_eo = *left_p;\n+\t\t\thit = !regexec(&p->regexp, bol, 1, &m, REG_STARTEND);\n+#else\n \t\t\thit = !regexec(&p->regexp, bol, 1, &m, 0);\n+#endif\n+\t\t}\n \t\tif (!hit || m.rm_so < 0 || m.rm_eo < 0)\n \t\t\tcontinue;\n \t\tif (earliest < 0 || m.rm_so < earliest)\n-- \n1.7.0.rc0.12.gc33c3\n"}]}