Re: [RFC 2/*] Benchmarking memmem

[OndÅej BÃlka <neleai at seznam dot cz>]

On Wed, Sep 04, 2013 at 02:07:59AM +0200, OndÅej BÃlka wrote:
> continuing check memchr and memcmp were ok.
> 
> When we look to memmem from results it is not clear if simple_memmem is
> slower or faster or what.
> 
To continue tradition of alternative implementations this patch add
stupid variant and results become clear.

                    simple_memmem stupid_memmem memmem
String 00000, offset 0: 70  16  171
String 00000, offset 7: 86  15  171
String 00000, offset 14:  111 15  176
String 00000, offset 21:  171 20  181
String 00000, offset 28:  191 15  181
String 00000, offset 35:  206 20  176
String 00000, offset 42:  222 15  176
String 00000, offset 49:  242 15  181
String 00000, offset 56:  257 20  181
String 00000, offset 63:  277 20  177
String 00000, offset 70:  292 20  177
String 00000, offset 77:  312 25  186
String 00000, offset 84:  338 30  186
String 00000, offset 91:  348 25  187
String 00000, offset 98:  363 25  186
String 00000, offset 105: 383 25  191
String 00000, offset 112: 403 30  191
String 00000, offset 119: 418 30  191


diff --git a/benchtests/bench-memmem.c b/benchtests/bench-memmem.c
index ca758a8..80822cd 100644
--- a/benchtests/bench-memmem.c
+++ b/benchtests/bench-memmem.c
@@ -24,9 +24,12 @@
 
 typedef char *(*proto_t) (const void *, size_t, const void *, size_t);
 void *simple_memmem (const void *, size_t, const void *, size_t);
+void *stupid_memmem (const void *, size_t, const void *, size_t);
+
 
 IMPL (simple_memmem, 0)
-IMPL (memmem, 1)
+IMPL (stupid_memmem, 1)
+IMPL (memmem, 2)
 
 void *
 simple_memmem (const void *haystack, size_t haystack_len, const void *needle,
@@ -56,6 +59,44 @@ simple_memmem (const void *haystack, size_t haystack_len, const void *needle,
   return NULL;
 }
 
+
+void *
+stupid_memmem (const void *haystack, size_t haystack_len, const void *needle,
+	       size_t needle_len)
+{
+  const char *begin, *needle2;
+  const char *const last_possible
+    = (const char *) haystack + haystack_len - needle_len;
+
+  if (needle_len == 0)
+    /* The first occurrence of the empty string is deemed to occur at
+       the beginning of the string.  */
+    return (void *) haystack;
+
+  /* Sanity check, otherwise the loop might search through the whole
+     memory.  */
+  if (__builtin_expect (haystack_len < needle_len, 0))
+    return NULL;
+
+  begin =  (const char *) haystack;
+  needle2 =  (const char *) needle;
+
+  while (1) {
+    begin=memchr(begin,needle2[0],last_possible-begin+1);
+    if (!begin)
+      return NULL;
+    size_t i;
+    for (i=0;needle2[i]==begin[i];i++)
+      if (i+1==needle_len)
+        return begin;
+    if (begin==last_possible)
+      return NULL;
+    begin++;
+  }
+}
+
+
+
 static void
 do_one_test (impl_t *impl, const void *haystack, size_t haystack_len,
 	     const void *needle, size_t needle_len, const void *expected)