Feature #6311

memmem()によるrb_memsearch()の高速化

Added by Masaki Matsushita about 2 years ago. Updated over 1 year ago.

[ruby-dev:45530]
Status:Closed
Priority:Normal
Assignee:Nobuyoshi Nakada
Category:core
Target version:-

Description

[Feature #6129]と類似していますが、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を添付します。

patch.diff Magnifier (1.96 KB) Masaki Matsushita, 04/17/2012 11:32 PM

patch2.diff Magnifier (2.46 KB) Masaki Matsushita, 04/28/2012 01:34 PM

patch3.diff Magnifier (2.23 KB) Masaki Matsushita, 04/30/2012 11:36 AM

patch4.diff Magnifier (1.73 KB) Masaki Matsushita, 11/11/2012 02:46 PM

use_memchr.diff Magnifier (442 Bytes) Akinori MUSHA, 11/13/2012 02:58 PM

use_memchr2.diff Magnifier (419 Bytes) Akinori MUSHA, 11/13/2012 03:12 PM

Associated revisions

Revision 37634
Added by glass over 1 year ago

  • re.c (rbmemsearchss): performance improvement by using memmem(3) if
    possible. [Feature #6311]

  • configure.in: check existence of memmem(3) and that it is not broken.

Revision 37793
Added by Akinori MUSHA over 1 year ago

Apply performance improvement to short byte array search.

  • re.c (rbmemsearchss): Apply performance improvement to short byte array search for platforms without memmem(3). [Feature #6311]

History

#1 Updated by Yusuke Endoh almost 2 years ago

  • Status changed from Open to Assigned
  • Assignee set to Nobuyoshi Nakada

いいんじゃないかなあと思いましたが、
configure スクリプトいじるので、なかださんどうでしょうか。

Yusuke Endoh mame@tsg.ne.jp

#2 Updated by Masaki Matsushita almost 2 years ago

rbmemsearchss()はrbmemsearch()以外からは使われていないので、memmem()を使う場合にはrbmemsearch_ss()がコンパイルされないようにしました。

#3 Updated by Nobuyoshi Nakada almost 2 years ago

=begin
(({rbmemsearchss()}))が何だったか思い出せないですが、これ自体を置き換えてはどうでしょうかね。
=end

#4 Updated by Masaki Matsushita almost 2 years ago

rbmemsearchss()が何だったか思い出せないですが、これ自体を置き換えてはどうでしょうかね。

添付のpatchのようにするのが良いでしょうか。

rbmemsearchss()についてですが、これは1つのVALUEの値にSIZEOF_VALUE以下の長さのバイト列の組み合わせを対応させた完全ハッシュ法のようです。

#5 Updated by Yui NARUSE almost 2 years ago

rbmemsearchss() を入れたのはわたしですね。
Linux と FreeBSD あたりで memmem 利用より速いのだったら置き換えちゃっていいんじゃないかと思います。
missing/memmem.c 作って rbmemsearchss() の実装移すって技もありますし。

#6 Updated by Masaki Matsushita over 1 year ago

時間が経ってしまいましたが、いかがでしょうか。
特に反対や議論がないようであれば、取り込んで頂けると幸いです。

#7 Updated by Masaki Matsushita over 1 year ago

こちらもベンチマークの実行時間が短すぎるのでやり直してみました。

require 'benchmark'

str = "hoge" * 100_0000 + "fugafuga"

Benchmark.bm do |x|
x.report do
1000.times { str.index("fugafuga") }
end
end

trunk(r37617):
user system total real
7.540000 0.000000 7.540000 ( 7.539292)

proposed:
user system total real
0.500000 0.000000 0.500000 ( 0.503217)

また、先に添付していたpatchではconfigure.inでACCHECKFUNCS(memmem)した後、
ACTRYRUNでglibc 2.0以前のmemmem()が持つバグがないかどうか確かめBROKENMEMMEMを定義していましたが、
1つの目的に2つのシンボルを定義するのはよろしくないと思ったので、memmem()が存在しかつバグを持っていない場合にHAVE
MEMMEMのみを定義するよう変更しました。

反対がなければ、コミットしようと思います。

#8 Updated by Masaki Matsushita over 1 year ago

#9 Updated by Anonymous over 1 year ago

  • Status changed from Assigned to Closed
  • % Done changed from 0 to 100

This issue was solved with changeset r37634.
Masaki, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.


  • re.c (rbmemsearchss): performance improvement by using memmem(3) if
    possible. [Feature #6311]

  • configure.in: check existence of memmem(3) and that it is not broken.

#10 Updated by Akinori MUSHA over 1 year ago

もしこういう特定のケースの高速化が必要とのことなら、memmem()を使わない版でも

Index: re.c

--- re.c (revision 37635)
+++ re.c (working copy)
@@ -126,6 +126,11 @@ rbmemsearchss(const unsigned char *xs,
if (m > SIZEOFVALUE)
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;

のような素朴なバイト比較ループの方が現状のハッシュ値比較より速いようです。
現状のコードはどのような性能特性を期待しているのでしょうね。

#11 Updated by Akinori MUSHA over 1 year ago

nは下で使われていないので更新不要ですね。

Also available in: Atom PDF