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, strcasestrand memmem for short needle.
- From: Carlos O'Donell <carlos_odonell at mentor dot com>
- To: Maxim Kuvyrkov <maxim at codesourcery 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 08:30:30 -0400
- Subject: Re: [PATCH 1/4] Optimize first-character loop of strstr, strcasestrand memmem for short needle.
- References: <2C516CF2-D083-4C1D-AD27-6A31D381D548@codesourcery.com> <64727868-8BC5-4513-B220-20A0E55D5DBE@codesourcery.com> <502DB184.1080707@mentor.com> <BF4F62B9-3C7C-4D0C-BCE6-7C810C49CC0B@codesourcery.com>
On 8/20/2012 7:33 PM, Maxim Kuvyrkov wrote:
> 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.
That makes sense. Thanks.
Cheers,
Carlos.
--
Carlos O'Donell
Mentor Graphics / CodeSourcery
carlos_odonell@mentor.com
carlos@codesourcery.com
+1 (613) 963 1026