DBとwebアプリ
高速化の哲学
最速のプログラムとは何か。
int main()
{
return 0;
}
この状態から余計なものを
いろいろつけるから重くなる。
ループとか、
データコピーとか、
再起呼び出しとか。
よって、何もしない領域に
近づけば近づくほど
プログラムは最速となる。
余計なことをやるから重くなる。
↓
余計なことをやらなければよい。
いかに余計なことをやらずに
問題を解決するか
最適化の種類
アルゴリズム(戦略)の最適化
ルーチン(戦術)の最適化
最適化なし
ルーチンの最適化
アルゴリズムの最適化
三分クッキング
どー見ても3分で作れない、
料理をどうやって3分で作るか。
三分クッキングがなぜ三分でできか。
→作り置き(キャッシュ)があるから。
キャッシュ最強
ツール
重い処理をどう見分けるか
-> プロファイラ
C++ フリー/有償/高いVC++には標準搭載
php xdebug
アプリケーション全体で早くなったか確認する
-> ベンチマーク
ダメな最適化
この辺が遅い気がする
早くなった気がする
オカルト
大切なこと:
計測し、
ネックを判断すること
プロファイラで調べれば、
関数ごとの呼び出し回数、
平均的な実行時間を教えてくれる。
呼び出し回数が多くて、
実行時間が長い関数を直す。
→すべて直す必要はない。
80/20の法則
(パレートの法則)
20%のルーチンが
80%の実行時間を使っている。
つまり、
上位20%の部分を直せば
残りの80%の部分に恩恵がある(かも)
効率的な最適化を
マルチコア/メニイコア
時代の高速化
今までの時代は
これだけでよかった。
しかし、
時代はマルチコア/メニイコアに
小型への物理的限界
に近づきCPUの
クロック数が
頭うちになってきた。
数で勝負といわんばかりに、
CPU4コア*HT = 8コアのマシンとかが
ふつーになってきた。
いかにマルチコアで
スケールさせるプログラムを
作るかが重要になってきている。
複数スレッド、複数プロセスが同時に協調して動作するプログラム
・OSネイティブなスレッド
・言語のスレッド
C++0x から C++もスレッドに対応
・コンパイラ拡張?
OpenMP
・その他 GPGPU
Nvidia -> Cuda
例:長崎大学のスーパーコンピュータ
ロックを避ける
並列動作しない部分で
全体のパフォーマンスが
低下する
いかにロックをなくすか。
並列動作を前提としたアルゴリズム
・並列ソート
ソートといえば クイックソートだったが、
並列可能なソートアルゴリズムの到来で地位が揺らぐ。
ロックフリー・アルゴリズム
ロックが必要なアルゴリズムをロックなしで動作させる。
CAS(Compare-and-Swap)命令 cmpxchg で実装。
#windows APIでいうところの InterlockedCompareExchange みたいもんか？
アルゴリズムのパラダイムシフトが
起きている感じがする
複数台構成
どんなにがんばっても、
一台のマシンで処理できることは
目に見えている。
高性能なマシンは高い。
平凡なマシンを
複数代のつなげてやればよくない？
MapReduce/Hadoopなどが有名
どうやって、
複数台のマシンで動作させるのか？
・ノード間のデータやり取りと排他の問題
・ノード間のコミニュケーションの問題
・一つの仕事をいかに分割してノードにやらせるか。
・いかにして同期を取るか。
リードはいいけど、ライトの分散がやりづらい。
・コミニュケーションを高速に行う方法
ここら辺は、、、
サーバ設計、
ネットワーク設計も絡んでくる話になる。
つまり、、
最強に早いプログラムを作るには
プログラムテクニックやアルゴリズムはもちろんのこと、
インフラが分かっていないとダメだということですね :p)
まとめ
・早くするには余計なことをやらないこと
・高速化にはアルゴリズム戦略が大切。
・ツールを使って計測する
・スレッドやプロセスと同期に注意すること。
・複数台構成も視野に入れた設計を。
えんいー\e
http://www.nicovideo.jp/watch/sm2415630
Lock-free Queueについて より
イタリアの経済学者
ヴィルフレド・パレートさん
http://lab.klab.org/wiki/Erlang_Performance より
F 並列できない箇所の割合
N コア数
アムダールの法則
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%A0%E3%83%80%E3%83%BC%E3%83%AB%E3%81%AE%E6%B3%95%E5%89%87
SSE memcpyの最適化
連載1 高速なメモリーコピー その７より
http://amalabo.blog35.fc2.com/category8-2.html
スレッド
(早い)
・アーキテクチャ依存の最適化
SSE -> movdqa命令でmemcpy系 が早くなる
SSE4.2 -> PcmpIstrI命令で strlen系 が早くなる
参考
http://www.strchr.com/strcmp_and_strlen_using_sse_4.2
http://labs.cybozu.co.jp/blog/mitsunari/2008/06/
fast_strlen_and_memchr_by_sse2_1.html
http://amalabo.blog35.fc2.com/blog-category-8.html
・__fastcall
コンパイラへのヒントだし
・分岐を避ける(パイプライン的な意味で)
やりすぎに注意。コンパイラを信じたい
・ループ展開
やりすぎに注意。コンパイラを信じたい
・より高速なAPIコール
・素直にintel コンパイラなどを利用する
仕組み(アルゴリズム)を変えずに
個々レベルの底上げを行う。
>>>>>>>
http://www.gotw.ca/publications/concurrency-ddj.htm より
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
高速化
仕組み、やり方、考え方を変えてしまう
・アプリケーションの特性を生かした最適化を行う。
読み込みが多い -> キャッシュ 、リードライトロック
毎回計算させるのが大変 -> 事前に計算しておく
(キャッシュ、ルックアップテーブル)
オブジェクトを毎回作りたくない ->
プール(スレッドプール、メモリプール等が有名)
・富豪的プログラミング
ディスクが遅い -> オンメモリ
64bit化で膨大なメモリが使える。
メモリ4ケタは当たり前の時代に
・アルゴリズムの見直し
バブルソート -> クイックソート
全件サーチ -> バイナリサーチ -> indexサーチ (ハッシュ or tree)
全件読み込み -> 部分読み込み
・発想の転換
高速に大量のデータを転送したい -> ハードディスクを持って走る
・最適化しやすい仕様に変えてしまう
設計者が開発を分かっていないと設計できない理由の一つ
by rti
http://rtilabs.net/
ソートアルゴリズム
ソート時間の比較 より
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/speed-compare.html
最速!!
の、話は落ちました。
また今度。
一台のマシンで超高速にすればいい。
そんな風に考えていた
時期が俺にもありました。
6時間6分35秒
とあるログ集計の事例
5分34秒
1台のマシン
Hadoopで、かんたん分散処理より
http://techblog.yahoo.co.jp/cat207/cat209/hadoop/
19台のスレーブと
1台のマスターからなる
Hadoop
クックパッドのデータ処理、たった5万円
クラウドでHadoop
http://business.nikkeibp.co.jp/article/tech/20100416/214016/