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

• Status: Closed
• Assignee: Glass_saga (Masaki Matsushita)
• Target version: 2.6

[Glass_saga (Masaki Matsushita)]

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

[nobu (Nobuyoshi Nakada)]

• Target version set to 2.0.0

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

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

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

[Glass_saga (Masaki Matsushita)]

• File patch2.diff patch2.diff added

Nobuyoshi Nakada 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()という関数を作りコードの重複を削減

[mame (Yusuke Endoh)]

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

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

--
Yusuke Endoh [e-mail]

[mame (Yusuke Endoh)]

• Target version changed from 2.0.0 to 2.6

[Glass_saga (Masaki Matsushita)]

• Status changed from Assigned to Closed
• Assignee changed from nobu (Nobuyoshi Nakada) to Glass_saga (Masaki Matsushita)

trunkでは既にrb_memsearch()を利用するようになっているため、このチケットは閉じます。