{"thread":{"id":"11072","subject":"memmem.c improvement","startedAt":"2007-12-01T00:48:15Z","lastAt":"2007-12-01T03:07:01Z","messageCount":4,"participants":["Christian Thaeter","Tor Myklebust"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"61532","messageId":"4750AF4F.6090207@pipapo.org","threadId":"11072","inReplyTo":null,"subject":"memmem.c improvement","fromName":"Christian Thaeter","fromEmail":"ct@pipapo.org","sentAt":"2007-12-01T00:48:15Z","receivedAt":"2007-12-01T00:48:15Z","isPatch":false,"sender":{"key":"ct@pipapo.org","avatar":null},"body":"Short story, 'memmem()' is a gnuish, nonstandard function. I wanted to\nprovide a generic fallback in some code. So, lets borrow it somewhere else:\n\nFirst looking at git's compat/memmem.c which I found was suboptimal with\nroughly O(M*N) performance (albeit ok for that case since it was just a\ngeneric fallback).\n\nWell, second taking a look at glibc's source surprised me, there is the\nsame code as in git. I somewhat expected a faster implementation from a\ngeneric C library.\n\nThat thought and done, the code is attached to this mail. The algorithm\nis similar to the Rabin/Karp method for string searches but uses a\nweaker and simpler additive rolling hash. The result is still somewhat\nlike O(M+N) for most cases (There may be corner cases where it not that\ngood, but its really hard to imagine those). Anyways, it is always\nfaster than the current implementation, in my tests with common data\n(parsing multipart/form-data cgi responses) it yields approx 20%-100%\nimprovements and with little artificial cheating (having strings in\nhaystack which only differ at the last char of needle) the improvements\nare much better (500%, since is another complexity class). The fact is\nthat the old implementation does a brute force search which has corner\ncases which are quite easy to hit (repeating symbol sequences, small set\nof possible symbols) while for my implementation the corner cases are\nmuch more rare and even then, it will still perform better than the old\nimplementation.\n\nThe code is not much more complex as the old one, not the original\n'Rabin/Karp' algorithm because that would require a efficient modulo\noperation with a prime number which might be slower on some platforms\n(just a guess, I didn't even tried, the performance satisfies me\nperfectly). Other search algorithms like 'Knuth/Morris/Pratt' or\n'Boyer/More' are more complex to implement and require O(Needle) extra\nmemory for common implementations, which reserve them for special\npurposes imo. I just wanted to keep it simple but still considerably\nbetter than the current one.\n\nFeel free to use the code in glibc and/or git.\n\n\tChristian\n\n\n/* Copyright (C) 1991,92,93,94,96,97,98,2000,2004 Free Software Foundation, Inc.\n   This file is part of the GNU C Library.\n\n   The GNU C Library is free software; you can redistribute it and/or\n   modify it under the terms of the GNU Lesser General Public\n   License as published by the Free Software Foundation; either\n   version 2.1 of the License, or (at your option) any later version.\n\n   The GNU C Library 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 GNU\n   Lesser General Public License for more details.\n\n   You should have received a copy of the GNU Lesser General Public\n   License along with the GNU C Library; if not, write to the Free\n   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA\n   02111-1307 USA.  */\n\n#include <stddef.h>\n#include <string.h>\n\n#ifndef _LIBC\n# define __builtin_expect(expr, val)   (expr)\n#endif\n\n#undef memmem\n\n/* Return the first occurrence of NEEDLE in HAYSTACK. */\nvoid *\nmemmem (haystack, haystack_len, needle, needle_len)\n     const void *haystack;\n     size_t haystack_len;\n     const void *needle;\n     size_t needle_len;\n{\n  /* not really Rabin-Karp, just using additive hashing */\n  char* haystack_ = (char*)haystack;\n  char* needle_ = (char*)needle;\n  int hash = 0;\t\t/* this is the static hash value of the needle */\n  int hay_hash = 0;\t/* rolling hash over the haystack */\n  char* last;\n  size_t i;\n\n  if (haystack_len < needle_len)\n    return NULL;\n\n  if (!needle_len)\n    return haystack_;\n\n  /* initialize hashes */\n  for (i = needle_len; i; --i)\n    {\n      hash += *needle_++;\n      hay_hash += *haystack_++;\n    }\n\n  /* iterate over the haystack */\n  haystack_ = (char*)haystack;\n  needle_ = (char*)needle;\n  last = haystack_+(haystack_len - needle_len + 1);\n  for (; haystack_ < last; ++haystack_)\n    {\n      if (__builtin_expect(hash == hay_hash, 0) &&\n\t  *haystack_ == *needle_ &&\t/* prevent calling memcmp, was a optimization from existing glibc */\n\t  !memcmp (haystack_, needle_, needle_len))\n\treturn haystack_;\n\n      /* roll the hash */\n      hay_hash -= *haystack_;\n      hay_hash += *(haystack_+needle_len);\n    }\n\n  return NULL;\n}\n"},{"id":"61535","messageId":"Pine.LNX.4.64.0711301954370.9426@caffeine.csclub.uwaterloo.ca","threadId":"11072","inReplyTo":"4750AF4F.6090207@pipapo.org","subject":"Re: (class=ham score=-4.96032) memmem.c improvement","fromName":"Tor Myklebust","fromEmail":"tmyklebu@csclub.uwaterloo.ca","sentAt":"2007-12-01T01:58:10Z","receivedAt":"2007-12-01T01:58:10Z","isPatch":false,"sender":{"key":"tmyklebu@csclub.uwaterloo.ca","avatar":null},"body":"On Sat, 1 Dec 2007, Christian Thaeter wrote:\n\n> Short story, 'memmem()' is a gnuish, nonstandard function. I wanted to \n> provide a generic fallback in some code. So, lets borrow it somewhere \n> else:\n>\n> First looking at git's compat/memmem.c which I found was suboptimal with \n> roughly O(M*N) performance (albeit ok for that case since it was just a \n> generic fallback).\n>\n> Well, second taking a look at glibc's source surprised me, there is the \n> same code as in git. I somewhat expected a faster implementation from a \n> generic C library.\n\nI don't think anybody involved with glibc really feels like having \nstrstr() (or memmem(), for that matter) go fast.  (The grounds I heard \nwere that \"applications requiring large searches are more likely to have \nown fast string search implementations.')\n\n> That thought and done, the code is attached to this mail. The algorithm \n> is similar to the Rabin/Karp method for string searches but uses a \n> weaker and simpler additive rolling hash.\n\nThere are rolling hashes based on arithmetic in fields of order 2^k. \nThese can typically be computed using a bunch of bit-shifts and additions; \nhave you tried using one?  There are lots of irreducible polynomials over \nZ_2 of degree k, so you can even fall back to a different one every few \nfalse positives.\n\n> The result is still somewhat like O(M+N) for most cases\n\nI don't think you get linear performance in the average case.  (But I do \nthink you shave a factor of 256 off of the quadratic term.  The same \nalgorithm, where your hash function is the population count, gives a \ncollision between two random strings of length m with probability \nsum_(i=0)^m (m choose i)^2 / 4^m, which grows like sqrt(m).  Your \nalgorithm helps this by a factor of 256.)\n\n> (There may be corner cases where it not that good, but its really hard \n> to imagine those).\n\nThe needle \"1100110011001100...1100\" and the haystack \n\"10101010101010...10\" will produce quite a few false matches with your \nhash function (simply because every substring of the haystack of the \nappropriate length has the same hash as your needle).  (Making the needle \n\"1010101010...101100\" makes it even worse.)\n\n> Anyways, it is always faster than the current implementation,\n\nTry the example above.  (Your code also needs a \"return NULL;\" at the end, \nby the way.)\n\n> in my tests with common data (parsing multipart/form-data cgi responses) \n> it yields approx 20%-100% improvements and with little artificial \n> cheating (having strings in haystack which only differ at the last char \n> of needle) the improvements are much better (500%, since is another \n> complexity class). The fact is that the old implementation does a brute \n> force search which has corner cases which are quite easy to hit \n> (repeating symbol sequences, small set of possible symbols) while for my \n> implementation the corner cases are much more rare and even then, it \n> will still perform better than the old implementation.\n\nThe old implementation is about 50% faster than yours in the example \nabove.\n\n> The code is not much more complex as the old one, not the original \n> 'Rabin/Karp' algorithm because that would require a efficient modulo \n> operation with a prime number which might be slower on some platforms \n> (just a guess, I didn't even tried, the performance satisfies me \n> perfectly).\n\nKarp-Rabin with hashing done mod a prime is an impractical string matching \nalgorithm.\n\n> Other search algorithms like 'Knuth/Morris/Pratt'\n\nA KMP-like algorithm can be implemented in a way that uses constant \nadditional space.  For unordered alphabets, it's called \"Galil-Seiferas\" \nand for ordered alphabets the analogous algorithm is to decompose (in \nlinear time and constant space) the string into its lexicographically \nlargest suffix and some prefix.  Then you look for the suffix.  Everywhere \nwhere the suffix appears and appears at least prefix-length later than the \nlast occurrence of the suffix, you check for the prefix.\n\n> or 'Boyer/More' are more complex to implement and require O(Needle) \n> extra memory\n\nThere are variants of both that require constant additional space.  (They \nalso perform way better than anything else I've seen.)\n\n> for common implementations, which reserve them for special purposes imo. \n> I just wanted to keep it simple but still considerably better than the \n> current one.\n\nAs it happens, the extra space consumed by the KMP and suffix shift tables \n(and the associated bad cache effects) make the usual KMP and Boyer-Moore \nway, way slower than naive string matching on random inputs.\n"},{"id":"61537","messageId":"4750C74B.8060308@pipapo.org","threadId":"11072","inReplyTo":"Pine.LNX.4.64.0711301954370.9426@caffeine.csclub.uwaterloo.ca","subject":"Re: (class=ham score=-4.96032) memmem.c improvement","fromName":"Christian Thaeter","fromEmail":"ct@pipapo.org","sentAt":"2007-12-01T02:30:35Z","receivedAt":"2007-12-01T02:30:35Z","isPatch":false,"sender":{"key":"ct@pipapo.org","avatar":null},"body":"Tor Myklebust wrote:\n> On Sat, 1 Dec 2007, Christian Thaeter wrote:\n> \n>> Short story, 'memmem()' is a gnuish, nonstandard function. I wanted to\n>> provide a generic fallback in some code. So, lets borrow it somewhere\n>> else:\n>>\n>> First looking at git's compat/memmem.c which I found was suboptimal\n>> with roughly O(M*N) performance (albeit ok for that case since it was\n>> just a generic fallback).\n>>\n>> Well, second taking a look at glibc's source surprised me, there is\n>> the same code as in git. I somewhat expected a faster implementation\n>> from a generic C library.\n> \n> I don't think anybody involved with glibc really feels like having\n> strstr() (or memmem(), for that matter) go fast.  (The grounds I heard\n> were that \"applications requiring large searches are more likely to have\n> own fast string search implementations.')\n> \n>> That thought and done, the code is attached to this mail. The\n>> algorithm is similar to the Rabin/Karp method for string searches but\n>> uses a weaker and simpler additive rolling hash.\n> \n> There are rolling hashes based on arithmetic in fields of order 2^k.\n> These can typically be computed using a bunch of bit-shifts and\n> additions; have you tried using one?  There are lots of irreducible\n> polynomials over Z_2 of degree k, so you can even fall back to a\n> different one every few false positives.\n> \n>> The result is still somewhat like O(M+N) for most cases\n> \n> I don't think you get linear performance in the average case.  (But I do\n> think you shave a factor of 256 off of the quadratic term.  The same\n> algorithm, where your hash function is the population count, gives a\n> collision between two random strings of length m with probability\n> sum_(i=0)^m (m choose i)^2 / 4^m, which grows like sqrt(m).  Your\n> algorithm helps this by a factor of 256.)\n...\n> \n>> (There may be corner cases where it not that good, but its really hard\n>> to imagine those).\n> \n> The needle \"1100110011001100...1100\" and the haystack\n> \"10101010101010...10\" will produce quite a few false matches with your\n> hash function (simply because every substring of the haystack of the\n> appropriate length has the same hash as your needle).  (Making the\n> needle \"1010101010...101100\" makes it even worse.)\n\nI am fully aware that this is not the best possible search algorithm. It\nis considerably better than the actual one for 'common' data. Having a\nstring with few symbols or other corner cases needs an algorithm better\nsuited for that task. But well, this was just reaching a low hanging\nfruit. I just wanted to share it because it is better than the algorithm\nwhich is in git and glibc, feel free to submit a even better one or keep\nthe old one, whatever. For me it suffices and I won't put more efforts\ninto improving or lobbying it, its just not worth it.\n\n\tChristian\n"},{"id":"61556","messageId":"Pine.LNX.4.64.0711302151340.9426@caffeine.csclub.uwaterloo.ca","threadId":"11072","inReplyTo":"4750C74B.8060308@pipapo.org","subject":"Re: memmem.c improvement","fromName":"Tor Myklebust","fromEmail":"tmyklebu@csclub.uwaterloo.ca","sentAt":"2007-12-01T03:07:01Z","receivedAt":"2007-12-01T03:07:01Z","isPatch":false,"sender":{"key":"tmyklebu@csclub.uwaterloo.ca","avatar":null},"body":"On Sat, 1 Dec 2007, Christian Thaeter wrote:\n\n> I am fully aware that this is not the best possible search algorithm.\n> It is considerably better than the actual one for 'common' data.\n\nAnd not considerably worse in the worst case I could think of.  (Which was \nmy point, not that it was slow or sucked in some other way.)\n\n> Having a string with few symbols or other corner cases needs an \n> algorithm better suited for that task.\n\nYes, if it's actually worth anyone's time making strstr() fast in the case \nwhere the haystack has length three and the needle length two.\n\nAmusingly enough, I haven't ever seen strstr() used to do any nontrivial \nstring matching in any free software I've bothered to grep.\n\n> But well, this was just reaching a low hanging fruit.\n\nSuitably hacked, your code looks clearly correct.  But there are valid \nreasons not to mess with the strstr() in libc (fewer for memmem()); chief \namong them is that *if* there is an undetected bug in the code, *then* \nlots of stuff can break.\n\n> For me it suffices and I won't put more efforts into improving or \n> lobbying it, its just not worth it.\n\nClearly, the tone of my email did not help convey my message.  (Perhaps I \nshould just stop trying to write words of encouragement altogether --- it \nnever goes according to plan and always seems to end in disaster.)  I do \ncommend you for submitting improvements (and this is clearly an \nimprovement); I was merely trying to point out that it will likely be an \nuphill battle, and that certain things are either wrong or can be done \nbetter than you have done.  Do go on, please!  (And I'm sorry if my \nprevious email caused you particular dismay.)\n\nTor Myklebust\n"}]}