Forum: Ruby-dev [ruby-trunk - Feature #7368][Open] rb str each line()のパフォーマンス向上とリファクタリング

C042517d59bed4761cc88681bf71fca8?d=identicon&s=25 Glass_saga (Masaki Matsushita) (Guest)
on 2012-11-16 06:31
(Received via mailing list)
Issue #7368 has been reported by Glass_saga (Masaki Matsushita).

----------------------------------------
Feature #7368: rb_str_each_line()のパフォーマンス向上とリファクタリング
https://bugs.ruby-lang.org/issues/7368

Author: Glass_saga (Masaki Matsushita)
Status: Open
Priority: Normal
Assignee:
Category: core
Target version:


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

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

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

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

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

* これまでrb_str_each_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)

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

手元ではtest-allが通っていますが、それなりにコードを削った上に関数を新設しているので、patchをレビューして頂けると大変助かります。
よろしくお願いします。
9361878d459f1709feec780518946ee5?d=identicon&s=25 naruse (Yui NARUSE) (Guest)
on 2012-11-17 12:44
(Received via mailing list)
Issue #7368 has been updated by naruse (Yui NARUSE).


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

行われるべき誤マッチ対策は rb_str_index にあるので、それを参考にしつつ直す必要があると思います。
----------------------------------------
Feature #7368: rb_str_each_line()のパフォーマンス向上とリファクタリング
https://bugs.ruby-lang.org/issues/7368#change-33019

Author: Glass_saga (Masaki Matsushita)
Status: Open
Priority: Normal
Assignee:
Category: core
Target version:


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

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

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

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

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

* これまでrb_str_each_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)

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

手元ではtest-allが通っていますが、それなりにコードを削った上に関数を新設しているので、patchをレビューして頂けると大変助かります。
よろしくお願いします。
C042517d59bed4761cc88681bf71fca8?d=identicon&s=25 Glass_saga (Masaki Matsushita) (Guest)
on 2012-11-20 14:02
(Received via mailing list)
Issue #7368 has been updated by Glass_saga (Masaki Matsushita).

File patch2.diff added

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

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

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

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

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

誤マッチ検出後のバグを修正したpatchを添付します。
----------------------------------------
Feature #7368: rb_str_each_line()のパフォーマンス向上とリファクタリング
https://bugs.ruby-lang.org/issues/7368#change-33264

Author: Glass_saga (Masaki Matsushita)
Status: Open
Priority: Normal
Assignee:
Category: core
Target version:


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

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

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

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

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

* これまでrb_str_each_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)

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

手元ではtest-allが通っていますが、それなりにコードを削った上に関数を新設しているので、patchをレビューして頂けると大変助かります。
よろしくお願いします。
F24ff61beb80aa5f13371aa22a35619c?d=identicon&s=25 mame (Yusuke Endoh) (Guest)
on 2012-11-24 03:26
(Received via mailing list)
Issue #7368 has been updated by mame (Yusuke Endoh).

Status changed from Open to Assigned
Assignee set to naruse (Yui NARUSE)
Target version set to next minor


----------------------------------------
Feature #7368: rb_str_each_line()のパフォーマンス向上とリファクタリング
https://bugs.ruby-lang.org/issues/7368#change-33743

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
Priority: Normal
Assignee: naruse (Yui NARUSE)
Category: core
Target version: next minor


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

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

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

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

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

* これまでrb_str_each_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)

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

手元ではtest-allが通っていますが、それなりにコードを削った上に関数を新設しているので、patchをレビューして頂けると大変助かります。
よろしくお願いします。
C042517d59bed4761cc88681bf71fca8?d=identicon&s=25 Glass_saga (Masaki Matsushita) (Guest)
on 2013-06-28 15:53
(Received via mailing list)
Issue #7368 has been updated by Glass_saga (Masaki Matsushita).

File patch3.diff added

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

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

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

以下は[ruby-dev:46523]と同じベンチマークの結果です。

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)
----------------------------------------
Feature #7368: rb_str_each_line()のパフォーマンス向上とリファクタリング
https://bugs.ruby-lang.org/issues/7368#change-40188

Author: Glass_saga (Masaki Matsushita)
Status: Assigned
Priority: Normal
Assignee: naruse (Yui NARUSE)
Category: core
Target version: next minor


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

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

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

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

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

* これまでrb_str_each_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)

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

手元ではtest-allが通っていますが、それなりにコードを削った上に関数を新設しているので、patchをレビューして頂けると大変助かります。
よろしくお願いします。
C042517d59bed4761cc88681bf71fca8?d=identicon&s=25 Glass_saga (Masaki Matsushita) (Guest)
on 2013-09-18 16:40
(Received via mailing list)
Issue #7368 has been updated by Glass_saga (Masaki Matsushita).

Status changed from Assigned to Closed

r42966でこのチケットのpatch3.diffとほぼ同様の変更をコミットしたので、こちらのチケットも閉じます。
----------------------------------------
Feature #7368: rb_str_each_line()のパフォーマンス向上とリファクタリング
https://bugs.ruby-lang.org/issues/7368#change-41880

Author: Glass_saga (Masaki Matsushita)
Status: Closed
Priority: Normal
Assignee: naruse (Yui NARUSE)
Category: core
Target version: next minor


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

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

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

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

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

* これまでrb_str_each_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)

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

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