Feature #7368

rb_str_each_line()のパフォーマンス向上とリファクタリング

Added by Masaki Matsushita over 1 year ago. Updated 7 months ago.

[ruby-dev:46523]
Status:Closed
Priority:Normal
Assignee:Yui NARUSE
Category:core
Target version:next minor

Description

rbstreachline()でmemmem(3)を使う事を [Feature #6129]で提案しましたが、
string.cからmemmem(3)を直接使わずに検索をrb
memsearch()にまとめた上で、
検索文字列と被検索文字列の両方がvalidなencodingである場合と、そうでない場合に関数を分けてリファクタリングしたpatchを作りました。
(どちらかがinvalidな場合には、rbenccodepoint_len()で舐めていき途中でArgumentErrorを投げる必要があるので、旧来の処理を使う必要があります)

このpatchには以下の利点があります。

  • string.c側でmemmem(3)の有無を意識する必要がない

  • これまで検索文字列がrbdefaultrsである場合にはrbstreachline()側でmemchr(3)を用いた最適化が施されていた(trunkのstring.cの6166行以降)が、
    rb
    memsearch()を使えば検索文字列の長さに合わせて最適化された検索をしてくれるので、このような特別扱いが不要になる

  • 検索文字列と被検索文字列のencodingがvalidなら、検索文字列がrbdefaultrsでない場合のパフォーマンスが向上する

  • これまでrbstreach_line()の冒頭で宣言されていた多数の変数を分けた関数毎に局所化できるので、以前よりは読みやすくなる

また、以下のコードでベンチマークを取りました。

require 'benchmark'

str = "hogehifuga\n" * 100_0000

Benchmark.bm do |x|
x.report("default rs") do
10.times do
str.each_line {}
end
end

x.report("not default rs") do
10.times do
str.each_line("hi") {}
end
end
end

trunk(r37670):
user system total real
default rs 2.060000 0.000000 2.060000 ( 2.055412)
not default rs 3.700000 0.000000 3.700000 ( 3.698057)

proposed:
user system total real
default rs 2.100000 0.000000 2.100000 ( 2.095167)
not default rs 2.150000 0.000000 2.150000 ( 2.153824)

検索文字列がrbdefaultrsな場合のパフォーマンスが低下していない事、検索文字列がrbdefaultrsでない場合にはパフォーマンスが向上している事が確認できます。

手元ではtest-allが通っていますが、それなりにコードを削った上に関数を新設しているので、patchをレビューして頂けると大変助かります。
よろしくお願いします。

patch.diff Magnifier (5.43 KB) Masaki Matsushita, 11/16/2012 02:31 PM

patch2.diff Magnifier (5.57 KB) Masaki Matsushita, 11/20/2012 10:01 PM

patch3.diff Magnifier (3.75 KB) Masaki Matsushita, 06/28/2013 10:53 PM


Related issues

Related to ruby-trunk - Bug #8698: レシーバに不正なバイト列が含まれている場合にString#each_lineや#linesの挙動が引数の有無で変わ... Closed 07/28/2013

History

#1 Updated by Yui NARUSE over 1 year ago

validかinvalidかで区別する必要は無いし、それで十分でもありません。
防ぐべき誤マッチは文字境界をまたいだマッチであり、このパッチだとたぶん、
EUC-JPで「スト」に「好」がマッチするような場合は防げないんじゃないでしょうか。
(それっぽいのがないなーってとこまでしか見てないので、ちゃんと対策してたら申し訳ない)

行われるべき誤マッチ対策は rbstrindex にあるので、それを参考にしつつ直す必要があると思います。

#2 Updated by Masaki Matsushita over 1 year ago

返信が遅くなってしまいました。
成瀬さん、レビュー頂きありがとうございます。

このパッチだとたぶん、EUC-JPで「スト」に「好」がマッチするような場合は防げないんじゃないでしょうか。

rbstrindex()相当の誤マッチ対策をしてはいたのですが、誤マッチを検出した後の処理がまずかったので意味を為していませんでした。
この点は添付のpatchで修正しました。

validかinvalidかで区別する必要は無いし、それで十分でもありません。

validとinvalidで区別しているのは、被検索文字列がinvalidである場合に途中でInvalidByteSequenceErrorがraiseされる事を期待しているテストがある為です。
rbmemsearch()は途中に不正なバイト列があっても素通りしてしまうので、検索の途中で例外を投げる事ができません。
従って、被検索文字列がinvalidな場合には従来のようにrb
enccodepointlen()で不正なバイト列でないかチェックしながら検索する必要があります。

誤マッチ検出後のバグを修正したpatchを添付します。

#3 Updated by Yusuke Endoh over 1 year ago

  • Status changed from Open to Assigned
  • Assignee set to Yui NARUSE
  • Target version set to next minor

#4 Updated by Masaki Matsushita 10 months ago

時間が経ってしまいましたが、そもそも「レシーバのStringに不正なバイト列が含まれていたら不正なバイト列を踏んだところで例外を投げる」というのは好ましい仕様なのでしょうか。
現状の実装では改行文字がdefaultrsである場合、memchrで舐めていくので不正なバイト列が含まれていても素通りしていってしまいます。
不正なバイト列が含まれている事を検知して途中で例外を投げるのは改行文字にdefault
rs以外の文字列を指定した場合のみです。

これではちぐはぐだと思うので、改行文字の指定に関わらずレシーバに不正なバイト列が含まれている場合の挙動について統一した方が良いのではないかと思いますが、いかがでしょうか。

添付のpatchは改行文字の指定に関わらずrbmemsearch()を使うようにして高速化を図ったものです。
rb
memsearch()は内部でmemcharやmemmem(3)を使っているので、不正なバイト列を踏んでも素通りします。
つまり現在の実装で改行文字がdefault_rsである場合の挙動に統一してあります。

以下はと同じベンチマークの結果です。

trunk(r41584):
user system total real
default rs 2.060000 0.000000 2.060000 ( 2.068874)
not default rs 3.660000 0.110000 3.770000 ( 3.780576)

proposal
user system total real
default rs 2.160000 0.010000 2.170000 ( 2.185718)
not default rs 2.350000 0.000000 2.350000 ( 2.374584)

#5 Updated by Masaki Matsushita 7 months ago

  • Status changed from Assigned to Closed

r42966でこのチケットのpatch3.diffとほぼ同様の変更をコミットしたので、こちらのチケットも閉じます。

Also available in: Atom PDF