This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
[PATCH 1/4] Optimize first-character loop of strstr, strcasestr and memmem for short needle.
- From: Maxim Kuvyrkov <maxim at codesourcery dot com>
- To: Carlos O'Donell <carlos at codesourcery dot com>
- Cc: GLIBC Devel <libc-alpha at sourceware dot org>, Eric Blake <eblake at redhat dot com>,Ryan Arnold <rsa at us dot ibm dot com>
- Date: Wed, 30 May 2012 21:08:50 +1200
- Subject: [PATCH 1/4] Optimize first-character loop of strstr, strcasestr and memmem for short needle.
- References: <2C516CF2-D083-4C1D-AD27-6A31D381D548@codesourcery.com>
[PATCH 1/4] Optimize first-character loop of strstr, strcasestr and memmem for short needle.
--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics
[BZ #11607]
* string/str-two-way.h (two_way_short_needle): Optimize matching of
the first character.
---
string/str-two-way.h | 15 ++++++++++++++-
1 files changed, 14 insertions(+), 1 deletions(-)
diff --git a/string/str-two-way.h b/string/str-two-way.h
index 1b2a8bd..3791404 100644
--- a/string/str-two-way.h
+++ b/string/str-two-way.h
@@ -261,14 +261,27 @@ two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
}
else
{
+ /* The comparison always starts from needle[suffix], so cache it
+ and use an optimized first-character loop. */
+ unsigned char needle_suffix = CANON_ELEMENT (needle[suffix]);
+
/* The two halves of needle are distinct; no extra memory is
required, and any mismatch results in a maximal shift. */
period = MAX (suffix, needle_len - suffix) + 1;
j = 0;
while (AVAILABLE (haystack, haystack_len, j, needle_len))
{
+ /* TODO: The first-character loop can be sped up by adapting
+ longword-at-a-time implementation of memchr/strchr. */
+ if (needle_suffix
+ != CANON_ELEMENT (haystack[suffix + j]))
+ {
+ ++j;
+ continue;
+ }
+
/* Scan for matches in right half. */
- i = suffix;
+ i = suffix + 1;
while (i < needle_len && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
++i;
--
1.7.4.1