From unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 24 May 2014 03:33:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 17576@debbugs.gnu.org X-Debbugs-Original-To: bug-grep@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.14009023344927 (code B ref -1); Sat, 24 May 2014 03:33:01 +0000 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 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-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 unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 24 May 2014 05:02:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka , 17576@debbugs.gnu.org Received: via spool by 17576-submit@debbugs.gnu.org id=B17576.140090771120102 (code B ref 17576); Sat, 24 May 2014 05:02:02 +0000 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 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-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 unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Jim Meyering Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 24 May 2014 05:24:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka Cc: 17576@debbugs.gnu.org Received: via spool by 17576-submit@debbugs.gnu.org id=B17576.140090900322824 (code B ref 17576); Sat, 24 May 2014 05:24:01 +0000 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: Content-Type: text/plain; charset=ISO-8859-1 X-Spam-Score: -0.7 (/) 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 unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 24 May 2014 05:37:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Jim Meyering Cc: 17576@debbugs.gnu.org Received: via spool by 17576-submit@debbugs.gnu.org id=B17576.140090977524578 (code B ref 17576); Sat, 24 May 2014 05:37:02 +0000 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 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-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 unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 24 May 2014 10:20:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Jim Meyering , Cc: 17576@debbugs.gnu.org Received: via spool by 17576-submit@debbugs.gnu.org id=B17576.140092677326220 (code B ref 17576); Sat, 24 May 2014 10:20:01 +0000 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 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-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 unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sat, 24 May 2014 19:18:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka Cc: 17576@debbugs.gnu.org Received: via spool by 17576-submit@debbugs.gnu.org id=B17576.140095905622594 (code B ref 17576); Sat, 24 May 2014 19:18:02 +0000 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 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-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 unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Mon, 26 May 2014 14:14:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 17576@debbugs.gnu.org Received: via spool by 17576-submit@debbugs.gnu.org id=B17576.140111358314593 (code B ref 17576); Mon, 26 May 2014 14:14:01 +0000 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 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-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 unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: 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> Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Fri, 30 May 2014 07:32:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 17576@debbugs.gnu.org, Norihiro Tanaka Received: via spool by 17576-submit@debbugs.gnu.org id=B17576.140143511525827 (code B ref 17576); Fri, 30 May 2014 07:32:02 +0000 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 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -3.0 (---) 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 unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Fri, 30 May 2014 11:41:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 17576@debbugs.gnu.org Received: via spool by 17576-submit@debbugs.gnu.org id=B17576.140145002529239 (code B ref 17576); Fri, 30 May 2014 11:41:02 +0000 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 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-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 unknown Fri Sep 05 20:55:48 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: Norihiro Tanaka Subject: bug#17576: closed (Re: [PATCH] dfa: speed-up at initial state) Message-ID: References: <5427880A.6080907@cs.ucla.edu> <20140524123134.2C5F.27F6AC2D@kcn.ne.jp> X-Gnu-PR-Message: they-closed 17576 X-Gnu-PR-Package: grep X-Gnu-PR-Keywords: patch Reply-To: 17576@debbugs.gnu.org Date: Sun, 28 Sep 2014 04:02:03 +0000 Content-Type: multipart/mixed; boundary="----------=_1411876923-19089-1" This is a multi-part message in MIME format... ------------=_1411876923-19089-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #17576: [PATCH] dfa: speed-up at initial state which was filed against the grep package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 17576@debbugs.gnu.org. --=20 17576: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D17576 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1411876923-19089-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit 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-- ------------=_1411876923-19089-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit 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_-- ------------=_1411876923-19089-1-- From unknown Fri Sep 05 20:55:48 2025 X-Loop: help-debbugs@gnu.org Subject: bug#17576: [PATCH] dfa: speed-up at initial state Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Sun, 28 Sep 2014 07:19:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17576 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Paul Eggert Cc: 17576-done@debbugs.gnu.org Received: via spool by 17576-done@debbugs.gnu.org id=D17576.14118887025505 (code D ref 17576); Sun, 28 Sep 2014 07:19:02 +0000 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 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-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.