Pickaxe search clean-up and optimization

This little series refactors the diffcore-pickaxe a bit and then optimizes its search for "needle" inside the haystacks.

Junio C Hamano (4):
diffcore-pickaxe: refactor diffcore_pickaxe()
diffcore-pickaxe: micro-optimize has_match() function
diffcore-pickaxe: further refactor count_match()
diffcore-pickaxe: optimize by trimming common initial and trailing
parts

 diffcore-pickaxe.c |  176 +++++++++++++++++++++++++++++++++++-----------------
 1 files changed, 118 insertions(+), 58 deletions(-)

Introduce pickaxe_match_one() to remove duplicated code that decides if a filepair is "interesting enough" for the purpose of pickaxe from the main loop of the function.

---
 diffcore-pickaxe.c |   83 ++++++++++++++++++++++++++-------------------------
 1 files changed, 42 insertions(+), 41 deletions(-)

index af9fffe..d27e725 100644
@@ -5,9 +5,9 @@
 #include "diff.h"
 #include "diffcore.h"
 
-static unsigned int contains(struct diff_filespec *one,
-			     const char *needle, unsigned long len,
-			     regex_t *regexp)
+static unsigned int count_match(struct diff_filespec *one,
+				const char *needle, unsigned long len,
+				regex_t *regexp)
 {
 	unsigned int cnt;
 	unsigned long offset, sz;

@@ -48,6 +48,38 @@ static unsigned int contains(struct diff_filespec *one,
 	return cnt;
 }
 
+static int has_match(struct diff_filespec *one,
+		     const char *needle, unsigned long len,
+		     regex_t *regexp)
+{
+	return !!count_match(one, needle, len, regexp);
+}
+
+static int has_different_matches(struct diff_filepair *p,
+				 const char *needle, unsigned long len,
+				 regex_t *regexp)
+{
+	return (count_match(p->one, needle, len, regexp)
+		!= count_match(p->two, needle, len, regexp));
+
+}
+
+static int pickaxe_match_one(struct diff_filepair *p,
+			     const char *needle, unsigned long len,
+			     regex_t *regexp)
+{
+	if (!DIFF_FILE_VALID(p->one)) {
+		if (!DIFF_FILE_VALID(p->two))
+			return 0;
+		return has_match(p->two, needle, len, regexp);
+	} else if (!DIFF_FILE_VALID(p->two))
+		return has_match(p->one, needle, len, regexp);
+	else if (diff_unmodified_pair(p))
+		return 0;
+	else
+		return has_different_matches(p, needle, len, regexp);
+}
+
 void diffcore_pickaxe(const char *needle, int opts)
 {
 	struct diff_queue_struct *q = &diff_queued_diff;

@@ -75,29 +107,14 @@ void diffcore_pickaxe(const char *needle, int opts)
 		/* Showing the whole changeset if needle exists */
 		for (i = has_changes = 0; !has_changes && i < q->nr; i++) {
 			struct diff_filepair *p = q->queue[i];
-			if (!DIFF_FILE_VALID(p->one)) {
-				if (!DIFF_FILE_VALID(p->two))
-					continue; /* ignore unmerged */
-				/* created */
-				if (contains(p->two, needle, len, regexp))
-					has_changes++;
-			}
-			else if (!DIFF_FILE_VALID(p->two)) {
-				if (contains(p->one, needle, len, regexp))
-					has_changes++;
-			}
-			else if (!diff_unmodified_pair(p) &&
-				 contains(p->one, needle, len, regexp) !=
-				 contains(p->two, needle, len, regexp))
-				has_changes++;
+			if (pickaxe_match_one(p, needle, len, regexp))
+				return; /* not munge the queue */
 		}
-		if (has_changes)
-			return; /* not munge the queue */
 
-		/* otherwise we will clear the whole queue
-		 * by copying the empty outq at the end of this
-		 * function, but first clear the current entries
-		 * in the queue.
+		/*
+		 * otherwise we will clear the whole queue by copying
+		 * the empty outq at the end of this function, but
+		 * first clear the current entries in the queue.
 		 */
 		for (i = 0; i < q->nr; i++)
 			diff_free_filepair(q->queue[i]);

@@ -106,24 +123,8 @@ void diffcore_pickaxe(const char *needle, int opts)
 		/* Showing only the filepairs that has the needle */
 		for (i = 0; i < q->nr; i++) {
 			struct diff_filepair *p = q->queue[i];
-			has_changes = 0;
-			if (!DIFF_FILE_VALID(p->one)) {
-				if (!DIFF_FILE_VALID(p->two))
-					; /* ignore unmerged */
-				/* created */
-				else if (contains(p->two, needle, len, regexp))
-					has_changes = 1;
-			}
-			else if (!DIFF_FILE_VALID(p->two)) {
-				if (contains(p->one, needle, len, regexp))
-					has_changes = 1;
-			}
-			else if (!diff_unmodified_pair(p) &&
-				 contains(p->one, needle, len, regexp) !=
-				 contains(p->two, needle, len, regexp))
-				has_changes = 1;
 
-			if (has_changes)
+			if (pickaxe_match_one(p, needle, len, regexp))
 				diff_q(&outq, p);
 			else
 				diff_free_filepair(p);

1.6.2.rc2.91.gf9a36

When we are looking at an event that creates (or removes) a path, we only need to see if the created (or removed) blob has an instance of the needle we are looking for. There is no need to count, once we know there is one.

---
 diffcore-pickaxe.c |   13 +++++++++----
 1 files changed, 9 insertions(+), 4 deletions(-)

index d27e725..007b39c 100644
@@ -5,7 +5,8 @@
 #include "diff.h"
 #include "diffcore.h"
 
-static unsigned int count_match(struct diff_filespec *one,
+static unsigned int count_match(int one_or_more,
+				struct diff_filespec *one,
 				const char *needle, unsigned long len,
 				regex_t *regexp)
 {

@@ -30,6 +31,8 @@ static unsigned int count_match(struct diff_filespec *one,
 			data += regmatch.rm_so;
 			if (*data) data++;
 			cnt++;
+			if (one_or_more)
+				break;
 		}
 
 	} else { /* Classic exact string match */

@@ -41,6 +44,8 @@ static unsigned int count_match(struct diff_filespec *one,
 			if (!memcmp(needle, data + offset, len)) {
 				offset += len - 1;
 				cnt++;
+				if (one_or_more)
+					break;
 			}
 		}
 	}

@@ -52,15 +57,15 @@ static int has_match(struct diff_filespec *one,
 		     const char *needle, unsigned long len,
 		     regex_t *regexp)
 {
-	return !!count_match(one, needle, len, regexp);
+	return count_match(1, one, needle, len, regexp);
 }
 
 static int has_different_matches(struct diff_filepair *p,
 				 const char *needle, unsigned long len,
 				 regex_t *regexp)
 {
-	return (count_match(p->one, needle, len, regexp)
-		!= count_match(p->two, needle, len, regexp));
+	return (count_match(0, p->one, needle, len, regexp)
+		!= count_match(0, p->two, needle, len, regexp));
 
 }
 

1.6.2.rc2.91.gf9a36

We separate out the part that prepares the blob data to be inspected and the part that does the actual counting in the data.

---
 diffcore-pickaxe.c |   46 +++++++++++++++++++++++++---------------------
 1 files changed, 25 insertions(+), 21 deletions(-)

index 007b39c..4a0dca1 100644
@@ -5,22 +5,13 @@
 #include "diff.h"
 #include "diffcore.h"
 
-static unsigned int count_match(int one_or_more,
-				struct diff_filespec *one,
-				const char *needle, unsigned long len,
-				regex_t *regexp)
+static unsigned int count_match_internal(int one_or_more,
+					 const char *data, unsigned long sz,
+					 const char *needle, unsigned long len,
+					 regex_t *regexp)
 {
-	unsigned int cnt;
-	unsigned long offset, sz;
-	const char *data;
-	if (diff_populate_filespec(one, 0))
-		return 0;
-	if (!len)
-		return 0;
-
-	sz = one->size;
-	data = one->data;
-	cnt = 0;
+	unsigned int cnt = 0;
+	unsigned long offset;
 
 	if (regexp) {
 		regmatch_t regmatch;

@@ -29,16 +20,14 @@ static unsigned int count_match(int one_or_more,
 		while (*data && !regexec(regexp, data, 1, &regmatch, flags)) {
 			flags |= REG_NOTBOL;
 			data += regmatch.rm_so;
-			if (*data) data++;
+			if (*data)
+				data++;
 			cnt++;
 			if (one_or_more)
 				break;
 		}
-
-	} else { /* Classic exact string match */
-		/* Yes, I've heard of strstr(), but the thing is *data may
-		 * not be NUL terminated.  Sue me.
-		 */
+	} else {
+		/* data many not be NUL terminated; we cannot use strstr() */
 		for (offset = 0; offset + len <= sz; offset++) {
 			/* we count non-overlapping occurrences of needle */
 			if (!memcmp(needle, data + offset, len)) {

@@ -49,6 +38,21 @@ static unsigned int count_match(int one_or_more,
 			}
 		}
 	}
+	return cnt;
+}
+
+static unsigned int count_match(int one_or_more,
+				struct diff_filespec *one,
+				const char *needle, unsigned long len,
+				regex_t *regexp)
+{
+	unsigned int cnt;
+	if (diff_populate_filespec(one, 0))
+		return 0;
+	if (!len)
+		return 0;
+	cnt = count_match_internal(one_or_more, one->data, one->size,
+				   needle, len, regexp);
 	diff_free_filespec_data(one);
 	return cnt;
 }

1.6.2.rc2.91.gf9a36

Probably yes, but regexp side is not my code and I never use it, so... ;-)

Thanks; it would be nice to bench this change.

With memmem() patch applied on top of [1-4/4], the same test as described in the commit log message of [4/4] which was:

    $ STRING='Ensure that the real time constraints are schedulable.'
    $ git log -S"$STRING" HEAD -- kernel/sched.c >/dev/null

(Before the patch, best of 5 runs)
5.59user 0.15system 0:05.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+39956minor)pagefaults 0swaps

(After the patch, best of 5 runs)
3.04user 0.17system 0:03.23elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+49697minor)pagefaults 0swaps

The file "kernel/sched.c" has roughly 900 changes applied to it, and over its lifetime, it has grown from 5kB to 9kB in size. I'd expect a larger file may see a bigger performance boost.

(With memmem() patch, best of 5 runs)
2.46user 0.15system 0:02.62elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+49698minor)pagefaults 0swaps

I get this (Ubuntu 8.10 x64, Fedora 10 x64 using the same Linux repo, Windows Vista x64 using a different Linux repo with the same HEAD on NTFS and msysgit, numbers are the elapsed time in seconds, best of five runs):

Ubuntu Fedora Windows

   v1.6.2-rc2                8.14    8.16    9.236
   v1.6.2-rc2+[1-4]          2.43    2.45    2.995
   v1.6.2-rc2+[1-4]+memmem   1.31    1.25    2.917
   v1.6.2-rc2+[1-3]+memmem   1.51    1.16    8.455

Ubuntu has glibc 2.8, while Fedora 10 has glibc 2.9, with a new and more efficient memmem() implementation. On Windows, we use our own naive memmem() implementation.

So using memmem() is worthwhile. And providing a better fall-back version in compat/ can speed up this particular case to the point where the fourth patch becomes moot.

Hmm, gnulib (http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=summary)
contains all parts ready for copy & paste, licensed under the GPL 2 or up. That won't cause problems with the libgit2 relicensing effort, as memmem() won't end up in there, right?

For the record, here the raw timings used to make the table above (best of five):

Fedora 10:
8.10user 0.05system 0:08.16elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+31943minor)pagefaults 0swaps

2.38user 0.06system 0:02.45elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+41294minor)pagefaults 0swaps

