2011/05/02

速く動くコードの書き方

オリジナルはassertTrue(): How to write fast code、以下の翻訳は 速く動くコードの書き方 - Radium Softwareより。

「CPUというものは……」

彼は言った。

「ある一定の速度で動く。それは１秒間に決まった数の命令を処理することができるが、それ以上はない。１秒間に実行される命令の数には有限個の上限が存在するわけだ。そうだな？」

「そうです」私は言った。

「つまり、コードを速く動かす方法なんでものは存在しないんだ。命令を速く実行する方法が無いんだからな。唯一あるのは、マシンがやることを少なくするということだけだ。」

彼は強調するために間を置いた。

「速くするには」彼はゆっくりと言った「少なくしろ」

まあ正論だけど、 現代においては「遅いのはただただCPUが待ってるから」ってことも 多々あるからなあ。それもトロい別コンポーネントを待ってるってだけじゃなくて、 速いCPU同士がお互いの足を踏み合ってるとか。

「CPUが実行できる有限個の上限」に達すること自体が、かなり難しいゴールなわけで。 (部分的にCPU-boundなボトルネックを見てるだけなら別だけど)。 マシン(あるいはその集合)を各コンポーネントからなるチームと考え、 「いかにチームワークを良くするか」ってとこも重要だよなあ。

とは言え、既に答えがわかっているなら計算せずに答えだけ書いておけばコストはゼロ、 なのだから、大きな意味で、必要の無い計算をしないってのはやっぱり大前提か。 O(n)で済むところをO(n^2)使ってるとかは明らかに改善の余地ありだし。

ただ、コードの字面だけ見て「ここ無駄な計算してるから節約しよう」と 思っても実はCPUの待ちが増えるだけで効果無かったりとかよくあるから、 ひとつの規則を当てはめるのは難しい。

Tag: Programming