[Ruby 1.9 - Feature #4495][Open] PStoreの高速化

Issue #4495 has been reported by Masaki M…


Feature #4495: PStoreの高速化
http://redmine.ruby-lang.org/issues/4495

Author: Masaki M.
Status: Open
Priority: Normal
Assignee:
Category: lib
Target version:

PStoreを少し速くしてみました。

加えた変更は以下の通りです。

  • チェックサムをDigest::MD5.digestではなくZlib.crc32で求めるようにした

PStoreは無駄なファイルアクセスを減らす為、外部ファイルのチェックサムと内部のHashをMarshal.dumpしたもののチェックサムを比較して
両者が異なる場合のみ書き込みを行うようになっているのですが、そのチェックサムをDigest::MD5.digestではなくZlib.crc32で求めるように変更しました。
PStoreにおける用途では、暗号学的ハッシュ関数を使う必要はないはずなので、Zlib.crc32で十分ではないでしょうか。
Digest::MD5.digestと比較すると、Zlib.crc32の方が1.3~1.5倍ほど速いようです。

  • 書き込みの際のチェックサム生成の後回し

上に書いたようにPStoreは書き込みの際にチェックサムを比較するのですが、その前にデータサイズの比較も行っていて、書き込み先のファイルのサイズと書き込もうとしているマーシャルデータのサイズが異なっていればその時点で書き込みが必要だと判断します。
しかし、データサイズの比較を行う前にチェックサムの生成を行っていたので、データサイズが同じである場合のみチェックサムを生成し比較するようにしました。
データサイズが異なっている場合にはチェックサムの生成と比較を行わずに済むので、若干の高速化が期待できます。

  • メソッドmarshal_dump_supports_canonical_option?の削除

Ruby1.8ではHashの順序が保証されていなかったので、あるHashをMarshal.dumpしてできたStringと、そのStringをMarshal.loadしてできたHashを再度Marshal.dumpしてできたStringをString#==で比較するとfalseになる場合がありました。

Hongli
Lai氏はこれを嫌ったようで、同じHashなら同じStringにdumpされるようなオプションを追加したMarshal.dumpのパッチを書いて、
さらにPStoreにもそのオプションがサポートされているかどうか調べるmarshal_dump_supports_canonical_option?というメソッドを追加したものと思われます。
(参考: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/17243 )

このメソッドの中では

435 begin
436 Marshal.dump(nil, -1, true)
437 result = true
438 rescue
439 result = false
440 end

という事をして、このメソッドはresultを返すのですが、少なくともRuby1.9ではMarshal.dumpの引数が正しくないので必ずfalseが返ります。
よって調べても無駄なのでメソッドごと削除しました。

  • File#truncateの後回し

PStoreは実際にマーシャルデータをファイルに書き込む際に

486 file.rewind
487 file.truncate(0)
488 file.write(data)

ファイルポインタを先頭に戻し、ファイルのサイズを0にしてから書き込みを始めていました。
しかし、File#truncateによるファイルサイズの変更は時間のかかる処理で、PStoreではこれがボトルネックとなっていました。

そこで、

file.rewind
file.write(data)
file.truncate(data.size)

ファイルポインタを先頭に戻したら、書き込みを始め、書き込みが終わった後に帳尻を合わせるようにしました。
File#truncateによって変更しなければならないサイズが抑えられ、高速化が期待できます。

全体でのパフォーマンスについてですが、次のようなベンチマークを行ったところ

require ‘pstore’

p = PStore.new(“foo”)
p.transaction { p[“hoge”] = “hoge” * ARGV.first.to_i }

10000.times do
p.transaction { p[“hoge”] += “hoge” }
end

現在のPStoreでは

% time ruby pstore_bench.rb 1000
ruby pstore_bench.rb 1000 2.94s user 2.43s system 69% cpu 7.723 total
% time ruby pstore_bench.rb 10000
ruby pstore_bench.rb 10000 5.37s user 2.99s system 70% cpu 11.810
total
% time ruby pstore_bench.rb 100000
ruby pstore_bench.rb 100000 31.98s user 11.09s system 69% cpu 1:02.15
total

となったのに対して上記の変更を加えたPStoreでは

% time ruby pstore_bench.rb 1000
ruby pstore_bench.rb 1000 1.67s user 0.44s system 99% cpu 2.119 total
% time ruby pstore_bench.rb 10000
ruby pstore_bench.rb 10000 3.24s user 0.63s system 99% cpu 3.876 total
% time ruby pstore_bench.rb 100000
ruby pstore_bench.rb 100000 14.29s user 3.13s system 100% cpu 17.416
total

となり、パフォーマンスの向上がみられました。
扱うデータのサイズが大きいほど差は開くものと思われます。

パッチを添付しました。
変更後もtest-allをパスします。

よろしくお願いします。

sora_h$B$G$9(B

2011/3/11 Masaki M. [email protected]:

$B%A%’%C%/%5%`$r(BDigest::MD5.digest$B$G$O$J$/(BZlib.crc32$B$G5a$a$k$h$&$K$7$?(B
zlib$B$,L5$$4D6-$O$I$&$J$k$N$G$7$g$&(B?

Issue #4495 has been updated by Kazuhiro NISHIYAMA.

Masaki M. wrote:

file.rewind
file.write(data)
file.truncate(data.size)

bytesize じゃなくても良いのでしょうか?

Feature #4495: PStoreの高速化
http://redmine.ruby-lang.org/issues/4495

Author: Masaki M.
Status: Open
Priority: Normal
Assignee:
Category: lib
Target version:

PStoreを少し速くしてみました。

加えた変更は以下の通りです。

  • チェックサムをDigest::MD5.digestではなくZlib.crc32で求めるようにした

PStoreは無駄なファイルアクセスを減らす為、外部ファイルのチェックサムと内部のHashをMarshal.dumpしたもののチェックサムを比較して
両者が異なる場合のみ書き込みを行うようになっているのですが、そのチェックサムをDigest::MD5.digestではなくZlib.crc32で求めるように変更しました。
PStoreにおける用途では、暗号学的ハッシュ関数を使う必要はないはずなので、Zlib.crc32で十分ではないでしょうか。
Digest::MD5.digestと比較すると、Zlib.crc32の方が1.3~1.5倍ほど速いようです。

  • 書き込みの際のチェックサム生成の後回し

上に書いたようにPStoreは書き込みの際にチェックサムを比較するのですが、その前にデータサイズの比較も行っていて、書き込み先のファイルのサイズと書き込もうとしているマーシャルデータのサイズが異なっていればその時点で書き込みが必要だと判断します。
しかし、データサイズの比較を行う前にチェックサムの生成を行っていたので、データサイズが同じである場合のみチェックサムを生成し比較するようにしました。
データサイズが異なっている場合にはチェックサムの生成と比較を行わずに済むので、若干の高速化が期待できます。

  • メソッドmarshal_dump_supports_canonical_option?の削除

Ruby1.8ではHashの順序が保証されていなかったので、あるHashをMarshal.dumpしてできたStringと、そのStringをMarshal.loadしてできたHashを再度Marshal.dumpしてできたStringをString#==で比較するとfalseになる場合がありました。

Hongli
Lai氏はこれを嫌ったようで、同じHashなら同じStringにdumpされるようなオプションを追加したMarshal.dumpのパッチを書いて、
さらにPStoreにもそのオプションがサポートされているかどうか調べるmarshal_dump_supports_canonical_option?というメソッドを追加したものと思われます。
(参考: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/17243 )

このメソッドの中では

435 begin
436 Marshal.dump(nil, -1, true)
437 result = true
438 rescue
439 result = false
440 end

という事をして、このメソッドはresultを返すのですが、少なくともRuby1.9ではMarshal.dumpの引数が正しくないので必ずfalseが返ります。
よって調べても無駄なのでメソッドごと削除しました。

  • File#truncateの後回し

PStoreは実際にマーシャルデータをファイルに書き込む際に

486 file.rewind
487 file.truncate(0)
488 file.write(data)

ファイルポインタを先頭に戻し、ファイルのサイズを0にしてから書き込みを始めていました。
しかし、File#truncateによるファイルサイズの変更は時間のかかる処理で、PStoreではこれがボトルネックとなっていました。

そこで、

file.rewind
file.write(data)
file.truncate(data.size)

ファイルポインタを先頭に戻したら、書き込みを始め、書き込みが終わった後に帳尻を合わせるようにしました。
File#truncateによって変更しなければならないサイズが抑えられ、高速化が期待できます。

全体でのパフォーマンスについてですが、次のようなベンチマークを行ったところ

require ‘pstore’

p = PStore.new(“foo”)
p.transaction { p[“hoge”] = “hoge” * ARGV.first.to_i }

10000.times do
p.transaction { p[“hoge”] += “hoge” }
end

現在のPStoreでは

% time ruby pstore_bench.rb 1000
ruby pstore_bench.rb 1000 2.94s user 2.43s system 69% cpu 7.723 total
% time ruby pstore_bench.rb 10000
ruby pstore_bench.rb 10000 5.37s user 2.99s system 70% cpu 11.810
total
% time ruby pstore_bench.rb 100000
ruby pstore_bench.rb 100000 31.98s user 11.09s system 69% cpu 1:02.15
total

となったのに対して上記の変更を加えたPStoreでは

% time ruby pstore_bench.rb 1000
ruby pstore_bench.rb 1000 1.67s user 0.44s system 99% cpu 2.119 total
% time ruby pstore_bench.rb 10000
ruby pstore_bench.rb 10000 3.24s user 0.63s system 99% cpu 3.876 total
% time ruby pstore_bench.rb 100000
ruby pstore_bench.rb 100000 14.29s user 3.13s system 100% cpu 17.416
total

となり、パフォーマンスの向上がみられました。
扱うデータのサイズが大きいほど差は開くものと思われます。

パッチを添付しました。
変更後もtest-allをパスします。

よろしくお願いします。

Issue #4495 has been updated by Masaki M…

File patch2.diff added

指摘を受けて修正しました。

zlibが無い環境はどうなるのでしょう?

これは問題ですね。
Zlib.crc32ではなく、String#sumを使うようにしました。
String#sumはZlib.crc32とほぼ同じぐらい速いです。

bytesize じゃなくても良いのでしょうか?

bytesizeにするべきですね。修正しました。

修正したパッチを添付します。test-allをpassします。
よろしくお願いします。

Feature #4495: PStoreの高速化
http://redmine.ruby-lang.org/issues/4495

Author: Masaki M.
Status: Open
Priority: Normal
Assignee:
Category: lib
Target version:

PStoreを少し速くしてみました。

加えた変更は以下の通りです。

  • チェックサムをDigest::MD5.digestではなくZlib.crc32で求めるようにした

PStoreは無駄なファイルアクセスを減らす為、外部ファイルのチェックサムと内部のHashをMarshal.dumpしたもののチェックサムを比較して
両者が異なる場合のみ書き込みを行うようになっているのですが、そのチェックサムをDigest::MD5.digestではなくZlib.crc32で求めるように変更しました。
PStoreにおける用途では、暗号学的ハッシュ関数を使う必要はないはずなので、Zlib.crc32で十分ではないでしょうか。
Digest::MD5.digestと比較すると、Zlib.crc32の方が1.3~1.5倍ほど速いようです。

  • 書き込みの際のチェックサム生成の後回し

上に書いたようにPStoreは書き込みの際にチェックサムを比較するのですが、その前にデータサイズの比較も行っていて、書き込み先のファイルのサイズと書き込もうとしているマーシャルデータのサイズが異なっていればその時点で書き込みが必要だと判断します。
しかし、データサイズの比較を行う前にチェックサムの生成を行っていたので、データサイズが同じである場合のみチェックサムを生成し比較するようにしました。
データサイズが異なっている場合にはチェックサムの生成と比較を行わずに済むので、若干の高速化が期待できます。

  • メソッドmarshal_dump_supports_canonical_option?の削除

Ruby1.8ではHashの順序が保証されていなかったので、あるHashをMarshal.dumpしてできたStringと、そのStringをMarshal.loadしてできたHashを再度Marshal.dumpしてできたStringをString#==で比較するとfalseになる場合がありました。

Hongli
Lai氏はこれを嫌ったようで、同じHashなら同じStringにdumpされるようなオプションを追加したMarshal.dumpのパッチを書いて、
さらにPStoreにもそのオプションがサポートされているかどうか調べるmarshal_dump_supports_canonical_option?というメソッドを追加したものと思われます。
(参考: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/17243 )

このメソッドの中では

435 begin
436 Marshal.dump(nil, -1, true)
437 result = true
438 rescue
439 result = false
440 end

という事をして、このメソッドはresultを返すのですが、少なくともRuby1.9ではMarshal.dumpの引数が正しくないので必ずfalseが返ります。
よって調べても無駄なのでメソッドごと削除しました。

  • File#truncateの後回し

PStoreは実際にマーシャルデータをファイルに書き込む際に

486 file.rewind
487 file.truncate(0)
488 file.write(data)

ファイルポインタを先頭に戻し、ファイルのサイズを0にしてから書き込みを始めていました。
しかし、File#truncateによるファイルサイズの変更は時間のかかる処理で、PStoreではこれがボトルネックとなっていました。

そこで、

file.rewind
file.write(data)
file.truncate(data.size)

ファイルポインタを先頭に戻したら、書き込みを始め、書き込みが終わった後に帳尻を合わせるようにしました。
File#truncateによって変更しなければならないサイズが抑えられ、高速化が期待できます。

全体でのパフォーマンスについてですが、次のようなベンチマークを行ったところ

require ‘pstore’

p = PStore.new(“foo”)
p.transaction { p[“hoge”] = “hoge” * ARGV.first.to_i }

10000.times do
p.transaction { p[“hoge”] += “hoge” }
end

現在のPStoreでは

% time ruby pstore_bench.rb 1000
ruby pstore_bench.rb 1000 2.94s user 2.43s system 69% cpu 7.723 total
% time ruby pstore_bench.rb 10000
ruby pstore_bench.rb 10000 5.37s user 2.99s system 70% cpu 11.810
total
% time ruby pstore_bench.rb 100000
ruby pstore_bench.rb 100000 31.98s user 11.09s system 69% cpu 1:02.15
total

となったのに対して上記の変更を加えたPStoreでは

% time ruby pstore_bench.rb 1000
ruby pstore_bench.rb 1000 1.67s user 0.44s system 99% cpu 2.119 total
% time ruby pstore_bench.rb 10000
ruby pstore_bench.rb 10000 3.24s user 0.63s system 99% cpu 3.876 total
% time ruby pstore_bench.rb 100000
ruby pstore_bench.rb 100000 14.29s user 3.13s system 100% cpu 17.416
total

となり、パフォーマンスの向上がみられました。
扱うデータのサイズが大きいほど差は開くものと思われます。

パッチを添付しました。
変更後もtest-allをパスします。

よろしくお願いします。

Issue #4495 has been updated by Shota F…

Status changed from Open to Closed

closing. thank you for your contribution.

Feature #4495: PStoreの高速化
https://bugs.ruby-lang.org/issues/4495

Author: Masaki M.
Status: Closed
Priority: Normal
Assignee:
Category: lib
Target version:

=begin
PStoreを少し速くしてみました。

加えた変更は以下の通りです。

  • チェックサムをDigest::MD5.digestではなくZlib.crc32で求めるようにした

PStoreは無駄なファイルアクセスを減らす為、外部ファイルのチェックサムと内部のHashをMarshal.dumpしたもののチェックサムを比較して
両者が異なる場合のみ書き込みを行うようになっているのですが、そのチェックサムをDigest::MD5.digestではなくZlib.crc32で求めるように変更しました。
PStoreにおける用途では、暗号学的ハッシュ関数を使う必要はないはずなので、Zlib.crc32で十分ではないでしょうか。
Digest::MD5.digestと比較すると、Zlib.crc32の方が1.3~1.5倍ほど速いようです。

  • 書き込みの際のチェックサム生成の後回し

上に書いたようにPStoreは書き込みの際にチェックサムを比較するのですが、その前にデータサイズの比較も行っていて、書き込み先のファイルのサイズと書き込もうとしているマーシャルデータのサイズが異なっていればその時点で書き込みが必要だと判断します。
しかし、データサイズの比較を行う前にチェックサムの生成を行っていたので、データサイズが同じである場合のみチェックサムを生成し比較するようにしました。
データサイズが異なっている場合にはチェックサムの生成と比較を行わずに済むので、若干の高速化が期待できます。

  • メソッドmarshal_dump_supports_canonical_option?の削除

Ruby1.8ではHashの順序が保証されていなかったので、あるHashをMarshal.dumpしてできたStringと、そのStringをMarshal.loadしてできたHashを再度Marshal.dumpしてできたStringをString#==で比較するとfalseになる場合がありました。

Hongli
Lai氏はこれを嫌ったようで、同じHashなら同じStringにdumpされるようなオプションを追加したMarshal.dumpのパッチを書いて、
さらにPStoreにもそのオプションがサポートされているかどうか調べるmarshal_dump_supports_canonical_option?というメソッドを追加したものと思われます。
(参考: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/17243 )

このメソッドの中では

435 begin
436 Marshal.dump(nil, -1, true)
437 result = true
438 rescue
439 result = false
440 end

という事をして、このメソッドはresultを返すのですが、少なくともRuby1.9ではMarshal.dumpの引数が正しくないので必ずfalseが返ります。
よって調べても無駄なのでメソッドごと削除しました。

  • File#truncateの後回し

PStoreは実際にマーシャルデータをファイルに書き込む際に

486 file.rewind
487 file.truncate(0)
488 file.write(data)

ファイルポインタを先頭に戻し、ファイルのサイズを0にしてから書き込みを始めていました。
しかし、File#truncateによるファイルサイズの変更は時間のかかる処理で、PStoreではこれがボトルネックとなっていました。

そこで、

file.rewind
file.write(data)
file.truncate(data.size)

ファイルポインタを先頭に戻したら、書き込みを始め、書き込みが終わった後に帳尻を合わせるようにしました。
File#truncateによって変更しなければならないサイズが抑えられ、高速化が期待できます。

全体でのパフォーマンスについてですが、次のようなベンチマークを行ったところ

require ‘pstore’

p = PStore.new(“foo”)
p.transaction { p[“hoge”] = “hoge” * ARGV.first.to_i }

10000.times do
p.transaction { p[“hoge”] += “hoge” }
end

現在のPStoreでは

% time ruby pstore_bench.rb 1000
ruby pstore_bench.rb 1000 2.94s user 2.43s system 69% cpu 7.723 total
% time ruby pstore_bench.rb 10000
ruby pstore_bench.rb 10000 5.37s user 2.99s system 70% cpu 11.810
total
% time ruby pstore_bench.rb 100000
ruby pstore_bench.rb 100000 31.98s user 11.09s system 69% cpu 1:02.15
total

となったのに対して上記の変更を加えたPStoreでは

% time ruby pstore_bench.rb 1000
ruby pstore_bench.rb 1000 1.67s user 0.44s system 99% cpu 2.119 total
% time ruby pstore_bench.rb 10000
ruby pstore_bench.rb 10000 3.24s user 0.63s system 99% cpu 3.876 total
% time ruby pstore_bench.rb 100000
ruby pstore_bench.rb 100000 14.29s user 3.13s system 100% cpu 17.416
total

となり、パフォーマンスの向上がみられました。
扱うデータのサイズが大きいほど差は開くものと思われます。

パッチを添付しました。
変更後もtest-allをパスします。

よろしくお願いします。
=end