From ce163c793d2058056ccc57563c350fd6415397ca Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= Date: Tue, 3 Mar 2009 00:00:55 +0100 Subject: diffcore-pickaxe: use memmem() 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 Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano --- diffcore-pickaxe.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) diff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c index af9fffe6e8..574b3e8337 100644 --- a/diffcore-pickaxe.c +++ b/diffcore-pickaxe.c @@ -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); -- cgit v1.2.3 From 56384e61ead8d41c39bfafb535eedcf67ef4fcc3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= Date: Tue, 3 Mar 2009 00:19:30 +0100 Subject: optimize compat/ memmem() 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 Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano --- compat/memmem.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/compat/memmem.c b/compat/memmem.c index cd0d877364..56bcb4277f 100644 --- a/compat/memmem.c +++ b/compat/memmem.c @@ -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; } -- cgit v1.2.3