さとうふみやす @ OSSTech です。

正規表現に「.*?」(「.+?」でも同じ)が含まれており、かつ文字列に
マッチしない場合に、異様に遅い(ことがある?)のですが、何がおかしい
のでしょうか。

以下は Debian GNU/Linux unstable (amd64) (+ 一部 Ubuntu のパッケージ)
での結果ですが、Solaris 10 (SPARC) の Ruby 1.8.6.383 でも遅いです。

$ /usr/bin/time ruby1.8 -v -r profile -e 't="<X\n><Y\n>"*9999; p t.match(/<X
(?:\s[^>]*)?>.*?<\/Y>/m);'
ruby 1.8.7 (2010-08-16 patchlevel 302) [x86_64-linux]
nil
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
100.00    21.68     21.68        1 21680.00 21680.00  Regexp#match
  0.00    21.68      0.00        2     0.00     0.00  IO#write
  0.00    21.68      0.00        1     0.00     0.00  Kernel.p
  0.00    21.68      0.00        1     0.00     0.00  NilClass#inspect
  0.00    21.68      0.00        1     0.00 21680.00  String#match
  0.00    21.68      0.00        1     0.00     0.00  String#*
  0.00    21.68      0.00        1     0.00 21680.00  #toplevel
21.68user 0.03system 0:21.75elapsed 99%CPU (0avgtext+0avgdata 10160maxresident)k
0inputs+0outputs (0major+722minor)pagefaults 0swaps

$ /usr/bin/time ruby1.9.1 -v -r profile -e 't="<X\n><Y\n>"*9999; p t.match(/<X(?:\s[^>]*)?>.*?<\/Y>/m);'
ruby 1.9.2dev (2010-07-30) [x86_64-linux]
nil
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
100.00    13.64     13.64        1 13640.00 13640.00  Regexp#match
  0.00    13.64      0.00        1     0.00 13640.00  String#match
  0.00    13.64      0.00        1     0.00     0.00  String#*
  0.00    13.64      0.00        1     0.00     0.00  NilClass#inspect
  0.00    13.64      0.00        1     0.00     0.00  Kernel.p
  0.00    13.64      0.00        1     0.00 13640.00  #toplevel
13.65user 0.00system 0:13.64elapsed 100%CPU (0avgtext+0avgdata 15056maxresident)k
0inputs+0outputs (0major+1019minor)pagefaults 0swaps

$ /usr/bin/time perl -e 'print "$]\n"; $t="<X\n><Y\n>"x9999; print $t=~/<X(?:\s[^>]*)?>.+?<\/Y>/ms;'
5.010001
0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 7792maxresident)k
0inputs+0outputs (0major+546minor)pagefaults 0swaps

$ /usr/bin/time python -Vc 'import re; t="<X\n><Y\n>"*9999; print re.match(r"<X(?:\s[^>]*)?>.+?<\/Y>", t, re.M);'
Python 2.6.6rc1+
0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 5984maxresident)k
0inputs+0outputs (0major+440minor)pagefaults 0swaps

元々の正規表現は /<X(?:\s.*?)?>.*?<\/Y>/m だったのですが、
これだと遅すぎて何秒かかるかわかりません。

-- 
-- Name: SATOH Fumiyasu (fumiyas @ osstech co jp)
-- Business Home: http://www.OSSTech.co.jp/
-- Personal Home: http://www.SFO.jp/blog/