From unknown Sat Sep 06 00:11:40 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#17576 <17576@debbugs.gnu.org> To: bug#17576 <17576@debbugs.gnu.org> Subject: Status: [PATCH] dfa: speed-up at initial state Reply-To: bug#17576 <17576@debbugs.gnu.org> Date: Sat, 06 Sep 2025 07:11:40 +0000 retitle 17576 [PATCH] dfa: speed-up at initial state reassign 17576 grep submitter 17576 Norihiro Tanaka severity 17576 normal tag 17576 patch thanks From debbugs-submit-bounces@debbugs.gnu.org Fri May 23 23:32:14 2014 Received: (at submit) by debbugs.gnu.org; 24 May 2014 03:32:14 +0000 Received: from localhost ([127.0.0.1]:58478 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo2gv-0001HP-Rh for submit@debbugs.gnu.org; Fri, 23 May 2014 23:32:14 -0400 Received: from eggs.gnu.org ([208.118.235.92]:60269) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo2gt-0001H5-V8 for submit@debbugs.gnu.org; Fri, 23 May 2014 23:32:12 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Wo2gg-0000zv-7Y for submit@debbugs.gnu.org; Fri, 23 May 2014 23:32:06 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:52863) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wo2gg-0000zn-4B for submit@debbugs.gnu.org; Fri, 23 May 2014 23:31:58 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:33716) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wo2gY-0002FM-GC for bug-grep@gnu.org; Fri, 23 May 2014 23:31:58 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Wo2gQ-0000uE-TU for bug-grep@gnu.org; Fri, 23 May 2014 23:31:50 -0400 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:35915) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wo2gQ-0000ty-Dl for bug-grep@gnu.org; Fri, 23 May 2014 23:31:42 -0400 Received: from imp03 (mailgw7.kcn.ne.jp [61.86.15.238]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id CE306B0010 for ; Sat, 24 May 2014 12:31:38 +0900 (JST) Received: from mail01.kcn.ne.jp ([61.86.6.180]) by imp03 with bizsmtp id 5fXe1o0163t2w9Z01fXe6n; Sat, 24 May 2014 12:31:38 +0900 X-OrgRCPT: bug-grep@gnu.org Received: from [10.120.1.19] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail01.kcn.ne.jp (Postfix) with ESMTPA id 98F825A82F6 for ; Sat, 24 May 2014 12:31:38 +0900 (JST) Date: Sat, 24 May 2014 12:31:37 +0900 From: Norihiro Tanaka To: bug-grep@gnu.org Subject: [PATCH] dfa: speed-up at initial state Message-Id: <20140524123134.2C5F.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_53800BB2000000002C56_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] 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: -4.0 (----) X-Debbugs-Envelope-To: submit 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: -4.0 (----) --------_53800BB2000000002C56_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Thanks to Jim and for the new release. Let's just start with, for next release I want to add further improvement to it. In dfaexec, DFA state is always 0 until have found potential match. So we can improve matching there by continuing to use the transition table without replacing it. I tested the patch, and got about 3x speed-up. $ yes j | head -10000000 >k $ env LC_ALL=C time -p src/grep '\(a\|b\)' k Before: real 1.12 user 1.06 sys 0.04 After : real 0.39 user 0.34 sys 0.04 I also tested for non-utf8 multibyte locale. $ env LC_ALL=ja_JP.eucJP time -p src/grep '\(a\|b\)' k Before: real 1.41 user 1.35 sys 0.05 After : real 0.38 user 0.32 sys 0.06 By the way, below on grep 2.18 (non-patch). (^_^) $ env LANG=ja_JP.eucJP time -p src/grep '\(a\|b\)' k real 12.00 user 11.86 sys 0.13 --------_53800BB2000000002C56_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-dfa-speed-up-at-initial-state.patch" Content-Disposition: attachment; filename="0001-dfa-speed-up-at-initial-state.patch" Content-Transfer-Encoding: base64 RnJvbSA2OTE4YmMyNDkzZmY3YWUyMWM1MGEzYjRkMzU4YWUzMDI4Mzc0YTA5IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBUdWUsIDEzIE1heSAyMDE0IDEwOjMwOjIxICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZGZh OiBzcGVlZC11cCBhdCBpbml0aWFsIHN0YXRlCgpERkEgc3RhdGUgaXMgYWx3YXlzIDAgdW50aWwg aGF2ZSBmb3VuZCBwb3RlbnRpYWwgbWF0Y2guICBTbyB3ZSBpbXByb3ZlCm1hdGNoaW5nIHRoZXJl IGJ5IGNvbnRpbnVpbmcgdG8gdXNlIHRoZSB0cmFuc2l0aW9uIHRhYmxlLgoKKiBzcmMvZGZhLmMg KHNraXBfcmVtYWluc19tYik6IE5ldyBmdW5jdGlvbi4KKGRmYWV4ZWMpOiBTcGVlZC11cCBhdCBp bml0aWFsIHN0YXRlLgotLS0KIHNyYy9kZmEuYyB8IDU0ICsrKysrKysrKysrKysrKysrKysrKysr KysrKysrKysrKysrLS0tLS0tLS0tLS0tLS0tLS0tLQogMSBmaWxlIGNoYW5nZWQsIDM1IGluc2Vy dGlvbnMoKyksIDE5IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9kZmEuYyBiL3NyYy9k ZmEuYwppbmRleCA4ZmYyOWQwLi4xZDczMTA1IDEwMDY0NAotLS0gYS9zcmMvZGZhLmMKKysrIGIv c3JjL2RmYS5jCkBAIC0zMjUwLDYgKzMyNTAsMjQgQEAgdHJhbnNpdF9zdGF0ZSAoc3RydWN0IGRm YSAqZCwgc3RhdGVfbnVtIHMsIHVuc2lnbmVkIGNoYXIgY29uc3QgKipwcCwKICAgcmV0dXJuIHMx OwogfQogCisvKiBUaGUgaW5pdGlhbCBzdGF0ZSBtYXkgZW5jb3VudGVyIGEgYnl0ZSB3aGljaCBp cyBub3QgYSBzaW5nbGUgYnl0ZSBjaGFyYWN0ZXIKKyAgIG5vciB0aGUgZmlyc3QgYnl0ZSBvZiBh IG11bHRpYnl0ZSBjaGFyYWN0ZXIuICBCdXQgaXQgaXMgaW5jb3JyZWN0IGZvciB0aGUKKyAgIGlu aXRpYWwgc3RhdGUgdG8gYWNjZXB0IHN1Y2ggYSBieXRlLiAgRm9yIGV4YW1wbGUsIGluIFNoaWZ0 IEpJUyB0aGUgcmVndWxhcgorICAgZXhwcmVzc2lvbiAiXFwiIGFjY2VwdHMgdGhlIGNvZGVwb2lu dCAweDVjLCBidXQgc2hvdWxkIG5vdCBhY2NlcHQgdGhlIHNlY29uZAorICAgYnl0ZSBvZiB0aGUg Y29kZXBvaW50IDB4ODE1Yy4gIFRoZW4gdGhlIGluaXRpYWwgc3RhdGUgbXVzdCBza2lwIHRoZSBi eXRlcworICAgdGhhdCBhcmUgbm90IGEgc2luZ2xlIGJ5dGUgY2hhcmFjdGVyIG5vciB0aGUgZmly c3QgYnl0ZSBvZiBhIG11bHRpYnl0ZQorICAgY2hhcmFjdGVyLiAgKi8KK3N0YXRpYyB1bnNpZ25l ZCBjaGFyIGNvbnN0ICoKK3NraXBfcmVtYWluc19tYiAoc3RydWN0IGRmYSAqZCwgdW5zaWduZWQg Y2hhciBjb25zdCAqcCwKKyAgICAgICAgICAgICAgICAgdW5zaWduZWQgY2hhciBjb25zdCAqbWJw LCBjaGFyIGNvbnN0ICplbmQpCit7CisgIHdpbnRfdCB3YzsKKyAgd2hpbGUgKG1icCA8IHApCisg ICAgbWJwICs9IG1ic190b193Y2hhciAoJndjLCAoY2hhciBjb25zdCAqKSBtYnAsCisgICAgICAg ICAgICAgICAgICAgICAgICAgZW5kIC0gKGNoYXIgY29uc3QgKikgbWJwLCBkKTsKKyAgcmV0dXJu IG1icDsKK30KKwogLyogU2VhcmNoIHRocm91Z2ggYSBidWZmZXIgbG9va2luZyBmb3IgYSBtYXRj aCB0byB0aGUgZ2l2ZW4gc3RydWN0IGRmYS4KICAgIEZpbmQgdGhlIGZpcnN0IG9jY3VycmVuY2Ug b2YgYSBzdHJpbmcgbWF0Y2hpbmcgdGhlIHJlZ2V4cCBpbiB0aGUKICAgIGJ1ZmZlciwgYW5kIHRo ZSBzaG9ydGVzdCBwb3NzaWJsZSB2ZXJzaW9uIHRoZXJlb2YuICBSZXR1cm4gYSBwb2ludGVyIHRv CkBAIC0zMzAzLDI3ICszMzIxLDE4IEBAIGRmYWV4ZWMgKHN0cnVjdCBkZmEgKmQsIGNoYXIgY29u c3QgKmJlZ2luLCBjaGFyICplbmQsCiAKICAgICAgICAgICAgICAgaWYgKHMgPT0gMCkKICAgICAg ICAgICAgICAgICB7Ci0gICAgICAgICAgICAgICAgICAvKiBUaGUgaW5pdGlhbCBzdGF0ZSBtYXkg ZW5jb3VudGVyIGEgYnl0ZSB3aGljaCBpcyBub3QKLSAgICAgICAgICAgICAgICAgICAgIGEgc2lu Z2xlIGJ5dGUgY2hhcmFjdGVyIG5vciB0aGUgZmlyc3QgYnl0ZSBvZiBhCi0gICAgICAgICAgICAg ICAgICAgICBtdWx0aWJ5dGUgY2hhcmFjdGVyLiAgQnV0IGl0IGlzIGluY29ycmVjdCBmb3IgdGhl Ci0gICAgICAgICAgICAgICAgICAgICBpbml0aWFsIHN0YXRlIHRvIGFjY2VwdCBzdWNoIGEgYnl0 ZS4gIEZvciBleGFtcGxlLAotICAgICAgICAgICAgICAgICAgICAgaW4gU2hpZnQgSklTIHRoZSBy ZWd1bGFyIGV4cHJlc3Npb24gIlxcIiBhY2NlcHRzCi0gICAgICAgICAgICAgICAgICAgICB0aGUg Y29kZXBvaW50IDB4NWMsIGJ1dCBzaG91bGQgbm90IGFjY2VwdCB0aGUgc2Vjb25kCi0gICAgICAg ICAgICAgICAgICAgICBieXRlIG9mIHRoZSBjb2RlcG9pbnQgMHg4MTVjLiAgVGhlbiB0aGUgaW5p dGlhbAotICAgICAgICAgICAgICAgICAgICAgc3RhdGUgbXVzdCBza2lwIHRoZSBieXRlcyB0aGF0 IGFyZSBub3QgYSBzaW5nbGUKLSAgICAgICAgICAgICAgICAgICAgIGJ5dGUgY2hhcmFjdGVyIG5v ciB0aGUgZmlyc3QgYnl0ZSBvZiBhIG11bHRpYnl0ZQotICAgICAgICAgICAgICAgICAgICAgY2hh cmFjdGVyLiAgKi8KLSAgICAgICAgICAgICAgICAgIHdpbnRfdCB3YzsKLSAgICAgICAgICAgICAg ICAgIHdoaWxlIChtYnAgPCBwKQotICAgICAgICAgICAgICAgICAgICBtYnAgKz0gbWJzX3RvX3dj aGFyICgmd2MsIChjaGFyIGNvbnN0ICopIG1icCwKLSAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgZW5kIC0gKGNoYXIgY29uc3QgKikgbWJwLCBkKTsKLSAgICAgICAgICAg ICAgICAgIHAgPSBtYnA7Ci0KLSAgICAgICAgICAgICAgICAgIGlmICgoY2hhciAqKSBwID4gZW5k KQorICAgICAgICAgICAgICAgICAgaWYgKGQtPnN0YXRlc1tzXS5tYnBzLm5lbGVtID09IDApCiAg ICAgICAgICAgICAgICAgICAgIHsKLSAgICAgICAgICAgICAgICAgICAgICBwID0gTlVMTDsKLSAg ICAgICAgICAgICAgICAgICAgICBnb3RvIGRvbmU7CisgICAgICAgICAgICAgICAgICAgICAgZG8K KyAgICAgICAgICAgICAgICAgICAgICAgIHsKKyAgICAgICAgICAgICAgICAgICAgICAgICAgd2hp bGUgKHRbKnBdID09IDApCisgICAgICAgICAgICAgICAgICAgICAgICAgICAgcCsrOworICAgICAg ICAgICAgICAgICAgICAgICAgICBwID0gbWJwID0gc2tpcF9yZW1haW5zX21iIChkLCBwLCBtYnAs IGVuZCk7CisgICAgICAgICAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAgICAgICAgICAg d2hpbGUgKHRbKnBdID09IDApOwogICAgICAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAg ICAgICBlbHNlCisgICAgICAgICAgICAgICAgICAgIHAgPSBtYnAgPSBza2lwX3JlbWFpbnNfbWIg KGQsIHAsIG1icCwgZW5kKTsKICAgICAgICAgICAgICAgICB9CiAKICAgICAgICAgICAgICAgaWYg KGQtPnN0YXRlc1tzXS5tYnBzLm5lbGVtID09IDApCkBAIC0zMzUxLDYgKzMzNjAsMTMgQEAgZGZh ZXhlYyAoc3RydWN0IGRmYSAqZCwgY2hhciBjb25zdCAqYmVnaW4sIGNoYXIgKmVuZCwKICAgICAg ICAgfQogICAgICAgZWxzZQogICAgICAgICB7CisgICAgICAgICAgaWYgKHMgPT0gMCAmJiAodCA9 IHRyYW5zW3NdKSAhPSBOVUxMKQorICAgICAgICAgICAgeworICAgICAgICAgICAgICB3aGlsZSAo dFsqcF0gPT0gMCkKKyAgICAgICAgICAgICAgICBwKys7CisgICAgICAgICAgICAgIHMgPSB0Wypw KytdOworICAgICAgICAgICAgfQorCiAgICAgICAgICAgd2hpbGUgKCh0ID0gdHJhbnNbc10pICE9 IE5VTEwpCiAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgIHMxID0gdFsqcCsrXTsKLS0gCjEu OS4zCgo= --------_53800BB2000000002C56_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Sat May 24 01:01:51 2014 Received: (at 17576) by debbugs.gnu.org; 24 May 2014 05:01:51 +0000 Received: from localhost ([127.0.0.1]:58536 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo45e-0005E8-TC for submit@debbugs.gnu.org; Sat, 24 May 2014 01:01:51 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:54487) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo45c-0005Dt-MV for 17576@debbugs.gnu.org; Sat, 24 May 2014 01:01:49 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id D093EA6001C; Fri, 23 May 2014 22:01:42 -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 UgGa-YxQr7xK; Fri, 23 May 2014 22:01:36 -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 D1BACA60006; Fri, 23 May 2014 22:01:36 -0700 (PDT) Message-ID: <538027B0.8020006@cs.ucla.edu> Date: Fri, 23 May 2014 22:01:36 -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.5.0 MIME-Version: 1.0 To: Norihiro Tanaka , 17576@debbugs.gnu.org Subject: Re: bug#17576: [PATCH] dfa: speed-up at initial state References: <20140524123134.2C5F.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140524123134.2C5F.27F6AC2D@kcn.ne.jp> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: 17576 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: -3.0 (---) Norihiro Tanaka wrote: > I tested the patch, and got about 3x speed-up. That, but unfortunately whan I timed that patch against the current grep trunk (879d86e6242eae688f9e72d42b230348d1c93a8f), it slowed things down on a similar test case (a test like yours, but 100x longer). $ yes j | head -1000000000 >k $ env LC_ALL=C time -p src/grep-old '\(a\|b\)' k real 8.25 user 7.74 sys 0.50 $ env LC_ALL=C time -p src/grep '\(a\|b\)' k real 11.11 user 10.63 sys 0.46 $ env LC_ALL=ja_JP.eucJP time -p src/grep-old '\(a\|b\)' k real 8.74 user 8.27 sys 0.43 $ env LC_ALL=ja_JP.eucJP time -p src/grep '\(a\|b\)' k real 8.95 user 8.44 sys 0.49 This is on my usual platform: Fedora 20 x86-64, AMD Phenum II X4 910e, GCC 4.9.0, default (-O2) optimization. From debbugs-submit-bounces@debbugs.gnu.org Sat May 24 01:23:23 2014 Received: (at 17576) by debbugs.gnu.org; 24 May 2014 05:23:23 +0000 Received: from localhost ([127.0.0.1]:58545 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo4QU-0005w4-O4 for submit@debbugs.gnu.org; Sat, 24 May 2014 01:23:23 -0400 Received: from mail-wi0-f175.google.com ([209.85.212.175]:47471) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo4QS-0005vn-76 for 17576@debbugs.gnu.org; Sat, 24 May 2014 01:23:21 -0400 Received: by mail-wi0-f175.google.com with SMTP id f8so1743219wiw.8 for <17576@debbugs.gnu.org>; Fri, 23 May 2014 22:23:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=nuMnsrNmS0D9ZYfmNVp2+mVdqyOx8p6tEUwGKGu9HMY=; b=wR3w0g5g1BHS4iWKn+X5cPDdgKnh4TEb0s04IAYQL0tvV3zUzeeh9Or0Kz4jkkjCFB oC6IJ4Kx9G1f/W1bJN7nwj+j5LZknzFv6DSoWkqm1zZ22pnq/xaBuU7mCabMIc+b2K0Z j3QT/KcI1drZmD1nAuuu/fvYo6zGbQvNcELTsdUKMBcK+/QcGneI7dynvlqJxGwvOBMl ayG0wi4AbFO66spmHv/XZuO7CNeWFYqZTl8KPee9q6zCMZ0vS46/af4YOeMtk2LaZPTg KoF3dW/LLHD5G+HkmGv6lG1j3c3iDPsvDeCw3GZZggL0taMTCQpec6dE1dSsfXyEznPm pdcw== X-Received: by 10.180.36.212 with SMTP id s20mr8218994wij.18.1400908994187; Fri, 23 May 2014 22:23:14 -0700 (PDT) MIME-Version: 1.0 Received: by 10.194.81.102 with HTTP; Fri, 23 May 2014 22:22:54 -0700 (PDT) In-Reply-To: <20140524123134.2C5F.27F6AC2D@kcn.ne.jp> References: <20140524123134.2C5F.27F6AC2D@kcn.ne.jp> From: Jim Meyering Date: Fri, 23 May 2014 22:22:54 -0700 X-Google-Sender-Auth: hDXLMp5xcE1mabjmEmpJRvG_LrU Message-ID: Subject: Re: bug#17576: [PATCH] dfa: speed-up at initial state To: Norihiro Tanaka Content-Type: text/plain; charset=ISO-8859-1 X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17576 Cc: 17576@debbugs.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: -0.7 (/) On Fri, May 23, 2014 at 8:31 PM, Norihiro Tanaka wrote: > Thanks to Jim and for the new release. Let's just start with, for next > release I want to add further improvement to it. > > In dfaexec, DFA state is always 0 until have found potential match. So > we can improve matching there by continuing to use the transition table > without replacing it. > > I tested the patch, and got about 3x speed-up. > > $ yes j | head -10000000 >k > $ env LC_ALL=C time -p src/grep '\(a\|b\)' k > Before: real 1.12 user 1.06 sys 0.04 > After : real 0.39 user 0.34 sys 0.04 > > I also tested for non-utf8 multibyte locale. > $ env LC_ALL=ja_JP.eucJP time -p src/grep '\(a\|b\)' k > Before: real 1.41 user 1.35 sys 0.05 > After : real 0.38 user 0.32 sys 0.06 ... Thank you for the patch, but with a 2.30GHz i7-3615QM using 1600MHz DDR3, I see a 40% decrease in performance in that first case: $ for i in grep src/grep; do env LC_ALL=C time -f %e $i '\(a\|b\)' k; done 0.40 0.65 and no change in the latter case. In each case, I used an input file 10 times larger: $ yes j | head -100000000 >k I've also compared on an i5-4250U w/1600MHz DDR3, where there is still a performance decrease, but only 19% this time (each time is the best of 5 trials): 0.43 0.53 From debbugs-submit-bounces@debbugs.gnu.org Sat May 24 01:36:15 2014 Received: (at 17576) by debbugs.gnu.org; 24 May 2014 05:36:15 +0000 Received: from localhost ([127.0.0.1]:58558 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo4cx-0006OM-3t for submit@debbugs.gnu.org; Sat, 24 May 2014 01:36:15 -0400 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:45404) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo4cu-0006O5-0T for 17576@debbugs.gnu.org; Sat, 24 May 2014 01:36:13 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id 8F4B0B0001 for <17576@debbugs.gnu.org>; Sat, 24 May 2014 14:36:04 +0900 (JST) Received: from mail05.kcn.ne.jp ([61.86.6.184]) by imp01 with bizsmtp id 5hc41o00Y3yDdWd01hc4jl; Sat, 24 May 2014 14:36:04 +0900 X-OrgRCPT: 17576@debbugs.gnu.org Received: from [10.120.1.19] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail05.kcn.ne.jp (Postfix) with ESMTPA id 2F1377D00A2; Sat, 24 May 2014 14:36:04 +0900 (JST) Date: Sat, 24 May 2014 14:36:02 +0900 From: Norihiro Tanaka To: Jim Meyering Subject: Re: bug#17576: [PATCH] dfa: speed-up at initial state In-Reply-To: References: <20140524123134.2C5F.27F6AC2D@kcn.ne.jp> Message-Id: <20140524143601.2C67.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17576 Cc: 17576@debbugs.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: -0.7 (/) Wow! Thanks to Paul and Jim for the review. I will retry it with newer OS and gcc. By the way, Have you already found what is wrong in the patch? From debbugs-submit-bounces@debbugs.gnu.org Sat May 24 06:19:33 2014 Received: (at 17576) by debbugs.gnu.org; 24 May 2014 10:19:33 +0000 Received: from localhost ([127.0.0.1]:58640 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo937-0006op-5k for submit@debbugs.gnu.org; Sat, 24 May 2014 06:19:33 -0400 Received: from mailgw04.kcn.ne.jp ([61.86.7.211]:36096) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wo933-0006oQ-PI for 17576@debbugs.gnu.org; Sat, 24 May 2014 06:19:30 -0400 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw04.kcn.ne.jp (Postfix) with ESMTP id 6E87E6C174F for <17576@debbugs.gnu.org>; Sat, 24 May 2014 19:19:27 +0900 (JST) Received: from mail07.kcn.ne.jp ([61.86.6.186]) by imp01 with bizsmtp id 5mKT1o00E40oyB901mKTBo; Sat, 24 May 2014 19:19:27 +0900 X-OrgRCPT: 17576@debbugs.gnu.org Received: from [10.120.1.19] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail07.kcn.ne.jp (Postfix) with ESMTPA id 2FD75D500B6; Sat, 24 May 2014 19:19:27 +0900 (JST) Date: Sat, 24 May 2014 19:19:24 +0900 From: Norihiro Tanaka To: Jim Meyering , Subject: Re: bug#17576: [PATCH] dfa: speed-up at initial state In-Reply-To: <20140524143601.2C67.27F6AC2D@kcn.ne.jp> References: <20140524143601.2C67.27F6AC2D@kcn.ne.jp> Message-Id: <20140524191924.5E6A.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17576 Cc: 17576@debbugs.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: -0.7 (/) Sorry, I was wrong. Correct test case is below. $ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k > Thank you for the patch, but with a 2.30GHz i7-3615QM > using 1600MHz DDR3, I see a 40% decrease in performance > in that first case: It's a case which has a lot of small lines. I will fix it in a future patch. From debbugs-submit-bounces@debbugs.gnu.org Sat May 24 15:17:36 2014 Received: (at 17576) by debbugs.gnu.org; 24 May 2014 19:17:36 +0000 Received: from localhost ([127.0.0.1]:59310 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WoHRo-0005sL-0p for submit@debbugs.gnu.org; Sat, 24 May 2014 15:17:36 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:50992) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WoHRj-0005s2-M4 for 17576@debbugs.gnu.org; Sat, 24 May 2014 15:17:32 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id BCF15A60013; Sat, 24 May 2014 12:17:24 -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 fwMcB7111XjN; Sat, 24 May 2014 12:17:16 -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 3BF1439E8015; Sat, 24 May 2014 12:17:16 -0700 (PDT) Message-ID: <5380F03B.9030600@cs.ucla.edu> Date: Sat, 24 May 2014 12:17:15 -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.5.0 MIME-Version: 1.0 To: Norihiro Tanaka Subject: Re: bug#17576: [PATCH] dfa: speed-up at initial state References: <20140524143601.2C67.27F6AC2D@kcn.ne.jp> <20140524191924.5E6A.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140524191924.5E6A.27F6AC2D@kcn.ne.jp> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: 17576 Cc: 17576@debbugs.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: -3.0 (---) Norihiro Tanaka wrote: >Have you already found what is wrong in the patch? Sorry, no, I just ran the test case you gave in your original report. I guess that grep needs a performance test suite, so that we can find problems like this in a more-disciplined way. From debbugs-submit-bounces@debbugs.gnu.org Mon May 26 10:13:03 2014 Received: (at 17576) by debbugs.gnu.org; 26 May 2014 14:13:03 +0000 Received: from localhost ([127.0.0.1]:60540 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WoveA-0003nI-8K for submit@debbugs.gnu.org; Mon, 26 May 2014 10:13:02 -0400 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:60540) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Wove5-0003ml-TO for 17576@debbugs.gnu.org; Mon, 26 May 2014 10:13:00 -0400 Received: from imp02 (mailgw6.kcn.ne.jp [61.86.15.232]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id 17D34E80627 for <17576@debbugs.gnu.org>; Mon, 26 May 2014 23:12:51 +0900 (JST) Received: from mail02.kcn.ne.jp ([61.86.6.181]) by imp02 with bizsmtp id 6eCr1o0023uLcVp01eCrQT; Mon, 26 May 2014 23:12:51 +0900 X-OrgRCPT: 17576@debbugs.gnu.org Received: from [10.120.1.56] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail02.kcn.ne.jp (Postfix) with ESMTPA id EBA45BE8001; Mon, 26 May 2014 23:12:50 +0900 (JST) Date: Mon, 26 May 2014 23:12:50 +0900 From: Norihiro Tanaka To: Paul Eggert Subject: Re: bug#17576: [PATCH] dfa: speed-up at initial state In-Reply-To: <5380F03B.9030600@cs.ucla.edu> References: <20140524191924.5E6A.27F6AC2D@kcn.ne.jp> <5380F03B.9030600@cs.ucla.edu> Message-Id: <20140526231248.16A4.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5383469000000000169B_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17576 Cc: 17576@debbugs.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: -0.7 (/) --------_5383469000000000169B_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Paul Eggert wrote: > I guess that grep needs a performance test suite, so that we can find > problems like this in a more-disciplined way. I agree, but I have no idea to perform it. BTW, I retried them on Fedora 20, but I couldn't confirm significant slowdown. Intel(R) Core(TM)2 Duo CPU E8500 @ 3.16GHz Fedora 20 GCC 4.8.2 20131017 (Red Hat 4.8.2-1) (x86-64) $ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k $ yes j | head -100000000 >l [ before 0001-dfa-speed-up-at-initial-state.patch ] $ env LC_ALL=C src/grep '\(a\|b\)' k real 0.96 user 0.85 sys 0.10 $ env LC_ALL=C src/grep '\(a\|b\)' l real 0.64 user 0.60 sys 0.03 [ after 0001-dfa-speed-up-at-initial-state.patch ] $ env LC_ALL=C src/grep '\(a\|b\)' k real 0.58 user 0.52 sys 0.05 $ env LC_ALL=C src/grep '\(a\|b\)' l real 0.75 user 0.69 sys 0.05 However, I could confirm slowdown on RHEL6 GCC 4.4.7. According to the result, I see that GCC fails in inlination. In addition to 0001-dfa-speed-up-at-initial-state.patch, I applied an attached patch, and retried them. Then I confirmed speed-up. $ env LC_ALL=C src/grep '\(a\|b\)' k real 0.46 user 0.35 sys 0.10 $ env LC_ALL=C src/grep '\(a\|b\)' l real 0.54 user 0.49 sys 0.04 Thanks, Norihiro --------_5383469000000000169B_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-dfa-separate-dfaexec-function-to-help-optimization-b.patch" Content-Disposition: attachment; filename="0001-dfa-separate-dfaexec-function-to-help-optimization-b.patch" Content-Transfer-Encoding: base64 RnJvbSBmNTI3YjRkMzQ0OGE4OGZiYzAzNWVlZDJmZTgxZGY1MmFhOGJhNzQzIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTdW4sIDI1IE1heSAyMDE0IDE3OjQxOjExICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZGZh OiBzZXBhcmF0ZSBkZmFleGVjIGZ1bmN0aW9uIHRvIGhlbHAgb3B0aW1pemF0aW9uIGJ5CiBjb21w aWxlcgoKKiBzcmMvZGZhLmMgKGRmYWV4ZWNfbWFpbik6IFJlbmFtZSBmcm9tIGRmYWV4ZWMsIGFk ZCBpbmxpbmUgYXR0cmlidXRlLgooZGZhZXhlY19tYik6IE5ldyBmdW5jdGlvbi4gIFJ1biBpdCB3 aGVuIGQtPm11bHRpYnl0ZSBpcyB0cnVlLiAgIEZvciB0aGlzCmZ1bmN0aW9uIGlubGluYXRpb24g bXVzdCBiZSBhdm9pZGVkLgooZGZhZXhlY19zYik6IE5ldyBmdW5jdGlvbi4gIFJ1biBpdCB3aGVu IGQtPm11bHRpYnl0ZSBpcyBmYWxzZS4gIEZvciB0aGlzCmZ1bmN0aW9uIGlubGluYXRpb24gbXVz dCBiZSBhdm9pZGVkLgooZGZhZXhlYyk6IENhbGwgZGZhZXhlY19tYiBvciBkZmFleGVjX3NiIGFj Y29kaW5nIHRvIGQtPm11bHRpYnl0ZS4KLS0tCiBzcmMvZGZhLmMgfCAzNSArKysrKysrKysrKysr KysrKysrKysrKysrKysrKy0tLS0tLQogMSBmaWxlIGNoYW5nZWQsIDI5IGluc2VydGlvbnMoKyks IDYgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2RmYS5jIGIvc3JjL2RmYS5jCmluZGV4 IGE0MWQwMDIuLjUxOTM2MWYgMTAwNjQ0Ci0tLSBhL3NyYy9kZmEuYworKysgYi9zcmMvZGZhLmMK QEAgLTMyODAsOSArMzI4MCw5IEBAIHNraXBfcmVtYWluc19tYiAoc3RydWN0IGRmYSAqZCwgdW5z aWduZWQgY2hhciBjb25zdCAqcCwKICAgIEZpbmFsbHksIGlmIEJBQ0tSRUYgaXMgbm9uLU5VTEwg c2V0ICpCQUNLUkVGIHRvIGluZGljYXRlIHdoZXRoZXIgd2UKICAgIGVuY291bnRlcmVkIGEgYmFj ay1yZWZlcmVuY2UgKDEpIG9yIG5vdCAoMCkuICBUaGUgY2FsbGVyIG1heSB1c2UgdGhpcwogICAg dG8gZGVjaWRlIHdoZXRoZXIgdG8gZmFsbCBiYWNrIG9uIGEgYmFja3RyYWNraW5nIG1hdGNoZXIu ICAqLwotY2hhciAqCi1kZmFleGVjIChzdHJ1Y3QgZGZhICpkLCBjaGFyIGNvbnN0ICpiZWdpbiwg Y2hhciAqZW5kLAotICAgICAgICAgaW50IGFsbG93X25sLCBzaXplX3QgKmNvdW50LCBpbnQgKmJh Y2tyZWYpCitzdGF0aWMgaW5saW5lIGNoYXIgKgorZGZhZXhlY19tYWluIChzdHJ1Y3QgZGZhICpk LCBjaGFyIGNvbnN0ICpiZWdpbiwgY2hhciAqZW5kLAorICAgICAgICAgICAgIGludCBhbGxvd19u bCwgc2l6ZV90ICpjb3VudCwgaW50ICpiYWNrcmVmLCBib29sIGNvbnN0IG11bHRpYnl0ZSkKIHsK ICAgc3RhdGVfbnVtIHMsIHMxOyAgICAgICAgICAgICAgLyogQ3VycmVudCBzdGF0ZS4gICovCiAg IHVuc2lnbmVkIGNoYXIgY29uc3QgKnAsICptYnA7IC8qIEN1cnJlbnQgaW5wdXQgY2hhcmFjdGVy LiAgKi8KQEAgLTMzMDEsNyArMzMwMSw3IEBAIGRmYWV4ZWMgKHN0cnVjdCBkZmEgKmQsIGNoYXIg Y29uc3QgKmJlZ2luLCBjaGFyICplbmQsCiAgIHNhdmVkX2VuZCA9ICoodW5zaWduZWQgY2hhciAq KSBlbmQ7CiAgICplbmQgPSBlb2w7CiAKLSAgaWYgKGQtPm11bHRpYnl0ZSkKKyAgaWYgKG11bHRp Ynl0ZSkKICAgICB7CiAgICAgICBtZW1zZXQgKCZkLT5tYnMsIDAsIHNpemVvZiBkLT5tYnMpOwog ICAgICAgaWYgKCEgZC0+bWJfbWF0Y2hfbGVucykKQEAgLTMzMTMsNyArMzMxMyw3IEBAIGRmYWV4 ZWMgKHN0cnVjdCBkZmEgKmQsIGNoYXIgY29uc3QgKmJlZ2luLCBjaGFyICplbmQsCiAKICAgZm9y ICg7OykKICAgICB7Ci0gICAgICBpZiAoZC0+bXVsdGlieXRlKQorICAgICAgaWYgKG11bHRpYnl0 ZSkKICAgICAgICAgewogICAgICAgICAgIHdoaWxlICgodCA9IHRyYW5zW3NdKSAhPSBOVUxMKQog ICAgICAgICAgICAgewpAQCAtMzQwMiw3ICszNDAyLDcgQEAgZGZhZXhlYyAoc3RydWN0IGRmYSAq ZCwgY2hhciBjb25zdCAqYmVnaW4sIGNoYXIgKmVuZCwKICAgICAgICAgICAgIH0KIAogICAgICAg ICAgIHMxID0gczsKLSAgICAgICAgICBpZiAoZC0+bXVsdGlieXRlKQorICAgICAgICAgIGlmICht dWx0aWJ5dGUpCiAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgIC8qIENhbiBtYXRjaCB3aXRo IGEgbXVsdGlieXRlIGNoYXJhY3RlciAoYW5kIG11bHRpY2hhcmFjdGVyCiAgICAgICAgICAgICAg ICAgIGNvbGxhdGluZyBlbGVtZW50KS4gIFRyYW5zaXRpb24gdGFibGUgbWlnaHQgYmUgdXBkYXRl ZC4gICovCkBAIC0zNDQ3LDYgKzM0NDcsMjkgQEAgZGZhZXhlYyAoc3RydWN0IGRmYSAqZCwgY2hh ciBjb25zdCAqYmVnaW4sIGNoYXIgKmVuZCwKICAgcmV0dXJuIChjaGFyICopIHA7CiB9CiAKK3N0 YXRpYyBjaGFyICpfX2F0dHJpYnV0ZV9fKChub2lubGluZSkpCitkZmFleGVjX21iIChzdHJ1Y3Qg ZGZhICpkLCBjaGFyIGNvbnN0ICpiZWdpbiwgY2hhciAqZW5kLAorICAgICAgICAgICBpbnQgYWxs b3dfbmwsIHNpemVfdCAqY291bnQsIGludCAqYmFja3JlZikKK3sKKyAgcmV0dXJuIGRmYWV4ZWNf bWFpbiAoZCwgYmVnaW4sIGVuZCwgYWxsb3dfbmwsIGNvdW50LCBiYWNrcmVmLCB0cnVlKTsKK30K Kworc3RhdGljIGNoYXIgKl9fYXR0cmlidXRlX18oKG5vaW5saW5lKSkKK2RmYWV4ZWNfc2IgKHN0 cnVjdCBkZmEgKmQsIGNoYXIgY29uc3QgKmJlZ2luLCBjaGFyICplbmQsCisgICAgICAgICAgIGlu dCBhbGxvd19ubCwgc2l6ZV90ICpjb3VudCwgaW50ICpiYWNrcmVmKQoreworICByZXR1cm4gZGZh ZXhlY19tYWluIChkLCBiZWdpbiwgZW5kLCBhbGxvd19ubCwgY291bnQsIGJhY2tyZWYsIGZhbHNl KTsKK30KKworY2hhciAqCitkZmFleGVjIChzdHJ1Y3QgZGZhICpkLCBjaGFyIGNvbnN0ICpiZWdp biwgY2hhciAqZW5kLAorICAgICAgICAgaW50IGFsbG93X25sLCBzaXplX3QgKmNvdW50LCBpbnQg KmJhY2tyZWYpCit7CisgIHJldHVybiAoZC0+bXVsdGlieXRlCisgICAgPyBkZmFleGVjX21iIChk LCBiZWdpbiwgZW5kLCBhbGxvd19ubCwgY291bnQsIGJhY2tyZWYpCisgICAgOiBkZmFleGVjX3Ni IChkLCBiZWdpbiwgZW5kLCBhbGxvd19ubCwgY291bnQsIGJhY2tyZWYpKTsKK30KKwogc3RydWN0 IGRmYSAqCiBkZmFzdXBlcnNldCAoc3RydWN0IGRmYSBjb25zdCAqZCkKIHsKLS0gCjEuOS4zCgo= --------_5383469000000000169B_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Fri May 30 03:31:55 2014 Received: (at 17576) by debbugs.gnu.org; 30 May 2014 07:31:55 +0000 Received: from localhost ([127.0.0.1]:36827 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WqHI6-0006iP-96 for submit@debbugs.gnu.org; Fri, 30 May 2014 03:31:55 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:60447) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WqHHz-0006hx-4M for 17576@debbugs.gnu.org; Fri, 30 May 2014 03:31:47 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 77729A60016; Fri, 30 May 2014 00:31:37 -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 ZCEjxAwRBKYJ; Fri, 30 May 2014 00:31:28 -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 C8308A60015; Fri, 30 May 2014 00:31:28 -0700 (PDT) Message-ID: <538833D0.6010802@cs.ucla.edu> Date: Fri, 30 May 2014 00:31:28 -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.5.0 MIME-Version: 1.0 To: 17576@debbugs.gnu.org, Norihiro Tanaka Subject: Re: [PATCH] dfa: speed-up at initial state Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -3.0 (---) X-Debbugs-Envelope-To: 17576 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: -3.0 (---) I don't think we need to complicate the code to improve optimization with older compilers. People who really care about performance will use newer compilers anyway. So let's focus on 0001-dfa-speed-up-at-initial-state.patch. I confirmed your performance results on my platform: the change makes test case "k" about 60% faster and test case "l" about 14% slower. At this point we're just in bugfix mode so this patch can wait. It'd be nice if it didn't slow down the short-line case so much. Also, I wonder how well this change works for "typical" searches. (I realize that "typical" is hard to define....) From debbugs-submit-bounces@debbugs.gnu.org Fri May 30 07:40:25 2014 Received: (at 17576) by debbugs.gnu.org; 30 May 2014 11:40:25 +0000 Received: from localhost ([127.0.0.1]:36896 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WqLAb-0007bT-8c for submit@debbugs.gnu.org; Fri, 30 May 2014 07:40:25 -0400 Received: from mailgw01.kcn.ne.jp ([61.86.7.208]:51971) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WqLAU-0007b3-Ug for 17576@debbugs.gnu.org; Fri, 30 May 2014 07:40:19 -0400 Received: from imp02 (mailgw6.kcn.ne.jp [61.86.15.232]) by mailgw01.kcn.ne.jp (Postfix) with ESMTP id C5B3C80296 for <17576@debbugs.gnu.org>; Fri, 30 May 2014 20:40:07 +0900 (JST) Received: from mail07.kcn.ne.jp ([61.86.6.186]) by imp02 with bizsmtp id 8Bg71o00g40oyB901Bg77w; Fri, 30 May 2014 20:40:07 +0900 X-OrgRCPT: 17576@debbugs.gnu.org Received: from [10.120.1.55] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail07.kcn.ne.jp (Postfix) with ESMTPA id 98658D5009A; Fri, 30 May 2014 20:40:07 +0900 (JST) Date: Fri, 30 May 2014 20:40:08 +0900 From: Norihiro Tanaka To: Paul Eggert Subject: Re: [PATCH] dfa: speed-up at initial state In-Reply-To: <538833D0.6010802@cs.ucla.edu> References: <538833D0.6010802@cs.ucla.edu> Message-Id: <20140530204008.F214.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 17576 Cc: 17576@debbugs.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: -0.7 (/) Paul Eggert wrote: > I don't think we need to complicate the code to improve optimization > with older compilers. Thanks for the confirmation. Two results of last are with not GCC 4.4.7 but GCC 4.8.2 after applying second patch. The test case "k" is 50% faster and "l" is also about 16% faster with GCC 4.8.2 on my platform by two changes. From debbugs-submit-bounces@debbugs.gnu.org Sun Sep 28 00:01:26 2014 Received: (at 17576-done) by debbugs.gnu.org; 28 Sep 2014 04:01:26 +0000 Received: from localhost ([127.0.0.1]:54024 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XY5fp-0004x7-Fj for submit@debbugs.gnu.org; Sun, 28 Sep 2014 00:01:26 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:46049) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XY5fl-0004wx-Fz for 17576-done@debbugs.gnu.org; Sun, 28 Sep 2014 00:01:23 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 0308539E8014; Sat, 27 Sep 2014 21:01:20 -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 PJW+UicnUYNx; Sat, 27 Sep 2014 21:01:15 -0700 (PDT) Received: from [192.168.1.9] (pool-71-177-17-123.lsanca.dsl-w.verizon.net [71.177.17.123]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 01AB939E8011; Sat, 27 Sep 2014 21:01:14 -0700 (PDT) Message-ID: <5427880A.6080907@cs.ucla.edu> Date: Sat, 27 Sep 2014 21:01:14 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.1.2 MIME-Version: 1.0 To: Norihiro Tanaka Subject: Re: [PATCH] dfa: speed-up at initial state References: <538833D0.6010802@cs.ucla.edu> <20140530204008.F214.27F6AC2D@kcn.ne.jp> In-Reply-To: <20140530204008.F214.27F6AC2D@kcn.ne.jp> Content-Type: multipart/mixed; boundary="------------080300050608070103080104" X-Spam-Score: -3.2 (---) X-Debbugs-Envelope-To: 17576-done Cc: 17576-done@debbugs.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: -3.2 (---) This is a multi-part message in MIME format. --------------080300050608070103080104 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Norihiro Tanaka wrote: > The test case "k" is 50% > faster and "l" is also about 16% faster with GCC 4.8.2 on my platform by > two changes. Thanks, I finally got around to looking at this and got similar performance results to yours. That __attribute__((noinline)) bothers me, though, as it's not portable and is a bit inelegant. I figured out a different way to avoid the inlining, and tweaked the commentary a bit, and so installed the attached additional patch after installing your patches. --------------080300050608070103080104 Content-Type: text/plain; charset=UTF-8; name="0001-dfa-minor-tweaks-mostly-to-remove-__attribute__-noin.patch" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename*0="0001-dfa-minor-tweaks-mostly-to-remove-__attribute__-noin.pa"; filename*1="tch" RnJvbSBhYzc1N2EzNGQ2YjkzOTQyNzMyZDEwMjZjMWU0ZTNjNjdmODgyZDg2IE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBQYXVsIEVnZ2VydCA8ZWdnZXJ0QGNzLnVjbGEuZWR1 PgpEYXRlOiBTYXQsIDI3IFNlcCAyMDE0IDIwOjU1OjEzIC0wNzAwClN1YmplY3Q6IFtQQVRD SF0gZGZhOiBtaW5vciB0d2Vha3MsIG1vc3RseSB0byByZW1vdmUgX19hdHRyaWJ1dGVfXwog KChub2lubGluZSkpCgpUaGF0IGF0dHJpYnV0ZSBpc24ndCBwb3J0YWJsZSwgYW5kIEkgZm91 bmQgYSB3YXkgdG8gZ2V0IHNpbWlsYXIKcGVyZm9ybWFuY2Ugd2l0aCBzdGFuZGFyZCBDIGZl YXR1cmVzLgoqIE5FV1M6IERvY3VtZW50IHRoZSByZWNlbnRseS1pbnN0YWxsZWQgcGVyZm9y bWFuY2UgaW1wcm92ZW1lbnQuCiogc3JjL2RmYS5jIChzdHJ1Y3QgZGZhKTogTmV3IG1lbWJl ciBkZmFleGVjLgooZGZhZXhlY19tYWluKTogUmVtb3ZlIHVubmVjZXNzYXJ5ICdjb25zdCcu CihkZmFleGVjX21iLCBkZmFleGVjX3NiKTogUmVtb3ZlIF9fYXR0cmlidXRlX18gKChub2lu bGluZSkpOwpubyBsb25nZXIgbmVlZGVkLgooZGZhZXhlYyk6IFVzZSBuZXcgZGZhZXhlYyBt ZW1iZXIuCihkZmFpbml0LCBkZmFvcHRpbWl6ZSwgZGZhc3NidWlsZCk6IEluaXRpYWxpemUg aXQuCi0tLQogTkVXUyAgICAgIHwgIDMgKysrCiBzcmMvZGZhLmMgfCAzMiArKysrKysrKysr KysrKysrKysrKysrKy0tLS0tLS0tLQogMiBmaWxlcyBjaGFuZ2VkLCAyNiBpbnNlcnRpb25z KCspLCA5IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL05FV1MgYi9ORVdTCmluZGV4IDVi Yzg5YzAuLmExNDZlOWUgMTAwNjQ0Ci0tLSBhL05FV1MKKysrIGIvTkVXUwpAQCAtNyw2ICs3 LDkgQEAgR05VIGdyZXAgTkVXUyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg IC0qLSBvdXRsaW5lIC0qLQogICBQZXJmb3JtYW5jZSBoYXMgYmVlbiBncmVhdGx5IGltcHJv dmVkIGZvciBzZWFyY2hpbmcgZmlsZXMgY29udGFpbmluZwogICBob2xlcywgb24gcGxhdGZv cm1zIHdoZXJlIGxzZWVrJ3MgU0VFS19EQVRBIGZsYWcgd29ya3MgZWZmaWNpZW50bHkuCiAK KyAgUGVyZm9ybWFuY2UgaGFzIGltcHJvdmVkIGZvciByZWplY3RpbmcgZGF0YSB0aGF0IGNh bm5vdCBtYXRjaCBldmVuCisgIHRoZSBmaXJzdCBwYXJ0IG9mIGEgbm9udHJpdmlhbCBwYXR0 ZXJuLgorCiAgIFBlcmZvcm1hbmNlIGhhcyBpbXByb3ZlZCBmb3IgdmVyeSBsb25nIHN0cmlu Z3MgaW4gcGF0dGVybnMuCiAKICAgSWYgYSBmaWxlIGNvbnRhaW5zIGRhdGEgaW1wcm9wZXJs eSBlbmNvZGVkIGZvciB0aGUgY3VycmVudCBsb2NhbGUsCmRpZmYgLS1naXQgYS9zcmMvZGZh LmMgYi9zcmMvZGZhLmMKaW5kZXggZmYyM2MwNy4uNGY0NWZmZiAxMDA2NDQKLS0tIGEvc3Jj L2RmYS5jCisrKyBiL3NyYy9kZmEuYwpAQCAtMzQyLDYgKzM0Miw5IEBAIHN0cnVjdCBkZmEK ICAgdG9rZW4gdXRmOF9hbnljaGFyX2NsYXNzZXNbNV07IC8qIFRvIGxvd2VyIEFOWUNIQVIg aW4gVVRGLTggbG9jYWxlcy4gICovCiAgIG1ic3RhdGVfdCBtYnM7CQkvKiBNdWx0aWJ5dGUg Y29udmVyc2lvbiBzdGF0ZS4gICovCiAKKyAgLyogZGZhZXhlYyBpbXBsZW1lbnRhdGlvbi4g ICovCisgIGNoYXIgKigqZGZhZXhlYykgKHN0cnVjdCBkZmEgKiwgY2hhciBjb25zdCAqLCBj aGFyICosIGludCwgc2l6ZV90ICosIGludCAqKTsKKwogICAvKiBUaGUgZm9sbG93aW5nIGFy ZSB2YWxpZCBvbmx5IGlmIE1CX0NVUl9NQVggPiAxLiAgKi8KIAogICAvKiBUaGUgdmFsdWUg b2YgbXVsdGlieXRlX3Byb3BbaV0gaXMgZGVmaW5lZCBieSBmb2xsb3dpbmcgcnVsZS4KQEAg LTMyNjYsMTAgKzMyNjksMTQgQEAgc2tpcF9yZW1haW5zX21iIChzdHJ1Y3QgZGZhICpkLCB1 bnNpZ25lZCBjaGFyIGNvbnN0ICpwLAogICAgSWYgQ09VTlQgaXMgbm9uLU5VTEwsIGluY3Jl bWVudCAqQ09VTlQgb25jZSBmb3IgZWFjaCBuZXdsaW5lIHByb2Nlc3NlZC4KICAgIEZpbmFs bHksIGlmIEJBQ0tSRUYgaXMgbm9uLU5VTEwgc2V0ICpCQUNLUkVGIHRvIGluZGljYXRlIHdo ZXRoZXIgd2UKICAgIGVuY291bnRlcmVkIGEgYmFjay1yZWZlcmVuY2UgKDEpIG9yIG5vdCAo MCkuICBUaGUgY2FsbGVyIG1heSB1c2UgdGhpcwotICAgdG8gZGVjaWRlIHdoZXRoZXIgdG8g ZmFsbCBiYWNrIG9uIGEgYmFja3RyYWNraW5nIG1hdGNoZXIuICAqLworICAgdG8gZGVjaWRl IHdoZXRoZXIgdG8gZmFsbCBiYWNrIG9uIGEgYmFja3RyYWNraW5nIG1hdGNoZXIuCisKKyAg IElmIE1VTFRJQllURSwgdGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpYnl0ZSBjaGFyYWN0 ZXJzIGFuZC9vcgorICAgZW5jb2RpbmctZXJyb3IgYnl0ZXMuICBPdGhlcndpc2UsIHRoZSBp bnB1dCBjb25zaXN0cyBvZiBzaW5nbGUtYnl0ZQorICAgY2hhcmFjdGVycy4gICovCiBzdGF0 aWMgaW5saW5lIGNoYXIgKgogZGZhZXhlY19tYWluIChzdHJ1Y3QgZGZhICpkLCBjaGFyIGNv bnN0ICpiZWdpbiwgY2hhciAqZW5kLAotICAgICAgICAgICAgIGludCBhbGxvd19ubCwgc2l6 ZV90ICpjb3VudCwgaW50ICpiYWNrcmVmLCBib29sIGNvbnN0IG11bHRpYnl0ZSkKKyAgICAg ICAgICAgICBpbnQgYWxsb3dfbmwsIHNpemVfdCAqY291bnQsIGludCAqYmFja3JlZiwgYm9v bCBtdWx0aWJ5dGUpCiB7CiAgIHN0YXRlX251bSBzLCBzMTsgICAgICAgICAgICAgIC8qIEN1 cnJlbnQgc3RhdGUuICAqLwogICB1bnNpZ25lZCBjaGFyIGNvbnN0ICpwLCAqbWJwOyAvKiBD dXJyZW50IGlucHV0IGNoYXJhY3Rlci4gICovCkBAIC0zNDMyLDI3ICszNDM5LDMxIEBAIGRm YWV4ZWNfbWFpbiAoc3RydWN0IGRmYSAqZCwgY2hhciBjb25zdCAqYmVnaW4sIGNoYXIgKmVu ZCwKICAgcmV0dXJuIChjaGFyICopIHA7CiB9CiAKLXN0YXRpYyBjaGFyICpfX2F0dHJpYnV0 ZV9fKChub2lubGluZSkpCisvKiBTcGVjaWFsaXplZCB2ZXJzaW9ucyBvZiBkZmFleGVjX21h aW4gZm9yIG11bHRpYnl0ZSBhbmQgc2luZ2xlLWJ5dGUKKyAgIGNhc2VzLiAgVGhpcyBpcyBm b3IgcGVyZm9ybWFuY2UuICAqLworCitzdGF0aWMgY2hhciAqCiBkZmFleGVjX21iIChzdHJ1 Y3QgZGZhICpkLCBjaGFyIGNvbnN0ICpiZWdpbiwgY2hhciAqZW5kLAotICAgICAgICAgICBp bnQgYWxsb3dfbmwsIHNpemVfdCAqY291bnQsIGludCAqYmFja3JlZikKKyAgICAgICAgICAg IGludCBhbGxvd19ubCwgc2l6ZV90ICpjb3VudCwgaW50ICpiYWNrcmVmKQogewogICByZXR1 cm4gZGZhZXhlY19tYWluIChkLCBiZWdpbiwgZW5kLCBhbGxvd19ubCwgY291bnQsIGJhY2ty ZWYsIHRydWUpOwogfQogCi1zdGF0aWMgY2hhciAqX19hdHRyaWJ1dGVfXygobm9pbmxpbmUp KQorc3RhdGljIGNoYXIgKgogZGZhZXhlY19zYiAoc3RydWN0IGRmYSAqZCwgY2hhciBjb25z dCAqYmVnaW4sIGNoYXIgKmVuZCwKLSAgICAgICAgICAgaW50IGFsbG93X25sLCBzaXplX3Qg KmNvdW50LCBpbnQgKmJhY2tyZWYpCisgICAgICAgICAgICBpbnQgYWxsb3dfbmwsIHNpemVf dCAqY291bnQsIGludCAqYmFja3JlZikKIHsKICAgcmV0dXJuIGRmYWV4ZWNfbWFpbiAoZCwg YmVnaW4sIGVuZCwgYWxsb3dfbmwsIGNvdW50LCBiYWNrcmVmLCBmYWxzZSk7CiB9CiAKKy8q IExpa2UgZGZhZXhlY19tYWluIChELCBCRUdJTiwgRU5ELCBBTExPV19OTCwgQ09VTlQsIEJB Q0tSRUYsIEQtPm11bHRpYnl0ZSksCisgICBidXQgZmFzdGVyLiAgKi8KKwogY2hhciAqCiBk ZmFleGVjIChzdHJ1Y3QgZGZhICpkLCBjaGFyIGNvbnN0ICpiZWdpbiwgY2hhciAqZW5kLAog ICAgICAgICAgaW50IGFsbG93X25sLCBzaXplX3QgKmNvdW50LCBpbnQgKmJhY2tyZWYpCiB7 Ci0gIHJldHVybiAoZC0+bXVsdGlieXRlCi0gICAgPyBkZmFleGVjX21iIChkLCBiZWdpbiwg ZW5kLCBhbGxvd19ubCwgY291bnQsIGJhY2tyZWYpCi0gICAgOiBkZmFleGVjX3NiIChkLCBi ZWdpbiwgZW5kLCBhbGxvd19ubCwgY291bnQsIGJhY2tyZWYpKTsKKyAgcmV0dXJuIGQtPmRm YWV4ZWMgKGQsIGJlZ2luLCBlbmQsIGFsbG93X25sLCBjb3VudCwgYmFja3JlZik7CiB9CiAK IHN0cnVjdCBkZmEgKgpAQCAtMzUwNCw2ICszNTE1LDcgQEAgZGZhaW5pdCAoc3RydWN0IGRm YSAqZCkKIHsKICAgbWVtc2V0IChkLCAwLCBzaXplb2YgKmQpOwogICBkLT5tdWx0aWJ5dGUg PSBNQl9DVVJfTUFYID4gMTsKKyAgZC0+ZGZhZXhlYyA9IGQtPm11bHRpYnl0ZSA/IGRmYWV4 ZWNfbWIgOiBkZmFleGVjX3NiOwogICBkLT5mYXN0ID0gIWQtPm11bHRpYnl0ZTsKIH0KIApA QCAtMzU0NCw2ICszNTU2LDcgQEAgZGZhb3B0aW1pemUgKHN0cnVjdCBkZmEgKmQpCiAKICAg ZnJlZV9tYmRhdGEgKGQpOwogICBkLT5tdWx0aWJ5dGUgPSBmYWxzZTsKKyAgZC0+ZGZhZXhl YyA9IGRmYWV4ZWNfc2I7CiB9CiAKIHN0YXRpYyB2b2lkCkBAIC0zNTU3LDYgKzM1NzAsNyBA QCBkZmFzc2J1aWxkIChzdHJ1Y3QgZGZhICpkKQogCiAgICpzdXAgPSAqZDsKICAgc3VwLT5t dWx0aWJ5dGUgPSBmYWxzZTsKKyAgc3VwLT5kZmFleGVjID0gZGZhZXhlY19zYjsKICAgc3Vw LT5tdWx0aWJ5dGVfcHJvcCA9IE5VTEw7CiAgIHN1cC0+bWJjc2V0cyA9IE5VTEw7CiAgIHN1 cC0+c3VwZXJzZXQgPSBOVUxMOwotLSAKMS45LjMKCg== --------------080300050608070103080104-- From debbugs-submit-bounces@debbugs.gnu.org Sun Sep 28 03:18:22 2014 Received: (at 17576-done) by debbugs.gnu.org; 28 Sep 2014 07:18:22 +0000 Received: from localhost ([127.0.0.1]:54042 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XY8kP-0001Qi-O0 for submit@debbugs.gnu.org; Sun, 28 Sep 2014 03:18:21 -0400 Received: from mailgw05.kcn.ne.jp ([61.86.7.212]:51251) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XY8kL-0001QX-Ns for 17576-done@debbugs.gnu.org; Sun, 28 Sep 2014 03:18:19 -0400 Received: from imp03 (mailgw7.kcn.ne.jp [61.86.15.238]) by mailgw05.kcn.ne.jp (Postfix) with ESMTP id 8952B67BD6 for <17576-done@debbugs.gnu.org>; Sun, 28 Sep 2014 16:18:15 +0900 (JST) Received: from mail06.kcn.ne.jp ([61.86.6.185]) by imp03 with bizsmtp id wXJF1o0063zXHqt01XJFey; Sun, 28 Sep 2014 16:18:15 +0900 X-OrgRCPT: 17576-done@debbugs.gnu.org Received: from [10.120.1.41] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail06.kcn.ne.jp (Postfix) with ESMTPA id DB7E21BF0092; Sun, 28 Sep 2014 16:18:14 +0900 (JST) Date: Sun, 28 Sep 2014 16:18:15 +0900 From: Norihiro Tanaka To: Paul Eggert Subject: Re: [PATCH] dfa: speed-up at initial state In-Reply-To: <5427880A.6080907@cs.ucla.edu> References: <20140530204008.F214.27F6AC2D@kcn.ne.jp> <5427880A.6080907@cs.ucla.edu> Message-Id: <20140928161814.6791.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.9 (/) X-Debbugs-Envelope-To: 17576-done Cc: 17576-done@debbugs.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: -0.9 (/) Paul Eggert wrote: > Thanks, I finally got around to looking at this and got similar > performance results to yours. That __attribute__((noinline)) bothers > me, though, as it's not portable and is a bit inelegant. I figured > out a different way to avoid the inlining, and tweaked the commentary > a bit, and so installed the attached additional patch after installing > your patches. Excellent. Thanks for the review and additional improvement. I don't like that my patch have uses `((noinline)) __attribute __' which isn't portable, but you fix it. From unknown Sat Sep 06 00:11:40 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, 26 Oct 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