Re: [PATCH] import memmem() with linear complexity from Gnulib

["René Scharfe" <rene.scharfe@lsrfire.ath.cx>]

Jeff King schrieb:
> On Sat, Feb 28, 2009 at 11:44:01PM +0100, Mike Hommey wrote:
> 
>>> ---
>>>  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;