[PATCH 1/4] Optimize first-character loop of strstr, strcasestr and memmem for short needle.

[Carlos O'Donell]

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