最近のコンパイラには、出力するバイナリコードをより高速に実行できるようにする「最適化」機能が搭載されている。CPUやPCアーキテクチャがより複雑化している近年、コンパイラによる最適化はより注目を浴びるようになっている。 たとえば、現在のCPUはいわゆる「マシン語」のコマンド列をそのまま実行するのではなく、内部でより細かい単位に分解して実行する。このとき、CPUのリソースをより効率良く利用できるよう、場合によってはその順序の並び替えや、並列化が行われる。また、処理を行うデータがキャッシュされているかどうかによっても処理速度が大きく変化する。CPUクロックの向上により、CPUとメモリ間でデータをやりとりする時間についても大きなボトルネックとなるようになったからだ。 このようにCPUの動作が複雑になっている現在、「より速く実行できるコード」を生成するには、CPUの構造やその動作についての知識も必
「N個の要素が与えられて、その中からM個を選んだ順列について何かを計算したい」というときの要素のたどり方って何が最速なんだろう。そしてどれが最速かを調べるベンチマークってどうやって書いたらいいんだろう。まわりのループの部分だけ書いたらコンパイラが「これは何もしていない」とか言って消してしまいそうだし、N個の要素だってうっかりプログラム中に記述するとコンパイルタイムにある程度計算されてしまったりしそうだ。 入力はまぁ、コマンドライン引数で渡すことにしてしまえばいいか。 あとは、なるべく処理時間を食わなくて、かつコンパイラが消さないようななにかを... グローバル変数を1個用意して、それに順列の各値を足すとか?
9,10日と今後の開発計画について議論を行った(非常に中身の濃い議論だった)。高速化等の改善のためには、まず現在のプログラムについて徹底した調査が必要になる。どのような問題を入力したときに、どの部分がボトルネックになるのかについても、いろいろな方法で直接的、間接的に知ることができる。今までのアルゴリズム開発というのは、計算量(CPU 上での演算量に近い)と記憶容量に重点を置いてきていたので、CPU とメモリ間のデータの移動量については考慮されることは少なかった。また、データを参照する範囲、局所性のような概念も取り入れる必要がある。 例えば現在、開発を行いながら同時に公開も行っている最短路問題に対するダイクストラ法を実装したプログラムでは、最小ポテンシャルの点を高速に見つけるために、ヒープやバケットを利用している。ヒープは最小点を見つけるのは大変高速だが、データの更新に非常にデータ参照と書き
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く