From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS22989 209.51.188.0/24 X-Spam-Status: No, score=-3.5 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 0BBC620248 for ; Sat, 23 Mar 2019 02:56:25 +0000 (UTC) Received: from localhost ([127.0.0.1]:37775 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h7Wpb-0006hQ-AB for normalperson@yhbt.net; Fri, 22 Mar 2019 22:56:23 -0400 Received: from eggs.gnu.org ([209.51.188.92]:41663) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h7WpV-0006dc-IA for bug-gnulib@gnu.org; Fri, 22 Mar 2019 22:56:18 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1h7WiY-0003TA-IG for bug-gnulib@gnu.org; Fri, 22 Mar 2019 22:49:07 -0400 Received: from mailgw01.kcn.ne.jp ([61.86.7.208]:42232) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h7WiX-0003Oy-R5 for bug-gnulib@gnu.org; Fri, 22 Mar 2019 22:49:06 -0400 Received: from mxs02-s (mailgw2.kcn.ne.jp [61.86.15.234]) by mailgw01.kcn.ne.jp (Postfix) with ESMTP id 6AFBB4A08D4 for ; Sat, 23 Mar 2019 11:49:03 +0900 (JST) X-matriXscan-loop-detect: f5892a53e0215d157fd3ec2055933e41d141c31b Received: from mail10.kcn.ne.jp ([61.86.6.128]) by mxs02-s with ESMTP; Sat, 23 Mar 2019 11:49:03 +0900 (JST) Received: from [10.120.1.89] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail10.kcn.ne.jp (Postfix) with ESMTPA id 1108640AA1CC; Sat, 23 Mar 2019 11:49:03 +0900 (JST) Date: Sat, 23 Mar 2019 11:49:02 +0900 From: Norihiro Tanaka To: 34951@debbugs.gnu.org Subject: Re: bug#34951: [PATCH] grep: a kwset matcher not work in a grep matcher In-Reply-To: <20190323080618.E6EB.27F6AC2D@kcn.ne.jp> References: <20190323080618.E6EB.27F6AC2D@kcn.ne.jp> Message-Id: <20190323114902.E6F6.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5C959DEC00000000E6FE_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.73 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 61.86.7.208 X-BeenThere: bug-gnulib@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: Gnulib discussion list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: bug-gnulib@gnu.org Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" --------_5C959DEC00000000E6FE_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit On Sat, 23 Mar 2019 08:06:35 +0900 Norihiro Tanaka wrote: > A kwset matcher is not built in a grep matcher after token re-order is > introduced in commit 5c7a0371823876cca7a1347fa09ca26bbbff0c98 in dfa. > It caused performance degradation in some typical cases. This bug is > introduced in grep-3.2. > > DFAMUST() does not work if tokens which are parsed in dfa matcher are > re-ordered. Therefore, change as it is called after parse and before > tokens re-order. > > BTW, this change does not affect programs that do not use DFAMUST(), > such as sed or gawk. > > $ yes $(printf '%040d' 0) | head -10000000 >inp > $ grep-2.2/src/grep 01.2 inp > real 1.61 > user 1.53 > sys 0.07 > $ grep-2.3/src/grep 01.2 inp > real 1.57 > user 1.48 > sys 0.08 > $ grep-2.4/src/grep 01.2 inp > real 1.50 > user 1.44 > sys 0.05 > $ grep-2.4.1/src/grep 01.2 inp > real 1.53 > user 1.48 > sys 0.05 > $ grep-2.4.2/src/grep 01.2 inp > real 1.52 > user 1.47 > sys 0.04 > $ grep-2.5.4/src/grep 01.2 inp > real 1.53 > user 1.47 > sys 0.05 > $ grep-2.6/src/grep 01.2 inp > real 1.51 > user 1.47 > sys 0.04 > $ grep-2.6.1/src/grep 01.2 inp > real 1.50 > user 1.44 > sys 0.05 > $ grep-2.6.2/src/grep 01.2 inp > real 1.52 > user 1.46 > sys 0.05 > $ grep-2.6.3/src/grep 01.2 inp > real 1.52 > user 1.47 > sys 0.05 > $ grep-2.7/src/grep 01.2 inp > real 1.53 > user 1.49 > sys 0.04 > $ grep-2.8/src/grep 01.2 inp > real 1.52 > user 1.46 > sys 0.05 > $ grep-2.9/src/grep 01.2 inp > real 1.54 > user 1.50 > sys 0.04 > $ grep-2.10/src/grep 01.2 inp > real 1.51 > user 1.46 > sys 0.05 > $ grep-2.11/src/grep 01.2 inp > real 1.53 > user 1.48 > sys 0.05 > $ grep-2.12/src/grep 01.2 inp > real 1.51 > user 1.47 > sys 0.03 > $ grep-2.13/src/grep 01.2 inp > real 1.52 > user 1.47 > sys 0.03 > $ grep-2.14/src/grep 01.2 inp > real 1.52 > user 1.47 > sys 0.04 > $ grep-2.15/src/grep 01.2 inp > real 1.55 > user 1.49 > sys 0.05 > $ grep-2.16/src/grep 01.2 inp > real 1.53 > user 1.48 > sys 0.04 > $ grep-2.17/src/grep 01.2 inp > real 1.53 > user 1.48 > sys 0.05 > $ grep-2.18/src/grep 01.2 inp > real 1.51 > user 1.44 > sys 0.06 > $ grep-2.19/src/grep 01.2 inp > real 0.06 > user 0.02 > sys 0.04 > $ grep-2.20/src/grep 01.2 inp > real 0.07 > user 0.01 > sys 0.05 > $ grep-2.21/src/grep 01.2 inp > real 0.06 > user 0.02 > sys 0.04 > $ grep-2.22/src/grep 01.2 inp > real 0.06 > user 0.01 > sys 0.05 > $ grep-2.23/src/grep 01.2 inp > real 0.09 > user 0.04 > sys 0.05 > $ grep-2.24/src/grep 01.2 inp > real 0.09 > user 0.04 > sys 0.04 > $ grep-2.25/src/grep 01.2 inp > real 0.09 > user 0.05 > sys 0.04 > $ grep-2.26/src/grep 01.2 inp > real 0.09 > user 0.04 > sys 0.05 > $ grep-2.27/src/grep 01.2 inp > real 0.09 > user 0.04 > sys 0.04 > $ grep-2.28/src/grep 01.2 inp > real 0.09 > user 0.04 > sys 0.04 > $ grep-3.0/src/grep 01.2 inp > real 0.09 > user 0.04 > sys 0.04 > $ grep-3.1/src/grep 01.2 inp > real 0.11 > user 0.05 > sys 0.06 > $ grep-3.2/src/grep 01.2 inp > real 0.37 > user 0.32 > sys 0.04 > $ grep-3.3/src/grep 01.2 inp > real 0.29 > user 0.25 > sys 0.04 > > Thanks, > Norihiro Missing a patch for dfa. Re-send correct patch file. --------_5C959DEC00000000E6FE_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-dfa-separate-parse-and-compile-phase.patch" Content-Disposition: attachment; filename="0001-dfa-separate-parse-and-compile-phase.patch" Content-Transfer-Encoding: base64 RnJvbSBkMTJkMzI1NjA0M2E3OTJmZTY1ODMwZmY2NDY5YmJhNjQxODg3NmUxIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDIzIE1hciAyMDE5IDA4OjE5OjExICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZGZh OiBzZXBhcmF0ZSBwYXJzZSBhbmQgY29tcGlsZSBwaGFzZQoKREZBTVVTVCgpIG11c3QgYmUgY2Fs bGVkIGFmdGVyIHBhcnNlIGFuZCBiZWZvcmUgdG9rZW5zIHJlLW9yZGVyIHdoaWNoIGlzCmludHJv ZHVjZWQgaW4gY29tbWl0IDVjN2EwMzcxODIzODc2Y2NhN2ExMzQ3ZmEwOWNhMjZiYmJmZjBjOTgs IGJ1dCBib3RoIGFyZQpleGVjdXRlZCBpbiBjb21waWxhdGlvbiBwaGFzZS4KCiogbGliL2RmYS5j IChkZmFwYXJzZSk6IENoYW5nZSBpdCB0byBnbG9iYWwgZnVuY3Rpb24uCihkZmFjb21wKTogSWYg Zmlyc3QgYXJndW1lbnQgaXMgTlVMTCwgc2tpcCBwYXJzZS4KKiBsaWIvZGZhLmg6IChkZmFwYXJz ZSk6IEFkZCBhIHByb3RvdHlwZS4KLS0tCiBsaWIvZGZhLmMgfCAgICA2ICsrKystLQogbGliL2Rm YS5oIHwgICAgMyArKysKIDIgZmlsZXMgY2hhbmdlZCwgNyBpbnNlcnRpb25zKCspLCAyIGRlbGV0 aW9ucygtKQoKZGlmZiAtLWdpdCBhL2xpYi9kZmEuYyBiL2xpYi9kZmEuYwppbmRleCAzMjlhMjA5 Li4xZTEyNWI0IDEwMDY0NAotLS0gYS9saWIvZGZhLmMKKysrIGIvbGliL2RmYS5jCkBAIC0xOTY5 LDcgKzE5NjksNyBAQCByZWdleHAgKHN0cnVjdCBkZmEgKmRmYSkKIC8qIE1haW4gZW50cnkgcG9p bnQgZm9yIHRoZSBwYXJzZXIuICBTIGlzIGEgc3RyaW5nIHRvIGJlIHBhcnNlZCwgbGVuIGlzIHRo ZQogICAgbGVuZ3RoIG9mIHRoZSBzdHJpbmcsIHNvIHMgY2FuIGluY2x1ZGUgTlVMIGNoYXJhY3Rl cnMuICBEIGlzIGEgcG9pbnRlciB0bwogICAgdGhlIHN0cnVjdCBkZmEgdG8gcGFyc2UgaW50by4g ICovCi1zdGF0aWMgdm9pZAordm9pZAogZGZhcGFyc2UgKGNoYXIgY29uc3QgKnMsIHNpemVfdCBs ZW4sIHN0cnVjdCBkZmEgKmQpCiB7CiAgIGQtPmxleC5wdHIgPSBzOwpAQCAtMzc0NSw3ICszNzQ1 LDkgQEAgZGZhc3NidWlsZCAoc3RydWN0IGRmYSAqZCkKIHZvaWQKIGRmYWNvbXAgKGNoYXIgY29u c3QgKnMsIHNpemVfdCBsZW4sIHN0cnVjdCBkZmEgKmQsIGJvb2wgc2VhcmNoZmxhZykKIHsKLSAg ZGZhcGFyc2UgKHMsIGxlbiwgZCk7CisgIGlmIChzICE9IE5VTEwpCisgICAgZGZhcGFyc2UgKHMs IGxlbiwgZCk7CisKICAgZGZhc3NidWlsZCAoZCk7CiAKICAgaWYgKGRmYV9zdXBwb3J0ZWQgKGQp KQpkaWZmIC0tZ2l0IGEvbGliL2RmYS5oIGIvbGliL2RmYS5oCmluZGV4IDYwNTEyZTIuLjIyMWY3 ZDEgMTAwNjQ0Ci0tLSBhL2xpYi9kZmEuaAorKysgYi9saWIvZGZhLmgKQEAgLTcxLDYgKzcxLDkg QEAgZXh0ZXJuIHN0cnVjdCBkZmFtdXN0ICpkZmFtdXN0IChzdHJ1Y3QgZGZhIGNvbnN0ICopOwog LyogRnJlZSB0aGUgc3RvcmFnZSBoZWxkIGJ5IHRoZSBjb21wb25lbnRzIG9mIGEgc3RydWN0IGRm YW11c3QuICovCiBleHRlcm4gdm9pZCBkZmFtdXN0ZnJlZSAoc3RydWN0IGRmYW11c3QgKik7CiAK Ky8qIFBhcnNlIHRoZSBnaXZlbiBzdHJpbmcgb2YgZ2l2ZW4gbGVuZ3RoIGludG8gdGhlIGdpdmVu IHN0cnVjdCBkZmEuICAqLworZXh0ZXJuIHZvaWQgZGZhcGFyc2UgKGNoYXIgY29uc3QgKiwgc2l6 ZV90LCBzdHJ1Y3QgZGZhICopOworCiAvKiBDb21waWxlIHRoZSBnaXZlbiBzdHJpbmcgb2YgdGhl IGdpdmVuIGxlbmd0aCBpbnRvIHRoZSBnaXZlbiBzdHJ1Y3QgZGZhLgogICAgRmluYWwgYXJndW1l bnQgaXMgYSBmbGFnIHNwZWNpZnlpbmcgd2hldGhlciB0byBidWlsZCBhIHNlYXJjaGluZyBvciBh bgogICAgZXhhY3QgbWF0Y2hlci4gKi8KLS0gCjEuNy4xCgo= --------_5C959DEC00000000E6FE_MULTIPART_MIXED_--