[ruby-trunk - Feature #6129][Open] String#each lineにおけるmemmem()の利用

luislavena · March 11, 2012, 3:36pm

Issue #6129 has been reported by Masaki M…

Feature #6129: String#each_lineにおけるmemmem()の利用

Author: Masaki M.
Status: Open
Priority: Normal
Assignee:
Category: core
Target version:

memmem()というGNU拡張のライブラリ関数がありますが、string.cのrb_str_each_line()で可能であればこのmemmem()を利用する事を提案します。

次のベンチマークを実行しました。

require ‘benchmark’

str = “hogehifuga” * 100_0000

Benchmark.bm do |x|
x.report do
str.each_line(“hi”) {}
end
end

結果:

trunk(r34969):

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

proposal:

   user     system      total        real

0.510000 0.000000 0.510000 ( 0.507389)

   user     system      total        real

0.530000 0.000000 0.530000 ( 0.541944)

   user     system      total        real

0.520000 0.000000 0.520000 ( 0.522825)

以上のように、memmem()を利用する事でパフォーマンスの改善が見られます。
但し、改行文字がrb_default_rsと同一である場合には既にmemchr()を用いた高速な検索が行われるようになっている為、
パフォーマンスが改善されるのはrb_default_rs以外の改行文字を指定した場合のみです。

patchを添付します。

Masaki_M · March 12, 2012, 5:50am

Issue #6129 has been updated by Nobuyoshi N…

Target version set to 2.0.0

=begin
確認したい点があります。

パラグラフモードでも効果があるか
マルチバイト文字の途中にマッチした場合はどうなるか

また、追加されたコードが既存のコードとかなり重複しているように見えます。
重複を減らすのは難しいでしょうか。
=end

Feature #6129: String#each_lineにおけるmemmem()の利用

Author: Masaki M.
Status: Open
Priority: Normal
Assignee:
Category: core
Target version: 2.0.0

memmem()というGNU拡張のライブラリ関数がありますが、string.cのrb_str_each_line()で可能であればこのmemmem()を利用する事を提案します。

次のベンチマークを実行しました。

require ‘benchmark’

str = “hogehifuga” * 100_0000

Benchmark.bm do |x|
x.report do
str.each_line(“hi”) {}
end
end

結果:

trunk(r34969):

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

proposal:

   user     system      total        real

0.510000 0.000000 0.510000 ( 0.507389)

   user     system      total        real

0.530000 0.000000 0.530000 ( 0.541944)

   user     system      total        real

0.520000 0.000000 0.520000 ( 0.522825)

以上のように、memmem()を利用する事でパフォーマンスの改善が見られます。
但し、改行文字がrb_default_rsと同一である場合には既にmemchr()を用いた高速な検索が行われるようになっている為、
パフォーマンスが改善されるのはrb_default_rs以外の改行文字を指定した場合のみです。

patchを添付します。

Masaki_M · March 29, 2012, 6:55pm

Issue #6129 has been updated by mame (Yusuke E.).

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

なかださん、更新されたパッチで問題ないと思います？

–
Yusuke E. [email protected]

Feature #6129: String#each_lineにおけるmemmem()の利用

Author: Glass_saga (Masaki M.)
Status: Assigned
Priority: Normal
Assignee: nobu (Nobuyoshi N.)
Category: core
Target version: 2.0.0

memmem()というGNU拡張のライブラリ関数がありますが、string.cのrb_str_each_line()で可能であればこのmemmem()を利用する事を提案します。

次のベンチマークを実行しました。

require ‘benchmark’

str = “hogehifuga” * 100_0000

Benchmark.bm do |x|
x.report do
str.each_line(“hi”) {}
end
end

結果:

trunk(r34969):

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

proposal:

   user     system      total        real

0.510000 0.000000 0.510000 ( 0.507389)

   user     system      total        real

0.530000 0.000000 0.530000 ( 0.541944)

   user     system      total        real

0.520000 0.000000 0.520000 ( 0.522825)

以上のように、memmem()を利用する事でパフォーマンスの改善が見られます。
但し、改行文字がrb_default_rsと同一である場合には既にmemchr()を用いた高速な検索が行われるようになっている為、
パフォーマンスが改善されるのはrb_default_rs以外の改行文字を指定した場合のみです。

patchを添付します。

Masaki_M · March 18, 2012, 9:23am

Issue #6129 has been updated by Glass_saga.

File patch2.diff added

Nobuyoshi N. wrote:

パラグラフモードでも効果があるか

マルチバイト文字の途中にマッチした場合はどうなるか
また、追加されたコードが既存のコードとかなり重複しているように見えます。重複を減らすのは難しいでしょうか。

パラグラフモードでも効果があるかどうかについてですが、次のようなベンチマークを実行してみました。

require ‘benchmark’

rs = “\n” * ARGV.first.to_i
str = “hoge#{rs}fuga” * 10_0000

Benchmark.bm do |x|
x.report do
str.each_line(“”) {|s| s }
end
end

“\n” * 2 の場合

proposal:
user system total real
0.070000 0.000000 0.070000 ( 0.070409)

trunk:
user system total real
0.090000 0.000000 0.090000 ( 0.094886)

“\n” * 100 の場合

proposal:
user system total real
0.310000 0.000000 0.310000 ( 0.307020)

trunk:
user system total real
0.320000 0.000000 0.320000 ( 0.320367)

以上のように、連続する改行文字の個数が少ない場合はパラグラフモードでも効果があります。
個数が多くなるにつれてtrunkと同程度の速さになりますが、逆転する事はありませんでした。

マルチバイト文字の途中にマッチした場合はどうなるか

お察しの通り正しく動きませんでした。

“表示”.encode(“SJIS”).each_line(“\”).to_a.map{|s| s.encode(“UTF-8”) } #=>
[“表”, “示”]
(UTF-8環境です)

また、追加されたコードが既存のコードとかなり重複しているように見えます。重複を減らすのは難しいでしょうか。

line = rb_str_new5(str, s, sublen)からの4行については関数に切り出す事もできますが、
それ以外の部分については重複を減らすのは難しいと思います。

以下の2点を改善した新しいpatchを添付します。

rb_enc_left_char_head()を用いて文字境界をチェックするようにした
configureでmemmem()の第3引数needleが空の場合に発生するバグをチェックできていなかったので修正
line_yield()という関数を作りコードの重複を削減

Feature #6129: String#each_lineにおけるmemmem()の利用

Author: Glass_saga
Status: Open
Priority: Normal
Assignee:
Category: core
Target version: 2.0.0

memmem()というGNU拡張のライブラリ関数がありますが、string.cのrb_str_each_line()で可能であればこのmemmem()を利用する事を提案します。

次のベンチマークを実行しました。

require ‘benchmark’

str = “hogehifuga” * 100_0000

Benchmark.bm do |x|
x.report do
str.each_line(“hi”) {}
end
end

結果:

trunk(r34969):

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

proposal:

   user     system      total        real

0.510000 0.000000 0.510000 ( 0.507389)

   user     system      total        real

0.530000 0.000000 0.530000 ( 0.541944)

   user     system      total        real

0.520000 0.000000 0.520000 ( 0.522825)

以上のように、memmem()を利用する事でパフォーマンスの改善が見られます。
但し、改行文字がrb_default_rsと同一である場合には既にmemchr()を用いた高速な検索が行われるようになっている為、
パフォーマンスが改善されるのはrb_default_rs以外の改行文字を指定した場合のみです。

patchを添付します。

Masaki_M · November 20, 2012, 2:24pm

Issue #6129 has been updated by mame (Yusuke E.).

Target version changed from 2.0.0 to next minor

Feature #6129: String#each_lineにおけるmemmem()の利用

Author: Glass_saga (Masaki M.)
Status: Assigned
Priority: Normal
Assignee: nobu (Nobuyoshi N.)
Category: core
Target version: next minor

memmem()というGNU拡張のライブラリ関数がありますが、string.cのrb_str_each_line()で可能であればこのmemmem()を利用する事を提案します。

次のベンチマークを実行しました。

require ‘benchmark’

str = “hogehifuga” * 100_0000

Benchmark.bm do |x|
x.report do
str.each_line(“hi”) {}
end
end

結果:

trunk(r34969):

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

   user     system      total        real

0.790000 0.000000 0.790000 ( 0.795141)

proposal:

   user     system      total        real

0.510000 0.000000 0.510000 ( 0.507389)

   user     system      total        real

0.530000 0.000000 0.530000 ( 0.541944)

   user     system      total        real

0.520000 0.000000 0.520000 ( 0.522825)

以上のように、memmem()を利用する事でパフォーマンスの改善が見られます。
但し、改行文字がrb_default_rsと同一である場合には既にmemchr()を用いた高速な検索が行われるようになっている為、
パフォーマンスが改善されるのはrb_default_rs以外の改行文字を指定した場合のみです。

patchを添付します。

[ruby-trunk - Feature #6129][Open] String#each lineにおけるmemmem()の利用

また、追加されたコードが既存のコードとかなり重複しているように見えます。 重複を減らすのは難しいでしょうか。 =end

– Yusuke E. [email protected]

また、追加されたコードが既存のコードとかなり重複しているように見えます。
重複を減らすのは難しいでしょうか。
=end

–
Yusuke E. [email protected]