1.19user 0.05system 0:01.25elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+39274minor)pagefaults 0swaps

1.10user 0.05system 0:01.16elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+31796minor)pagefaults 0swaps

Ubuntu 8.10:
8.08user 0.05system 0:08.14elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+29579minor)pagefaults 0swaps

2.35user 0.07system 0:02.43elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+40437minor)pagefaults 0swaps

1.23user 0.08system 0:01.31elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+41097minor)pagefaults 0swaps

1.46user 0.05system 0:01.51elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+30533minor)pagefaults 0swaps

Windows:

real    0m9.236s
user    0m0.000s
sys     0m0.000s

real    0m2.995s
user    0m0.000s
sys     0m0.000s

real    0m2.917s
user    0m0.000s
sys     0m0.015s

real    0m8.455s
user    0m0.000s
sys     0m0.000s

Shoot, I was not being careful enough.

Are these numbers telling me that with a good memmem() implementation, patch 4/4 is not just moot but actively detrimental?

With a long enough needle, it entirely is possible that scanning the whole image with sublinear string search algorithm would perform much better than the preprocessing patch 4/4 does which has to scan all the bytes in the common parts.

Correction: On Windows, we use the previous, quadratic, naive memmem() implementation from glibc, not anything we came up with.

Yes, patch 4 makes it go slower than using memmem() alone, in this test.

