スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

--.--.-- | スポンサー広告

[Lua] Luaでの文字列生成速度とガーベージ

以前Luaのガーベージコレクションの効率に関して、こちらのような記事を書いたのですが、
某スレッドでそれに対する反応と思われる書き込みを発見。割合気になる話でしたので、検証してみました。

引用させて頂きますと・・・


848
”..”とか使って生成た文字列が以前生成した文字列と内容が
同じな場合、以前の文字列に参照を追加して同じ文字列を複数
生成されない最適化が行われてるみたいね(多分)。
ただ、文字列が多くなると以前の文字列との比較に時間がかかって
しまい文字列生成のパフォーマンスが徐々に落ちてくるっていう、
マイナス面もあるみたい。
某所のGCパフォーマンス調査で文字列を大量に生成&破棄を
繰り返して調査してたけど、GCよりも文字列生成のパフォーマンス
を調査してるようなもんだと思った。



なになに?:-)



850
>>848
Lua 内で利用する文字列はすべて、参照時に「以前と同じ文字列があるかどう
か」をチェックしているよ。生成する経路はべつに関係ない。
またそのチェックはハッシュだから、理想的には文字列が増えてもパフォーマ
ンスはそれほど落ちない。

ただ、大量生成&破棄の繰返しの場合、ハッシュテーブルの再構成や再配置が
頻発すると思うので、そのコストが効いてくるんじゃないかと推測するがどう
か。


私もそんな風に思ってました。


852
>>850
私が試したコードは
collectgarbage("stop");
for i=1,50000 do;a=i.."aaaa..(ここ沢山)..a";end
です。長い文字列に関しては全文字がHash計算対象ではないので
Hash値が一致する文字列が多くなり、最後の文字列全比較に時間が
かかっているのではと考えています。


なるほど、その可能性は否定できませんね。文字列のバイト単位の直接比較をしているとすると、相当な負荷がかかってもおかしくありません。
実際、例のGCテストでは、大量に生成した文字列を「ガーベージ」としてテストを行っています。

ガーベージコレクションの試験ですから、共有されない、ユニークなデータをたくさん生成する必要があるということで、以下のような方法でユニークな文字列をガンガン生成したわけですが、この状況がかなりLuaにとって不利な「特異状況」を作り出していた可能性があります。



for i=0,50000 do
-- some heavy trash
local text = tostring(i)..[[;eofih;afowicmaafcloaj,
wcf;wtcopiaujwetpcmoahwfgmpciauhwefmpcfhcaiouhcfg
maiouefhmcpoaihwefmcpoaihcfm;oaiwtcm;oaiuwerm;oci
auwermc;auiopwe,r;cwuioefmco;awuio;iweuxm;oaixmoai
whfmx;aoiwhfxam;oifhmax;oif]]

t[math.mod(i,100)] = { [text] = i } -- max 100 item alive

if math.mod(i,interval) == 0 then
collectgarbage(threshold)
end
end


VCでプロファイルをとると、たしかに文字列生成関数luaS_newlstr()の内部でほとんどの時間(約80%)を消費していることがわかりました。
ついでにCodeAnalystで調べてみました。

LuaGCテストをCodeAnalystで解析


ここのループでは、以前使った文字列の中に新しい文字列と一致するものがないかどうか、ハッシュテーブルをチェックしているようです。なるほど、ハッシュが一致する文字列群をmemcmpで比較しているところにサンプルが集中しています。


それと、ハッシュ値の計算方法としては、長い文字列(64文字以上)の場合は一定のステップで文字をかいつまんでハッシュを計算しています。上のテストコードのような文字列のつくり方をしていると、文字列のうちほとんどが同じ値のため、ハッシュ値が一致する文字列が非常にできやすい状況です。

どうもLuaの文字列生成部にとって最悪の状況を作ってしまったようです。




GCテストプログラムで文字列を生成するのをやめて数値を含んだテーブルなどにしたところ、
ガーベージが多くても(100MBとか)ほとんどパフォーマンスが劣化していないことがわかりました。
文字列バージョンに比べれば100倍以上高速といった感じです。

また、文字列でも64文字以下であれば比較的高速です。


結論としては・・・

・64文字以上で、
・かつハッシュ値が一致する(ほとんどの文字が一致するが、一部だけ異なる)ような文字列が
・大量(1000個以上)に生成され、ガーベージコレクトされていない

というような状況で、Luaの文字列生成は非常に遅くなる、ということになります。


ガーベージが溜まりっぱなしの状況での実行結果をまとめてみました。
(Lua5.0の場合ですが、Lua5.1でも大きくは変わらないものと思います。)

ガーベージの種別による実行結果(50000個生成)
文字列(200文字程度で、一部だけ異なる):200.765sec
文字列(70文字程度で、一部だけ異なる):12.625sec
文字列(50文字程度で、一部だけ異なる):0.921sec
数値:0.234sec


前回のガーベージコレクションテストの有効性に関しては、
たしかに結果としては非常に(x100ぐらい)誇張されたものですが、
逆にガーベージのたまり具合がシビアにわかるという意味はあったような気もします。

とはいえ、Luaのガーベージの問題が大きく見えすぎるという点ではあまり良くないテスト方法
だったかもしれませんね。

Luaで文字列処理を行う場合には上記のような状況を作らないように注意して頂くと良いかと思います。



テストしたコードはこんな感じ。

local t = {}

-- make trash
local threshold = 100000
collectgarbage(threshold)
for i=0,50000 do
-- some heavy trash

-- 200文字程度の文字列
local garbage = i..[[;eofih;afowicmaafcloaj,
wcf;wtcopiaujwetpcmoahwfgmpciauhwefmpcfhcaiouhcfg
maiouefhmcpoaihwefmcpoaihcfm;oaiwtcm;oaiuwerm;oci
auwermc;auiopwe,r;cwuioefmco;awuio;iweuxm;oaixmoai
whfmx;aoiwhfxam;oifhmax;oif]]

-- 50文字程度の文字列の場合
--local garbage = i..[[012345678901234567890123456789
012345678901234567890]]

-- 70文字程度の文字列の場合
--local garbage = i..[[012345678901234567890123456789
0123456789012345678901234567890123456789]]

-- 数値の場合
--local garbage = i

t[math.mod(i,100)] = { garbage } -- max 100 item alive

if math.mod(i,1000) == 0 then
local a,b = gcinfo()
io.write("["..i.."|"..a.."]")
end
end

print( "\nclock="..os.clock())



スポンサーサイト

テーマ:プログラミング - ジャンル:コンピュータ

2006.09.10 | Comments(0) | Trackback(0) | Lua

新しい記事へ <<  | HOME |  >> 古い記事へ

広告:

カテゴリ展開メニュー

  • 未分類(13)
  • Lua(38)
  • プログラミング(11)
  • 食べ物(3)
  • SPAM(2)
  • ゲーム開発(4)
  • GIS/GPS/GoogleMaps(2)
  • スポーツ(1)
  • Skype API(1)
  • AR(1)

はてブ ランキング

ブログ全体: このWikiのはてなブックマーク数

プロフィール

はむ!

Author:はむ!
よく使う言語・環境:
C++,C,Lua,java,VBA,DB
たまにPHPとかjavascript
血液型:O型

メール: lua%ham.nifty.jp
(%を@に変えてください)
ついったー: @hammmm

Lua関連アンテナ

ブロとも申請フォーム

この人とブロともになる

全記事表示リンク

全ての記事を表示する

ブログ内検索


上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。