Project

General

Profile

Actions

Feature #6311

closed

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

Added by Glass_saga (Masaki Matsushita) almost 12 years ago. Updated over 11 years ago.

Status:
Closed
Target version:
-
[ruby-dev:45530]

Description

[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を添付します。


Files

patch.diff (1.96 KB) patch.diff Glass_saga (Masaki Matsushita), 04/17/2012 11:32 PM
patch2.diff (2.46 KB) patch2.diff Glass_saga (Masaki Matsushita), 04/28/2012 01:34 PM
patch3.diff (2.23 KB) patch3.diff Glass_saga (Masaki Matsushita), 04/30/2012 11:36 AM
patch4.diff (1.73 KB) patch4.diff Glass_saga (Masaki Matsushita), 11/11/2012 02:46 PM
use_memchr.diff (442 Bytes) use_memchr.diff knu (Akinori MUSHA), 11/13/2012 02:58 PM
use_memchr2.diff (419 Bytes) use_memchr2.diff knu (Akinori MUSHA), 11/13/2012 03:12 PM

Updated by mame (Yusuke Endoh) almost 12 years ago

  • Status changed from Open to Assigned
  • Assignee set to nobu (Nobuyoshi Nakada)

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

--
Yusuke Endoh

Updated by Glass_saga (Masaki Matsushita) almost 12 years ago

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

Updated by nobu (Nobuyoshi Nakada) almost 12 years ago

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

Updated by Glass_saga (Masaki Matsushita) almost 12 years ago

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

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

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

Updated by naruse (Yui NARUSE) almost 12 years ago

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

Updated by Glass_saga (Masaki Matsushita) over 11 years ago

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

Updated by Glass_saga (Masaki Matsushita) over 11 years 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でAC_CHECK_FUNCS(memmem)した後、
AC_TRY_RUNでglibc 2.0以前のmemmem()が持つバグがないかどうか確かめBROKEN_MEMMEMを定義していましたが、
1つの目的に2つのシンボルを定義するのはよろしくないと思ったので、memmem()が存在しかつバグを持っていない場合にHAVE_MEMMEMのみを定義するよう変更しました。

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

Actions #9

Updated by Anonymous over 11 years 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 (rb_memsearch_ss): performance improvement by using memmem(3) if
    possible. [ruby-dev:45530] [Feature #6311]

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

Updated by knu (Akinori MUSHA) over 11 years ago

もしこういう特定のケースの高速化が必要とのことなら、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;

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

Updated by knu (Akinori MUSHA) over 11 years ago

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

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0