From unknown Sun Jun 22 20:59:02 2025 X-Loop: help-debbugs@gnu.org Subject: bug#15241: [bug-diffutils] Multithreading support? Resent-From: David =?UTF-8?Q?Bala=C5=BEic?= Original-Sender: "Debbugs-submit" Resent-CC: bug-diffutils@gnu.org Resent-Date: Mon, 02 Sep 2013 00:04:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 15241 X-GNU-PR-Package: diffutils X-GNU-PR-Keywords: To: Paul Eggert Cc: 15241@debbugs.gnu.org X-Debbugs-Original-Cc: bug-diffutils@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.13780802026498 (code B ref -1); Mon, 02 Sep 2013 00:04:02 +0000 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: From: David =?UTF-8?Q?Bala=C5=BEic?= 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-Mailman-Approved-At: Sun, 01 Sep 2013 20:03:19 -0400 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 unknown Sun Jun 22 20:59:02 2025 X-Loop: help-debbugs@gnu.org Subject: bug#15241: [bug-diffutils] Multithreading support? Resent-From: David =?UTF-8?Q?Bala=C5=BEic?= Original-Sender: "Debbugs-submit" Resent-CC: bug-diffutils@gnu.org Resent-Date: Mon, 02 Sep 2013 19:35:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 15241 X-GNU-PR-Package: diffutils X-GNU-PR-Keywords: To: Paul Eggert Cc: 15241@debbugs.gnu.org X-Debbugs-Original-Cc: bug-diffutils@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.13781504873134 (code B ref -1); Mon, 02 Sep 2013 19:35:02 +0000 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: From: David =?UTF-8?Q?Bala=C5=BEic?= 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-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 unknown Sun Jun 22 20:59:02 2025 X-Loop: help-debbugs@gnu.org Subject: bug#15241: [bug-diffutils] Multithreading support? Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-diffutils@gnu.org Resent-Date: Mon, 02 Sep 2013 21:38:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 15241 X-GNU-PR-Package: diffutils X-GNU-PR-Keywords: To: David =?UTF-8?Q?Bala=C5=BEic?= Cc: 15241@debbugs.gnu.org X-Debbugs-Original-Cc: bug-diffutils@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.137815782914915 (code B ref -1); Mon, 02 Sep 2013 21:38:02 +0000 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 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-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 unknown Sun Jun 22 20:59:02 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.503 (Entity 5.503) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: David =?UTF-8?Q?Bala=C5=BEic?= Subject: bug#15241: closed (Re: [bug-diffutils] Multithreading support?) Message-ID: References: <5337AEE0.4070202@cs.ucla.edu> X-Gnu-PR-Message: they-closed 15241 X-Gnu-PR-Package: diffutils Reply-To: 15241@debbugs.gnu.org Date: Sun, 30 Mar 2014 05:43:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1396158182-21874-1" This is a multi-part message in MIME format... ------------=_1396158182-21874-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #15241: [bug-diffutils] Multithreading support? which was filed against the diffutils package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 15241@debbugs.gnu.org. --=20 15241: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D15241 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1396158182-21874-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit 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. ------------=_1396158182-21874-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit 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 > > ------------=_1396158182-21874-1--