{"thread":{"id":"18027","subject":"[PATCH 0/4] Pickaxe search clean-up and optimization","startedAt":"2009-02-26T06:52:02Z","lastAt":"2009-03-02T23:19:30Z","messageCount":23,"participants":["Junio C Hamano","Kjetil Barvik","René Scharfe","Mike Hommey","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"106291","messageId":"cover.1235629933.git.gitster@pobox.com","threadId":"18027","inReplyTo":null,"subject":"[PATCH 0/4] Pickaxe search clean-up and optimization","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-26T06:52:02Z","receivedAt":"2009-02-26T06:52:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This little series refactors the diffcore-pickaxe a bit and then optimizes\nits search for \"needle\" inside the haystacks.\n\nJunio C Hamano (4):\n  diffcore-pickaxe: refactor diffcore_pickaxe()\n  diffcore-pickaxe: micro-optimize has_match() function\n  diffcore-pickaxe: further refactor count_match()\n  diffcore-pickaxe: optimize by trimming common initial and trailing\n    parts\n\n diffcore-pickaxe.c |  176 +++++++++++++++++++++++++++++++++++-----------------\n 1 files changed, 118 insertions(+), 58 deletions(-)\n"},{"id":"106292","messageId":"4b1358cc6558ec05a134431b603e4781b42deabd.1235629933.git.gitster@pobox.com","threadId":"18027","inReplyTo":"cover.1235629933.git.gitster@pobox.com","subject":"[PATCH 1/4] diffcore-pickaxe: refactor diffcore_pickaxe()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-26T06:52:03Z","receivedAt":"2009-02-26T06:52:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Introduce pickaxe_match_one() to remove duplicated code that decides if a\nfilepair is \"interesting enough\" for the purpose of pickaxe from the main\nloop of the function.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n diffcore-pickaxe.c |   83 ++++++++++++++++++++++++++-------------------------\n 1 files changed, 42 insertions(+), 41 deletions(-)\n\ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nindex af9fffe..d27e725 100644\n--- a/diffcore-pickaxe.c\n+++ b/diffcore-pickaxe.c\n@@ -5,9 +5,9 @@\n #include \"diff.h\"\n #include \"diffcore.h\"\n \n-static unsigned int contains(struct diff_filespec *one,\n-\t\t\t     const char *needle, unsigned long len,\n-\t\t\t     regex_t *regexp)\n+static unsigned int count_match(struct diff_filespec *one,\n+\t\t\t\tconst char *needle, unsigned long len,\n+\t\t\t\tregex_t *regexp)\n {\n \tunsigned int cnt;\n \tunsigned long offset, sz;\n@@ -48,6 +48,38 @@ static unsigned int contains(struct diff_filespec *one,\n \treturn cnt;\n }\n \n+static int has_match(struct diff_filespec *one,\n+\t\t     const char *needle, unsigned long len,\n+\t\t     regex_t *regexp)\n+{\n+\treturn !!count_match(one, needle, len, regexp);\n+}\n+\n+static int has_different_matches(struct diff_filepair *p,\n+\t\t\t\t const char *needle, unsigned long len,\n+\t\t\t\t regex_t *regexp)\n+{\n+\treturn (count_match(p->one, needle, len, regexp)\n+\t\t!= count_match(p->two, needle, len, regexp));\n+\n+}\n+\n+static int pickaxe_match_one(struct diff_filepair *p,\n+\t\t\t     const char *needle, unsigned long len,\n+\t\t\t     regex_t *regexp)\n+{\n+\tif (!DIFF_FILE_VALID(p->one)) {\n+\t\tif (!DIFF_FILE_VALID(p->two))\n+\t\t\treturn 0;\n+\t\treturn has_match(p->two, needle, len, regexp);\n+\t} else if (!DIFF_FILE_VALID(p->two))\n+\t\treturn has_match(p->one, needle, len, regexp);\n+\telse if (diff_unmodified_pair(p))\n+\t\treturn 0;\n+\telse\n+\t\treturn has_different_matches(p, needle, len, regexp);\n+}\n+\n void diffcore_pickaxe(const char *needle, int opts)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n@@ -75,29 +107,14 @@ void diffcore_pickaxe(const char *needle, int opts)\n \t\t/* Showing the whole changeset if needle exists */\n \t\tfor (i = has_changes = 0; !has_changes && i < q->nr; i++) {\n \t\t\tstruct diff_filepair *p = q->queue[i];\n-\t\t\tif (!DIFF_FILE_VALID(p->one)) {\n-\t\t\t\tif (!DIFF_FILE_VALID(p->two))\n-\t\t\t\t\tcontinue; /* ignore unmerged */\n-\t\t\t\t/* created */\n-\t\t\t\tif (contains(p->two, needle, len, regexp))\n-\t\t\t\t\thas_changes++;\n-\t\t\t}\n-\t\t\telse if (!DIFF_FILE_VALID(p->two)) {\n-\t\t\t\tif (contains(p->one, needle, len, regexp))\n-\t\t\t\t\thas_changes++;\n-\t\t\t}\n-\t\t\telse if (!diff_unmodified_pair(p) &&\n-\t\t\t\t contains(p->one, needle, len, regexp) !=\n-\t\t\t\t contains(p->two, needle, len, regexp))\n-\t\t\t\thas_changes++;\n+\t\t\tif (pickaxe_match_one(p, needle, len, regexp))\n+\t\t\t\treturn; /* not munge the queue */\n \t\t}\n-\t\tif (has_changes)\n-\t\t\treturn; /* not munge the queue */\n \n-\t\t/* otherwise we will clear the whole queue\n-\t\t * by copying the empty outq at the end of this\n-\t\t * function, but first clear the current entries\n-\t\t * in the queue.\n+\t\t/*\n+\t\t * otherwise we will clear the whole queue by copying\n+\t\t * the empty outq at the end of this function, but\n+\t\t * first clear the current entries in the queue.\n \t\t */\n \t\tfor (i = 0; i < q->nr; i++)\n \t\t\tdiff_free_filepair(q->queue[i]);\n@@ -106,24 +123,8 @@ void diffcore_pickaxe(const char *needle, int opts)\n \t\t/* Showing only the filepairs that has the needle */\n \t\tfor (i = 0; i < q->nr; i++) {\n \t\t\tstruct diff_filepair *p = q->queue[i];\n-\t\t\thas_changes = 0;\n-\t\t\tif (!DIFF_FILE_VALID(p->one)) {\n-\t\t\t\tif (!DIFF_FILE_VALID(p->two))\n-\t\t\t\t\t; /* ignore unmerged */\n-\t\t\t\t/* created */\n-\t\t\t\telse if (contains(p->two, needle, len, regexp))\n-\t\t\t\t\thas_changes = 1;\n-\t\t\t}\n-\t\t\telse if (!DIFF_FILE_VALID(p->two)) {\n-\t\t\t\tif (contains(p->one, needle, len, regexp))\n-\t\t\t\t\thas_changes = 1;\n-\t\t\t}\n-\t\t\telse if (!diff_unmodified_pair(p) &&\n-\t\t\t\t contains(p->one, needle, len, regexp) !=\n-\t\t\t\t contains(p->two, needle, len, regexp))\n-\t\t\t\thas_changes = 1;\n \n-\t\t\tif (has_changes)\n+\t\t\tif (pickaxe_match_one(p, needle, len, regexp))\n \t\t\t\tdiff_q(&outq, p);\n \t\t\telse\n \t\t\t\tdiff_free_filepair(p);\n-- \n1.6.2.rc2.91.gf9a36\n"},{"id":"106294","messageId":"2dbd5fcdfd9da5f8fbbab5b0928b361d8119c97b.1235629933.git.gitster@pobox.com","threadId":"18027","inReplyTo":"cover.1235629933.git.gitster@pobox.com","subject":"[PATCH 2/4] diffcore-pickaxe: micro-optimize has_match() function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-26T06:52:04Z","receivedAt":"2009-02-26T06:52:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When we are looking at an event that creates (or removes) a path, we only\nneed to see if the created (or removed) blob has an instance of the needle\nwe are looking for.  There is no need to count, once we know there is one.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n diffcore-pickaxe.c |   13 +++++++++----\n 1 files changed, 9 insertions(+), 4 deletions(-)\n\ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nindex d27e725..007b39c 100644\n--- a/diffcore-pickaxe.c\n+++ b/diffcore-pickaxe.c\n@@ -5,7 +5,8 @@\n #include \"diff.h\"\n #include \"diffcore.h\"\n \n-static unsigned int count_match(struct diff_filespec *one,\n+static unsigned int count_match(int one_or_more,\n+\t\t\t\tstruct diff_filespec *one,\n \t\t\t\tconst char *needle, unsigned long len,\n \t\t\t\tregex_t *regexp)\n {\n@@ -30,6 +31,8 @@ static unsigned int count_match(struct diff_filespec *one,\n \t\t\tdata += regmatch.rm_so;\n \t\t\tif (*data) data++;\n \t\t\tcnt++;\n+\t\t\tif (one_or_more)\n+\t\t\t\tbreak;\n \t\t}\n \n \t} else { /* Classic exact string match */\n@@ -41,6 +44,8 @@ static unsigned int count_match(struct diff_filespec *one,\n \t\t\tif (!memcmp(needle, data + offset, len)) {\n \t\t\t\toffset += len - 1;\n \t\t\t\tcnt++;\n+\t\t\t\tif (one_or_more)\n+\t\t\t\t\tbreak;\n \t\t\t}\n \t\t}\n \t}\n@@ -52,15 +57,15 @@ static int has_match(struct diff_filespec *one,\n \t\t     const char *needle, unsigned long len,\n \t\t     regex_t *regexp)\n {\n-\treturn !!count_match(one, needle, len, regexp);\n+\treturn count_match(1, one, needle, len, regexp);\n }\n \n static int has_different_matches(struct diff_filepair *p,\n \t\t\t\t const char *needle, unsigned long len,\n \t\t\t\t regex_t *regexp)\n {\n-\treturn (count_match(p->one, needle, len, regexp)\n-\t\t!= count_match(p->two, needle, len, regexp));\n+\treturn (count_match(0, p->one, needle, len, regexp)\n+\t\t!= count_match(0, p->two, needle, len, regexp));\n \n }\n \n-- \n1.6.2.rc2.91.gf9a36\n"},{"id":"106295","messageId":"cd73512d11e63554396983ed4e9556b2d18b3e4a.1235629933.git.gitster@pobox.com","threadId":"18027","inReplyTo":"cover.1235629933.git.gitster@pobox.com","subject":"[PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-26T06:52:05Z","receivedAt":"2009-02-26T06:52:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"We separate out the part that prepares the blob data to be inspected and\nthe part that does the actual counting in the data.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n diffcore-pickaxe.c |   46 +++++++++++++++++++++++++---------------------\n 1 files changed, 25 insertions(+), 21 deletions(-)\n\ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nindex 007b39c..4a0dca1 100644\n--- a/diffcore-pickaxe.c\n+++ b/diffcore-pickaxe.c\n@@ -5,22 +5,13 @@\n #include \"diff.h\"\n #include \"diffcore.h\"\n \n-static unsigned int count_match(int one_or_more,\n-\t\t\t\tstruct diff_filespec *one,\n-\t\t\t\tconst char *needle, unsigned long len,\n-\t\t\t\tregex_t *regexp)\n+static unsigned int count_match_internal(int one_or_more,\n+\t\t\t\t\t const char *data, unsigned long sz,\n+\t\t\t\t\t const char *needle, unsigned long len,\n+\t\t\t\t\t regex_t *regexp)\n {\n-\tunsigned int cnt;\n-\tunsigned long offset, sz;\n-\tconst char *data;\n-\tif (diff_populate_filespec(one, 0))\n-\t\treturn 0;\n-\tif (!len)\n-\t\treturn 0;\n-\n-\tsz = one->size;\n-\tdata = one->data;\n-\tcnt = 0;\n+\tunsigned int cnt = 0;\n+\tunsigned long offset;\n \n \tif (regexp) {\n \t\tregmatch_t regmatch;\n@@ -29,16 +20,14 @@ static unsigned int count_match(int one_or_more,\n \t\twhile (*data && !regexec(regexp, data, 1, &regmatch, flags)) {\n \t\t\tflags |= REG_NOTBOL;\n \t\t\tdata += regmatch.rm_so;\n-\t\t\tif (*data) data++;\n+\t\t\tif (*data)\n+\t\t\t\tdata++;\n \t\t\tcnt++;\n \t\t\tif (one_or_more)\n \t\t\t\tbreak;\n \t\t}\n-\n-\t} else { /* Classic exact string match */\n-\t\t/* Yes, I've heard of strstr(), but the thing is *data may\n-\t\t * not be NUL terminated.  Sue me.\n-\t\t */\n+\t} else {\n+\t\t/* data many not be NUL terminated; we cannot use strstr() */\n \t\tfor (offset = 0; offset + len <= sz; offset++) {\n \t\t\t/* we count non-overlapping occurrences of needle */\n \t\t\tif (!memcmp(needle, data + offset, len)) {\n@@ -49,6 +38,21 @@ static unsigned int count_match(int one_or_more,\n \t\t\t}\n \t\t}\n \t}\n+\treturn cnt;\n+}\n+\n+static unsigned int count_match(int one_or_more,\n+\t\t\t\tstruct diff_filespec *one,\n+\t\t\t\tconst char *needle, unsigned long len,\n+\t\t\t\tregex_t *regexp)\n+{\n+\tunsigned int cnt;\n+\tif (diff_populate_filespec(one, 0))\n+\t\treturn 0;\n+\tif (!len)\n+\t\treturn 0;\n+\tcnt = count_match_internal(one_or_more, one->data, one->size,\n+\t\t\t\t   needle, len, regexp);\n \tdiff_free_filespec_data(one);\n \treturn cnt;\n }\n-- \n1.6.2.rc2.91.gf9a36\n"},{"id":"106293","messageId":"30c0d4d9b64924679c9af00796f7e0b562020ddf.1235629933.git.gitster@pobox.com","threadId":"18027","inReplyTo":"cover.1235629933.git.gitster@pobox.com","subject":"[PATCH 4/4] diffcore-pickaxe: optimize by trimming common initial and trailing parts","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-26T06:52:06Z","receivedAt":"2009-02-26T06:52:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"We can optimize the pickaxe search by removing the lines at the beginning\nand at the end that are common between the preimage and the postimage, and\ncounting the occurrences of the \"needle\" in the haystack that is now made\nsmaller.\n\nOne thing that we need to be careful about is that we should not remove\nthe common part in full.  We need to keep at least the same length as the\n\"needle\" from the common part, so that we can detect the differences in a\ncase like this:\n\n  preimage: common part then needle appears in this file\n postimage: common part then needlX appears in this file\n\nIf we literally remove the common leading part up to \"needl\" and start\ncounting from the byte after that, we will miss that preimage has an\noccurrence of \"needle\" but postimage does not.\n\nWith this optimization in place, the following query in the Linux kernel\nrepository on my machine becomes about 40% faster:\n\n$ STRING='Ensure that the real time constraints are schedulable.'\n$ git log -S\"$STRING\" HEAD -- kernel/sched.c >/dev/null\n\n(Before the patch, best of 5 runs)\n5.59user 0.15system 0:05.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+39956minor)pagefaults 0swaps\n\n(After the patch, best of 5 runs)\n3.04user 0.17system 0:03.23elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+49697minor)pagefaults 0swaps\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n diffcore-pickaxe.c |   54 ++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 52 insertions(+), 2 deletions(-)\n\ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nindex 4a0dca1..b447d75 100644\n--- a/diffcore-pickaxe.c\n+++ b/diffcore-pickaxe.c\n@@ -68,9 +68,59 @@ static int has_different_matches(struct diff_filepair *p,\n \t\t\t\t const char *needle, unsigned long len,\n \t\t\t\t regex_t *regexp)\n {\n-\treturn (count_match(0, p->one, needle, len, regexp)\n-\t\t!= count_match(0, p->two, needle, len, regexp));\n+\tconst char *one, *two;\n+\tunsigned long one_size, two_size, common, trim;\n+\tint differs;\n \n+\tif (regexp)\n+\t\treturn (count_match(0, p->one, needle, len, regexp)\n+\t\t\t!= count_match(0, p->two, needle, len, regexp));\n+\tif (diff_populate_filespec(p->one, 0) ||\n+\t    diff_populate_filespec(p->two, 0))\n+\t\treturn 0;\n+\n+\tone = p->one->data;\n+\ttwo = p->two->data;\n+\tone_size = p->one->size;\n+\ttwo_size = p->two->size;\n+\tcommon = (one_size < two_size) ? one_size : two_size;\n+\n+\t/* Skip the initial common part */\n+\tfor (trim = 0;\n+\t     trim < common && one[trim] == two[trim];\n+\t     trim++)\n+\t\t;\n+\n+\t/* Start comparing at (len-1) bytes before the first difference */\n+\tif (len <= trim) {\n+\t\ttrim -= len;\n+\t\tone += trim;\n+\t\ttwo += trim;\n+\t\tcommon -= trim;\n+\t\tone_size -= trim;\n+\t\ttwo_size -= trim;\n+\t}\n+\n+\t/* Trim the common part at the end */\n+\tfor (trim = 0;\n+\t     trim < common && one[one_size - trim - 1] == two[two_size - trim - 1];\n+\t     trim++)\n+\t\t;\n+\n+\t/* Leave (len-1) bytes */\n+\tif (len <= trim) {\n+\t\ttrim -= len;\n+\t\tone_size -= trim;\n+\t\ttwo_size -= trim;\n+\t}\n+\n+\tdiffers = (count_match_internal(0, one, one_size, needle, len, regexp) !=\n+\t\t   count_match_internal(0, two, two_size, needle, len, regexp));\n+\n+\tdiff_free_filespec_data(p->one);\n+\tdiff_free_filespec_data(p->two);\n+\n+\treturn differs;\n }\n \n static int pickaxe_match_one(struct diff_filepair *p,\n-- \n1.6.2.rc2.91.gf9a36\n"},{"id":"106299","messageId":"86bpspy83w.fsf@broadpark.no","threadId":"18027","inReplyTo":"cd73512d11e63554396983ed4e9556b2d18b3e4a.1235629933.git.gitster@pobox.com","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"Kjetil Barvik","fromEmail":"barvik@broadpark.no","sentAt":"2009-02-26T07:23:31Z","receivedAt":"2009-02-26T07:23:31Z","isPatch":true,"sender":{"key":"barvik@broadpark.no","avatar":null},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> -\n> -\t} else { /* Classic exact string match */\n> -\t\t/* Yes, I've heard of strstr(), but the thing is *data may\n> -\t\t * not be NUL terminated.  Sue me.\n> -\t\t */\n> +\t} else {\n> +\t\t/* data many not be NUL terminated; we cannot use strstr() */\n\n  spellfix: s/many/may/\n\n  -- kjetil\n"},{"id":"106303","messageId":"7vy6vtva9d.fsf@gitster.siamese.dyndns.org","threadId":"18027","inReplyTo":"30c0d4d9b64924679c9af00796f7e0b562020ddf.1235629933.git.gitster@pobox.com","subject":"Re: [PATCH 4/4] diffcore-pickaxe: optimize by trimming common initial and trailing parts","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-26T09:05:18Z","receivedAt":"2009-02-26T09:05:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> With this optimization in place, the following query in the Linux kernel\n> repository on my machine becomes about 40% faster:\n>\n> $ STRING='Ensure that the real time constraints are schedulable.'\n> $ git log -S\"$STRING\" HEAD -- kernel/sched.c >/dev/null\n>\n> (Before the patch, best of 5 runs)\n> 5.59user 0.15system 0:05.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (0major+39956minor)pagefaults 0swaps\n>\n> (After the patch, best of 5 runs)\n> 3.04user 0.17system 0:03.23elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (0major+49697minor)pagefaults 0swaps\n    \nThe file \"kernel/sched.c\" has roughly 900 changes applied to it, and over\nits lifetime, it has grown from 5kB to 9kB in size.\n\nI suspect a larger file might see a bigger performance boost.\n"},{"id":"106488","messageId":"49A87E1D.3030400@lsrfire.ath.cx","threadId":"18027","inReplyTo":"4b1358cc6558ec05a134431b603e4781b42deabd.1235629933.git.gitster@pobox.com","subject":"Re: [PATCH 1/4] diffcore-pickaxe: refactor diffcore_pickaxe()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-02-27T23:58:21Z","receivedAt":"2009-02-27T23:58:21Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Junio C Hamano schrieb:\n>  void diffcore_pickaxe(const char *needle, int opts)\n>  {\n>  \tstruct diff_queue_struct *q = &diff_queued_diff;\n> @@ -75,29 +107,14 @@ void diffcore_pickaxe(const char *needle, int opts)\n>  \t\t/* Showing the whole changeset if needle exists */\n>  \t\tfor (i = has_changes = 0; !has_changes && i < q->nr; i++) {\n>  \t\t\tstruct diff_filepair *p = q->queue[i];\n> -\t\t\tif (!DIFF_FILE_VALID(p->one)) {\n> -\t\t\t\tif (!DIFF_FILE_VALID(p->two))\n> -\t\t\t\t\tcontinue; /* ignore unmerged */\n> -\t\t\t\t/* created */\n> -\t\t\t\tif (contains(p->two, needle, len, regexp))\n> -\t\t\t\t\thas_changes++;\n> -\t\t\t}\n> -\t\t\telse if (!DIFF_FILE_VALID(p->two)) {\n> -\t\t\t\tif (contains(p->one, needle, len, regexp))\n> -\t\t\t\t\thas_changes++;\n> -\t\t\t}\n> -\t\t\telse if (!diff_unmodified_pair(p) &&\n> -\t\t\t\t contains(p->one, needle, len, regexp) !=\n> -\t\t\t\t contains(p->two, needle, len, regexp))\n> -\t\t\t\thas_changes++;\n> +\t\t\tif (pickaxe_match_one(p, needle, len, regexp))\n> +\t\t\t\treturn; /* not munge the queue */\n>  \t\t}\n> -\t\tif (has_changes)\n> -\t\t\treturn; /* not munge the queue */\n>  \n> -\t\t/* otherwise we will clear the whole queue\n> -\t\t * by copying the empty outq at the end of this\n> -\t\t * function, but first clear the current entries\n> -\t\t * in the queue.\n> +\t\t/*\n> +\t\t * otherwise we will clear the whole queue by copying\n> +\t\t * the empty outq at the end of this function, but\n> +\t\t * first clear the current entries in the queue.\n>  \t\t */\n>  \t\tfor (i = 0; i < q->nr; i++)\n>  \t\t\tdiff_free_filepair(q->queue[i]);\n> @@ -106,24 +123,8 @@ void diffcore_pickaxe(const char *needle, int opts)\n>  \t\t/* Showing only the filepairs that has the needle */\n>  \t\tfor (i = 0; i < q->nr; i++) {\n>  \t\t\tstruct diff_filepair *p = q->queue[i];\n> -\t\t\thas_changes = 0;\n> -\t\t\tif (!DIFF_FILE_VALID(p->one)) {\n> -\t\t\t\tif (!DIFF_FILE_VALID(p->two))\n> -\t\t\t\t\t; /* ignore unmerged */\n> -\t\t\t\t/* created */\n> -\t\t\t\telse if (contains(p->two, needle, len, regexp))\n> -\t\t\t\t\thas_changes = 1;\n> -\t\t\t}\n> -\t\t\telse if (!DIFF_FILE_VALID(p->two)) {\n> -\t\t\t\tif (contains(p->one, needle, len, regexp))\n> -\t\t\t\t\thas_changes = 1;\n> -\t\t\t}\n> -\t\t\telse if (!diff_unmodified_pair(p) &&\n> -\t\t\t\t contains(p->one, needle, len, regexp) !=\n> -\t\t\t\t contains(p->two, needle, len, regexp))\n> -\t\t\t\thas_changes = 1;\n>  \n> -\t\t\tif (has_changes)\n> +\t\t\tif (pickaxe_match_one(p, needle, len, regexp))\n>  \t\t\t\tdiff_q(&outq, p);\n>  \t\t\telse\n>  \t\t\t\tdiff_free_filepair(p);\n\nYou might want to squash this in, because has_changes is now constantly set\nto zero:\n\ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nindex d27e725..d294d29 100644\n--- a/diffcore-pickaxe.c\n+++ b/diffcore-pickaxe.c\n@@ -84,7 +84,7 @@ void diffcore_pickaxe(const char *needle, int opts)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tunsigned long len = strlen(needle);\n-\tint i, has_changes;\n+\tint i;\n \tregex_t regex, *regexp = NULL;\n \tstruct diff_queue_struct outq;\n \toutq.queue = NULL;\n@@ -105,7 +105,7 @@ void diffcore_pickaxe(const char *needle, int opts)\n \n \tif (opts & DIFF_PICKAXE_ALL) {\n \t\t/* Showing the whole changeset if needle exists */\n-\t\tfor (i = has_changes = 0; !has_changes && i < q->nr; i++) {\n+\t\tfor (i = 0; i < q->nr; i++) {\n \t\t\tstruct diff_filepair *p = q->queue[i];\n \t\t\tif (pickaxe_match_one(p, needle, len, regexp))\n \t\t\t\treturn; /* not munge the queue */\n"},{"id":"106495","messageId":"49A88FA7.1020402@lsrfire.ath.cx","threadId":"18027","inReplyTo":"cd73512d11e63554396983ed4e9556b2d18b3e4a.1235629933.git.gitster@pobox.com","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-02-28T01:13:11Z","receivedAt":"2009-02-28T01:13:11Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Junio C Hamano schrieb:\n> -static unsigned int count_match(int one_or_more,\n> -\t\t\t\tstruct diff_filespec *one,\n> -\t\t\t\tconst char *needle, unsigned long len,\n> -\t\t\t\tregex_t *regexp)\n> +static unsigned int count_match_internal(int one_or_more,\n> +\t\t\t\t\t const char *data, unsigned long sz,\n> +\t\t\t\t\t const char *needle, unsigned long len,\n> +\t\t\t\t\t regex_t *regexp)\n>  {\n\nI don't especially like flags like one_or_more.  Having two functions\n(which possibly call a common function that does most of the work) is\nnicer.  And it's a bit sad here because there already are two functions\nwith nice names: count_match() and has_match().  But, well, since the\nfunctions are not exported anyway it doesn't matter much.\n\n> @@ -29,16 +20,14 @@ static unsigned int count_match(int one_or_more,\n>  \t\twhile (*data && !regexec(regexp, data, 1, &regmatch, flags)) {\n>  \t\t\tflags |= REG_NOTBOL;\n>  \t\t\tdata += regmatch.rm_so;\n> -\t\t\tif (*data) data++;\n> +\t\t\tif (*data)\n> +\t\t\t\tdata++;\n>  \t\t\tcnt++;\n>  \t\t\tif (one_or_more)\n>  \t\t\t\tbreak;\n>  \t\t}\n> -\n> -\t} else { /* Classic exact string match */\n> -\t\t/* Yes, I've heard of strstr(), but the thing is *data may\n> -\t\t * not be NUL terminated.  Sue me.\n> -\t\t */\n> +\t} else {\n> +\t\t/* data many not be NUL terminated; we cannot use strstr() */\n\nThat looks fishy to me.  regexec() expects data to be a NUL-terminated\nstring, so either the comment is wrong or the regexp case needs to take\nbetter care to add a NUL at the end of the buffer.\n\nIn any case, there is also memmem(), which uses the same fast algorithm\nas strstr() in recent glibc versions.  Like this?\n\n\ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nindex f4870b4..4c19967 100644\n--- a/diffcore-pickaxe.c\n+++ b/diffcore-pickaxe.c\n@@ -11,7 +11,6 @@ static unsigned int count_match_internal(int one_or_more,\n \t\t\t\t\t regex_t *regexp)\n {\n \tunsigned int cnt = 0;\n-\tunsigned long offset;\n \n \tif (regexp) {\n \t\tregmatch_t regmatch;\n@@ -27,15 +26,15 @@ static unsigned int count_match_internal(int one_or_more,\n \t\t\t\tbreak;\n \t\t}\n \t} else {\n-\t\t/* data many not be NUL terminated; we cannot use strstr() */\n-\t\tfor (offset = 0; offset + len <= sz; offset++) {\n-\t\t\t/* we count non-overlapping occurrences of needle */\n-\t\t\tif (!memcmp(needle, data + offset, len)) {\n-\t\t\t\toffset += len - 1;\n-\t\t\t\tcnt++;\n-\t\t\t\tif (one_or_more)\n-\t\t\t\t\tbreak;\n-\t\t\t}\n+\t\twhile (sz) {\n+\t\t\tconst char *found = memmem(data, sz, needle, len);\n+\t\t\tif (!found)\n+\t\t\t\tbreak;\n+\t\t\tsz -= found - data + len;\n+\t\t\tdata = found + len;\n+\t\t\tcnt++;\n+\t\t\tif (one_or_more)\n+\t\t\t\tbreak;\n \t\t}\n \t}\n \treturn cnt;\n"},{"id":"106498","messageId":"7vy6vrgxnn.fsf@gitster.siamese.dyndns.org","threadId":"18027","inReplyTo":"49A88FA7.1020402@lsrfire.ath.cx","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-28T01:25:48Z","receivedAt":"2009-02-28T01:25:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n\n>> -\n>> -\t} else { /* Classic exact string match */\n>> -\t\t/* Yes, I've heard of strstr(), but the thing is *data may\n>> -\t\t * not be NUL terminated.  Sue me.\n>> -\t\t */\n>> +\t} else {\n>> +\t\t/* data many not be NUL terminated; we cannot use strstr() */\n>\n> That looks fishy to me.  regexec() expects data to be a NUL-terminated\n> string, so either the comment is wrong or the regexp case needs to take\n> better care to add a NUL at the end of the buffer.\n\nProbably yes, but regexp side is not my code and I never use it, so... ;-)\n\n> In any case, there is also memmem(), which uses the same fast algorithm\n> as strstr() in recent glibc versions.  Like this?\n\nThanks; it would be nice to bench this change.\n"},{"id":"106512","messageId":"7v8wnrgkjw.fsf@gitster.siamese.dyndns.org","threadId":"18027","inReplyTo":"7vy6vrgxnn.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-28T06:08:51Z","receivedAt":"2009-02-28T06:08:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n> ...\n>> In any case, there is also memmem(), which uses the same fast algorithm\n>> as strstr() in recent glibc versions.  Like this?\n>\n> Thanks; it would be nice to bench this change.\n\nWith memmem() patch applied on top of [1-4/4], the same test as described\nin the commit log message of [4/4] which was:\n\n    $ STRING='Ensure that the real time constraints are schedulable.'\n    $ git log -S\"$STRING\" HEAD -- kernel/sched.c >/dev/null\n\n    (Before the patch, best of 5 runs)\n    5.59user 0.15system 0:05.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+39956minor)pagefaults 0swaps\n\n    (After the patch, best of 5 runs)\n    3.04user 0.17system 0:03.23elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+49697minor)pagefaults 0swaps\n\n    The file \"kernel/sched.c\" has roughly 900 changes applied to it, and over\n    its lifetime, it has grown from 5kB to 9kB in size.  I'd expect a larger\n    file may see a bigger performance boost.\n\n(With memmem() patch, best of 5 runs)\n2.46user 0.15system 0:02.62elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+49698minor)pagefaults 0swaps\n"},{"id":"106529","messageId":"49A937B8.1030205@lsrfire.ath.cx","threadId":"18027","inReplyTo":"7v8wnrgkjw.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-02-28T13:10:16Z","receivedAt":"2009-02-28T13:10:16Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Junio C Hamano schrieb:\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n>> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n>> ...\n>>> In any case, there is also memmem(), which uses the same fast algorithm\n>>> as strstr() in recent glibc versions.  Like this?\n>> Thanks; it would be nice to bench this change.\n> \n> With memmem() patch applied on top of [1-4/4], the same test as described\n> in the commit log message of [4/4] which was:\n> \n>     $ STRING='Ensure that the real time constraints are schedulable.'\n>     $ git log -S\"$STRING\" HEAD -- kernel/sched.c >/dev/null\n> \n>     (Before the patch, best of 5 runs)\n>     5.59user 0.15system 0:05.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n>     0inputs+0outputs (0major+39956minor)pagefaults 0swaps\n> \n>     (After the patch, best of 5 runs)\n>     3.04user 0.17system 0:03.23elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n>     0inputs+0outputs (0major+49697minor)pagefaults 0swaps\n> \n>     The file \"kernel/sched.c\" has roughly 900 changes applied to it, and over\n>     its lifetime, it has grown from 5kB to 9kB in size.  I'd expect a larger\n>     file may see a bigger performance boost.\n> \n> (With memmem() patch, best of 5 runs)\n> 2.46user 0.15system 0:02.62elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (0major+49698minor)pagefaults 0swaps\n\nI get this (Ubuntu 8.10 x64, Fedora 10 x64 using the same Linux repo,\nWindows Vista x64 using a different Linux repo with the same HEAD on\nNTFS and msysgit, numbers are the elapsed time in seconds, best of five\nruns):\n\n                           Ubuntu  Fedora  Windows\n   v1.6.2-rc2                8.14    8.16    9.236\n   v1.6.2-rc2+[1-4]          2.43    2.45    2.995\n   v1.6.2-rc2+[1-4]+memmem   1.31    1.25    2.917\n   v1.6.2-rc2+[1-3]+memmem   1.51    1.16    8.455\n\nUbuntu has glibc 2.8, while Fedora 10 has glibc 2.9, with a new and more\nefficient memmem() implementation.  On Windows, we use our own naive\nmemmem() implementation.\n\nSo using memmem() is worthwhile.  And providing a better fall-back\nversion in compat/ can speed up this particular case to the point where\nthe fourth patch becomes moot.\n\nHmm, gnulib (http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=summary)\ncontains all parts ready for copy & paste, licensed under the GPL 2 or\nup.  That won't cause problems with the libgit2 relicensing effort, as\nmemmem()  won't end up in there, right?\n\n\nFor the record, here the raw timings used to make the table above (best\nof five):\n\nFedora 10:\n8.10user 0.05system 0:08.16elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+31943minor)pagefaults 0swaps\n\n2.38user 0.06system 0:02.45elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41294minor)pagefaults 0swaps\n\n1.19user 0.05system 0:01.25elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+39274minor)pagefaults 0swaps\n\n1.10user 0.05system 0:01.16elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+31796minor)pagefaults 0swaps\n\nUbuntu 8.10:\n8.08user 0.05system 0:08.14elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+29579minor)pagefaults 0swaps\n\n2.35user 0.07system 0:02.43elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+40437minor)pagefaults 0swaps\n\n1.23user 0.08system 0:01.31elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41097minor)pagefaults 0swaps\n\n1.46user 0.05system 0:01.51elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+30533minor)pagefaults 0swaps\n\nWindows:\nreal    0m9.236s\nuser    0m0.000s\nsys     0m0.000s\n\nreal    0m2.995s\nuser    0m0.000s\nsys     0m0.000s\n\nreal    0m2.917s\nuser    0m0.000s\nsys     0m0.015s\n\nreal    0m8.455s\nuser    0m0.000s\nsys     0m0.000s\n"},{"id":"106543","messageId":"7vmyc6foj3.fsf@gitster.siamese.dyndns.org","threadId":"18027","inReplyTo":"49A937B8.1030205@lsrfire.ath.cx","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-02-28T17:40:32Z","receivedAt":"2009-02-28T17:40:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n\n> I get this (Ubuntu 8.10 x64, Fedora 10 x64 using the same Linux repo,\n> Windows Vista x64 using a different Linux repo with the same HEAD on\n> NTFS and msysgit, numbers are the elapsed time in seconds, best of five\n> runs):\n>\n>                            Ubuntu  Fedora  Windows\n>    v1.6.2-rc2                8.14    8.16    9.236\n>    v1.6.2-rc2+[1-4]          2.43    2.45    2.995\n>    v1.6.2-rc2+[1-4]+memmem   1.31    1.25    2.917\n>    v1.6.2-rc2+[1-3]+memmem   1.51    1.16    8.455\n>\n> Ubuntu has glibc 2.8, while Fedora 10 has glibc 2.9, with a new and more\n> efficient memmem() implementation.  On Windows, we use our own naive\n> memmem() implementation.\n\nYeah, what does glibc use these days?  Some variant of Boyer-Moore?\n\n> So using memmem() is worthwhile.  And providing a better fall-back\n> version in compat/ can speed up this particular case to the point where\n> the fourth patch becomes moot.\n>\n> Hmm, gnulib (http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=summary)\n> contains all parts ready for copy & paste, licensed under the GPL 2 or\n> up.  That won't cause problems with the libgit2 relicensing effort, as\n> memmem()  won't end up in there, right?\n\nCorrect.\n"},{"id":"106546","messageId":"49A97F52.4080405@lsrfire.ath.cx","threadId":"18027","inReplyTo":"7vmyc6foj3.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-02-28T18:15:46Z","receivedAt":"2009-02-28T18:15:46Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Junio C Hamano schrieb:\n> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n> \n>> I get this (Ubuntu 8.10 x64, Fedora 10 x64 using the same Linux repo,\n>> Windows Vista x64 using a different Linux repo with the same HEAD on\n>> NTFS and msysgit, numbers are the elapsed time in seconds, best of five\n>> runs):\n>>\n>>                            Ubuntu  Fedora  Windows\n>>    v1.6.2-rc2                8.14    8.16    9.236\n>>    v1.6.2-rc2+[1-4]          2.43    2.45    2.995\n>>    v1.6.2-rc2+[1-4]+memmem   1.31    1.25    2.917\n>>    v1.6.2-rc2+[1-3]+memmem   1.51    1.16    8.455\n>>\n>> Ubuntu has glibc 2.8, while Fedora 10 has glibc 2.9, with a new and more\n>> efficient memmem() implementation.  On Windows, we use our own naive\n>> memmem() implementation.\n> \n> Yeah, what does glibc use these days?  Some variant of Boyer-Moore?\n\nNo, the algorithm is called Two Way, which, unlike Boyer-Moore, only\nneeds constant space.  The implementation seems to originate from this bug:\n\n\thttp://sourceware.org/bugzilla/show_bug.cgi?id=5514\n\nAnd the algorithm is documented here:\n\n\thttp://www-igm.univ-mlv.fr/~lecroq/string/node26.html\n\nRené\n"},{"id":"106549","messageId":"1235848615.7043.30.camel@ubuntu.ubuntu-domain","threadId":"18027","inReplyTo":"7vmyc6foj3.fsf@gitster.siamese.dyndns.org","subject":"[PATCH] import memmem() with linear complexity from Gnulib","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-02-28T19:16:55Z","receivedAt":"2009-02-28T19:16:55Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Gnulib and glibc have gained a memmem() implementation using the Two-Way\nalgorithm, which needs constant space and linear time.  Import it to\ncompat/ in order to replace the simple quadratic implementation there.\n\nmemmem.c and str-two-way.h are copied verbatim from the repository at\ngit://git.savannah.gnu.org/gnulib.git, with the following changes to\nmemmem.c to make it fit into git's build environment:\n\n\t21,23c21\n\t< #ifndef _LIBC\n\t< # include <config.h>\n\t< #endif\n\t---\n\t> #include \"../git-compat-util.h\"\n\t40c38\n\t< memmem (const void *haystack_start, size_t haystack_len,\n\t---\n\t> gitmemmem(const void *haystack_start, size_t haystack_len,\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n---\n Makefile             |    1 +\n compat/memmem.c      |  103 +++++++++----\n compat/str-two-way.h |  429 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 504 insertions(+), 29 deletions(-)\n rewrite compat/memmem.c (91%)\n create mode 100644 compat/str-two-way.h\n\ndiff --git a/Makefile b/Makefile\nindex 0675c43..b2b15d9 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -359,6 +359,7 @@ LIB_H += cache-tree.h\n LIB_H += commit.h\n LIB_H += compat/cygwin.h\n LIB_H += compat/mingw.h\n+LIB_H += compat/str-two-way.h\n LIB_H += csum-file.h\n LIB_H += decorate.h\n LIB_H += delta.h\ndiff --git a/compat/memmem.c b/compat/memmem.c\ndissimilarity index 91%\nindex cd0d877..b0b7821 100644\n--- a/compat/memmem.c\n+++ b/compat/memmem.c\n@@ -1,29 +1,74 @@\n-#include \"../git-compat-util.h\"\n-\n-void *gitmemmem(const void *haystack, size_t haystack_len,\n-                const void *needle, size_t needle_len)\n-{\n-\tconst char *begin = haystack;\n-\tconst char *last_possible = begin + haystack_len - needle_len;\n-\n-\t/*\n-\t * The first occurrence of the empty string is deemed to occur at\n-\t * the beginning of the string.\n-\t */\n-\tif (needle_len == 0)\n-\t\treturn (void *)begin;\n-\n-\t/*\n-\t * Sanity check, otherwise the loop might search through the whole\n-\t * memory.\n-\t */\n-\tif (haystack_len < needle_len)\n-\t\treturn NULL;\n-\n-\tfor (; begin <= last_possible; begin++) {\n-\t\tif (!memcmp(begin, needle, needle_len))\n-\t\t\treturn (void *)begin;\n-\t}\n-\n-\treturn NULL;\n-}\n+/* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2007,2008 Free Software\n+   Foundation, Inc.\n+   This file is part of the GNU C Library.\n+\n+   This program is free software; you can redistribute it and/or modify\n+   it under the terms of the GNU General Public License as published by\n+   the Free Software Foundation; either version 2, or (at your option)\n+   any later version.\n+\n+   This program is distributed in the hope that it will be useful,\n+   but WITHOUT ANY WARRANTY; without even the implied warranty of\n+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n+   GNU General Public License for more details.\n+\n+   You should have received a copy of the GNU General Public License along\n+   with this program; if not, write to the Free Software Foundation,\n+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */\n+\n+/* This particular implementation was written by Eric Blake, 2008.  */\n+\n+#include \"../git-compat-util.h\"\n+\n+/* Specification of memmem.  */\n+#include <string.h>\n+\n+#ifndef _LIBC\n+# define __builtin_expect(expr, val)   (expr)\n+#endif\n+\n+#define RETURN_TYPE void *\n+#define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))\n+#include \"str-two-way.h\"\n+\n+/* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK\n+   if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in\n+   HAYSTACK.  */\n+void *\n+gitmemmem(const void *haystack_start, size_t haystack_len,\n+\tconst void *needle_start, size_t needle_len)\n+{\n+  /* Abstract memory is considered to be an array of 'unsigned char' values,\n+     not an array of 'char' values.  See ISO C 99 section 6.2.6.1.  */\n+  const unsigned char *haystack = (const unsigned char *) haystack_start;\n+  const unsigned char *needle = (const unsigned char *) needle_start;\n+\n+  if (needle_len == 0)\n+    /* The first occurrence of the empty string is deemed to occur at\n+       the beginning of the string.  */\n+    return (void *) haystack;\n+\n+  /* Sanity check, otherwise the loop might search through the whole\n+     memory.  */\n+  if (__builtin_expect (haystack_len < needle_len, 0))\n+    return NULL;\n+\n+  /* Use optimizations in memchr when possible, to reduce the search\n+     size of haystack using a linear algorithm with a smaller\n+     coefficient.  However, avoid memchr for long needles, since we\n+     can often achieve sublinear performance.  */\n+  if (needle_len < LONG_NEEDLE_THRESHOLD)\n+    {\n+      haystack = memchr (haystack, *needle, haystack_len);\n+      if (!haystack || __builtin_expect (needle_len == 1, 0))\n+\treturn (void *) haystack;\n+      haystack_len -= haystack - (const unsigned char *) haystack_start;\n+      if (haystack_len < needle_len)\n+\treturn NULL;\n+      return two_way_short_needle (haystack, haystack_len, needle, needle_len);\n+    }\n+  else\n+    return two_way_long_needle (haystack, haystack_len, needle, needle_len);\n+}\n+\n+#undef LONG_NEEDLE_THRESHOLD\ndiff --git a/compat/str-two-way.h b/compat/str-two-way.h\nnew file mode 100644\nindex 0000000..b0338a7\n--- /dev/null\n+++ b/compat/str-two-way.h\n@@ -0,0 +1,429 @@\n+/* Byte-wise substring search, using the Two-Way algorithm.\n+   Copyright (C) 2008 Free Software Foundation, Inc.\n+   This file is part of the GNU C Library.\n+   Written by Eric Blake <ebb9@byu.net>, 2008.\n+\n+   This program is free software; you can redistribute it and/or modify\n+   it under the terms of the GNU General Public License as published by\n+   the Free Software Foundation; either version 2, or (at your option)\n+   any later version.\n+\n+   This program is distributed in the hope that it will be useful,\n+   but WITHOUT ANY WARRANTY; without even the implied warranty of\n+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n+   GNU General Public License for more details.\n+\n+   You should have received a copy of the GNU General Public License along\n+   with this program; if not, write to the Free Software Foundation,\n+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */\n+\n+/* Before including this file, you need to include <config.h> and\n+   <string.h>, and define:\n+     RESULT_TYPE             A macro that expands to the return type.\n+     AVAILABLE(h, h_l, j, n_l)\n+\t\t\t     A macro that returns nonzero if there are\n+\t\t\t     at least N_L bytes left starting at H[J].\n+\t\t\t     H is 'unsigned char *', H_L, J, and N_L\n+\t\t\t     are 'size_t'; H_L is an lvalue.  For\n+\t\t\t     NUL-terminated searches, H_L can be\n+\t\t\t     modified each iteration to avoid having\n+\t\t\t     to compute the end of H up front.\n+\n+  For case-insensitivity, you may optionally define:\n+     CMP_FUNC(p1, p2, l)     A macro that returns 0 iff the first L\n+\t\t\t     characters of P1 and P2 are equal.\n+     CANON_ELEMENT(c)        A macro that canonicalizes an element right after\n+\t\t\t     it has been fetched from one of the two strings.\n+\t\t\t     The argument is an 'unsigned char'; the result\n+\t\t\t     must be an 'unsigned char' as well.\n+\n+  This file undefines the macros documented above, and defines\n+  LONG_NEEDLE_THRESHOLD.\n+*/\n+\n+#include <limits.h>\n+#include <stdint.h>\n+\n+/* We use the Two-Way string matching algorithm, which guarantees\n+   linear complexity with constant space.  Additionally, for long\n+   needles, we also use a bad character shift table similar to the\n+   Boyer-Moore algorithm to achieve improved (potentially sub-linear)\n+   performance.\n+\n+   See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260\n+   and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm\n+*/\n+\n+/* Point at which computing a bad-byte shift table is likely to be\n+   worthwhile.  Small needles should not compute a table, since it\n+   adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a\n+   speedup no greater than a factor of NEEDLE_LEN.  The larger the\n+   needle, the better the potential performance gain.  On the other\n+   hand, on non-POSIX systems with CHAR_BIT larger than eight, the\n+   memory required for the table is prohibitive.  */\n+#if CHAR_BIT < 10\n+# define LONG_NEEDLE_THRESHOLD 32U\n+#else\n+# define LONG_NEEDLE_THRESHOLD SIZE_MAX\n+#endif\n+\n+#ifndef MAX\n+# define MAX(a, b) ((a < b) ? (b) : (a))\n+#endif\n+\n+#ifndef CANON_ELEMENT\n+# define CANON_ELEMENT(c) c\n+#endif\n+#ifndef CMP_FUNC\n+# define CMP_FUNC memcmp\n+#endif\n+\n+/* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.\n+   Return the index of the first byte in the right half, and set\n+   *PERIOD to the global period of the right half.\n+\n+   The global period of a string is the smallest index (possibly its\n+   length) at which all remaining bytes in the string are repetitions\n+   of the prefix (the last repetition may be a subset of the prefix).\n+\n+   When NEEDLE is factored into two halves, a local period is the\n+   length of the smallest word that shares a suffix with the left half\n+   and shares a prefix with the right half.  All factorizations of a\n+   non-empty NEEDLE have a local period of at least 1 and no greater\n+   than NEEDLE_LEN.\n+\n+   A critical factorization has the property that the local period\n+   equals the global period.  All strings have at least one critical\n+   factorization with the left half smaller than the global period.\n+\n+   Given an ordered alphabet, a critical factorization can be computed\n+   in linear time, with 2 * NEEDLE_LEN comparisons, by computing the\n+   larger of two ordered maximal suffixes.  The ordered maximal\n+   suffixes are determined by lexicographic comparison of\n+   periodicity.  */\n+static size_t\n+critical_factorization (const unsigned char *needle, size_t needle_len,\n+\t\t\tsize_t *period)\n+{\n+  /* Index of last byte of left half, or SIZE_MAX.  */\n+  size_t max_suffix, max_suffix_rev;\n+  size_t j; /* Index into NEEDLE for current candidate suffix.  */\n+  size_t k; /* Offset into current period.  */\n+  size_t p; /* Intermediate period.  */\n+  unsigned char a, b; /* Current comparison bytes.  */\n+\n+  /* Invariants:\n+     0 <= j < NEEDLE_LEN - 1\n+     -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)\n+     min(max_suffix, max_suffix_rev) < global period of NEEDLE\n+     1 <= p <= global period of NEEDLE\n+     p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]\n+     1 <= k <= p\n+  */\n+\n+  /* Perform lexicographic search.  */\n+  max_suffix = SIZE_MAX;\n+  j = 0;\n+  k = p = 1;\n+  while (j + k < needle_len)\n+    {\n+      a = CANON_ELEMENT (needle[j + k]);\n+      b = CANON_ELEMENT (needle[max_suffix + k]);\n+      if (a < b)\n+\t{\n+\t  /* Suffix is smaller, period is entire prefix so far.  */\n+\t  j += k;\n+\t  k = 1;\n+\t  p = j - max_suffix;\n+\t}\n+      else if (a == b)\n+\t{\n+\t  /* Advance through repetition of the current period.  */\n+\t  if (k != p)\n+\t    ++k;\n+\t  else\n+\t    {\n+\t      j += p;\n+\t      k = 1;\n+\t    }\n+\t}\n+      else /* b < a */\n+\t{\n+\t  /* Suffix is larger, start over from current location.  */\n+\t  max_suffix = j++;\n+\t  k = p = 1;\n+\t}\n+    }\n+  *period = p;\n+\n+  /* Perform reverse lexicographic search.  */\n+  max_suffix_rev = SIZE_MAX;\n+  j = 0;\n+  k = p = 1;\n+  while (j + k < needle_len)\n+    {\n+      a = CANON_ELEMENT (needle[j + k]);\n+      b = CANON_ELEMENT (needle[max_suffix_rev + k]);\n+      if (b < a)\n+\t{\n+\t  /* Suffix is smaller, period is entire prefix so far.  */\n+\t  j += k;\n+\t  k = 1;\n+\t  p = j - max_suffix_rev;\n+\t}\n+      else if (a == b)\n+\t{\n+\t  /* Advance through repetition of the current period.  */\n+\t  if (k != p)\n+\t    ++k;\n+\t  else\n+\t    {\n+\t      j += p;\n+\t      k = 1;\n+\t    }\n+\t}\n+      else /* a < b */\n+\t{\n+\t  /* Suffix is larger, start over from current location.  */\n+\t  max_suffix_rev = j++;\n+\t  k = p = 1;\n+\t}\n+    }\n+\n+  /* Choose the longer suffix.  Return the first byte of the right\n+     half, rather than the last byte of the left half.  */\n+  if (max_suffix_rev + 1 < max_suffix + 1)\n+    return max_suffix + 1;\n+  *period = p;\n+  return max_suffix_rev + 1;\n+}\n+\n+/* Return the first location of non-empty NEEDLE within HAYSTACK, or\n+   NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This\n+   method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.\n+   Performance is guaranteed to be linear, with an initialization cost\n+   of 2 * NEEDLE_LEN comparisons.\n+\n+   If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at\n+   most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.\n+   If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *\n+   HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.  */\n+static RETURN_TYPE\n+two_way_short_needle (const unsigned char *haystack, size_t haystack_len,\n+\t\t      const unsigned char *needle, size_t needle_len)\n+{\n+  size_t i; /* Index into current byte of NEEDLE.  */\n+  size_t j; /* Index into current window of HAYSTACK.  */\n+  size_t period; /* The period of the right half of needle.  */\n+  size_t suffix; /* The index of the right half of needle.  */\n+\n+  /* Factor the needle into two halves, such that the left half is\n+     smaller than the global period, and the right half is\n+     periodic (with a period as large as NEEDLE_LEN - suffix).  */\n+  suffix = critical_factorization (needle, needle_len, &period);\n+\n+  /* Perform the search.  Each iteration compares the right half\n+     first.  */\n+  if (CMP_FUNC (needle, needle + period, suffix) == 0)\n+    {\n+      /* Entire needle is periodic; a mismatch can only advance by the\n+\t period, so use memory to avoid rescanning known occurrences\n+\t of the period.  */\n+      size_t memory = 0;\n+      j = 0;\n+      while (AVAILABLE (haystack, haystack_len, j, needle_len))\n+\t{\n+\t  /* Scan for matches in right half.  */\n+\t  i = MAX (suffix, memory);\n+\t  while (i < needle_len && (CANON_ELEMENT (needle[i])\n+\t\t\t\t    == CANON_ELEMENT (haystack[i + j])))\n+\t    ++i;\n+\t  if (needle_len <= i)\n+\t    {\n+\t      /* Scan for matches in left half.  */\n+\t      i = suffix - 1;\n+\t      while (memory < i + 1 && (CANON_ELEMENT (needle[i])\n+\t\t\t\t\t== CANON_ELEMENT (haystack[i + j])))\n+\t\t--i;\n+\t      if (i + 1 < memory + 1)\n+\t\treturn (RETURN_TYPE) (haystack + j);\n+\t      /* No match, so remember how many repetitions of period\n+\t\t on the right half were scanned.  */\n+\t      j += period;\n+\t      memory = needle_len - period;\n+\t    }\n+\t  else\n+\t    {\n+\t      j += i - suffix + 1;\n+\t      memory = 0;\n+\t    }\n+\t}\n+    }\n+  else\n+    {\n+      /* The two halves of needle are distinct; no extra memory is\n+\t required, and any mismatch results in a maximal shift.  */\n+      period = MAX (suffix, needle_len - suffix) + 1;\n+      j = 0;\n+      while (AVAILABLE (haystack, haystack_len, j, needle_len))\n+\t{\n+\t  /* Scan for matches in right half.  */\n+\t  i = suffix;\n+\t  while (i < needle_len && (CANON_ELEMENT (needle[i])\n+\t\t\t\t    == CANON_ELEMENT (haystack[i + j])))\n+\t    ++i;\n+\t  if (needle_len <= i)\n+\t    {\n+\t      /* Scan for matches in left half.  */\n+\t      i = suffix - 1;\n+\t      while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])\n+\t\t\t\t       == CANON_ELEMENT (haystack[i + j])))\n+\t\t--i;\n+\t      if (i == SIZE_MAX)\n+\t\treturn (RETURN_TYPE) (haystack + j);\n+\t      j += period;\n+\t    }\n+\t  else\n+\t    j += i - suffix + 1;\n+\t}\n+    }\n+  return NULL;\n+}\n+\n+/* Return the first location of non-empty NEEDLE within HAYSTACK, or\n+   NULL.  HAYSTACK_LEN is the minimum known length of HAYSTACK.  This\n+   method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.\n+   Performance is guaranteed to be linear, with an initialization cost\n+   of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.\n+\n+   If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at\n+   most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,\n+   and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.\n+   If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *\n+   HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and\n+   sublinear performance is not possible.  */\n+static RETURN_TYPE\n+two_way_long_needle (const unsigned char *haystack, size_t haystack_len,\n+\t\t     const unsigned char *needle, size_t needle_len)\n+{\n+  size_t i; /* Index into current byte of NEEDLE.  */\n+  size_t j; /* Index into current window of HAYSTACK.  */\n+  size_t period; /* The period of the right half of needle.  */\n+  size_t suffix; /* The index of the right half of needle.  */\n+  size_t shift_table[1U << CHAR_BIT]; /* See below.  */\n+\n+  /* Factor the needle into two halves, such that the left half is\n+     smaller than the global period, and the right half is\n+     periodic (with a period as large as NEEDLE_LEN - suffix).  */\n+  suffix = critical_factorization (needle, needle_len, &period);\n+\n+  /* Populate shift_table.  For each possible byte value c,\n+     shift_table[c] is the distance from the last occurrence of c to\n+     the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.\n+     shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0.  */\n+  for (i = 0; i < 1U << CHAR_BIT; i++)\n+    shift_table[i] = needle_len;\n+  for (i = 0; i < needle_len; i++)\n+    shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;\n+\n+  /* Perform the search.  Each iteration compares the right half\n+     first.  */\n+  if (CMP_FUNC (needle, needle + period, suffix) == 0)\n+    {\n+      /* Entire needle is periodic; a mismatch can only advance by the\n+\t period, so use memory to avoid rescanning known occurrences\n+\t of the period.  */\n+      size_t memory = 0;\n+      size_t shift;\n+      j = 0;\n+      while (AVAILABLE (haystack, haystack_len, j, needle_len))\n+\t{\n+\t  /* Check the last byte first; if it does not match, then\n+\t     shift to the next possible match location.  */\n+\t  shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];\n+\t  if (0 < shift)\n+\t    {\n+\t      if (memory && shift < period)\n+\t\t{\n+\t\t  /* Since needle is periodic, but the last period has\n+\t\t     a byte out of place, there can be no match until\n+\t\t     after the mismatch.  */\n+\t\t  shift = needle_len - period;\n+\t\t  memory = 0;\n+\t\t}\n+\t      j += shift;\n+\t      continue;\n+\t    }\n+\t  /* Scan for matches in right half.  The last byte has\n+\t     already been matched, by virtue of the shift table.  */\n+\t  i = MAX (suffix, memory);\n+\t  while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])\n+\t\t\t\t\t== CANON_ELEMENT (haystack[i + j])))\n+\t    ++i;\n+\t  if (needle_len - 1 <= i)\n+\t    {\n+\t      /* Scan for matches in left half.  */\n+\t      i = suffix - 1;\n+\t      while (memory < i + 1 && (CANON_ELEMENT (needle[i])\n+\t\t\t\t\t== CANON_ELEMENT (haystack[i + j])))\n+\t\t--i;\n+\t      if (i + 1 < memory + 1)\n+\t\treturn (RETURN_TYPE) (haystack + j);\n+\t      /* No match, so remember how many repetitions of period\n+\t\t on the right half were scanned.  */\n+\t      j += period;\n+\t      memory = needle_len - period;\n+\t    }\n+\t  else\n+\t    {\n+\t      j += i - suffix + 1;\n+\t      memory = 0;\n+\t    }\n+\t}\n+    }\n+  else\n+    {\n+      /* The two halves of needle are distinct; no extra memory is\n+\t required, and any mismatch results in a maximal shift.  */\n+      size_t shift;\n+      period = MAX (suffix, needle_len - suffix) + 1;\n+      j = 0;\n+      while (AVAILABLE (haystack, haystack_len, j, needle_len))\n+\t{\n+\t  /* Check the last byte first; if it does not match, then\n+\t     shift to the next possible match location.  */\n+\t  shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];\n+\t  if (0 < shift)\n+\t    {\n+\t      j += shift;\n+\t      continue;\n+\t    }\n+\t  /* Scan for matches in right half.  The last byte has\n+\t     already been matched, by virtue of the shift table.  */\n+\t  i = suffix;\n+\t  while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])\n+\t\t\t\t\t== CANON_ELEMENT (haystack[i + j])))\n+\t    ++i;\n+\t  if (needle_len - 1 <= i)\n+\t    {\n+\t      /* Scan for matches in left half.  */\n+\t      i = suffix - 1;\n+\t      while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])\n+\t\t\t\t       == CANON_ELEMENT (haystack[i + j])))\n+\t\t--i;\n+\t      if (i == SIZE_MAX)\n+\t\treturn (RETURN_TYPE) (haystack + j);\n+\t      j += period;\n+\t    }\n+\t  else\n+\t    j += i - suffix + 1;\n+\t}\n+    }\n+  return NULL;\n+}\n+\n+#undef AVAILABLE\n+#undef CANON_ELEMENT\n+#undef CMP_FUNC\n+#undef MAX\n+#undef RETURN_TYPE\n-- \n1.6.2.rc2\n"},{"id":"106561","messageId":"20090228224401.GA27262@glandium.org","threadId":"18027","inReplyTo":"1235848615.7043.30.camel@ubuntu.ubuntu-domain","subject":"Re: [PATCH] import memmem() with linear complexity from Gnulib","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2009-02-28T22:44:01Z","receivedAt":"2009-02-28T22:44:01Z","isPatch":true,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Sat, Feb 28, 2009 at 08:16:55PM +0100, René Scharfe wrote:\n> Gnulib and glibc have gained a memmem() implementation using the Two-Way\n> algorithm, which needs constant space and linear time.  Import it to\n> compat/ in order to replace the simple quadratic implementation there.\n> \n> memmem.c and str-two-way.h are copied verbatim from the repository at\n> git://git.savannah.gnu.org/gnulib.git, with the following changes to\n> memmem.c to make it fit into git's build environment:\n> \n> \t21,23c21\n> \t< #ifndef _LIBC\n> \t< # include <config.h>\n> \t< #endif\n> \t---\n> \t> #include \"../git-compat-util.h\"\n> \t40c38\n> \t< memmem (const void *haystack_start, size_t haystack_len,\n> \t---\n> \t> gitmemmem(const void *haystack_start, size_t haystack_len,\n> \n> Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n> ---\n>  Makefile             |    1 +\n>  compat/memmem.c      |  103 +++++++++----\n>  compat/str-two-way.h |  429 ++++++++++++++++++++++++++++++++++++++++++++++++++\n>  3 files changed, 504 insertions(+), 29 deletions(-)\n\nSeeing how much memmem is being used in the codebase, is it really worth?\n\nMike\n"},{"id":"106574","messageId":"20090301034123.GC30384@coredump.intra.peff.net","threadId":"18027","inReplyTo":"20090228224401.GA27262@glandium.org","subject":"Re: [PATCH] import memmem() with linear complexity from Gnulib","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-03-01T03:41:23Z","receivedAt":"2009-03-01T03:41:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Feb 28, 2009 at 11:44:01PM +0100, Mike Hommey wrote:\n\n> > ---\n> >  Makefile             |    1 +\n> >  compat/memmem.c      |  103 +++++++++----\n> >  compat/str-two-way.h |  429 ++++++++++++++++++++++++++++++++++++++++++++++++++\n> >  3 files changed, 504 insertions(+), 29 deletions(-)\n> \n> Seeing how much memmem is being used in the codebase, is it really worth?\n\nSee earlier in the thread, where \"git log -Stoken\" is substantially\nfaster on Linux versus Windows (but some exact numbers before and after\non Windows would be nice to have in the commit message).\n\n-Peff\n"},{"id":"106588","messageId":"7viqmtaec4.fsf@gitster.siamese.dyndns.org","threadId":"18027","inReplyTo":"49A937B8.1030205@lsrfire.ath.cx","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-01T07:31:55Z","receivedAt":"2009-03-01T07:31:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n\n> I get this (Ubuntu 8.10 x64, Fedora 10 x64 using the same Linux repo,\n> Windows Vista x64 using a different Linux repo with the same HEAD on\n> NTFS and msysgit, numbers are the elapsed time in seconds, best of five\n> runs):\n>\n>                            Ubuntu  Fedora  Windows\n>    v1.6.2-rc2                8.14    8.16    9.236\n>    v1.6.2-rc2+[1-4]          2.43    2.45    2.995\n>    v1.6.2-rc2+[1-4]+memmem   1.31    1.25    2.917\n>    v1.6.2-rc2+[1-3]+memmem   1.51    1.16    8.455\n>\n> Ubuntu has glibc 2.8, while Fedora 10 has glibc 2.9, with a new and more\n> efficient memmem() implementation.  On Windows, we use our own naive\n> memmem() implementation.\n\nShoot, I was not being careful enough.\n\n> So using memmem() is worthwhile.  And providing a better fall-back\n> version in compat/ can speed up this particular case to the point where\n> the fourth patch becomes moot.\n\nAre these numbers telling me that with a good memmem() implementation,\npatch 4/4 is not just moot but actively detrimental?\n\nWith a long enough needle, it entirely is possible that scanning the whole\nimage with sublinear string search algorithm would perform much better\nthan the preprocessing patch 4/4 does which has to scan all the bytes in\nthe common parts.\n"},{"id":"106600","messageId":"49AA693B.5060108@lsrfire.ath.cx","threadId":"18027","inReplyTo":"7viqmtaec4.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-03-01T10:53:47Z","receivedAt":"2009-03-01T10:53:47Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Junio C Hamano schrieb:\n> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n> \n>> I get this (Ubuntu 8.10 x64, Fedora 10 x64 using the same Linux repo,\n>> Windows Vista x64 using a different Linux repo with the same HEAD on\n>> NTFS and msysgit, numbers are the elapsed time in seconds, best of five\n>> runs):\n>>\n>>                            Ubuntu  Fedora  Windows\n>>    v1.6.2-rc2                8.14    8.16    9.236\n>>    v1.6.2-rc2+[1-4]          2.43    2.45    2.995\n>>    v1.6.2-rc2+[1-4]+memmem   1.31    1.25    2.917\n>>    v1.6.2-rc2+[1-3]+memmem   1.51    1.16    8.455\n>>\n>> Ubuntu has glibc 2.8, while Fedora 10 has glibc 2.9, with a new and more\n>> efficient memmem() implementation.  On Windows, we use our own naive\n>> memmem() implementation.\n\nCorrection: On Windows, we use the previous, quadratic, naive memmem()\nimplementation from glibc, not anything we came up with.\n\n>> So using memmem() is worthwhile.  And providing a better fall-back\n>> version in compat/ can speed up this particular case to the point where\n>> the fourth patch becomes moot.\n> \n> Are these numbers telling me that with a good memmem() implementation,\n> patch 4/4 is not just moot but actively detrimental?\n> \n> With a long enough needle, it entirely is possible that scanning the whole\n> image with sublinear string search algorithm would perform much better\n> than the preprocessing patch 4/4 does which has to scan all the bytes in\n> the common parts.\n\nYes, patch 4 makes it go slower than using memmem() alone, in this test.\n\nHere are a few more numbers, all measured on Windows.  The topmost four\ntimes in the column \"long\" should be the same as in the Windows column\nabove, yet they are slightly bigger.  Some background process must've\ndecided to do some work.\n\n  git log -S\"$STRING\" HEAD -- kernel/sched.c >/dev/null\n\n  short: STRING='e'\n  long:  STRING='Ensure that the real time constraints are schedulable.'\n\n                                  short  long\n  v1.6.2-rc2                      9.120  9.266\n  v1.6.2-rc2+[1-4]                3.037  3.048\n  v1.6.2-rc2+[1-4]+memmem         2.994  2.964\n  v1.6.2-rc2+[1-3]+memmem         8.514  8.528\n  v1.6.2-rc2+[1-4]+memmem+linear  1.939  1.759\n  v1.6.2-rc2+[1-3]+memmem+linear  2.315  1.559\n\nSo patch 4 helps significantly with short needles, while it hurts a bit\nwith long needles.  Linear memmem() is faster than the quadratic one we\ncurrently have in compat/ in all cases.\n\nRené\n"},{"id":"106601","messageId":"49AA6E35.40205@lsrfire.ath.cx","threadId":"18027","inReplyTo":"20090301034123.GC30384@coredump.intra.peff.net","subject":"Re: [PATCH] import memmem() with linear complexity from Gnulib","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-03-01T11:15:01Z","receivedAt":"2009-03-01T11:15:01Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Jeff King schrieb:\n> On Sat, Feb 28, 2009 at 11:44:01PM +0100, Mike Hommey wrote:\n> \n>>> ---\n>>>  Makefile             |    1 +\n>>>  compat/memmem.c      |  103 +++++++++----\n>>>  compat/str-two-way.h |  429 ++++++++++++++++++++++++++++++++++++++++++++++++++\n>>>  3 files changed, 504 insertions(+), 29 deletions(-)\n>> Seeing how much memmem is being used in the codebase, is it really worth?\n> \n> See earlier in the thread, where \"git log -Stoken\" is substantially\n> faster on Linux versus Windows (but some exact numbers before and after\n> on Windows would be nice to have in the commit message).\n\nYes, and also please see the other numbers I just posted.  It's more of\nan update -- we took the current memmem() fall-back from glibc, too, and\nthey switched to this shiny new implementation to avoid the quadratic\ncomplexity of the old one in the meantime.\n\nI was going to say that with a fast memmem() we could convert some\nstrstr() calls, especially those where we know the lengths of the\nstrings anyway -- intuitively, memmem() should be faster than strstr()\nin that case.  However, the following patch on top of the Gnulib import\nmakes \"git grep grep v1.6.1\" take 10% *more* time for me (on Windows).\nI wonder why.\n\n\ndiff --git a/grep.c b/grep.c\nindex 062b2b6..66ef171 100644\n--- a/grep.c\n+++ b/grep.c\n@@ -39,6 +39,8 @@ static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)\n {\n \tint err;\n \n+\tp->pattern_len = strlen(p->pattern);\n+\n \tif (opt->fixed || is_fixed(p->pattern))\n \t\tp->fixed = 1;\n \tif (opt->regflags & REG_ICASE)\n@@ -268,16 +270,17 @@ static void show_name(struct grep_opt *opt, const char *name)\n \tprintf(\"%s%c\", name, opt->null_following_name ? '\\0' : '\\n');\n }\n \n-static int fixmatch(const char *pattern, char *line, regmatch_t *match)\n+static int fixmatch(const char *pattern, size_t pattern_len, const char *bol,\n+\t\t    const char *eol, regmatch_t *match)\n {\n-\tchar *hit = strstr(line, pattern);\n+\tchar *hit = memmem(bol, eol - bol, pattern, pattern_len);\n \tif (!hit) {\n \t\tmatch->rm_so = match->rm_eo = -1;\n \t\treturn REG_NOMATCH;\n \t}\n \telse {\n-\t\tmatch->rm_so = hit - line;\n-\t\tmatch->rm_eo = match->rm_so + strlen(pattern);\n+\t\tmatch->rm_so = hit - bol;\n+\t\tmatch->rm_eo = match->rm_so + pattern_len;\n \t\treturn 0;\n \t}\n }\n@@ -335,7 +338,7 @@ static int match_one_pattern(struct grep_opt *opt, struct grep_pat *p, char *bol\n \t\t\t       pmatch, 0);\n \t}\n \telse {\n-\t\thit = !fixmatch(p->pattern, bol, pmatch);\n+\t\thit = !fixmatch(p->pattern, p->pattern_len, bol, eol, pmatch);\n \t}\n \n \tif (hit && opt->word_regexp) {\ndiff --git a/grep.h b/grep.h\nindex 5102ce3..2e22ab2 100644\n--- a/grep.h\n+++ b/grep.h\n@@ -28,6 +28,7 @@ struct grep_pat {\n \tint no;\n \tenum grep_pat_token token;\n \tconst char *pattern;\n+\tsize_t pattern_len;\n \tenum grep_header_field field;\n \tregex_t regexp;\n \tunsigned fixed:1;\n"},{"id":"106631","messageId":"49AADA09.6020305@lsrfire.ath.cx","threadId":"18027","inReplyTo":"49AA6E35.40205@lsrfire.ath.cx","subject":"Re: [PATCH] import memmem() with linear complexity from Gnulib","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-03-01T18:55:05Z","receivedAt":"2009-03-01T18:55:05Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"René Scharfe schrieb:\n> I was going to say that with a fast memmem() we could convert some\n> strstr() calls, especially those where we know the lengths of the\n> strings anyway -- intuitively, memmem() should be faster than strstr()\n> in that case.  However, the following patch on top of the Gnulib import\n> makes \"git grep grep v1.6.1\" take 10% *more* time for me (on Windows).\n> I wonder why.\n\nMore numbers.  \"memmem\" is the patch I'm replying to which converts\ngrep's fixed string search from strstr() to memmem().  \"quadratic\" means\nthe current version of compat/memmem.c was used (NO_MEMMEM=yes),\n\"linear\" is the same, but with the newer memmem() from Gnulib imported.\n The numbers are elapsed seconds for the following command, run in a\nLinux kernel repo:\n\n   git grep grep v2.6.28 >/dev/null\n\n                                   Ubuntu Fedora\n   [1] v1.6.2-rc2                    2.99   3.52\n   [2] v1.6.2-rc2+memmem             3.09   3.28\n   [3] v1.6.2-rc2+memmem+quadratic   8.42   8.50\n   [4] v1.6.2-rc2+memmem+linear      3.17   3.25\n\nSo, we should be careful when using memmem() as long as we have the\ncurrent implementation in compat/, as the quadratic complexity can\nresult in a significant slowdown ([3]).\n\nThe new memmem() indeed is faster than the new strstr(), as expected\n(Fedora [2] and [4] vs. Fedora [1]).  Remember, Fedora 10 already\nincludes the glibc version with the linear implementations while Ubuntu\n8.10 doesn't.\n\nI'm not sure if the difference between the old and new memmem() is\nsignificant or in the noise (Ubuntu [2] and [4]).\n\nIn any case, and this surprised me, the fastest of them all is the old\nstrstr() (Ubuntu [1]).  This is consistent with the slowdown observed on\nWindows.\n\nWhat's even more surprising is the difference between Ubuntu [2] and\n[3], which use basically the same memmem().  Or so I thought.  Wrong.\nThe old memmem() in glibc has a small but effective optimization, that\nour version lacks.  I don't remember if I cut it out during the initial\nimport for increased simplicity or if the version the import was based\non didn't have it.  Anyway, with the following patch, case [3] runs as\nfast as case [2] on both Fedora and Ubuntu.\n\nNext step would be to check if pickaxe simply needs this short patch or\nreally the full-blown linear reimplementation.  I'm off to an\nappointment, though, so I'll look into this again tomorrow.\n\nRené\n\n\ndiff --git a/compat/memmem.c b/compat/memmem.c\nindex cd0d877..fed5a77 100644\n--- a/compat/memmem.c\n+++ b/compat/memmem.c\n@@ -5,6 +5,7 @@ void *gitmemmem(const void *haystack, size_t haystack_len,\n {\n \tconst char *begin = haystack;\n \tconst char *last_possible = begin + haystack_len - needle_len;\n+\tchar tip;\n \n \t/*\n \t * The first occurrence of the empty string is deemed to occur at\n@@ -20,8 +21,10 @@ void *gitmemmem(const void *haystack, size_t haystack_len,\n \tif (haystack_len < needle_len)\n \t\treturn NULL;\n \n+\ttip = *((const char *)needle);\n+\n \tfor (; begin <= last_possible; begin++) {\n-\t\tif (!memcmp(begin, needle, needle_len))\n+\t\tif (*begin == tip && !memcmp(begin, needle, needle_len))\n \t\t\treturn (void *)begin;\n \t}\n \n"},{"id":"106737","messageId":"49AC6527.5010808@lsrfire.ath.cx","threadId":"18027","inReplyTo":"cover.1235629933.git.gitster@pobox.com","subject":"[PATCH 1/2] diffcore-pickaxe: use memmem()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-03-02T23:00:55Z","receivedAt":"2009-03-02T23:00:55Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use memmem() instead of open-coding it.  The system libraries usually have a\nmuch faster version than the memcmp()-loop here.  Even our own fall-back in\ncompat/, which is used on Windows, is slightly faster.\n\nThe following commands were run in a Linux kernel repository and timed, the\nbest of five results is shown:\n\n  $ STRING='Ensure that the real time constraints are schedulable.'\n  $ git log -S\"$STRING\" HEAD -- kernel/sched.c >/dev/null\n\nOn Ubuntu 8.10 x64, before (v1.6.2-rc2):\n\n  8.09user 0.04system 0:08.14elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+30952minor)pagefaults 0swaps\n\nAnd with the patch:\n\n  1.50user 0.04system 0:01.54elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+30645minor)pagefaults 0swaps\n\nOn Fedora 10 x64, before:\n\n  8.34user 0.05system 0:08.39elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+29268minor)pagefaults 0swaps\n\nAnd with the patch:\n\n  1.15user 0.05system 0:01.20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+32253minor)pagefaults 0swaps\n\nOn Windows Vista x64, before:\n\n  real    0m9.204s\n  user    0m0.000s\n  sys     0m0.000s\n\nAnd with the patch:\n\n  real    0m8.470s\n  user    0m0.000s\n  sys     0m0.000s\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n---\n diffcore-pickaxe.c |   18 ++++++++----------\n 1 files changed, 8 insertions(+), 10 deletions(-)\n\ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nindex af9fffe..574b3e8 100644\n--- a/diffcore-pickaxe.c\n+++ b/diffcore-pickaxe.c\n@@ -10,7 +10,7 @@ static unsigned int contains(struct diff_filespec *one,\n \t\t\t     regex_t *regexp)\n {\n \tunsigned int cnt;\n-\tunsigned long offset, sz;\n+\tunsigned long sz;\n \tconst char *data;\n \tif (diff_populate_filespec(one, 0))\n \t\treturn 0;\n@@ -33,15 +33,13 @@ static unsigned int contains(struct diff_filespec *one,\n \t\t}\n \n \t} else { /* Classic exact string match */\n-\t\t/* Yes, I've heard of strstr(), but the thing is *data may\n-\t\t * not be NUL terminated.  Sue me.\n-\t\t */\n-\t\tfor (offset = 0; offset + len <= sz; offset++) {\n-\t\t\t/* we count non-overlapping occurrences of needle */\n-\t\t\tif (!memcmp(needle, data + offset, len)) {\n-\t\t\t\toffset += len - 1;\n-\t\t\t\tcnt++;\n-\t\t\t}\n+\t\twhile (sz) {\n+\t\t\tconst char *found = memmem(data, sz, needle, len);\n+\t\t\tif (!found)\n+\t\t\t\tbreak;\n+\t\t\tsz -= found - data + len;\n+\t\t\tdata = found + len;\n+\t\t\tcnt++;\n \t\t}\n \t}\n \tdiff_free_filespec_data(one);\n-- \n1.6.2.rc2\n"},{"id":"106739","messageId":"49AC6982.6000804@lsrfire.ath.cx","threadId":"18027","inReplyTo":"49AC6527.5010808@lsrfire.ath.cx","subject":"[PATCH 2/2] optimize compat/ memmem()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2009-03-02T23:19:30Z","receivedAt":"2009-03-02T23:19:30Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"When memmem() was imported from glibc 2.2 into compat/, an optimization\nwas dropped in the process, in order to make the code smaller and simpler.\nIt was OK because memmem() wasn't used in performance-critical code.  Now\nthe situation has changed and we can benefit from this optimization.\n\nThe trick is to avoid calling memcmp() if the first character of the needle\nalready doesn't match.  Checking one character directly is much cheaper\nthan the function call overhead.  We keep the first character of the needle\nin the variable named point and the rest in the one named tail.\n\nThe following commands were run in a Linux kernel repository and timed, the\nbest of five results is shown:\n\n  $ STRING='Ensure that the real time constraints are schedulable.'\n  $ git log -S\"$STRING\" HEAD -- kernel/sched.c >/dev/null\n\nOn Windows Vista x64, before:\n\n  real    0m8.470s\n  user    0m0.000s\n  sys     0m0.000s\n\nAnd after the patch:\n\n  real    0m1.887s\n  user    0m0.000s\n  sys     0m0.000s\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n---\nThis performance fix is a good idea, even if we later decide to import\nthe latest version of memmem() from Gnulib, I think.  And I'm not so\nsure any more that we want to do that in the first place.  More\nmeasurements are needed (which goes for these two patches, too, of\ncourse), but this version should provide a better baseline.\n\n compat/memmem.c |    5 ++++-\n 1 files changed, 4 insertions(+), 1 deletions(-)\n\ndiff --git a/compat/memmem.c b/compat/memmem.c\nindex cd0d877..56bcb42 100644\n--- a/compat/memmem.c\n+++ b/compat/memmem.c\n@@ -5,6 +5,8 @@ void *gitmemmem(const void *haystack, size_t haystack_len,\n {\n \tconst char *begin = haystack;\n \tconst char *last_possible = begin + haystack_len - needle_len;\n+\tconst char *tail = needle;\n+\tchar point;\n \n \t/*\n \t * The first occurrence of the empty string is deemed to occur at\n@@ -20,8 +22,9 @@ void *gitmemmem(const void *haystack, size_t haystack_len,\n \tif (haystack_len < needle_len)\n \t\treturn NULL;\n \n+\tpoint = *tail++;\n \tfor (; begin <= last_possible; begin++) {\n-\t\tif (!memcmp(begin, needle, needle_len))\n+\t\tif (*begin == point && !memcmp(begin + 1, tail, needle_len - 1))\n \t\t\treturn (void *)begin;\n \t}\n \n-- \n1.6.2.rc2\n"}]}