[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[bug-gawk] [PATCH] Use superset with dfa in re.c.
From: |
Norihiro Tanaka |
Subject: |
[bug-gawk] [PATCH] Use superset with dfa in re.c. |
Date: |
Sun, 02 Nov 2014 19:00:22 +0900 |
Hi,
grep-2.19 or later may build a superset of a dfa, and use it. The
superset will be able to find a potential match faster than an original
dfa. As it is always built when it is useful, Gawk can also use it
easily.
I measured performance for matching with Gawk before and after apply a
patch.
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000
$ time -p env LC_ALL=en_US.utf8 ./gawk '/[a-c]k/ { print }' ../k
real 2.79
user 2.71
sys 0.07
$ time -p env LC_ALL=en_US.utf8 ./gawk '/[a-c]k/ { print }' ../k
real 1.66
user 1.59
sys 0.07
For further information, please see
http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16966.
Thanks,
Norihiro
0001-Use-superset-with-dfa-in-re.c.patch
Description: Text document
- [bug-gawk] [PATCH] Use superset with dfa in re.c.,
Norihiro Tanaka <=