This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [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_odonell at mentor dot com>
- Cc: Carlos O'Donell <carlos at codesourcery dot com>, 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: Tue, 21 Aug 2012 11:33:54 +1200
- Subject: Re: [PATCH 1/4] Optimize first-character loop of strstr, strcasestr and memmem for short needle.
- References: <2C516CF2-D083-4C1D-AD27-6A31D381D548@codesourcery.com> <64727868-8BC5-4513-B220-20A0E55D5DBE@codesourcery.com> <502DB184.1080707@mentor.com>
On 17/08/2012, at 2:50 PM, Carlos O'Donell wrote:
> On 5/30/2012 5:08 AM, Maxim Kuvyrkov wrote:
>> [PATCH 1/4] Optimize first-character loop of strstr, strcasestr and memmem for short needle.
...
>>
>> {
>> + /* 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]);
>> +
>
> OK.
>
>> /* 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;
>> + }
>> +
>
> OK.
>
>> /* Scan for matches in right half. */
>> - i = suffix;
>> + i = suffix + 1;
>
> OK. Though I can't quite figure out why we went from suffix => suffix +1.
That's because we processed suffix'th element (which is the element we start comparison from) in the if-statement above -- needle[suffix] is disguised as needle_suffix there.
Thanks for the reviews!
--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics