Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

speed高速化

speed高速化
by

rti 7743

on 28 April 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of speed高速化

高速化 高速化の哲学 最速のプログラムとは何か。 int main()
{
return 0;
} 最速!! この状態から余計なものを
いろいろつけるから重くなる。 よって、何もしない領域に
近づけば近づくほど
プログラムは最速となる。
余計なことをやるから重くなる。

余計なことをやらなければよい。 いかに余計なことをやらずに
問題を解決するか ループとか、
データコピーとか、
再起呼び出しとか。 三分クッキング どー見ても3分で作れない、
料理をどうやって3分で作るか。 三分クッキングがなぜ三分でできか。 →作り置き(キャッシュ)があるから。 ・アプリケーションの特性を生かした最適化を行う。
読み込みが多い -> キャッシュ 、リードライトロック

毎回計算させるのが大変 -> 事前に計算しておく
(キャッシュ、ルックアップテーブル)

オブジェクトを毎回作りたくない ->
プール(スレッドプール、メモリプール等が有名)




・富豪的プログラミング
ディスクが遅い -> オンメモリ
64bit化で膨大なメモリが使える。
メモリ4ケタは当たり前の時代に

・アルゴリズムの見直し
バブルソート -> クイックソート
全件サーチ -> バイナリサーチ -> indexサーチ (ハッシュ or tree)
全件読み込み -> 部分読み込み

・発想の転換
高速に大量のデータを転送したい -> ハードディスクを持って走る


・最適化しやすい仕様に変えてしまう
設計者が開発を分かっていないと設計できない理由の一つ キャッシュ最強 オカルト マルチコア/メニイコア
時代の高速化 今までの時代は
これだけでよかった。 しかし、
時代はマルチコア/メニイコアに 小型への物理的限界
に近づきCPUの
クロック数が
頭うちになってきた。

数で勝負といわんばかりに、
CPU4コア*HT = 8コアのマシンとかが
ふつーになってきた。 いかにマルチコアで
スケールさせるプログラムを
作るかが重要になってきている。 複数スレッド、複数プロセスが同時に協調して動作するプログラム スレッド ・OSネイティブなスレッド

・言語のスレッド
C++0x から C++もスレッドに対応

・コンパイラ拡張?
OpenMP

・その他 GPGPU
Nvidia -> Cuda
例:長崎大学のスーパーコンピュータ ロックを避ける 並列動作しない部分で
全体のパフォーマンスが
低下する アムダールの法則 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 F 並列できない箇所の割合
N コア数 いかにロックをなくすか。 並列動作を前提としたアルゴリズム ロックフリー・アルゴリズム ・並列ソート
ソートといえば クイックソートだったが、
並列可能なソートアルゴリズムの到来で地位が揺らぐ。 http://lab.klab.org/wiki/Erlang_Performance より http://www.nicovideo.jp/watch/sm2415630
Lock-free Queueについて より ロックが必要なアルゴリズムをロックなしで動作させる。

CAS(Compare-and-Swap)命令 cmpxchg で実装。

#windows APIでいうところの InterlockedCompareExchange みたいもんか? アルゴリズムのパラダイムシフトが
起きている感じがする 複数台構成 どんなにがんばっても、
一台のマシンで処理できることは
目に見えている。 平凡なマシンを
複数代のつなげてやればよくない? 一台のマシンで超高速にすればいい。
そんな風に考えていた
時期が俺にもありました。 高性能なマシンは高い。 どうやって、
複数台のマシンで動作させるのか? ・ノード間のデータやり取りと排他の問題

・ノード間のコミニュケーションの問題 ・一つの仕事をいかに分割してノードにやらせるか。

・いかにして同期を取るか。
リードはいいけど、ライトの分散がやりづらい。

・コミニュケーションを高速に行う方法 ここら辺は、、、
サーバ設計、
ネットワーク設計も絡んでくる話になる。 つまり、、
最強に早いプログラムを作るには
プログラムテクニックやアルゴリズムはもちろんのこと、
インフラが分かっていないとダメだということですね :p)
まとめ ・早くするには余計なことをやらないこと

・高速化にはアルゴリズム戦略が大切。

・ツールを使って計測する

・スレッドやプロセスと同期に注意すること。

・複数台構成も視野に入れた設計を。
えんいー\e ツール 重い処理をどう見分けるか
-> プロファイラ
C++ フリー/有償/高いVC++には標準搭載
php xdebug

アプリケーション全体で早くなったか確認する
-> ベンチマーク
ダメな最適化 この辺が遅い気がする 大切なこと:
計測し、
ネックを判断すること 早くなった気がする プロファイラで調べれば、

関数ごとの呼び出し回数、
平均的な実行時間を教えてくれる。
呼び出し回数が多くて、
実行時間が長い関数を直す。
→すべて直す必要はない。 80/20の法則
(パレートの法則) 20%のルーチンが
80%の実行時間を使っている。 効率的な最適化を by rti DBとwebアプリ の、話は落ちました。
また今度。 ヴィルフレド・パレートさん イタリアの経済学者 つまり、
上位20%の部分を直せば
残りの80%の部分に恩恵がある(かも) http://www.gotw.ca/publications/concurrency-ddj.htm より http://rtilabs.net/ ソート時間の比較 より
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/speed-compare.html ソートアルゴリズム MapReduce/Hadoopなどが有名 とあるログ集計の事例 1台のマシン 19台のスレーブと
1台のマスターからなる
Hadoop 6時間6分35秒 5分34秒 Hadoopで、かんたん分散処理より
http://techblog.yahoo.co.jp/cat207/cat209/hadoop/ クラウドでHadoop http://business.nikkeibp.co.jp/article/tech/20100416/214016/ クックパッドのデータ処理、たった5万円 ・アーキテクチャ依存の最適化
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 コンパイラなどを利用する 最適化の種類 アルゴリズム(戦略)の最適化 >>>>>>> ルーチン(戦術)の最適化 (早い) >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 最適化なし ルーチンの最適化 アルゴリズムの最適化 仕組み(アルゴリズム)を変えずに
個々レベルの底上げを行う。 仕組み、やり方、考え方を変えてしまう SSE memcpyの最適化 連載1 高速なメモリーコピー その7より
http://amalabo.blog35.fc2.com/category8-2.html
Full transcript