Re: [PATCH] Speedup wc -l

[Pádraig Brady]

On 18/03/15 17:24, Bernhard Voelker wrote:
> On 03/18/2015 04:57 PM, Pádraig Brady wrote:
>> +  wc -l is now up to 6 times faster with short lines.
> 
>> diff --git a/src/wc.c b/src/wc.c
>> index 8cb5163..8125100 100644
>> --- a/src/wc.c
>> +++ b/src/wc.c
>> @@ -264,6 +264,8 @@ wc (int fd, char const *file_x, struct fstatus *fstatus, 
>> off_t current_pos)
>>       {
>>         /* Use a separate loop when counting only lines or lines and bytes --
>>            but not chars or words.  */
>> +      bool long_lines = false;
>> +      bool check_len = true;
>>         while ((bytes_read = safe_read (fd, buf, BUFFER_SIZE)) > 0)
>>           {
>>             char *p = buf;
>> @@ -275,12 +277,39 @@ wc (int fd, char const *file_x, struct fstatus 
>> *fstatus, off_t current_pos)
>>                 break;
>>               }
>>
>> +          char *end = p + bytes_read;
>> +          char *line_start = p;
>> +
>> +          /* Avoid function call overhead for shorter lines.  */
>> +          if (check_len)
>> +            while (p != end)
>> +              {
>> +                lines += *p++ == '\n';
>> +                /* If there are more than 300 chars in the first 10 lines,
>> +                   then use memchr, where system specific optimizations
>> +                   may outweigh any function call overhead.  */
>> +                if (lines <= 10)
>> +                  {
>> +                    if (p - line_start > 300)
>> +                      {
>> +                        long_lines = true;
>> +                        break;
>> +                      }
>> +                  }
>> +              }
>> +          else if (! long_lines)
>> +            while (p != end)
>> +              lines += *p++ == '\n';
>> +
> 
> Doesn't this run into the memchr loop in both cases
> (which the compiler seems to optimize away, but looks odd)?

There will be a single memchr(,,0) call per block which is insignificant.

>> +          /* memchr is more efficient with longer lines.  */
>>             while ((p = memchr (p, '\n', (buf + bytes_read) - p)))
>>               {
>>                 ++p;
>>                 ++lines;
>>               }
>> +
>>             bytes += bytes_read;
>> +          check_len = false;
>>           }
>>       }
>>   #if MB_LEN_MAX > 1
> 
> In my first tests I can second the speedup for short lines.
> 
> Where do you have the magic 30 from?
> Tests here show that the effect reverses with line length
> between 10 and ~27, i.e., the new version is ~80% slower.
> Beyond that, both versions behave the same, as expected.
> I have to test more this night.

Yes 30 was a bit aggressive.
I had already changed it to 15 (150) locally here after more testing.

Latest attached.

thanks for the careful review!
Pádraig.

wc-l-short-lines.patch
Description: Text Data