From: "knu (Akinori MUSHA)" Date: 2012-11-13T14:58:45+09:00 Subject: [ruby-dev:46506] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化 Issue #6311 has been updated by knu (Akinori MUSHA). File use_memchr.diff added もしこういう特定のケースの高速化が必要とのことなら、memmem()を使わない版でも Index: re.c =================================================================== --- re.c (revision 37635) +++ re.c (working copy) @@ -126,6 +126,11 @@ rb_memsearch_ss(const unsigned char *xs, if (m > SIZEOF_VALUE) rb_bug("!!too long pattern string!!"); + if (y = memchr(y, *x, n - m + 1)) + n -= y - ys; + else + return -1; + /* Prepare hash value */ for (hx = *x++, hy = *y++; x < xe; ++x, ++y) { hx <<= CHAR_BIT; のようなコードを入れればよさそうですが、どうでしょうか。 ちなみに、このケースに限って言えば、ハッシュを使わない /* FreeBSD's implementation of memmem() */ for (cur = (char *)cl; cur <= last; cur++) if (cur[0] == cs[0] && memcmp(cur, cs, s_len) == 0) return cur; のような素朴なバイト比較ループの方が現状のハッシュ値比較より速いようです。 現状のコードはどのような性能特性を期待しているのでしょうね。 ---------------------------------------- Feature #6311: memmem()によるrb_memsearch()の高速化 https://bugs.ruby-lang.org/issues/6311#change-32837 Author: Glass_saga (Masaki Matsushita) Status: Closed Priority: Normal Assignee: nobu (Nobuyoshi Nakada) Category: core Target version: [Feature #6129][ruby-dev:45344]と類似していますが、memmem()によるre.cのrb_memsearch()の高速化を試みました。 次のベンチマークを実行したところ以下の結果となり、有意な性能向上がみられました。 require 'benchmark' str = "hoge" * 10000 + "fugafuga" Benchmark.bm do |x| x.report do 1000.times { str.index("fugafuga") } end end trunk(r35363): user system total real 0.070000 0.000000 0.070000 ( 0.072126) user system total real 0.070000 0.010000 0.080000 ( 0.081420) user system total real 0.080000 0.000000 0.080000 ( 0.091658) proposal: user system total real 0.000000 0.000000 0.000000 ( 0.004237) user system total real 0.000000 0.000000 0.000000 ( 0.003737) user system total real 0.010000 0.000000 0.010000 ( 0.004696) patchを添付します。 -- http://bugs.ruby-lang.org/