Here are a few more numbers, all measured on Windows. The topmost four times in the column "long" should be the same as in the Windows column above, yet they are slightly bigger. Some background process must've decided to do some work.

git log -S"$STRING" HEAD -- kernel/sched.c >/dev/null

short: STRING='e'
long: STRING='Ensure that the real time constraints are schedulable.'

                                  short  long
  v1.6.2-rc2                      9.120  9.266
  v1.6.2-rc2+[1-4]                3.037  3.048
  v1.6.2-rc2+[1-4]+memmem         2.994  2.964
  v1.6.2-rc2+[1-3]+memmem         8.514  8.528
  v1.6.2-rc2+[1-4]+memmem+linear  1.939  1.759
  v1.6.2-rc2+[1-3]+memmem+linear  2.315  1.559

So patch 4 helps significantly with short needles, while it hurts a bit with long needles. Linear memmem() is faster than the quadratic one we currently have in compat/ in all cases.

René

Yeah, what does glibc use these days? Some variant of Boyer-Moore?

Correct.

Gnulib and glibc have gained a memmem() implementation using the Two-Way algorithm, which needs constant space and linear time. Import it to compat/ in order to replace the simple quadratic implementation there.

memmem.c and str-two-way.h are copied verbatim from the repository at
git://git.savannah.gnu.org/gnulib.git, with the following changes to memmem.c to make it fit into git's build environment:

	21,23c21
	< #ifndef _LIBC
	< # include <config.h>
	< #endif
	---
	> #include "../git-compat-util.h"
	40c38
	< memmem (const void *haystack_start, size_t haystack_len,
	---
	> gitmemmem(const void *haystack_start, size_t haystack_len,

---
 Makefile             |    1 +
 compat/memmem.c      |  103 +++++++++----
 compat/str-two-way.h |  429 ++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 504 insertions(+), 29 deletions(-)
 rewrite compat/memmem.c (91%)
 create mode 100644 compat/str-two-way.h

index 0675c43..b2b15d9 100644
@@ -359,6 +359,7 @@ LIB_H += cache-tree.h
 LIB_H += commit.h
 LIB_H += compat/cygwin.h
 LIB_H += compat/mingw.h
+LIB_H += compat/str-two-way.h
 LIB_H += csum-file.h
 LIB_H += decorate.h
 LIB_H += delta.h

1.6.2.rc2

Seeing how much memmem is being used in the codebase, is it really worth?

Mike

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).

-Peff

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.

index 062b2b6..66ef171 100644
@@ -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) {

index 5102ce3..2e22ab2 100644
@@ -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;

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é

index cd0d877..fed5a77 100644
@@ -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;
 	}
 

