ロブ・パイクのプログラミング規則（1989年）
(users.ece.utexas.edu)- 1989年のRob Pikeによる、プログラミングの5つの規則に関する記事
- 規則1: プログラムがほとんどの時間をどこで費やすかを決めつけてはならない。ボトルネックは予想外の場所で発生しうる。ボトルネックが実証されるまで速度ハックは避けよ。
- 規則2: 速度のためにチューニングする前に、必ず測定せよ。コードの一部が残りに大きな影響を与える場合にのみ最適化せよ。
- 規則3:
nが小さいとき、複雑なアルゴリズムは遅い。たいていの場合はこれに当てはまる。nがしばしば大きい場合にのみ複雑なアルゴリズムを使い、その場合でもまず規則2を適用せよ。 - 規則4: 単純なアルゴリズムとデータ構造が望ましい。複雑なものよりバグに弱くなく、実装もしやすい。
- 規則5: 正しいデータ構造はプログラミングにおいて決定的である。データが適切に構成されていれば、アルゴリズムは自明になる。
- Pikeの規則1と2は、Tony Hoareの格言「早すぎる最適化は諸悪の根源である」を反映している。
- Ken Thompsonは、Pikeの規則3と4を「疑わしいときは brute force を使え」と言い換えた。
- 規則3と4は、KISS（Keep It Simple, Stupid）という設計哲学を体現している。
- 規則5は、Fred Brooksの『The Mythical Man-Month』での発言と一致しており、しばしば「賢いオブジェクトを使う愚かなコードを書け」と要約される。
1件のコメント
Hacker News のコメント
「データが支配する」という言葉には完全に同意する
だから LeetCode の面接はいつも妙に感じていた。たいていアルゴリズムに焦点を当てるが、実際には最初からそうアプローチすべきでない場合が多く、データ構造のほうが中心であるべきだ
もちろん、アルゴリズムをまったく知らないと、例外的な状況や特定の理由で特定のアルゴリズムに頼るべき場面に気づけないことはある。それでもアルゴリズムは比較的短く教えられる一方で、どのデータ構造を使うべきかの勘所をつかむほうが、人はより苦手なように思う
その瞬間、「あ、本当にシニアエンジニアが来たな」という空気に変わり、技術的な問題をもっと開かれた形で話すようになって、「ちゃんとコーディングできるか」を証明させようとする態度も薄れる
逆に、良い変化を作ること、マイルストーンの達成、チーム協業で最も苦労したチームは、データ構造とコードアーキテクチャをきちんと作れる人がいない場所だった。フレームワークが全部やってくれて、だめならもっと賢い誰かが作ったプラグインやミドルウェアが解決してくれる、という考え方に慣れた人が増えたように思う
データ構造を避けるエンジニアは自分の足を撃っているようなもので、最も有用な道具の一つを捨てているのだから、日常的に限界が露呈する
たとえばコードは重み付き有向非巡回グラフ(DAG)で最長経路を見つけるのに多く使えるが、核心は問題を重み付き DAGとして表現できると気づくことにあった。それが見えなければ解けるとしても、はるかに遅く複雑な解法になる
面接官が優先度付きキュー、隣接行列、トライのようなものを使うべきだと先に教えてくれるわけではない。行き詰まればヒントはもらえるかもしれないが、過度な誘導は強い採用シグナルとは見なしにくい
「すばらしいアルゴリズムは n が小さいと遅く、そして n はたいてい小さい」という言葉に関連して、最近のプロジェクトで実感したのは、大きな n は思ったよりずっと大きくなり得るということだ
「10万回演算するのだから必ず最適化しなければ」と考えがちだが、コンピュータは速く、10万回の乗算程度ならたいていあまりに速いので深く悩む必要がないかもしれない
何も考えるなと言いたいわけではないが、現代のハードウェアがどれほど狂ったように速いかには、しばしば驚かされる
うっかり二次時間になったコードが本番障害を起こしたのを見たことがあるし、99% のユーザーがいつも小さな n を使うとしても、一部のユーザーはしばしば大きな n に出会って非常に遅いアプリを体験することがある
ほとんどの場合、通常ケースで少し遅く実装が少し複雑になるとしても、二次時間より良いアルゴリズムを選びたい。よくある遅い経路は最適化されるが、まれな遅い経路は開発者自身が踏まずに見逃したり、本番で爆発したりする
もちろん、あまりに複雑なアルゴリズムなら単純な二次時間実装を選ぶこともあるが、デフォルトではできるだけ二次未満にしたい。関連して書いた記事もある: https://kevincox.ca/2023/05/09/less-than-quadratic/
そのため、CPU がメモリに対してそこまで速くなく、コンシューマ向けハードウェアで分岐予測ミスをそれほど気にしていなかった 40 年前には、もっと当てはまっていたのかもしれない
面接のたびに、採用マネージャーは欲しがっているのに、本番の傷をまだ味わっていない LeetCode 初心者がその判断を拒むことが起きる
https://www.frankmcsherry.org/assets/COST.pdf
この 20 年間のコンピュータ性能向上を考えると、その基準を10万に引き上げるのはかなり妥当に思える
「早すぎる最適化は諸悪の根源」という有名な格言は Tony Hoare ではなく、実際には Donald Knuth に由来する言葉であり、最適化一般に反対する言葉として文脈なしに使われることが多い
全文は「小さな効率、たとえば 97% のケースについては忘れるべきである。早すぎる最適化は諸悪の根源である。しかし重要な 3% においては、その機会を逃してはならない」というもの
要点は、影響のある場所に時間を使って最適化せよ、ということ
両方のものとして扱うのがいちばんよさそうだ。おそらく Tony が先に言い、Knuth が整えて出版した可能性がある。必要な文脈を与える長い引用を併記するのは、常によいことだ
ほぼ 50 年前の話だ。当時のプログラミングは今とはかなり違っていた。そのころの「早すぎる最適化」は、「スケーラビリティの高い人気ライブラリをそのまま使おう」ではなく、「このハードウェアでしか動かない理解不能なビット操作アルゴリズムを使おう」に近かった
それは「早すぎる最適化は諸悪の根源」という言葉にすでに含まれている意味であり、格言は「最適化は諸悪の根源」ではない
会社のデータ構造・アルゴリズム面接で、バブルソートが最善だと言うフロントエンド開発者を数えきれないほど見てきた。その場で導出までできる必要はなく、いくつか知っていて、問題に合ったよい選択を言えれば十分だ
「早すぎる最適化をするな」を極端に受け取りすぎて、効率的な方法すら知らないのなら、どこが重要かをどうやって見極めるのか
「データ構造が核心」という話は、データベース では二倍重要になる
DB を愚かなビットの保存箱、あるいはオブジェクト定義の 1:1 の写し程度にしか使わない人は、DB がそれを個人的に受け取ったかのように性能を台無しにしてくると驚きがちだ
ORM が生成した DB スキーマをまた見ることになったら、あまりに早すぎる再会だと思う
問題は、一部または多くの開発者が SQL を知らず、ORM を使うのに必要な DB 知識も持っていないことにある
ORM は、その下に何があるかを理解している必要がある、かなり漏れやすい抽象化だ。それを理解していれば、ほとんどの ORM でもまともなスキーマは作れる
データ構造をうまく整理し、設計が変わってもそうした状態を維持するには、データとコードを組織レベルで分離しなければならない
DB スキーマ設計、ユースケース、その間のマッピングを他の実装から切り離し、このグループが整合性検証なども書くべきだ。組織構造がデータとコードを分離していなければ、コードとデータを分離するのは難しい
私の追加ルールは、小さな 性能の無駄 でも積み重なれば、それぞれは大したことがなくても最終的にはプログラムを遅くする、というものだ
複雑さ、可読性、保守性、実装コストに影響がないなら、性能をただ捨て置くべきではない。他の条件がほぼ同じなら、二つの選択肢のうち遅い方を選ぶのはよくない
また、n が小さいと仮定すれば、ほとんど何でも通用する。しかし n が 100 以下ではうまく動き、10000 以上で破綻するコード、たとえば O(n²) のようなものを使うなら、単に制限を設けるべきだ。小さな n という仮定が崩れたとき、大きなエラーを出して止まる方が、AWS の請求爆弾や停止したプログラムよりましだ
これらの指針のかなり多くは、結局 過剰設計 を防ぐ戦略に行き着く
私の経験では、早すぎる最適化は最も高くつく罠の一つだ。潜在的な問題をあまりに早く回避しようとすると、その前提は検証されないままで、次のチームが不要な複雑さを解消するために高価な解決策を作る羽目になる
学んだアプローチはこうだ。最適化は推測に頼り、初期の推測はしばしば間違う
また、人が過度に複雑なコードを書かないようにするには、自尊心のマネジメント と心理への理解がかなり重要だということも分かった
過剰生産は通常、最悪の無駄と見なされる。不要なものを作るだけでなく、本当に必要なことに使えたはずの労力まで使ってしまうからだ。過剰設計も同じようなものだ
たとえばユーザーが 100 人しかいないのに、いつか 100 万人になったときモノリスを再設計するのは難しいだろうとして、マイクロサービスアーキテクチャ で始めるようなものだ
だからこそ、時間がたつにつれてコードがなぜ柔軟性を失っていくのかから先に対処すべきだ
おおむね良いルールだが、実際には1番はそのままでは成り立たない。
始める時点では、何がボトルネックになるかについての仮説が必要だ。XYZを実装してから何が遅いかを計測して直せばよい、というやり方が常に可能とは限らない。X、Y、Zが結び付いていて、Yを速くするためにXとZを特定の方法で作らなければならないこともあるし、Yがボトルネックになると最初から分かっている場合もある。
後で計測して何が遅いかが分かったとしても、より高速にするためのアプローチに賭ける必要はある。より根拠のある賭けであるほどよい。
良いプログラマは計測するが、何が遅く、何がバグが多く、何がメモリを多く使うかを予測できるので、反復が少なくて済む。性能の振る舞いは予測できない、とルールのように語るのは、優れたプログラマが積み上げてきた経験と技術を無視することになる。
1番を守る過程こそが、ボトルネックを予想するための良い直感に必要な経験と経験的背景を得る最良の方法だからだ。
速度の予測が外れると、プロジェクトの寿命のあいだずっと不要に複雑なコードを抱えることになる。
人はアルゴリズムの速度をしばしば見誤る。コンピュータが時間の99%をDBサーバーからnを取得するのに使っているなら、O(n)とO(n²)が実時間では同じに見えることも多い。
Cで書いたアルゴリズムが、等価なPythonコードより遅いことすらあるが、それはバイトコードコンパイラが賢い最適化をしているからかもしれない。
レガシーコードを高速化する仕事を数多くしてきたが、たいていは思っているよりずっと簡単で、しかも元の作者には明白でなかった理由で遅くなっている。実際には、コードベースが複雑になりすぎて、元の作者がもはや推論できなくなっているために遅いことが多い。私にとっては「遅すぎる」という具体例があるので、実行しながら遅い箇所を観察してデバッグしやすい。
物理オブジェクトが大量にあるビデオゲームを作っていて、経験上、衝突検知が大きな問題になると確実に分かっているなら、ゲームとシステムをそれ中心に設計するのは速度ハックではない。
性能が大きな関心事になると分かっている作業なら、当然計測すべきだ。関心事かどうかを確かめるためではなく、その関心事をどれだけうまく扱えているかを確かめるためである。
新しい要求に対して新しいシステムを作るなら、まず始めてしまってよいことが多いのではないかと思う。作って、テスト・計測して、捨てるかリファクタリングして、また繰り返せばよい。
Rustを例にすると、試作言語とOCaml製のコンパイラから始めて反復してきた。いつかOCamlからセルフホスティングへ移れると分かっていたとしても、それが大きな違いを生んだかはよく分からない。
ユーザーがいなければ、数時間かかる関数でも、最適化すればミリ秒になる関数と比べてなお十分に速い。そういう予測を正確にできることを立証した人がいるのかは、あまり分からない。
5番への反論として、単純なデータの上での複雑なアルゴリズムが、大きな性能向上をもたらし、障害を取り除き、かえって単純化につながることもある。
たとえばBinaryTreeオブジェクトの代わりに、ソート済み配列に対する二分探索を使えば、マージはconcatしてからソートするだけなので単純になり、ポインタがないのでシリアライズが容易で、場合によってはシリアライズ自体が不要になる。配列はディスク上にもメモリ上にも、あるいはmmapでその両方にも置けるし、RAMより大きいデータも扱える。ファイルやマッピングを指すだけですぐ動かすコールドスタートも可能だ。キャッシュ無視（cache-oblivious）の性質もある。
Huffman符号化も例の一つだ。大学ではたいてい木ベースのアルゴリズムとO(n log n)の計算量で学んだが、インプレースな配列ベースでHuffman木を線形時間に構築する方法があることは知らなかった。
もちろん、時間の99%は標準的なコレクションデータ構造を使ってバックエンドのマイクロサービスを作っている。しかし仕事でビッグデータを扱うなら、その時々の流行であるMapReduce系を導入するより、ローカルに大容量ディスクを積んだ単一マシンで処理するほうをはるかに好む。
Rob Pikeなら、まずコードをプロファイリングし、そのうえで気の利いたコードや代替データ構造が本当に速いかどうかを見ろと言っただろう。
この記事は10年以上前にcat-vで初めて読んだが、設計や複雑さへの向き合い方、考え方に消えない影響を受けた。
http://doc.cat-v.org/bell_labs/pikestyle
元のルールは「データ構造が肝心だ」なのに、どうして「賢いオブジェクトを使う愚かなコードを書け」に要約されるのか分からない。
“smart objects”という表現はいまひとつで、元のルールは長くてもずっと良い。