いまさらgrepが10倍高速化したのはなぜか | はむかず！
の
1. マルチバイトロケールによっては、「大文字→小文字」または「小文字→大文字」の変換をすると文字のバイト数が変わってしまうことがある（！）
2. そのため、バッファを使った効率の良い検索が使えず、1行読み込んで変換して検索するという効率の悪い実装が行われていた
3. そこで発想を変えて、検索される文字列を同値な正規表現にあらかじめ変換すると速くなった。つまり「foo」という文字列を検索するときは「[fF][oO][oO]」という正規表現に変換してから検索する。
という結論に違和感。
1. については良いのだけど、
なぜ、バイト数が変わるケースがあると「効率の良い検索」ができないのか?
(「そのため、」というのはそういうことですよね)
そして、行ごとに処理することでなぜそんなに効率が落ちるのか?
(三つのなかで遅くなる要因に言及しているのはこれだけ)
最後に、なぜ正規表現に変換すると速くなるのか。
これはまあ2. で使えなくなった「効率の良い検索」が使えるようになったということなのだろうけど
それはなぜ?
(「正規表現に変換したから」というのは理由になっていない)
まず、一行ごと云々に関して
main.c
/* Invoke the matcher, EXECUTE, on buffer BUF of SIZE bytes. If there
is no match, return (size_t) -1. Otherwise, set *MATCH_SIZE to the
length of the match and return the offset of the start of the match. */
static size_t
do_execute (char const *buf, size_t size, size_t *match_size,
char const *start_ptr)
{
size_t result;
const char *line_next;
/* With the current implementation, using --ignore-case with a multi-byte
character set is very inefficient when applied to a large buffer
containing many matches. We can avoid much of the wasted effort
by matching line-by-line.
FIXME: this is just an ugly workaround, and it doesn't really
belong here. Also, PCRE is always using this same per-line
matching algorithm. Either we fix -i, or we should refactor
this code---for example, we could add another function pointer
to struct matcher to split the buffer passed to execute. It would
perform the memchr if line-by-line matching is necessary, or just
return buf + size otherwise. */
if (MB_CUR_MAX == 1 || !match_icase)
return execute (buf, size, match_size, start_ptr);
for (line_next = buf; line_next < buf + size; )
{
const char *line_buf = line_next;
const char *line_end = memchr (line_buf, eolbyte,
(buf + size) - line_buf);
if (line_end == NULL)
line_next = line_end = buf + size;
else
line_next = line_end + 1;
if (start_ptr && start_ptr >= line_end)
continue;
result = execute (line_buf, line_next - line_buf, match_size, start_ptr);
if (result != (size_t) -1)
return (line_buf - buf) + result;
}
return (size_t) -1;
}
MB_CUR_MAX が1でなく、また、大小文字無視の検索(match_icase が0以外)場合に
execute() の呼び出しが一行ごとになっているのが見て取れます。
中身はともかくとして、execute() の呼び出し回数の増加分だけ
オーバーヘッドも増えるだろうことが予想できます。
が、なぜこのような使い分けが必要なのかはわかりません。
do_execute() がどこで呼ばれているかというとここ。
名前からしてバッファに対してgrepするというところですか
/* Scan the specified portion of the buffer, matching lines (or
between matching lines if OUT_INVERT is true). Return a count of
lines printed. */
static intmax_t
grepbuf (char const *beg, char const *lim)
{
intmax_t nlines, n;
char const *p;
size_t match_offset;
size_t match_size;
nlines = 0;
p = beg;
while ((match_offset = do_execute (p, lim - p, &match_size,
NULL)) != (size_t) -1)
{
char const *b = p + match_offset;
char const *endp = b + match_size;
/* Avoid matching the empty line at the end of the buffer. */
if (b == lim)
break;
if (!out_invert)
{
prtext (b, endp, NULL);
nlines++;
outleft--;
if (!outleft || done_on_match)
{
if (exit_on_match)
exit (EXIT_SUCCESS);
after_last_match = bufoffset - (buflim - endp);
return nlines;
}
}
else if (p < b)
{
prtext (p, b, &n);
nlines += n;
outleft -= n;
if (!outleft)
return nlines;
}
p = endp;
}
if (out_invert && p < lim)
{
prtext (p, lim, &n);
nlines += n;
outleft -= n;
}
return nlines;
}
さらに呼び出し階層の上に行くとファイルに対する grep な関数に
なっていくので省略
次に目先を変えて
main() のオプション解析のあたり
int
main (int argc, char **argv)
{
case 'i':
case 'y': /* For old-timers . . . */
match_icase = 1;
break;
-i オプション指定時には
match_icase という変数に1をセットと。
そこからちょっと進むと
/* 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 regular expression, /foo/i, 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]. */
if (match_icase)
{
size_t new_keycc;
char *new_keys;
/* It is not possible with -F, not useful with -P (pcre) and there is no
point when there is no regexp. It also depends on which constructs
appear in the regexp. See trivial_case_ignore for those details. */
if (keycc
&& ! (matcher
&& (STREQ (matcher, "fgrep") || STREQ (matcher, "pcre")))
&& trivial_case_ignore (keycc, keys, &new_keycc, &new_keys))
{
match_icase = 0;
free (keys);
keys = new_keys;
keycc = new_keycc;
}
}
#if MBS_SUPPORT
if (MB_CUR_MAX > 1)
build_mbclen_cache ();
#endif
compile (keys, keycc);
free (keys);
match_icase が0以外のときに、
さらに keycc があって、matcher が fgrep でも pcre でもないときに
trivial_case_ignore を呼び出してその戻り値が0以外のときに
match_icase を 0 にしています。
つまり、大小文字の違いを無視するという指定を無効にしているわけですね。
ということは、名前からしても trivial_case_ignore がアヤシイ。
#define MBRTOWC(pwc, s, n, ps) \
(MB_CUR_MAX == 1 ? \
(*(pwc) = btowc (*(unsigned char *) (s)), 1) : \
mbrtowc ((pwc), (s), (n), (ps)))
#define WCRTOMB(s, wc, ps) \
(MB_CUR_MAX == 1 ? \
(*(s) = wctob ((wint_t) (wc)), 1) : \
wcrtomb ((s), (wc), (ps)))
/* If the newline-separated regular expressions, KEYS (with length, LEN
and no trailing NUL byte), are amenable to transformation into
otherwise equivalent case-ignoring ones, perform the transformation,
put the result into malloc'd memory, *NEW_KEYS with length *NEW_LEN,
and return true. Otherwise, return false. */
static bool
trivial_case_ignore (size_t len, char const *keys,
size_t *new_len, char **new_keys)
{
/* FIXME: consider removing the following restriction:
Reject if KEYS contain ASCII '\\' or '['. */
if (memchr (keys, '\\', len) || memchr (keys, '[', len))
return false;
/* Worst case is that each byte B of KEYS is ASCII alphabetic and each
other_case(B) character, C, occupies MB_CUR_MAX bytes, so each B
maps to [BC], which requires MB_CUR_MAX + 3 bytes. */
*new_keys = xnmalloc (MB_CUR_MAX + 3, len + 1);
char *p = *new_keys;
mbstate_t mb_state;
memset (&mb_state, 0, sizeof mb_state);
while (len)
{
wchar_t wc;
int n = MBRTOWC (&wc, keys, len, &mb_state);
/* For an invalid, incomplete or L'\0', skip this optimization. */
if (n <= 0)
{
skip_case_ignore_optimization:
free (*new_keys);
return false;
}
char const *orig = keys;
keys += n;
len -= n;
if (!iswalpha (wc))
{
memcpy (p, orig, n);
p += n;
}
else
{
*p++ = '[';
memcpy (p, orig, n);
p += n;
wchar_t wc2 = iswupper (wc) ? towlower (wc) : towupper (wc);
char buf[MB_CUR_MAX];
int n2 = WCRTOMB (buf, wc2, &mb_state);
if (n2 <= 0)
goto skip_case_ignore_optimization;
assert (n2 <= MB_CUR_MAX);
memcpy (p, buf, n2);
p += n2;
*p++ = ']';
}
}
*new_len = p - *new_keys;
return true;
}
ここで foobar → [Ff][Oo][Oo][Bb][Aa][Rr] への変換をやってました。
さて、では続いて正規表現マッチングのところを…
と思いましたが時間切れのようです。
あ、あとあれだ。今回見ているこれはそもそも
Savannah Git Hosting - grep.git/commitdiff
These days, nearly everyone uses a multibyte locale, and grep is often
used with the --ignore-case (-i) option, but that option imposes a very
high cost in order to handle some unusual cases in just a few multibyte
locales. This change gets most of the performance of using LC_ALL=C
without eliminating the ability to search for multibyte strings.
With the following example, I see an 11x speed-up with a 2.3GHz i7:
Generate a 10M-line file, with each line consisting of 40 'j's:
yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 > k
Time searching it for the simple/noexistent string "foobar",
first with this patch (best-of-5 trials):
LC_ALL=en_US.UTF-8 env time src/grep -i foobar k
1.10 real 1.03 user 0.07 sys
Back out that commit (temporarily), recompile, and rerun the experiment:
git log -1 -p|patch -R -p1; make
LC_ALL=en_US.UTF-8 env time src/grep -i foobar k
12.50 real 12.41 user 0.08 sys
元がとんでもなく遅いものだったというのをお忘れなく。
この先続けるかどうかは気分次第。
![OVA 新 破裏拳ポリマー [DVD]](http://ecx.images-amazon.com/images/I/61E0FM3TJ1L._SL160_.jpg)