No, the algorithm is called Two Way, which, unlike Boyer-Moore, only needs constant space. The implementation seems to originate from this bug:

	http://sourceware.org/bugzilla/show_bug.cgi?id=5514

And the algorithm is documented here:

	http://www-igm.univ-mlv.fr/~lecroq/string/node26.html

René

We can optimize the pickaxe search by removing the lines at the beginning and at the end that are common between the preimage and the postimage, and counting the occurrences of the "needle" in the haystack that is now made smaller.

One thing that we need to be careful about is that we should not remove the common part in full. We need to keep at least the same length as the "needle" from the common part, so that we can detect the differences in a case like this:

preimage: common part then needle appears in this file
postimage: common part then needlX appears in this file

If we literally remove the common leading part up to "needl" and start counting from the byte after that, we will miss that preimage has an occurrence of "needle" but postimage does not.

With this optimization in place, the following query in the Linux kernel repository on my machine becomes about 40% faster:

$ STRING='Ensure that the real time constraints are schedulable.'
$ git log -S"$STRING" HEAD -- kernel/sched.c >/dev/null

(Before the patch, best of 5 runs)
5.59user 0.15system 0:05.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+39956minor)pagefaults 0swaps

(After the patch, best of 5 runs)
3.04user 0.17system 0:03.23elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+49697minor)pagefaults 0swaps

