From: Budi <budikusasi@gmail.com>
To: Norihiro Tanaka <noritnk@kcn.ne.jp>
Cc: 34951@debbugs.gnu.org, bug-gnulib@gnu.org
Subject: Re: bug#34951: [PATCH] grep: a kwset matcher not work in a grep matcher
Date: Sat, 23 Mar 2019 09:58:37 +0700 [thread overview]
Message-ID: <CAH0GyZCWJbxQ3XD-gFvkFcB963XYSG2UT5TYJVK5_rJn+VcYNg@mail.gmail.com> (raw)
In-Reply-To: <20190323114902.E6F6.27F6AC2D@kcn.ne.jp>
How make grep walinh through FS by scanning breadth first instead of
the usual depth
On 3/23/19, Norihiro Tanaka <noritnk@kcn.ne.jp> wrote:
> On Sat, 23 Mar 2019 08:06:35 +0900
> Norihiro Tanaka <noritnk@kcn.ne.jp> 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.
>
next prev parent reply other threads:[~2019-03-23 4:09 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-03-22 23:06 [PATCH] grep: a kwset matcher not work in a grep matcher Norihiro Tanaka
2019-03-23 2:49 ` bug#34951: " Norihiro Tanaka
2019-03-23 2:58 ` Budi [this message]
2019-03-23 2:59 ` Budi
2019-03-23 12:39 ` Eric Blake
2019-03-29 10:58 ` arnold
2019-12-11 23:25 ` Paul Eggert
2019-12-12 7:23 ` arnold
2019-12-12 7:31 ` arnold
2019-12-12 7:47 ` arnold
2019-12-12 22:26 ` Paul Eggert
2019-12-13 8:09 ` arnold
2019-12-13 12:08 ` arnold
2019-12-13 17:53 ` Jim Meyering
2019-12-13 20:00 ` Paul Eggert
2019-12-14 2:35 ` intptr_t vs. uintptr_t Bruno Haible
2019-12-14 3:19 ` Paul Eggert
2019-12-14 9:14 ` Bruno Haible
2019-12-14 22:29 ` Paul Eggert
2019-12-15 0:35 ` Bruno Haible
2019-12-16 10:02 ` Paul Eggert
2019-12-15 8:14 ` bug#34951: [PATCH] grep: a kwset matcher not work in a grep matcher arnold
2019-12-16 9:56 ` Paul Eggert
2019-12-16 10:12 ` arnold
2019-12-20 3:18 ` Paul Eggert
2019-12-20 10:35 ` arnold
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://lists.gnu.org/mailman/listinfo/bug-gnulib
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAH0GyZCWJbxQ3XD-gFvkFcB963XYSG2UT5TYJVK5_rJn+VcYNg@mail.gmail.com \
--to=budikusasi@gmail.com \
--cc=34951@debbugs.gnu.org \
--cc=bug-gnulib@gnu.org \
--cc=noritnk@kcn.ne.jp \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).