Feature #6129

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

Added by Masaki Matsushita about 2 years ago. Updated over 1 year ago.

[ruby-dev:45344]
Status:Assigned
Priority:Normal
Assignee:Nobuyoshi Nakada
Category:core
Target version:next minor

Description

memmem()というGNU拡張のライブラリ関数がありますが、string.cのrbstreach_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()を利用する事でパフォーマンスの改善が見られます。
但し、改行文字がrbdefaultrsと同一である場合には既にmemchr()を用いた高速な検索が行われるようになっている為、
パフォーマンスが改善されるのはrbdefaultrs以外の改行文字を指定した場合のみです。

patchを添付します。

patch.diff Magnifier (2.7 KB) Masaki Matsushita, 03/11/2012 11:35 PM

patch2.diff Magnifier (4.12 KB) Masaki Matsushita, 03/18/2012 05:23 PM

History

#1 Updated by Nobuyoshi Nakada about 2 years ago

  • Target version set to 2.0.0

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

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

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

#2 Updated by Masaki Matsushita about 2 years ago

Nobuyoshi Nakada wrote:

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

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

require 'benchmark'

rs = "\n" * ARGV.first.toi
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").eachline("\").toa.map{|s| s.encode("UTF-8") } #=> "表", "示"

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

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

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

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

#3 Updated by Yusuke Endoh about 2 years ago

  • Status changed from Open to Assigned
  • Assignee set to Nobuyoshi Nakada

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

Yusuke Endoh mame@tsg.ne.jp

#4 Updated by Yusuke Endoh over 1 year ago

  • Target version changed from 2.0.0 to next minor

Also available in: Atom PDF