This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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





Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]