BSD では ignore-case な検索のときに今回話題になったようなやり方を昔からしていた
とかいう話を伝え聞きまして。
しかし、GNU regex (昔のね。0.12とか) でも translate テーブル使ってごにょごにょ
してたよなあ…と思いつつ昔の GNU grep どうだったか確かめようとしたら
2.0からしかなかった○|￣|＿
Index of /pub/GNU/grep
gawkは 1.01 ってのがあるんですけどねえ(日付はともかく)
Index of /pub/GNU/gawk
さて。
#16232 - [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales - GNU bug report logs
のやり取りを追いかけてみよう。
問題の十倍高速化云々の話題のやり取りがあるところ。
メッセージの番号が所々抜けてるのはなんなんだろう(先頭が#5だし)
#16232 - [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales - GNU bug report logs
GNU bug report logs - #16232
[PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Reported by: Jim Meyering
Date: Mon, 23 Dec 2013 22:40:02 UTC
To reply to this bug, email your comments to 16232 AT debbugs.gnu.org.
Toggle the display of automated, internal messages from the tracker.
View this report as an mbox folder, status mbox, maintainer mbox
Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):
From: Jim Meyering
To: bug-grep <at> gnu.org
Subject: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Mon, 23 Dec 2013 14:39:14 -0800
FYI, here is a quick and clean/safe performance improvement for grep -i.
I expect to push this commit right after the upcoming bug-fix release.
Currently, this optimization is enabled when the search string is
ASCII and contains neither of '\' (backslash) nor '['. I expect to
eliminate the latter two constraints in a follow-on commit including
tests to exercise all of the corner cases.
Happy holidays,
Jim
どうやらここが始まりのようですね。
以下適当に、引用部分などを削ります。
Message #8 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Eric Blake
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Mon, 23 Dec 2013 15:52:26 -0700
On 12/23/2013 03:39 PM, Jim Meyering wrote:
> +
> + /* Worst case is that every byte of keys will be alpha,
> + so every byte B will map to the sequence of 4 bytes [Bb]. */
Umm, is this always true? Consider the UTF-8 Turkish locale, where
single-byte i has a multi-byte uppercase (and conversely the single-byte
I has a multi-byte lowercase) - that is, 'i' and 'I' are not case pairs.
> + else
> + {
> + *p++ = '[';
> + *p++ = *keys;
> + *p++ = islower (*keys) ? toupper (*keys) : tolower (*keys);
This performs the ASCII-only toupper/tolower, rather than the proper
locale-sensitive case conversion, which probably makes this patch
misbehave for LC_ALL=tr_TR.UTF-8.
>
> + /* As currently implemented, case-insensitive matching is expensive in
> + multi-byte locales because of a few outlier locales in which some
> + characters change size when converted to upper or lower case. To
> + accommodate those, we revert to searching the input one line at a
> + time, rather than using the much more efficient buffer search.
> + However, if we have a plain ascii search string, /foo/, we can
> + convert it to an equivalent case-insensitive /[fF][oO][oO]/, and thus
> + avoid the expensive read-and-process-a-line-at-a-time requirement.
> + Optimize-away the "-i" option, when possible, converting each
> + candidate alpha, C, in the regexp to [Cc]. */
In other words, this comment describes the very flaw of the outlier
tr_TR locale that you are now violating with your optimization.
Without your patch, this is correct behavior:
$ echo i | LC_ALL=tr_TR.UTF-8 grep -i I
$ echo i | LC_ALL=tr_TR.UTF-8 grep -i i
i
ここで UTF-8 Turkish locale の話が出たと。
Message #11 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Jim Meyering
To: Eric Blake
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Mon, 23 Dec 2013 15:12:26 -0800
On Mon, Dec 23, 2013 at 2:52 PM, Eric Blake <eblake <at> redhat.com> wrote:
>> + /* Worst case is that every byte of keys will be alpha,
>> + so every byte B will map to the sequence of 4 bytes [Bb]. */
>
> Umm, is this always true? Consider the UTF-8 Turkish locale, where
Hi Eric,
Thanks for the review.
Did you miss the "isascii" check in the new trivial_case_convert function?
If you can describe circumstances in which the new patch malfunctions,
please do,
but everything you wrote seems to rely on a false assumption.
E.g., your turkish-I example works fine with my patch.
Message #14 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Eric Blake
To: Jim Meyering <jim <at> meyering.net>
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Mon, 23 Dec 2013 16:30:19 -0700
On 12/23/2013 04:12 PM, Jim Meyering wrote:
> Did you miss the "isascii" check in the new trivial_case_convert function?
No. But even with that check in place:
> If you can describe circumstances in which the new patch malfunctions,
> please do,
> but everything you wrote seems to rely on a false assumption.
No, it's a quite real complaint - your patch is broken for tr_TR.
> E.g., your turkish-I example works fine with my patch.
isascii('i') is true, but converting 'i' to '[iI]' is incorrect in the
tr_TR locale. Rather, the conversion must be to '[iİ]'; similarly, 'I'
would be translated to '[Iı]'. Neither of those conversions fit in 4
bytes (since dotted-capital-I and dotless-lower-i are both multi-byte
characters).
Need help easily finding those characters on a non-Turkish keyboard? I
used:
$ echo iI | LC_ALL=tr_TR.UTF-8 sed 's/\(.\)\(.\)/\U\1\L\2/'
At any rate, prior to your patch, lower dotless i in the buffer gives an
insensitive match to upper dotless I in the pattern:
$ echo ı | LC_ALL=tr_TR.UTF-8 grep -i I || echo no match
ı
After your patch:
$ echo ı | LC_ALL=tr_TR.UTF-8 src/grep -i I || echo no match
no match
Oops, you failed to match lower dotless i insensitively against upper
dotless I, because upper dotless I is ascii, but you incorrectly
converted it into the wrong pattern.
んーと、#5で投稿したパッチに対して、それじゃ UTF-8 Turkish locale でおかしくなるよ
という指摘をしてるわけですよね。でも基本的なロジックは2.17で話題になったアレと同じなわけで、
大文字化/小文字化で長さが変わる云々はやっぱり高速化とは関係ないって話なんじゃあ…
Message #17 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Jim Meyering
To: Eric Blake
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Mon, 23 Dec 2013 15:54:27 -0800
Thanks for dotting those 'i's. While there is no risk of buffer
overrun, there would definitely be a problem with the tr_TR locale.
I will resolve it by removing the isascii check and performing
multibyte case conversion to form each [cC] pair. Of course,
that will mean removing the "4 * byte-length-of-search-string"
buffer size limitation.
I will also add tests based on your examples.
ここで Jim さん multibyte case conversion を入れました。と。
こっからざっくりカット。
多重の引用部がたくさんあるのでそっち生かした方が楽だ :)
Message #41 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Jim Meyering <jim <at> meyering.net>
To: Pádraig Brady <P <at> draigbrady.com>
Cc: 16232 <16232 <at> debbugs.gnu.org>
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Sat, 11 Jan 2014 09:56:53 -0800
On Sat, Jan 11, 2014 at 6:15 AM, Pádraig Brady <P <at> draigbrady.com> wrote:
> On 01/11/2014 11:33 AM, Pádraig Brady wrote:
>> On 01/11/2014 05:40 AM, Jim Meyering wrote:
>>> On Fri, Jan 10, 2014 at 8:52 PM, Jim Meyering <jim <at> meyering.net> wrote:
>>>>> I wonder might this faster path be restricted to a safer but very common input subset of:
>>>>>
>>>>> (MB_CUR_MAX == 1 || (in_utf8 && *c < 0x80))
>>>>
>>>> That sounds like a good approach.
>>>> Now I need another test case, to demonstrate that the current code can
>>>> cause trouble.
>>>
>>> Hmm... after thinking about this for a while and actually trying to
>>> break the current code (did not find a way to demonstrate a regression),
>>> I have concluded that the current approach is no worse than the prior
>>> one of matching a case-mapped regexp vs. each case-mapped input line.
>>>
>>> That's not to say that it's perfect, of course.
>>> The "LATIN SMALL LETTER J WITH CARON, COMBINING DOT BELOW" example
>>> from gnulib's test-ulc-casecmp.c is a great example: this matches:
>>>
>>> printf '\x6A\xCC\x8C\xCC\xA3\n'|src/grep -i "$(printf
>>> '\x6A\xCC\x8C\xCC\xA3')"
>>>
>>> but this does not, yet probably should:
>>>
>>> printf '\xC7\xB0\xCC\xA3\n'|src/grep -i "$(printf '\x6A\xCC\x8C\xCC\xA3')"
>>>
>>> Can you see a way to demonstrate a regression?
>>
>> Oh right, it doesn't handle these cases already.
>> Fair enough I don't see a regression then.
>
> This is also a good summary of stuff to consider with case:
> http://www.unicode.org/faq/casemap_charprop.html
>
> So picking another case situation from there:
> "in the Greek script, capital sigma (U+03A3) is the uppercase form of both
> the regular (U+03C2) and final (U+03C3) lowercase sigma."
>
> One can see that sed handles this:
> $ printf '\u03C2\u03C3\n' | sed 's/.*/&\U&/'
> ςσΣΣ
> $ printf '\u03A3\n' | sed 's/.*/&\L&/'
> Σσ
>
> Though I was surprised the grep (2.14) didn't match any combo of these
> $ printf '\u03C2\u03C3\n' | grep -Fi "$(printf \u03A3)"
> $ printf '\u03A3\n' | grep -Fi "$(printf \u03C2)"
> $ printf '\u03A3\n' | grep -Fi "$(printf \u03C3)"
>
> Not a regression of course.
Thank you for the reference and the fine examples.
I'll add the latter as a known-failing test.
Message #47 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Pádraig Brady
To: Jim Meyering
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Sun, 12 Jan 2014 12:56:23 +0000
On 01/12/2014 04:36 AM, Jim Meyering wrote:
> On Sat, Jan 11, 2014 at 6:15 AM, Pádraig Brady <P <at> draigbrady.com> wrote:
>> On 01/11/2014 11:33 AM, Pádraig Brady wrote:
> ...
>> This is also a good summary of stuff to consider with case:
>> http://www.unicode.org/faq/casemap_charprop.html
>>
>> So picking another case situation from there:
>> "in the Greek script, capital sigma (U+03A3) is the uppercase form of both
>> the regular (U+03C2) and final (U+03C3) lowercase sigma."
>>
>> One can see that sed handles this:
>> $ printf '\u03C2\u03C3\n' | sed 's/.*/&\U&/'
>> ςσΣΣ
>> $ printf '\u03A3\n' | sed 's/.*/&\L&/'
>> Σσ
>>
>> Though I was surprised the grep (2.14) didn't match any combo of these
>> $ printf '\u03C2\u03C3\n' | grep -Fi "$(printf \u03A3)"
>> $ printf '\u03A3\n' | grep -Fi "$(printf \u03C2)"
>> $ printf '\u03A3\n' | grep -Fi "$(printf \u03C3)"
>
> Actually, if you quote the argument to the latter printf, two of those
> do match, both with -F and without:
>
> $ printf '\u03C2\u03C3\n' | grep -Fi "$(printf '\u03A3')"
> ςσ
> $ printf '\u03A3\n' | grep -Fi "$(printf '\u03C2')"
> $ printf '\u03A3\n' | grep -Fi "$(printf '\u03C3')"
> Σ
Oops right.
So that's still no regression with the new scheme
since grep is 1:1 here for Σ and σ.
thanks,
Pádraig.
ここでタナカさん登場。
Message #50 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Norihiro Tanaka
To: Padraig Brady
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Wed, 19 Feb 2014 23:22:08 +0900
Hi,
Slow down may be caused by the patch, because MBCSET is processed by not
DFA engine but regexp engine.
I tested performance on grep-2.17 and the version which the patch is reverted.
Latter is 100x faster.
yes $(printf '%078dm' 0)|head -10000 > in
(略)
Message #56 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Jim Meyering
To: Norihiro Tanaka
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Wed, 19 Feb 2014 11:17:16 -0800
On Wed, Feb 19, 2014 at 6:22 AM, Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
> for i in $(seq 10); do env LC_ALL=ja_JP.eucJP time src/grep -i n in; done
Wow. You're right. With the attached patch, I see a speedup of more
than 130x in this case: (fyi, the "time" output is slightly different,
because I have installed GNU time)
grep-2.17$ for i in $(seq 5); do env LC_ALL=ja_JP.eucJP time grep -i n in; done
2.78 real 2.78 user 0.00 sys
2.73 real 2.73 user 0.00 sys
2.75 real 2.75 user 0.00 sys
2.73 real 2.73 user 0.00 sys
2.74 real 2.74 user 0.00 sys
2.17+patch$ for i in $(seq 5); do env LC_ALL=ja_JP.eucJP time src/grep -i n in; done
0.02 real 0.02 user 0.00 sys
0.02 real 0.02 user 0.00 sys
0.02 real 0.02 user 0.00 sys
0.02 real 0.02 user 0.00 sys
0.02 real 0.02 user 0.00 sys
I haven't investigated they "why" yet, but expect that I will make
grep-2.18 with just this one performance-improving patch.
Thank you, Norihiro,
Jim
200倍時間がかかるようになってたというのはここから出た数字ですね。
んで、2.18すぐ出すよ。と。
そして問題の核心へ
Message #68 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Jim Meyering
To: Norihiro Tanaka
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Wed, 19 Feb 2014 19:44:59 -0800
Hmm... it's not as clear-cut as I first thought.
(I built 2.17+ the above patch and put it in a directory named grep-2.18)
The following times 2.16, 2.17 and 2.17+patch two ways:
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 > k
$ for i in 16 17 18; do echo $i; env LC_ALL=en_US.UTF-8 time /p/p/grep-2.$i/bin/grep -i foobar k; done
16
15.96 real 14.57 user 0.12 sys
17
1.13 real 1.07 user 0.06 sys
18
1.96 real 1.89 user 0.06 sys
The above search takes more than 70% longer with the proposed patch.
Contrast that with performance in the non-UTF8 ja_JP.eucJP locale:
$ yes $(printf '%078dm' 0)|head -10000 > in
$ for i in 16 17 18; do echo $i; env LC_ALL=ja_JP.eucJP time /p/p/grep-2.$i/bin/grep -i n in; done
16
0.03 real 0.02 user 0.00 sys
17
2.98 real 2.96 user 0.00 sys
18
0.02 real 0.02 user 0.00 sys
Using the jjj+foobar example, but with only 100k lines, we see there
was a 200x performance regression going from grep-2.16 to 2.17:
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -100000 > k
$ for i in 16 17 18; do echo $i; env LC_ALL=ja_JP.eucJP time /p/p/grep-2.$i/bin/grep -i foobar k; done
16
0.15 real 0.14 user 0.00 sys
17
27.74 real 27.72 user 0.01 sys
18
0.11 real 0.11 user 0.00 sys
Obviously, I want to retain all of 2.17's performance gain in UTF-8 locales,
while avoiding the 200x penalty in multi-byte non-UTF8 locales like ja_JP.eucJP.
So I have prepared a better patch.
With the two attached commits (on top of 2.17), I get these timings,
i.e., the same 200x improvement with ja_JP.eucJP, and no regression with en_US.UTF8)
$ for i in 16 17 18; do printf "$i: "; env LC_ALL=ja_JP.eucJP time /p/p/grep-2.$i/bin/grep -i foobar k; done
16: 0.14 real 0.14 user 0.00 sys
17: 27.97 real 27.95 user 0.01 sys
18: 0.12 real 0.12 user 0.00 sys
$ for i in 16 17 18; do printf "$i: "; env LC_ALL=en_US.UTF-8 time /p/p/grep-2.$i/bin/grep -i foobar k; done
16: 0.13 real 0.12 user 0.00 sys
17: 0.01 real 0.01 user 0.00 sys
18: 0.01 real 0.01 user 0.00 sys
Message #71 received at 16232 <at> debbugs.gnu.org (full text, mbox):
From: Norihiro TANAKA
To: Jim Meyering
Cc: 16232 <16232 <at> debbugs.gnu.org>, Padraig Brady <P <at> draigbrady.com>
Subject: Re: bug#16232: [PATCH] grep: make --ignore-case (-i) faster (sometimes 10x) in multibyte locales
Date: Thu, 20 Feb 2014 22:39:18 +0900
Hi Jim,
Your patch is probably right.
However, I think that the true cause for 100x slow is that DFA engine is
slower than regex engine for case-insensitive matching on a non-UTF-8
locle.
On a multibyte locale, for case-insensitive "a" grep prefers DFA engine,
but for character class "[Aa]" prefers regex engine.
Norihiro
このあとも幾つかやり取りがありますが、
速くなったり一部の環境でやたらと遅くなったりはこう言う話
(On a multibyte locale, for case-insensitive "a" grep prefers DFA engine,
but for character class "[Aa]" prefers regex engine.
)
であったと。
DFA engine でない方のときに遅くなるというのは
過去の経験からしてまあ納得なんだけど、きっちり追いかけてはいないので
分からない部分もまだ残っていたり。
さて、grep の話はどこまで追いかけたものやら…w
でもまああの「間違い」は訂正されることなく定説化するんだろうねえ。
この本、見かけたんで買って読んだ(サクサク読めた)けど、
解析機関と階差機関ごっちゃになっているような。
まあ本文とは関係ない部分なんだけど
(そしてそういうところが妙に気になってしまうワタシ)
![アポロ13 [Blu-ray]](http://ecx.images-amazon.com/images/I/513Y%2BT-l5PL._SL160_.jpg)
