[ruby-dev:45530] [ruby-trunk - Feature #6311][Open] memmem()によるrb_memsearch()の高速化

[ruby-dev:45530] [ruby-trunk - Feature #6311][Open] memmem()によるrb_memsearch()の高速化

[Glass_saga (Masaki Matsushita)]

Issue #6311 has been reported by Glass_saga (Masaki Matsushita).

----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311

Author: Glass_saga (Masaki Matsushita)
Status: Open
Priority: Normal
Assignee: 
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/

[ruby-dev:45539] [ruby-trunk - Feature #6311][Assigned] memmem()によるrb_memsearch()の高速化

[mame (Yusuke Endoh)]

Issue #6311 has been updated by mame (Yusuke Endoh).

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

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

-- 
Yusuke Endoh <mame@tsg•ne.jp>
----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-26010

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
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/

[ruby-dev:45590] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[Glass_saga (Masaki Matsushita)]

Issue #6311 has been updated by Glass_saga (Masaki Matsushita).

File patch2.diff added

rb_memsearch_ss()はrb_memsearch()以外からは使われていないので、memmem()を使う場合にはrb_memsearch_ss()がコンパイルされないようにしました。
----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-26278

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
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/

[ruby-dev:45592] Re: [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-dev:45590] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化"
    on Sat, 28 Apr 2012 13:34:36 +0900, "Glass_saga (Masaki Matsushita)" <glass.saga@gmail•com> writes:

|Issue #6311 has been updated by Glass_saga (Masaki Matsushita).
|
|File patch2.diff added
|
|rb_memsearch_ss()はrb_memsearch()以外からは使われていないので、memmem()を使う場合にはrb_memsearch_ss()がコンパイルされないようにしました。

なかださん、レビューして問題なければ取り込んでもらえませんか？

[ruby-dev:45593] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[nobu (Nobuyoshi Nakada)]

Issue #6311 has been updated by nobu (Nobuyoshi Nakada).


=begin
(({rb_memsearch_ss()}))が何だったか思い出せないですが、これ自体を置き換えてはどうでしょうかね。
=end
----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-26316

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
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/

[ruby-dev:45595] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[Glass_saga (Masaki Matsushita)]

Issue #6311 has been updated by Glass_saga (Masaki Matsushita).

File patch3.diff added

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

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

rb_memsearch_ss()についてですが、これは1つのVALUEの値にSIZEOF_VALUE以下の長さのバイト列の組み合わせを対応させた完全ハッシュ法のようです。
----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-26324

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
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/

[ruby-dev:45624] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[naruse (Yui NARUSE)]

Issue #6311 has been updated by naruse (Yui NARUSE).


rb_memsearch_ss() を入れたのはわたしですね。
Linux と FreeBSD あたりで memmem 利用より速いのだったら置き換えちゃっていいんじゃないかと思います。
missing/memmem.c 作って rb_memsearch_ss() の実装移すって技もありますし。
----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-26459

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
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/

[ruby-dev:46103] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[Glass_saga (Masaki Matsushita)]

Issue #6311 has been updated by Glass_saga (Masaki Matsushita).


時間が経ってしまいましたが、いかがでしょうか。
特に反対や議論がないようであれば、取り込んで頂けると幸いです。
----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-29158

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
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/

[ruby-dev:46478] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[Glass_saga (Masaki Matsushita)]

Issue #6311 has been updated by Glass_saga (Masaki Matsushita).


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

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のみを定義するよう変更しました。

反対がなければ、コミットしようと思います。
----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-32763

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
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/

[ruby-dev:46479] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[Glass_saga (Masaki Matsushita)]

Issue #6311 has been updated by Glass_saga (Masaki Matsushita).

File patch4.diff added


----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-32764

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
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/

[ruby-dev:46506] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[knu (Akinori MUSHA)]

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/

[ruby-dev:46507] [ruby-trunk - Feature #6311] memmem()によるrb_memsearch()の高速化

[knu (Akinori MUSHA)]

Issue #6311 has been updated by knu (Akinori MUSHA).

File use_memchr2.diff added

nは下で使われていないので更新不要ですね。
----------------------------------------
Feature #6311: memmem()によるrb_memsearch()の高速化
https://bugs.ruby-lang.org/issues/6311#change-32838

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/