From unknown Sun Jun 22 20:56:54 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#15241 <15241@debbugs.gnu.org> To: bug#15241 <15241@debbugs.gnu.org> Subject: Status: [bug-diffutils] Multithreading support? Reply-To: bug#15241 <15241@debbugs.gnu.org> Date: Mon, 23 Jun 2025 03:56:54 +0000 retitle 15241 [bug-diffutils] Multithreading support? reassign 15241 diffutils submitter 15241 David Bala=C5=BEic severity 15241 normal thanks From debbugs-submit-bounces@debbugs.gnu.org Sun Sep 01 20:03:22 2013 Received: (at submit) by debbugs.gnu.org; 2 Sep 2013 00:03:22 +0000 Received: from localhost ([127.0.0.1]:35883 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VGHc1-0001gj-Ha for submit@debbugs.gnu.org; Sun, 01 Sep 2013 20:03:22 -0400 Received: from eggs.gnu.org ([208.118.235.92]:39564) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VGEiZ-0005SI-8G for submit@debbugs.gnu.org; Sun, 01 Sep 2013 16:57:56 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VGEiS-00056N-48 for submit@debbugs.gnu.org; Sun, 01 Sep 2013 16:57:49 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: * X-Spam-Status: No, score=1.1 required=5.0 tests=BAYES_50, FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,T_DKIM_INVALID autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:35776) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGEiS-00056J-0h for submit@debbugs.gnu.org; Sun, 01 Sep 2013 16:57:48 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:41277) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGEiQ-0007cr-KQ for bug-diffutils@gnu.org; Sun, 01 Sep 2013 16:57:47 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VGEiP-00055b-7Z for bug-diffutils@gnu.org; Sun, 01 Sep 2013 16:57:46 -0400 Received: from mail-la0-x22f.google.com ([2a00:1450:4010:c03::22f]:48666) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGEiO-00055R-R3 for bug-diffutils@gnu.org; Sun, 01 Sep 2013 16:57:45 -0400 Received: by mail-la0-f47.google.com with SMTP id eo20so2999818lab.34 for ; Sun, 01 Sep 2013 13:57:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=Q9q/zibBhP7wvgExxtzzg6SVNSvY3Xk7shVvAzlCHBM=; b=Ch0whGKqY8jyGW4eE9rJ9RVJ/C/wYXaE0TMllhty4oJKg/FMxkXzDX8m/DEaKbXpOD Zbz8OgkMxnNJBXLmACe9MSQZ67eFxFjKC/6xqfuDQCXPQsu8OPahdBNj0AQ2to7W3u9m /d7R9wyZNb2T6ic4SQf8S6owPLpQqSJ1jXTQbzCHAFncMOpro8wud9IBCh6Th0giNoDC OTCYW5oC9ZFKOfTJB1wWBVhnGWm1vp0ZsGFCwBcVn2BYe4HNwh9Veh8YofjjM5z5ncM+ C81tHN14lM7WK15He7lwvXqU9FmUueZctD0q3sbVeQ2sSFAbH+Tpy4oiEjGrWQFK2r7n QATQ== MIME-Version: 1.0 X-Received: by 10.152.36.98 with SMTP id p2mr18308794laj.14.1378069062997; Sun, 01 Sep 2013 13:57:42 -0700 (PDT) Received: by 10.112.75.231 with HTTP; Sun, 1 Sep 2013 13:57:42 -0700 (PDT) In-Reply-To: <521697CF.4000700@cs.ucla.edu> References: <520904CD.5040606@cs.ucla.edu> <520948E7.1080006@cs.ucla.edu> <52096F69.9090006@cs.ucla.edu> <520A4B2F.2020803@cs.ucla.edu> <521697CF.4000700@cs.ucla.edu> Date: Sun, 1 Sep 2013 22:57:42 +0200 Message-ID: Subject: Re: [bug-diffutils] Multithreading support? From: =?UTF-8?Q?David_Bala=C5=BEic?= To: Paul Eggert Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -2.1 (--) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Sun, 01 Sep 2013 20:03:19 -0400 Cc: bug-diffutils@gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.1 (--) 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=3D/dev/urandom of=3Dtest bs=3D1M count=3D17 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=3D/dev/zero bs=3D1M count=3D64 | 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=3D/dev/zero bs=3D1M count=3D64 | 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=3D/dev/zero bs=3D1M count=3D64 | 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 secon= d. Regards, David On 23 August 2013 00:59, Paul Eggert wrote: > On 08/13/13 08:48, David Bala=C5=BEic 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 > 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_P= URE; > -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 =3D=3D SIZE_MAX) > error (EXIT_TROUBLE, errno, "%s", file[1]); > > - /* Insert sentinels for the block compare. */ > + smaller =3D MIN (read0, read1); > > - buf0[read0] =3D ~buf1[read0]; > - buf1[read1] =3D ~buf0[read1]; > + /* Optimize the common case where the buffers are the same. */ > + if (memcmp (buf0, buf1, smaller) =3D=3D 0) > + first_diff =3D smaller; > + else > + { > + /* Insert sentinels for the block compare. */ > + buf0[read0] =3D ~buf1[read0]; > + buf1[read1] =3D ~buf0[read1]; > > - /* If the line number should be written for differing files, > - compare the blocks and count the number of newlines > - simultaneously. */ > - first_diff =3D (comparison_type =3D=3D type_first_diff > - ? block_compare_and_count (buffer0, buffer1, &line_nu= mber) > - : block_compare (buffer0, buffer1)); > + first_diff =3D block_compare (buffer0, buffer1); > + } > > byte_number +=3D first_diff; > - smaller =3D MIN (read0, read1); > + if (comparison_type =3D=3D type_first_diff) > + line_number +=3D count_newlines (buf0, first_diff); > > if (first_diff < smaller) > { > @@ -567,54 +570,6 @@ cmp (void) > return differing =3D=3D 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 th= e 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 =3D 0; /* Number of '\n' occurrences. */ > - word nnnn; /* Newline, sizeof (word) times. */ > - int i; > - > - nnnn =3D 0; > - for (i =3D 0; i < sizeof nnnn; i++) > - nnnn =3D (nnnn << CHAR_BIT) | '\n'; > - > - /* Find the rough position of the first difference by reading words, > - not bytes. */ > - > - for (l0 =3D p0, l1 =3D p1; (l =3D *l0) =3D=3D *l1; l0++, l1++) > - { > - l ^=3D nnnn; > - for (i =3D 0; i < sizeof l; i++) > - { > - unsigned char uc =3D l; > - cnt +=3D ! uc; > - l >>=3D CHAR_BIT; > - } > - } > - > - /* Find the exact differing position (endianness independent). */ > - > - for (c0 =3D (char const *) l0, c1 =3D (char const *) l1; > - *c0 =3D=3D *c1; > - c0++, c1++) > - cnt +=3D *c0 =3D=3D '\n'; > - > - *count +=3D 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 th= e 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 =3D 0; > + char *p; > + char *lim =3D buf + bufsize; > + *lim =3D '\n'; > + for (p =3D buf; (p =3D rawmemchr (p, '\n')) !=3D 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 =3D current->buffered; > char *p =3D FILE_BUFFER (current); > - char *dst; > > if (buffered =3D=3D 0 || p[buffered - 1] =3D=3D '\n') > current->missing_newline =3D 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 =3D memchr (p, '\r', buffered))) > + if (strip_trailing_cr) > { > - char const *src =3D dst; > - char const *srclim =3D p + buffered; > + char *dst; > + char *srclim =3D p + buffered; > + *srclim =3D '\r'; > + dst =3D rawmemchr (p, '\r'); > > - do > - dst +=3D ! ((*dst =3D *src++) =3D=3D '\r' && *src =3D=3D '\n'); > - while (src < srclim); > + if (dst !=3D srclim) > + { > + char const *src =3D dst; > + do > + { > + *dst =3D *src++; > + dst +=3D ! (*dst =3D=3D '\r' && *src =3D=3D '\n'); > + } > + while (src < srclim); > > - buffered -=3D src - dst; > + buffered -=3D src - dst; > + } > } > > current->buffered =3D 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 *out= file) > > while (lines) > { > - lf->bufpos =3D (char *) memchr (lf->bufpos, '\n', lf->buflim - lf-= >bufpos); > - if (! lf->bufpos) > + lf->bufpos =3D rawmemchr (lf->bufpos, '\n'); > + if (lf->bufpos =3D=3D 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 =3D (char *) memchr (lf->bufpos, '\n', lf->buflim - lf-= >bufpos); > - if (! lf->bufpos) > + lf->bufpos =3D rawmemchr (lf->bufpos, '\n'); > + if (lf->bufpos =3D=3D 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 =3D lf->bufpos; > - char *next =3D (char *) memchr (start, '\n', lf->buflim + 1 - star= t); > + char *next =3D rawmemchr (start, '\n'); > size_t s =3D next - start; > if (bufsize <=3D s) > return 0; > -- > 1.7.11.7 > > From debbugs-submit-bounces@debbugs.gnu.org Mon Sep 02 15:34:47 2013 Received: (at submit) by debbugs.gnu.org; 2 Sep 2013 19:34:47 +0000 Received: from localhost ([127.0.0.1]:37846 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VGZte-0000oT-P5 for submit@debbugs.gnu.org; Mon, 02 Sep 2013 15:34:47 -0400 Received: from eggs.gnu.org ([208.118.235.92]:48319) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VGZtb-0000oC-4b for submit@debbugs.gnu.org; Mon, 02 Sep 2013 15:34:44 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VGZtU-0007lr-7m for submit@debbugs.gnu.org; Mon, 02 Sep 2013 15:34:37 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: * X-Spam-Status: No, score=1.1 required=5.0 tests=BAYES_50, FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,T_DKIM_INVALID autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:39005) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGZtU-0007ln-4A for submit@debbugs.gnu.org; Mon, 02 Sep 2013 15:34:36 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:50036) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGZtS-0004ca-0T for bug-diffutils@gnu.org; Mon, 02 Sep 2013 15:34:36 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VGZtQ-0007lO-B0 for bug-diffutils@gnu.org; Mon, 02 Sep 2013 15:34:33 -0400 Received: from mail-la0-x236.google.com ([2a00:1450:4010:c03::236]:44028) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGZtP-0007lB-TE for bug-diffutils@gnu.org; Mon, 02 Sep 2013 15:34:32 -0400 Received: by mail-la0-f54.google.com with SMTP id ea20so3943811lab.13 for ; Mon, 02 Sep 2013 12:34:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=uPKzaRmSQ0pqp0DS3wmPobe5/saBb6IXpUqiPCYQ2Qk=; b=RumKBuT/4o7m2msrq2e/55eiedfVLYguJrMUkRMMxep5axL+NBnamYW9Nffi0QvufI YCoaPjxeQTPRCWe/dKrNMkHQYfEXfCNTW0c990zVCOsaLdFSoWwIAnHxcqo+ME65WtAl mgmO+jJLSM9mVgVM+wuKshvx7VzWRVPh+7FSwHXmIofaSWFCxB63Zwxv6b85XzjJwIQz 6rKxdX2Q6ROX4nkY9Ja6FDBwjeO6goPRi1LoqLpOO92pQv+Hdd2QqypUmX1pt1BZimbg H5Gq3lMF2YU49wITpVraCaXaDwQgcJP46pI0PcV/jX1Z1HgudoS5Yfd1CuU4k0KTJTzu /otA== MIME-Version: 1.0 X-Received: by 10.112.89.100 with SMTP id bn4mr22256576lbb.16.1378150470653; Mon, 02 Sep 2013 12:34:30 -0700 (PDT) Received: by 10.112.75.231 with HTTP; Mon, 2 Sep 2013 12:34:30 -0700 (PDT) In-Reply-To: References: <520904CD.5040606@cs.ucla.edu> <520948E7.1080006@cs.ucla.edu> <52096F69.9090006@cs.ucla.edu> <520A4B2F.2020803@cs.ucla.edu> <521697CF.4000700@cs.ucla.edu> Date: Mon, 2 Sep 2013 21:34:30 +0200 Message-ID: Subject: Re: [bug-diffutils] Multithreading support? From: =?UTF-8?Q?David_Bala=C5=BEic?= To: Paul Eggert Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -2.1 (--) X-Debbugs-Envelope-To: submit Cc: bug-diffutils@gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.1 (--) 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=C5=BEic 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=3D/dev/urandom of=3Dtest bs=3D1M count=3D17 > time cmp test test # busybox cmp reads the inputs even if they are the sa= me 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=3D/dev/zero bs=3D1M count=3D64 | 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=3D/dev/zero bs=3D1M count=3D64 | 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=3D/dev/zero bs=3D1M count=3D64 | 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 sec= ond. > > Regards, > David > > > On 23 August 2013 00:59, Paul Eggert wrote: >> On 08/13/13 08:48, David Bala=C5=BEic 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 >> 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 =3D=3D SIZE_MAX) >> error (EXIT_TROUBLE, errno, "%s", file[1]); >> >> - /* Insert sentinels for the block compare. */ >> + smaller =3D MIN (read0, read1); >> >> - buf0[read0] =3D ~buf1[read0]; >> - buf1[read1] =3D ~buf0[read1]; >> + /* Optimize the common case where the buffers are the same. */ >> + if (memcmp (buf0, buf1, smaller) =3D=3D 0) >> + first_diff =3D smaller; >> + else >> + { >> + /* Insert sentinels for the block compare. */ >> + buf0[read0] =3D ~buf1[read0]; >> + buf1[read1] =3D ~buf0[read1]; >> >> - /* If the line number should be written for differing files, >> - compare the blocks and count the number of newlines >> - simultaneously. */ >> - first_diff =3D (comparison_type =3D=3D type_first_diff >> - ? block_compare_and_count (buffer0, buffer1, &line_n= umber) >> - : block_compare (buffer0, buffer1)); >> + first_diff =3D block_compare (buffer0, buffer1); >> + } >> >> byte_number +=3D first_diff; >> - smaller =3D MIN (read0, read1); >> + if (comparison_type =3D=3D type_first_diff) >> + line_number +=3D count_newlines (buf0, first_diff); >> >> if (first_diff < smaller) >> { >> @@ -567,54 +570,6 @@ cmp (void) >> return differing =3D=3D 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 t= he 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 =3D 0; /* Number of '\n' occurrences. */ >> - word nnnn; /* Newline, sizeof (word) times. */ >> - int i; >> - >> - nnnn =3D 0; >> - for (i =3D 0; i < sizeof nnnn; i++) >> - nnnn =3D (nnnn << CHAR_BIT) | '\n'; >> - >> - /* Find the rough position of the first difference by reading words, >> - not bytes. */ >> - >> - for (l0 =3D p0, l1 =3D p1; (l =3D *l0) =3D=3D *l1; l0++, l1++) >> - { >> - l ^=3D nnnn; >> - for (i =3D 0; i < sizeof l; i++) >> - { >> - unsigned char uc =3D l; >> - cnt +=3D ! uc; >> - l >>=3D CHAR_BIT; >> - } >> - } >> - >> - /* Find the exact differing position (endianness independent). */ >> - >> - for (c0 =3D (char const *) l0, c1 =3D (char const *) l1; >> - *c0 =3D=3D *c1; >> - c0++, c1++) >> - cnt +=3D *c0 =3D=3D '\n'; >> - >> - *count +=3D 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 t= he 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 =3D 0; >> + char *p; >> + char *lim =3D buf + bufsize; >> + *lim =3D '\n'; >> + for (p =3D buf; (p =3D rawmemchr (p, '\n')) !=3D 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 =3D current->buffered; >> char *p =3D FILE_BUFFER (current); >> - char *dst; >> >> if (buffered =3D=3D 0 || p[buffered - 1] =3D=3D '\n') >> current->missing_newline =3D 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 =3D memchr (p, '\r', buffered))) >> + if (strip_trailing_cr) >> { >> - char const *src =3D dst; >> - char const *srclim =3D p + buffered; >> + char *dst; >> + char *srclim =3D p + buffered; >> + *srclim =3D '\r'; >> + dst =3D rawmemchr (p, '\r'); >> >> - do >> - dst +=3D ! ((*dst =3D *src++) =3D=3D '\r' && *src =3D=3D '\n'); >> - while (src < srclim); >> + if (dst !=3D srclim) >> + { >> + char const *src =3D dst; >> + do >> + { >> + *dst =3D *src++; >> + dst +=3D ! (*dst =3D=3D '\r' && *src =3D=3D '\n'); >> + } >> + while (src < srclim); >> >> - buffered -=3D src - dst; >> + buffered -=3D src - dst; >> + } >> } >> >> current->buffered =3D 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 *ou= tfile) >> >> while (lines) >> { >> - lf->bufpos =3D (char *) memchr (lf->bufpos, '\n', lf->buflim - lf= ->bufpos); >> - if (! lf->bufpos) >> + lf->bufpos =3D rawmemchr (lf->bufpos, '\n'); >> + if (lf->bufpos =3D=3D 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 =3D (char *) memchr (lf->bufpos, '\n', lf->buflim - lf= ->bufpos); >> - if (! lf->bufpos) >> + lf->bufpos =3D rawmemchr (lf->bufpos, '\n'); >> + if (lf->bufpos =3D=3D 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 =3D lf->bufpos; >> - char *next =3D (char *) memchr (start, '\n', lf->buflim + 1 - sta= rt); >> + char *next =3D rawmemchr (start, '\n'); >> size_t s =3D next - start; >> if (bufsize <=3D s) >> return 0; >> -- >> 1.7.11.7 >> >> From debbugs-submit-bounces@debbugs.gnu.org Mon Sep 02 17:37:09 2013 Received: (at submit) by debbugs.gnu.org; 2 Sep 2013 21:37:09 +0000 Received: from localhost ([127.0.0.1]:37929 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VGbo5-0003sU-6R for submit@debbugs.gnu.org; Mon, 02 Sep 2013 17:37:09 -0400 Received: from eggs.gnu.org ([208.118.235.92]:41752) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VGbo2-0003s0-06 for submit@debbugs.gnu.org; Mon, 02 Sep 2013 17:37:07 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VGbnn-0005LI-EF for submit@debbugs.gnu.org; Mon, 02 Sep 2013 17:37:00 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:55488) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGbnn-0005LE-B0 for submit@debbugs.gnu.org; Mon, 02 Sep 2013 17:36:51 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:43454) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGbnf-00045c-Pm for bug-diffutils@gnu.org; Mon, 02 Sep 2013 17:36:51 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VGbnY-0005K8-BJ for bug-diffutils@gnu.org; Mon, 02 Sep 2013 17:36:43 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:48396) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VGbnY-0005K4-5L for bug-diffutils@gnu.org; Mon, 02 Sep 2013 17:36:36 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id B3BD939E8105; Mon, 2 Sep 2013 14:36:35 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id DeV4xbsM0iYs; Mon, 2 Sep 2013 14:36:35 -0700 (PDT) Received: from [192.168.1.9] (pool-71-108-49-126.lsanca.fios.verizon.net [71.108.49.126]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 6144D39E8008; Mon, 2 Sep 2013 14:36:35 -0700 (PDT) Message-ID: <522504E3.20502@cs.ucla.edu> Date: Mon, 02 Sep 2013 14:36:35 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130803 Thunderbird/17.0.8 MIME-Version: 1.0 To: =?UTF-8?B?RGF2aWQgQmFsYcW+aWM=?= Subject: Re: [bug-diffutils] Multithreading support? References: <520904CD.5040606@cs.ucla.edu> <520948E7.1080006@cs.ucla.edu> <52096F69.9090006@cs.ucla.edu> <520A4B2F.2020803@cs.ucla.edu> <521697CF.4000700@cs.ucla.edu> In-Reply-To: X-Enigmail-Version: 1.5.2 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -2.4 (--) X-Debbugs-Envelope-To: submit Cc: bug-diffutils@gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.4 (--) Thanks for all that testing. It seems clear that the recent patches are a performance win for your CPU too. Maybe we should look for other opportunities to use rawmemchr in the standard utilities. From debbugs-submit-bounces@debbugs.gnu.org Sun Mar 30 01:42:58 2014 Received: (at 15241-done) by debbugs.gnu.org; 30 Mar 2014 05:42:59 +0000 Received: from localhost ([127.0.0.1]:56675 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WU8WI-0005gX-DE for submit@debbugs.gnu.org; Sun, 30 Mar 2014 01:42:58 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:42489) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WU8WH-0005gQ-3r for 15241-done@debbugs.gnu.org; Sun, 30 Mar 2014 01:42:57 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id A9DBA39E8012 for <15241-done@debbugs.gnu.org>; Sat, 29 Mar 2014 22:42:56 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id q6d6eFo4Yjy7 for <15241-done@debbugs.gnu.org>; Sat, 29 Mar 2014 22:42:56 -0700 (PDT) Received: from [192.168.1.9] (pool-108-0-233-62.lsanca.fios.verizon.net [108.0.233.62]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 64F3139E8011 for <15241-done@debbugs.gnu.org>; Sat, 29 Mar 2014 22:42:56 -0700 (PDT) Message-ID: <5337AEE0.4070202@cs.ucla.edu> Date: Sat, 29 Mar 2014 22:42:56 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 MIME-Version: 1.0 To: 15241-done@debbugs.gnu.org Subject: Re: [bug-diffutils] Multithreading support? Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.7 (--) X-Debbugs-Envelope-To: 15241-done X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.7 (--) Closing this bug report, as it seems to be done. From unknown Sun Jun 22 20:56:54 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Sun, 27 Apr 2014 11:24:04 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator