Re: [PATCH] import memmem() with linear complexity from Gnulib
From: René Scharfe <hidden>
Date: 2016-06-15 22:46:18
Subsystem:
the rest · Maintainer:
Linus Torvalds
Jeff King schrieb:
On Sat, Feb 28, 2009 at 11:44:01PM +0100, Mike Hommey wrote:quoted
quoted
--- Makefile | 1 + compat/memmem.c | 103 +++++++++---- compat/str-two-way.h | 429 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 504 insertions(+), 29 deletions(-)Seeing how much memmem is being used in the codebase, is it really worth?See earlier in the thread, where "git log -Stoken" is substantially faster on Linux versus Windows (but some exact numbers before and after on Windows would be nice to have in the commit message).
Yes, and also please see the other numbers I just posted. It's more of an update -- we took the current memmem() fall-back from glibc, too, and they switched to this shiny new implementation to avoid the quadratic complexity of the old one in the meantime. I was going to say that with a fast memmem() we could convert some strstr() calls, especially those where we know the lengths of the strings anyway -- intuitively, memmem() should be faster than strstr() in that case. However, the following patch on top of the Gnulib import makes "git grep grep v1.6.1" take 10% *more* time for me (on Windows). I wonder why.
diff --git a/grep.c b/grep.c
index 062b2b6..66ef171 100644
--- a/grep.c
+++ b/grep.c@@ -39,6 +39,8 @@ static void compile_regexp(struct grep_pat *p, struct grep_opt *opt) { int err; + p->pattern_len = strlen(p->pattern); + if (opt->fixed || is_fixed(p->pattern)) p->fixed = 1; if (opt->regflags & REG_ICASE)
@@ -268,16 +270,17 @@ static void show_name(struct grep_opt *opt, const char *name) printf("%s%c", name, opt->null_following_name ? '\0' : '\n'); } -static int fixmatch(const char *pattern, char *line, regmatch_t *match) +static int fixmatch(const char *pattern, size_t pattern_len, const char *bol, + const char *eol, regmatch_t *match) { - char *hit = strstr(line, pattern); + char *hit = memmem(bol, eol - bol, pattern, pattern_len); if (!hit) { match->rm_so = match->rm_eo = -1; return REG_NOMATCH; } else { - match->rm_so = hit - line; - match->rm_eo = match->rm_so + strlen(pattern); + match->rm_so = hit - bol; + match->rm_eo = match->rm_so + pattern_len; return 0; } }
@@ -335,7 +338,7 @@ static int match_one_pattern(struct grep_opt *opt, struct grep_pat *p, char *bol pmatch, 0); } else { - hit = !fixmatch(p->pattern, bol, pmatch); + hit = !fixmatch(p->pattern, p->pattern_len, bol, eol, pmatch); } if (hit && opt->word_regexp) {
diff --git a/grep.h b/grep.h
index 5102ce3..2e22ab2 100644
--- a/grep.h
+++ b/grep.h@@ -28,6 +28,7 @@ struct grep_pat { int no; enum grep_pat_token token; const char *pattern; + size_t pattern_len; enum grep_header_field field; regex_t regexp; unsigned fixed:1;