---
 diffcore-pickaxe.c |   54 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 52 insertions(+), 2 deletions(-)

index 4a0dca1..b447d75 100644
@@ -68,9 +68,59 @@ static int has_different_matches(struct diff_filepair *p,
 				 const char *needle, unsigned long len,
 				 regex_t *regexp)
 {
-	return (count_match(0, p->one, needle, len, regexp)
-		!= count_match(0, p->two, needle, len, regexp));
+	const char *one, *two;
+	unsigned long one_size, two_size, common, trim;
+	int differs;
 
+	if (regexp)
+		return (count_match(0, p->one, needle, len, regexp)
+			!= count_match(0, p->two, needle, len, regexp));
+	if (diff_populate_filespec(p->one, 0) ||
+	    diff_populate_filespec(p->two, 0))
+		return 0;
+
+	one = p->one->data;
+	two = p->two->data;
+	one_size = p->one->size;
+	two_size = p->two->size;
+	common = (one_size < two_size) ? one_size : two_size;
+
+	/* Skip the initial common part */
+	for (trim = 0;
+	     trim < common && one[trim] == two[trim];
+	     trim++)
+		;
+
+	/* Start comparing at (len-1) bytes before the first difference */
+	if (len <= trim) {
+		trim -= len;
+		one += trim;
+		two += trim;
+		common -= trim;
+		one_size -= trim;
+		two_size -= trim;
+	}
+
+	/* Trim the common part at the end */
+	for (trim = 0;
+	     trim < common && one[one_size - trim - 1] == two[two_size - trim - 1];
+	     trim++)
+		;
+
+	/* Leave (len-1) bytes */
+	if (len <= trim) {
+		trim -= len;
+		one_size -= trim;
+		two_size -= trim;
+	}
+
+	differs = (count_match_internal(0, one, one_size, needle, len, regexp) !=
+		   count_match_internal(0, two, two_size, needle, len, regexp));
+
+	diff_free_filespec_data(p->one);
+	diff_free_filespec_data(p->two);
+
+	return differs;
 }
 
 static int pickaxe_match_one(struct diff_filepair *p,

1.6.2.rc2.91.gf9a36

The file "kernel/sched.c" has roughly 900 changes applied to it, and over its lifetime, it has grown from 5kB to 9kB in size.

I suspect a larger file might see a bigger performance boost.

Use memmem() instead of open-coding it. The system libraries usually have a much faster version than the memcmp()-loop here. Even our own fall-back in compat/, which is used on Windows, is slightly faster.

The following commands were run in a Linux kernel repository and timed, the best of five results is shown:

  $ STRING='Ensure that the real time constraints are schedulable.'
  $ git log -S"$STRING" HEAD -- kernel/sched.c >/dev/null

On Ubuntu 8.10 x64, before (v1.6.2-rc2):

8.09user 0.04system 0:08.14elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+30952minor)pagefaults 0swaps

