プロファイル取りながらボトルネックを確認したいんだけど
(場所よりはその程度を)、環境作るのが面倒(ry
それはさておき。
multibyte の検索のときに速度低下する原因であろう関数二つ。
/* searchutils.c - helper subroutines for grep's matchers.
Copyright 1992, 1998, 2000, 2007, 2009-2014 Free Software Foundation, Inc.
(略)
char *
mbtolower (const char *beg, size_t *n, mb_len_map_t **len_map_p)
{
static char *out;
static mb_len_map_t *len_map;
static size_t outalloc;
size_t outlen, mb_cur_max;
mbstate_t is, os;
const char *end;
char *p;
mb_len_map_t *m;
bool lengths_differ = false;
if (*n > outalloc || outalloc == 0)
{
outalloc = MAX(1, *n);
out = xrealloc (out, outalloc);
len_map = xrealloc (len_map, outalloc);
}
/* appease clang-2.6 */
assert (out);
assert (len_map);
if (*n == 0)
return out;
memset (&is, 0, sizeof (is));
memset (&os, 0, sizeof (os));
end = beg + *n;
mb_cur_max = MB_CUR_MAX;
p = out;
m = len_map;
outlen = 0;
while (beg < end)
{
wchar_t wc;
size_t mbclen = mbrtowc (&wc, beg, end - beg, &is);
#ifdef __CYGWIN__
/* Handle a UTF-8 sequence for a character beyond the base plane.
Cygwin's wchar_t is UTF-16, as in the underlying OS. This
results in surrogate pairs which need some extra attention. */
略()
#endif
if (outlen + mb_cur_max >= outalloc)
{
size_t dm = m - len_map;
out = x2nrealloc (out, &outalloc, 1);
len_map = xrealloc (len_map, outalloc);
p = out + outlen;
m = len_map + dm;
}
if (mbclen == (size_t) -1 || mbclen == (size_t) -2 || mbclen == 0)
{
/* An invalid sequence, or a truncated multi-octet character.
We treat it as a single-octet character. */
*m++ = 0;
*p++ = *beg++;
outlen++;
memset (&is, 0, sizeof (is));
memset (&os, 0, sizeof (os));
}
else
{
size_t ombclen;
beg += mbclen;
#ifdef __CYGWIN__
/* Handle Unicode characters beyond the base plane. */
(略)
#endif
ombclen = wcrtomb (p, towlower ((wint_t) wc), &os);
*m = mbclen - ombclen;
memset (m + 1, 0, ombclen - 1);
m += ombclen;
p += ombclen;
outlen += ombclen;
lengths_differ |= (mbclen != ombclen);
}
}
*len_map_p = lengths_differ ? len_map : NULL;
*n = p - out;
*p = 0;
return out;
}
cygwin 固有のところはサロゲートペアをごにょごにょしているので
大まかなロジックを見るにはなくても構わないだろうということで削ってます。
この関数は、mutibyte locale かつ大小文字を無視する設定のときに呼ばれ、
検索対象の内容を「小文字化」したものを返します。
ここでも wide char 変換→小文字変換→narrow char 変換ということをひたすらやるので
時間を食うのは明らかですね。
そして、小文字化したものを収める領域を確保しているのですが、
ignore case な検索を指定したときに
「一行ごとの検索」を行うようになっているのはたぶんここの処理の影響でしょうね。
そしてもう一つ。
こっちはcase sensitive なときにも通ると思うんで、
影響の出方が今ひとつ把握できないのだけど
bool
is_mb_middle (const char **good, const char *buf, const char *end,
size_t match_len)
{
const char *p = *good;
const char *prev = p;
mbstate_t cur_state;
/* TODO: can be optimized for UTF-8. */
memset(&cur_state, 0, sizeof(mbstate_t));
while (p < buf)
{
size_t mbclen = mbrlen(p, end - p, &cur_state);
/* Store the beginning of the previous complete multibyte character. */
if (mbclen != (size_t) -2)
prev = p;
if (mbclen == (size_t) -1 || mbclen == (size_t) -2 || mbclen == 0)
{
/* An invalid sequence, or a truncated multibyte character.
We treat it as a single byte character. */
mbclen = 1;
memset(&cur_state, 0, sizeof cur_state);
}
p += mbclen;
}
*good = prev;
if (p > buf)
return true;
/* P == BUF here. */
return 0 < match_len && match_len < mbrlen (p, end - p, &cur_state);
}
#endif /* MBS_SUPPORT */
この関数では、マッチするものがみつかったときにそれが文字の切れ目を跨いだものでないかチェックしています。
ここだけ見るとバッファの先頭からチェックするようにも読めるんですが、
たぶんこれを呼び出すところで改行を印にして、それより前には行かないようにしているぽいです。
コメント(どこにあったのか忘れたw)には、
multibyte locale で、マッチするものがたくさん見つかるようなケースでは
いちいち先頭から切れ目チェックをするので遅くなるから
line by line で処理するよとかあったような。
あ、あとUTF-8だと分かっている場合にはこのチェックがとても簡単にできるのは
説明するまでもないですね。
2.17 あたりでタナカさんが手を入れた部分にそういうコードがあります。
grep -Pなら速度低下あまりなし - jarp,
PCRE は utf-8 以外の multibyte encoding には対応してなかったよなあと
思い出しつつちょっと眺めてみる
/* pcresearch.c - searching subroutines using PCRE for grep.
Copyright 2000, 2007, 2009-2014 Free Software Foundation, Inc.
(略)
void
Pcompile (char const *pattern, size_t size)
{
#if !HAVE_LIBPCRE
error (EXIT_TROUBLE, 0, "%s",
_("support for the -P option is not compiled into "
"this --disable-perl-regexp binary"));
#else
int e;
char const *ep;
char *re = xnmalloc (4, size + 7);
int flags = PCRE_MULTILINE | (match_icase ? PCRE_CASELESS : 0);
char const *patlim = pattern + size;
char *n = re;
char const *p;
char const *pnul;
# if defined HAVE_LANGINFO_CODESET
if (STREQ (nl_langinfo (CODESET), "UTF-8"))
{
/* Enable PCRE's UTF-8 matching. Note also the use of
PCRE_NO_UTF8_CHECK when calling pcre_extra, below. */
flags |= PCRE_UTF8;
}
# endif
/* FIXME: Remove these restrictions. */
if (memchr (pattern, '\n', size))
error (EXIT_TROUBLE, 0, _("the -P option only supports a single pattern"));
*n = '\0';
if (match_lines)
strcpy (n, "^(");
if (match_words)
strcpy (n, "\\b(");
n += strlen (n);
/* The PCRE interface doesn't allow NUL bytes in the pattern, so
replace each NUL byte in the pattern with the four characters
"\000", removing a preceding backslash if there are an odd
number of backslashes before the NUL.
FIXME: This method does not work with some multibyte character
encodings, notably Shift-JIS, where a multibyte character can end
in a backslash byte. */
for (p = pattern; (pnul = memchr (p, '\0', patlim - p)); p = pnul + 1)
{
memcpy (n, p, pnul - p);
n += pnul - p;
for (p = pnul; pattern < p && p[-1] == '\\'; p--)
continue;
n -= (pnul - p) & 1;
strcpy (n, "\\000");
n += 4;
}
memcpy (n, p, patlim - p);
n += patlim - p;
*n = '\0';
if (match_words)
strcpy (n, ")\\b");
if (match_lines)
strcpy (n, ")$");
cre = pcre_compile (re, flags, &ep, &e, pcre_maketables ());
if (!cre)
error (EXIT_TROUBLE, 0, "%s", ep);
(略)
うーん特にコード変換の類はしてないような。FIXME のところに怪しげなコメントもあるし。