[bug-diffutils] bug#15241: Multithreading support?

[David Balažic]

Additional tests, using the command from the patch (same router):

cmp -n 8GiB /dev/full /dev/zero

v3.3: 23 sec
size_t patch: 20 sec
size_t+rawmemchr: 8 secs

cmp -n 8GiB /dev/full /dev/zero

v3.3: 4.7 sec
size_t patch: 5.3 sec
size_t+rawmemchr: 3.7 secs



On 1 September 2013 22:57, David Balažic <address@hidden> wrote:
> Hi!
>
> I finally tested the patches on my Netgear WNDR3700v2 router running
> OpenWRT 12.09 "Attitude Ajdustment".
>
> I tested the "builtin" cmp (part of busybox), and versions of cmp
> compiled by me:
>  - unmodified diffutils-3.3 ("./cmp")
>  - patch # define word size_t ("./cmpp1")
>  - additionally patch tune by using rawmemchr ("./cmpp2")
>
> I did two tests:
>
>  - test file with random contents:
> dd if=/dev/urandom of=test bs=1M count=17
> time cmp test test # busybox cmp reads the inputs even if they are the same 
> file
> 1.22 seconds
>
> time cat test | ./cmp test  -
> real    0m 0.90s
>
> time cat test | ./cmpp1 test  -
> real    0m 0.80s
>
> time cat test | ./cmpp2 test  -
> real    0m 0.60s
>
> (average of multiple runs)
>
>  - test with /dev/zero
>
> # dd if=/dev/zero bs=1M count=64 | time ./cmp - /dev/zero
> 64+0 records in
> 64+0 records out
> cmp: EOF on -
> Command exited with non-zero status 1
> real    0m 2.79s
> user    0m 1.12s
> sys     0m 0.94s
>
>
> # dd if=/dev/zero bs=1M count=64 | time ./cmpp1 - /dev/zero
> 64+0 records in
> 64+0 records out
> cmp: EOF on -
> Command exited with non-zero status 1
> real    0m 2.53s
> user    0m 1.13s
> sys     0m 0.80s
>
> # dd if=/dev/zero bs=1M count=64 | time ./cmpp2 - /dev/zero
> 64+0 records in
> 64+0 records out
> cmp: EOF on -
> Command exited with non-zero status 1
> real    0m 1.80s
> user    0m 0.32s
> sys     0m 0.69s
>
>
> So both patches seem to improve speed on this machine, especially the second.
>
> Regards,
> David
>
>
> On 23 August 2013 00:59, Paul Eggert <address@hidden> wrote:
>> On 08/13/13 08:48, David Balažic wrote:
>>> I'll try to benchmark it on my ARM based router, when time permits.
>>
>> Thanks.  While you're at it, could you also benchmark the following
>> patch, which I just now pushed to the diffutils git master on
>> Savannah?
>>
>> From 6749fe1ddd6805828b526c73b2f1a579eb0d9f63 Mon Sep 17 00:00:00 2001
>> From: Paul Eggert <address@hidden>
>> Date: Thu, 22 Aug 2013 15:45:56 -0700
>> Subject: [PATCH] cmp, diff, sdiff: tune by using rawmemchr
>>
>> On my platform (AMD Phenom II X4 910e, Fedora 17 x86-64), this sped up
>> 'cmp -n 8GiB /dev/full /dev/zero' by a factor of 3.8, and
>> 'cmp -sn 8GiB /dev/full /dev/zero' by a factor of 1.8.
>> * bootstrap.conf (gnulib_modules): Add rawmemchr.
>> * src/cmp.c (cmp): Optimize the common case where buffers are the same,
>> by using count_newlines rather than block_compare_and_count.
>> (block_compare_and_count): Remove.
>> (count_newlines): New function.
>> * src/cmp.c (count_newlines):
>> * src/io.c (prepare_text):
>> * src/sdiff.c (lf_copy, lf_skip, lf_snarf):
>> Use rawmemchr instead of memchr, for speed.
>> ---
>>  bootstrap.conf |  1 +
>>  src/cmp.c      | 88 
>> +++++++++++++++++++---------------------------------------
>>  src/io.c       | 24 ++++++++++------
>>  src/sdiff.c    | 10 +++----
>>  4 files changed, 51 insertions(+), 72 deletions(-)
>>
>> diff --git a/bootstrap.conf b/bootstrap.conf
>> index 240754b..ac85adf 100644
>> --- a/bootstrap.conf
>> +++ b/bootstrap.conf
>> @@ -56,6 +56,7 @@ mkstemp
>>  mktime
>>  progname
>>  propername
>> +rawmemchr
>>  readme-release
>>  regex
>>  sh-quote
>> diff --git a/src/cmp.c b/src/cmp.c
>> index 97473c9..9e35b07 100644
>> --- a/src/cmp.c
>> +++ b/src/cmp.c
>> @@ -52,7 +52,7 @@
>>  static int cmp (void);
>>  static off_t file_position (int);
>>  static size_t block_compare (word const *, word const *) _GL_ATTRIBUTE_PURE;
>> -static size_t block_compare_and_count (word const *, word const *, off_t *);
>> +static size_t count_newlines (char *, size_t);
>>  static void sprintc (char *, unsigned char);
>>
>>  /* Filenames of the compared files.  */
>> @@ -448,20 +448,23 @@ cmp (void)
>>        if (read1 == SIZE_MAX)
>>         error (EXIT_TROUBLE, errno, "%s", file[1]);
>>
>> -      /* Insert sentinels for the block compare.  */
>> +      smaller = MIN (read0, read1);
>>
>> -      buf0[read0] = ~buf1[read0];
>> -      buf1[read1] = ~buf0[read1];
>> +      /* Optimize the common case where the buffers are the same.  */
>> +      if (memcmp (buf0, buf1, smaller) == 0)
>> +       first_diff = smaller;
>> +      else
>> +       {
>> +         /* Insert sentinels for the block compare.  */
>> +         buf0[read0] = ~buf1[read0];
>> +         buf1[read1] = ~buf0[read1];
>>
>> -      /* If the line number should be written for differing files,
>> -        compare the blocks and count the number of newlines
>> -        simultaneously.  */
>> -      first_diff = (comparison_type == type_first_diff
>> -                   ? block_compare_and_count (buffer0, buffer1, 
>> &line_number)
>> -                   : block_compare (buffer0, buffer1));
>> +         first_diff = block_compare (buffer0, buffer1);
>> +       }
>>
>>        byte_number += first_diff;
>> -      smaller = MIN (read0, read1);
>> +      if (comparison_type == type_first_diff)
>> +       line_number += count_newlines (buf0, first_diff);
>>
>>        if (first_diff < smaller)
>>         {
>> @@ -567,54 +570,6 @@ cmp (void)
>>    return differing == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
>>  }
>>
>> -/* Compare two blocks of memory P0 and P1 until they differ,
>> -   and count the number of '\n' occurrences in the common
>> -   part of P0 and P1.
>> -   If the blocks are not guaranteed to be different, put sentinels at the 
>> ends
>> -   of the blocks before calling this function.
>> -
>> -   Return the offset of the first byte that differs.
>> -   Increment *COUNT by the count of '\n' occurrences.  */
>> -
>> -static size_t
>> -block_compare_and_count (word const *p0, word const *p1, off_t *count)
>> -{
>> -  word l;              /* One word from first buffer. */
>> -  word const *l0, *l1; /* Pointers into each buffer. */
>> -  char const *c0, *c1; /* Pointers for finding exact address. */
>> -  size_t cnt = 0;      /* Number of '\n' occurrences. */
>> -  word nnnn;           /* Newline, sizeof (word) times.  */
>> -  int i;
>> -
>> -  nnnn = 0;
>> -  for (i = 0; i < sizeof nnnn; i++)
>> -    nnnn = (nnnn << CHAR_BIT) | '\n';
>> -
>> -  /* Find the rough position of the first difference by reading words,
>> -     not bytes.  */
>> -
>> -  for (l0 = p0, l1 = p1;  (l = *l0) == *l1;  l0++, l1++)
>> -    {
>> -      l ^= nnnn;
>> -      for (i = 0; i < sizeof l; i++)
>> -       {
>> -         unsigned char uc = l;
>> -         cnt += ! uc;
>> -         l >>= CHAR_BIT;
>> -       }
>> -    }
>> -
>> -  /* Find the exact differing position (endianness independent).  */
>> -
>> -  for (c0 = (char const *) l0, c1 = (char const *) l1;
>> -       *c0 == *c1;
>> -       c0++, c1++)
>> -    cnt += *c0 == '\n';
>> -
>> -  *count += cnt;
>> -  return c0 - (char const *) p0;
>> -}
>> -
>>  /* Compare two blocks of memory P0 and P1 until they differ.
>>     If the blocks are not guaranteed to be different, put sentinels at the 
>> ends
>>     of the blocks before calling this function.
>> @@ -643,6 +598,21 @@ block_compare (word const *p0, word const *p1)
>>    return c0 - (char const *) p0;
>>  }
>>
>> +/* Return the number of newlines in BUF, of size BUFSIZE,
>> +   where BUF[NBYTES] is available for use as a sentinel.  */
>> +
>> +static size_t
>> +count_newlines (char *buf, size_t bufsize)
>> +{
>> +  size_t count = 0;
>> +  char *p;
>> +  char *lim = buf + bufsize;
>> +  *lim = '\n';
>> +  for (p = buf; (p = rawmemchr (p, '\n')) != lim; p++)
>> +    count++;
>> +  return count;
>> +}
>> +
>>  /* Put into BUF the unsigned char C, making unprintable bytes
>>     visible by quoting like cat -t does.  */
>>
>> diff --git a/src/io.c b/src/io.c
>> index 463ee35..05a898c 100644
>> --- a/src/io.c
>> +++ b/src/io.c
>> @@ -474,7 +474,6 @@ prepare_text (struct file_data *current)
>>  {
>>    size_t buffered = current->buffered;
>>    char *p = FILE_BUFFER (current);
>> -  char *dst;
>>
>>    if (buffered == 0 || p[buffered - 1] == '\n')
>>      current->missing_newline = false;
>> @@ -490,16 +489,25 @@ prepare_text (struct file_data *current)
>>    /* Don't use uninitialized storage when planting or using sentinels.  */
>>    memset (p + buffered, 0, sizeof (word));
>>
>> -  if (strip_trailing_cr && (dst = memchr (p, '\r', buffered)))
>> +  if (strip_trailing_cr)
>>      {
>> -      char const *src = dst;
>> -      char const *srclim = p + buffered;
>> +      char *dst;
>> +      char *srclim = p + buffered;
>> +      *srclim = '\r';
>> +      dst = rawmemchr (p, '\r');
>>
>> -      do
>> -       dst += ! ((*dst = *src++) == '\r' && *src == '\n');
>> -      while (src < srclim);
>> +      if (dst != srclim)
>> +       {
>> +         char const *src = dst;
>> +         do
>> +           {
>> +             *dst = *src++;
>> +             dst += ! (*dst == '\r' && *src == '\n');
>> +           }
>> +         while (src < srclim);
>>
>> -      buffered -= src - dst;
>> +         buffered -= src - dst;
>> +       }
>>      }
>>
>>    current->buffered = buffered;
>> diff --git a/src/sdiff.c b/src/sdiff.c
>> index b7f9f6a..e7bc657 100644
>> --- a/src/sdiff.c
>> +++ b/src/sdiff.c
>> @@ -379,8 +379,8 @@ lf_copy (struct line_filter *lf, lin lines, FILE 
>> *outfile)
>>
>>    while (lines)
>>      {
>> -      lf->bufpos = (char *) memchr (lf->bufpos, '\n', lf->buflim - 
>> lf->bufpos);
>> -      if (! lf->bufpos)
>> +      lf->bufpos = rawmemchr (lf->bufpos, '\n');
>> +      if (lf->bufpos == lf->buflim)
>>         {
>>           ck_fwrite (start, lf->buflim - start, outfile);
>>           if (! lf_refill (lf))
>> @@ -403,8 +403,8 @@ lf_skip (struct line_filter *lf, lin lines)
>>  {
>>    while (lines)
>>      {
>> -      lf->bufpos = (char *) memchr (lf->bufpos, '\n', lf->buflim - 
>> lf->bufpos);
>> -      if (! lf->bufpos)
>> +      lf->bufpos = rawmemchr (lf->bufpos, '\n');
>> +      if (lf->bufpos == lf->buflim)
>>         {
>>           if (! lf_refill (lf))
>>             break;
>> @@ -424,7 +424,7 @@ lf_snarf (struct line_filter *lf, char *buffer, size_t 
>> bufsize)
>>    for (;;)
>>      {
>>        char *start = lf->bufpos;
>> -      char *next = (char *) memchr (start, '\n', lf->buflim + 1 - start);
>> +      char *next = rawmemchr (start, '\n');
>>        size_t s = next - start;
>>        if (bufsize <= s)
>>         return 0;
>> --
>> 1.7.11.7
>>
>>