Open yumetodo opened 8 years ago
KCS_CUI -i "sample\3-5.json" "sample\3-5 high.map" -f 0 0 -n 10000 -t 4 -o output.json
のプロファイル結果です。
Hot Pathは確認されていたかもしれませんが、Functions With Most Indivisual Workも重要です。
mainCRTStartup
は後述しますが起動時のCSV処理の部分です。
まずVisual C++版std::vector
のcapacity()
管理はかなり酷いです。
std::vector<int> v;
std::wcout << L"vector.size() = " << v.size() << L", vector.capacity() = " << v.capacity() << std::endl;
v.push_back(1);
std::wcout << L"vector.size() = " << v.size() << L", vector.capacity() = " << v.capacity() << std::endl;
v.push_back(1);
std::wcout << L"vector.size() = " << v.size() << L", vector.capacity() = " << v.capacity() << std::endl;
v.push_back(1);
std::wcout << L"vector.size() = " << v.size() << L", vector.capacity() = " << v.capacity() << std::endl;
v.push_back(1);
std::wcout << L"vector.size() = " << v.size() << L", vector.capacity() = " << v.capacity() << std::endl;
v.push_back(1);
std::wcout << L"vector.size() = " << v.size() << L", vector.capacity() = " << v.capacity() << std::endl;
v.push_back(1);
std::wcout << L"vector.size() = " << v.size() << L", vector.capacity() = " << v.capacity() << std::endl;
v.push_back(1);
std::wcout << L"vector.size() = " << v.size() << L", vector.capacity() = " << v.capacity() << std::endl;
これの実行結果が
vector.size() = 0, vector.capacity() = 0
vector.size() = 1, vector.capacity() = 1
vector.size() = 2, vector.capacity() = 2
vector.size() = 3, vector.capacity() = 3
vector.size() = 4, vector.capacity() = 4
vector.size() = 5, vector.capacity() = 6
vector.size() = 6, vector.capacity() = 6
vector.size() = 7, vector.capacity() = 9
となっていて、capacity()
が増えるたびにoperator new[]
が呼び出されているわけです。サイズをある程度見積もってreserve()
するだけでstd::_Allocate
、operator new
の呼び出し回数を削減できるでしょう。
更にはstd::_Allocate
、operator new
、std::vector::vector
、これらは個別の関数ですがよくよく見るとstd::vector
コピーコンストラクターの延長上で呼び出されるもので、要するにシミュレーション全体の20%はstd::vectorの操作とコピーということになります。意図しないstd::vector
コピーが大量に発生しているのではないかと。
std::vector
のコピーが発生しているということはWeapon
、Kammusu
、Fleet
辺りのオブジェクトもコピーされまくっているということで、ところどころにあるmove()
はほとんど効いていません。その結果、CSV読み込み部分もかなりのコピー&deleteとなっていて処理コストが上がっています。
@sayurin そこは見てなかった。 どんだけお粗末なんですか、capacity管理・・・。
なんかstd::vectorがやたらコピーされてますよね。なんでだろ。
moveが効かないというのは
とかかなぁ、どれも考えにくいけど
いっそvectorは全部sheard_ptrに放り込んでしまおうか・・・
というかそもそもWeapon
, Kammusu
, Fleet
クラスがコピーorムーブされる場面ってDBからのGet以外でどこにありましたっけ
@yumetodo
vector
のcapacity()
拡大時に新しい領域へムーブですね。ほかにもvector
への格納
v[i] = val;
がoperator=()
によるコピーですね。で、Fleet
のコピーが走るとメンバーに持つvector
のコピー、そしてKammusu
、Kammusu
のvectorメンバー、'Weapon`とコピーが波及します。
@sayurin ちょっと該当箇所をぱっと見つけられないですが、それ、前にemplace_backとかmoveしようとして失敗した記憶がある。
@YSRKEN
Simulator::DetermineAttackOrder
のstable_sort、本当にstable_sortじゃないとダメですか?
というか真面目な話capacity固定size可変のpush_backできるstd::arrayが欲しい。sprout::stringみたいな
ベンチしたけど https://github.com/YSRKEN/KanColleSimulator_KAI/commit/9403c0ec226ebb97f55d5dd4dcd1a17884999741 やはり誤差程度にしかならないね
mtより高速な疑似乱数へ変更します? Google Chromeで採用された https://ja.wikipedia.org/wiki/Xorshift とかあからさまに軽いですし。
たしかにそのほうがいいかもしれない http://d.hatena.ne.jp/gintenlabo/20100925/1285432088 http://d.hatena.ne.jp/gintenlabo/20100930/1285859540 http://kudannlab.blogspot.jp/2013/12/c11.html http://kitayuta.hatenablog.com/entry/2014/11/15/230145
のように実装例もあるし、簡単に実装できそう(著作権無視すれば)。
問題はLICENSE・・・。もっというと、誰が書いても同じだからLICENSEなんざねぇ!とゴリ押せるかどうか。
-n 10000
シミュレーションでWeapon::name_
のコピーが2,000,000回行われているんですが、これを削減するには #62 を前提にせざるを得ないです…。これも10%くらいは早くなるかと。
http://kitayuta.hatenablog.com/entry/2014/11/15/230145 の作者と https://twitter.com/kitayuta この人同一人物かなぁ・・・。それなら許可取ってまるパクしたい
うん同一人物だな (出典)http://qnighy.hatenablog.com/entry/2012/08/30/231559
@YSRKEN kitayuta氏にXorshiftのコードの使用許可取りにTwitterに凸しますか?
stable_sortについての指摘がありましたが、「シャッフル後、射程順に安定ソート」と「シャッフル後に、射程順に不安定ソート」が統計的に同等と見なせる場合には安定でなくとも構いません。
そもそもシャッフルしたものを順序保証する必要があるのかという・・・・。 @sayurin どう思います?
そもそも1艦隊6隻ですよね? 要素数が少ない場合、複雑なアルゴリズムよりも簡単アルゴリズムの方が早い(≠速い)かと。 Visual C++でいうと要素数32以下では挿入ソートを使うようになっているので、これで十分に思います。
要素数32以下では挿入ソート
それでならそれでいいか。
split
を再発明した理由は
vector<wstring>
中間オブジェクトを避けたいvector
のcapacity()
管理がひどい(結果オブジェクトと中間オブジェクトに効く)constexpr
で置き換えたいですね。
template
化するなら未確認ですがこんな感じですかねぇ…
template<class String, class Separator, class Converter>
auto split(const String& str, const Separator& separator, Converter converter) {
std::basic_stringstream<String::value_type, String::traits_type, String::allocator_type> ss{ str };
String element;
std::vector<decltype(std::invoke(converter, element))> result;
while (std::getline(ss, element, separator))
result.emplace_back(std::invoke(converter, element));
return result;
}
// split(line, L'.', std::stoi);
stringstreamが重いと思うんですが。find_first_ofのほうが
削減すべきはメインループ内で何百万回も実行されている処理であって、初期化処理についてはこだわらずにセオリー通りでいいかなと思って書きました。
まあそうですけど、costexpr化することを見越すならfind_first_ofで書いたほうがいいかなと思いました。区切り文字が複数の場合がちょっと面倒ですけど
ここの進捗はどのような感じでしょうか?
splitに関しては深夜テンションで書いた結果恐ろしいコードになったものがこちらです https://gist.github.com/yumetodo/936010a8ab2370e71368 区切り文字1文字の時のほうはsproutあればconstexprにできると思います。
一応、ばっさばっさと軽くする個所は確認できていますが、 #71 をベースとせざるを得ないので手を出せずにいます。
そうですね・・・。
そういえば文字列splitに関しては https://github.com/yumetodo/string_split で真面目に高速化したものを作りました。 @sayurin 氏が指摘していた中間オブジェクト問題も綺麗サッパリ消えました。
@yumetodo さん、メインループはシミュレーション試行回数であり100,000回とか回し、更に内側でも大量のループが存在します。それに対し、文字列操作は所詮外部入力の初期化処理で具体的には500回程度しか実行されません。つまり200倍以上の高速化でなければそもそも土俵にすら上がれません。その上で当該処理が実行時間に対して支配的でなければたいした効果は得られません。そういう意味では直大さんの https://twitter.com/chokudai/status/762660240969969665
「Stringを+=で何度も結合してる!クソコードだ!」みたいなこと割と言われるけど、そこがボトルネックにならない時だけ使ってるんだからええやん、って言いたいことが殆どである。アルゴリズム判らん人のほうが無駄なところの速度を早くしたがる傾向がある。
と同じ状況です。
@sayurin 氏が指摘していた中間オブジェクト問題も綺麗サッパリ消えました。
中間オブジェクトはなにもvector
だけではありません。必要がなければstring
も作らない方がいいでしょう。std::sub_match
みたいな持ち方をすることでstring
インスタンス化は呼び出し側に任せ、std::regex_token_iterator
みたいな返し方ができたらいいなと思ってます。
@sayurin 文字列分割についてはこのプロジェクトからは完全に独立していて、必要があれば取り込めばいい程度のものです。
中間オブジェクトはなにもvectorだけではありません。必要がなければstringも作らない方がいいでしょう。
そういえばQiitaでstring_viewつかおうみたいな事言われた・・・。
@YSRKEN https://github.com/YSRKEN/KanColleSimulator_KAI/issues/119#issuecomment-256243084 で言っていたハッシュ化及びsproutへの依存追加やります?そこはかとなく前のReleaseより速度落ちている気がしているので・・・
うーん、どうしましょう。Ver.2.1.1からかなり長い期間経ってしまっているので、とりあえず先にVer.2.2.0を出しておきたい気持ちがありますわね
なんかあまりVer.2.1.1からユーザー的には #155 除けば変化がないような気がしてきて・・・。コーディングする上ではだいぶ変わっているんですが。計測できてないけどどのくらい実行速度変化しているのかな・・・。もし遅くなってたらハッシュ化はしてからにしたい。
乱数の範囲調整を高速化できないか(よく使うdistribusionをキャッシュするとか(_Evalのほうが時間かかってるからあまり意味ない?))RandBoolの高速化(50%の確率の時、distribusionをキャッシュしたら早くなったりしないか)Simulator::DetermineAttackOrder
のpush_backの前にreserve
Simulator::AirWarPhase
のvector<int> anti_air_score
をarrayにFleet::RandomKammusuSS
のvector<size_t> list
,vector<KammusuIndex> alived_list
のarray化Simulator::TorpedoPhase
のvector<vector<int>> all_damage
のarray化Fleet::SearchValue
の高速化(無理じゃね?)Simulator::Calc
のreturn文のstd::make_tupleでvectorがコピーされている・・・?Result::JudgeWinReason
からvectorを排除するどんぶり勘定で計算時間の半分以上が乱数生成なのでネタ切れ感がある。重たかった文字列検索は @sayurin 氏のpull requestをマージしたことでぐんと下がったし、シュミレーションの一部キャッシュもそれなりに効いている
高速化の方針?