And with the patch:

1.50user 0.04system 0:01.54elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+30645minor)pagefaults 0swaps

On Fedora 10 x64, before:

8.34user 0.05system 0:08.39elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+29268minor)pagefaults 0swaps

And with the patch:

1.15user 0.05system 0:01.20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+32253minor)pagefaults 0swaps

On Windows Vista x64, before:

  real    0m9.204s
  user    0m0.000s
  sys     0m0.000s

And with the patch:

  real    0m8.470s
  user    0m0.000s
  sys     0m0.000s

---
 diffcore-pickaxe.c |   18 ++++++++----------
 1 files changed, 8 insertions(+), 10 deletions(-)

index af9fffe..574b3e8 100644
@@ -10,7 +10,7 @@ static unsigned int contains(struct diff_filespec *one,
 			     regex_t *regexp)
 {
 	unsigned int cnt;
-	unsigned long offset, sz;
+	unsigned long sz;
 	const char *data;
 	if (diff_populate_filespec(one, 0))
 		return 0;

@@ -33,15 +33,13 @@ static unsigned int contains(struct diff_filespec *one,
 		}
 
 	} else { /* Classic exact string match */
-		/* Yes, I've heard of strstr(), but the thing is *data may
-		 * not be NUL terminated.  Sue me.
-		 */
-		for (offset = 0; offset + len <= sz; offset++) {
-			/* we count non-overlapping occurrences of needle */
-			if (!memcmp(needle, data + offset, len)) {
-				offset += len - 1;
-				cnt++;
-			}
+		while (sz) {
+			const char *found = memmem(data, sz, needle, len);
+			if (!found)
+				break;
+			sz -= found - data + len;
+			data = found + len;
+			cnt++;
 		}
 	}
 	diff_free_filespec_data(one);

1.6.2.rc2

When memmem() was imported from glibc 2.2 into compat/, an optimization was dropped in the process, in order to make the code smaller and simpler. It was OK because memmem() wasn't used in performance-critical code. Now the situation has changed and we can benefit from this optimization.

The trick is to avoid calling memcmp() if the first character of the needle already doesn't match. Checking one character directly is much cheaper than the function call overhead. We keep the first character of the needle in the variable named point and the rest in the one named tail.

The following commands were run in a Linux kernel repository and timed, the best of five results is shown:

  $ STRING='Ensure that the real time constraints are schedulable.'
  $ git log -S"$STRING" HEAD -- kernel/sched.c >/dev/null

On Windows Vista x64, before:

  real    0m8.470s
  user    0m0.000s
  sys     0m0.000s

And after the patch:

  real    0m1.887s
  user    0m0.000s
  sys     0m0.000s

---
This performance fix is a good idea, even if we later decide to import the latest version of memmem() from Gnulib, I think. And I'm not so sure any more that we want to do that in the first place. More measurements are needed (which goes for these two patches, too, of course), but this version should provide a better baseline.

 compat/memmem.c |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

index cd0d877..56bcb42 100644
@@ -5,6 +5,8 @@ void *gitmemmem(const void *haystack, size_t haystack_len,
 {
 	const char *begin = haystack;
 	const char *last_possible = begin + haystack_len - needle_len;
+	const char *tail = needle;
+	char point;
 
 	/*
 	 * The first occurrence of the empty string is deemed to occur at

@@ -20,8 +22,9 @@ void *gitmemmem(const void *haystack, size_t haystack_len,
 	if (haystack_len < needle_len)
 		return NULL;
 
+	point = *tail++;
 	for (; begin <= last_possible; begin++) {
-		if (!memcmp(begin, needle, needle_len))
+		if (*begin == point && !memcmp(begin + 1, tail, needle_len - 1))
 			return (void *)begin;
 	}
 

1.6.2.rc2