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

From: René Scharfe <rene.scharfe@lsrfire.ath.cx>
Date: Mar 1, 2009, 18:55 UTC
Message-ID: <49AADA09.6020305@lsrfire.ath.cx>
In-Reply-To: <49AA6E35.40205@lsrfire.ath.cx>

René Scharfe schrieb:

Show 6 quoted lines

> 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;
 	}