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

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

René Scharfe schrieb:
> 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.

More numbers.  "memmem" is the patch I'm replying to which converts
grep's fixed string search from strstr() to memmem().  "quadratic" means
the current version of compat/memmem.c was used (NO_MEMMEM=yes),
"linear" is the same, but with the newer memmem() from Gnulib imported.
 The numbers are elapsed seconds for the following command, run in a
Linux kernel repo:

   git grep grep v2.6.28 >/dev/null

                                   Ubuntu Fedora
   [1] v1.6.2-rc2                    2.99   3.52
   [2] v1.6.2-rc2+memmem             3.09   3.28
   [3] v1.6.2-rc2+memmem+quadratic   8.42   8.50
   [4] v1.6.2-rc2+memmem+linear      3.17   3.25

So, we should be careful when using memmem() as long as we have the
current implementation in compat/, as the quadratic complexity can
result in a significant slowdown ([3]).

The new memmem() indeed is faster than the new strstr(), as expected
(Fedora [2] and [4] vs. Fedora [1]).  Remember, Fedora 10 already
includes the glibc version with the linear implementations while Ubuntu
8.10 doesn't.

I'm not sure if the difference between the old and new memmem() is
significant or in the noise (Ubuntu [2] and [4]).

In any case, and this surprised me, the fastest of them all is the old
strstr() (Ubuntu [1]).  This is consistent with the slowdown observed on
Windows.

What's even more surprising is the difference between Ubuntu [2] and
[3], which use basically the same memmem().  Or so I thought.  Wrong.
The old memmem() in glibc has a small but effective optimization, that
our version lacks.  I don't remember if I cut it out during the initial
import for increased simplicity or if the version the import was based
on didn't have it.  Anyway, with the following patch, case [3] runs as
fast as case [2] on both Fedora and Ubuntu.

Next step would be to check if pickaxe simply needs this short patch or
really the full-blown linear reimplementation.  I'm off to an
appointment, though, so I'll look into this again tomorrow.

René


diff --git a/compat/memmem.c b/compat/memmem.c
index cd0d877..fed5a77 100644
--- a/compat/memmem.c
+++ b/compat/memmem.c
@@ -5,6 +5,7 @@ void *gitmemmem(const void *haystack, size_t haystack_len,
 {
 	const char *begin = haystack;
 	const char *last_possible = begin + haystack_len - needle_len;
+	char tip;
 
 	/*
 	 * The first occurrence of the empty string is deemed to occur at
@@ -20,8 +21,10 @@ void *gitmemmem(const void *haystack, size_t haystack_len,
 	if (haystack_len < needle_len)
 		return NULL;
 
+	tip = *((const char *)needle);
+
 	for (; begin <= last_possible; begin++) {
-		if (!memcmp(begin, needle, needle_len))
+		if (*begin == tip && !memcmp(begin, needle, needle_len))
 			return (void *)begin;
 	}