From: Glass_saga <glass.saga@...>
Date: 2012-03-18T17:23:03+09:00
Subject: [ruby-dev:45391] [ruby-trunk - Feature #6129] String#each_lineにおけるmemmem()の利用


Issue #6129 has been updated by Glass_saga.

File 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()という関数を作りコードの重複を削減
----------------------------------------
Feature #6129: String#each_lineにおけるmemmem()の利用
https://bugs.ruby-lang.org/issues/6129#change-24727

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


-- 
http://bugs.ruby-lang.org/