GNU bug report logs - #17070
[PATCH] grep: optimization of DFA by reuse of multi-byte buffers in non-UTF8 locales

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 17070 in the body.
You can then email your comments to 17070 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: submit <at> debbugs.gnu.org
Subject: [PATCH] grep: optimization of DFA by reuse of multi-byte buffers in
 non-UTF8 locales
Date: Sun, 23 Mar 2014 22:19:36 +0900

[Message part 1 (text/plain, inline)]

Package: grep
Tags: patch

dfaexec() allocates and deallocates many buffers in non-UTF8 locales, but
it's very inefficient.

If put them on struct dfa and reuse them, when use not regex but DFA for
ANYCHAR, it will speed up about 20-30% in non-UTF8 locales.

Norihiro

[patch.txt (text/plain, attachment)]

Message #8 received at 17070 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 17070 <at> debbugs.gnu.org
Subject: Re: bug#17070: [PATCH] grep: optimization of DFA by reuse of
 multi-byte buffers in non-UTF8 locales
Date: Sat, 29 Mar 2014 02:34:59 +0900

[Message part 1 (text/plain, inline)]

I rebased this patch, and add a bug fix to it.

If `elems' of `follows' is re-allocated in transit_state(), It may cause
a segfault.  So, I changed so that don't copy d->mb_follows to `follows'
variable.

[patch.txt (text/plain, attachment)]

Message #11 received at 17070 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: 17070 <at> debbugs.gnu.org
Subject: bug#17070: [PATCH] grep: optimization of DFA by reuse of multi-byte
 buffers in non-UTF8 locales
Date: Sun, 30 Mar 2014 07:11:22 +0900

[Message part 1 (text/plain, inline)]

I added further improvement to previous patch.

If dfaexec() runs in non-UTF8 locales, length and wide character
representation are checked for all characters of a line in a input
string.  However, if matched early in the line, results for remaining
characters are wasted.

The new patch doesn't reuse both `mblen_buf' and `inputwcs' but stops
using them, and checks multibyte characters on demand.  It enables to
accomplish to speed-up for matched early and reduce required memories.

Norihiro

[patch.txt (text/plain, attachment)]

Message #14 received at 17070 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: 17070 <at> debbugs.gnu.org
Subject: bug#17070: [PATCH] grep: optimization of DFA by reuse of multi-byte
 buffers in non-UTF8 locales
Date: Sun, 30 Mar 2014 20:14:21 +0900

[Message part 1 (text/plain, inline)]

I added further improvement to previous patch.

If dfaexec() runs in non-UTF8 locales, length and wide character
representation are checked for all characters of a line in a input
string.  However, if matched early in the line, results for remaining
characters are wasted.

The new patch doesn't reuse both `mblen_buf' and `inputwcs' but stops
using them, and checks multibyte characters on demand.  It enables to
accomplish to speed-up for matched early and reduce required memories.

Norihiro

[patch.txt (text/plain, attachment)]

Message #17 received at 17070 <at> debbugs.gnu.org (full text, mbox):

From: Paolo Bonzini <bonzini <at> gnu.org>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, 17070 <at> debbugs.gnu.org
Subject: Re: bug#17070: [PATCH] grep: optimization of DFA by reuse of
 multi-byte buffers in non-UTF8 locales
Date: Tue, 01 Apr 2014 10:53:10 +0200

Applying this patch too.

Paolo

Message #22 received at 17070-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: Paolo Bonzini <bonzini <at> gnu.org>, 17070-done <at> debbugs.gnu.org,
 17156 <at> debbugs.gnu.org
Subject: Re: bug#17070: [PATCH] grep: optimization of DFA by reuse of
 multi-byte buffers in non-UTF8 locales
Date: Sat, 05 Apr 2014 22:12:58 -0700

[Message part 1 (text/plain, inline)]

Norihiro Tanaka wrote:
> I rebased this patch, and add a bug fix to it.

Thanks.  Paolo wrote it up in <http://bugs.gnu.org/17156#11>, and I just 
now tweaked its ChangeLog and merged the code and installed it (patch 
attached).  I followed up with minor cleanups (2nd patch attached).

[0001-grep-reuse-multibyte-DFA-buffers-in-non-UTF8-locales.patch (text/plain, attachment)]

[0002-grep-minor-improvements-to-previous-patch.patch (text/plain, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.