[解決済み] 最後の手段としてのパフォーマンス最適化戦略【終了しました

質問

このサイトにはすでにたくさんのパフォーマンスに関する質問がありますが、ほとんどすべてが非常に問題に特化した、かなり狭い範囲での質問であることに思い当たりました。そして、ほとんどすべてが、早すぎる最適化を避けるためのアドバイスを繰り返しています。

と仮定してみましょう。

• このコードはすでに正しく動作しています。
• 選択されたアルゴリズムが、問題の状況に対して既に最適である。
• コードが測定され、問題のあるルーチンが特定されました。
• 最適化のためのすべての試みは、問題を悪化させないように測定されます。

私がここで求めているのは、重要なアルゴリズムにおいて、何が何でも最後の数パーセントまで絞り出すための戦略やコツです。

理想的には、言語にとらわれない回答を心がけ、提案された戦略の欠点があれば、それを示してください。

私自身の最初の提案と、Stack Overflowコミュニティの他のどんな考えも楽しみにしていることを返信します。

どのように解決するのですか？

さて、改善の余地があまりないと思われるところまで問題を定義していますね。私の経験では、これはかなり稀なことです。私は、1993年11月のDr. Dobbsの記事で、このことを説明しようとしました。明らかに無駄のない、従来よく設計された非自明なプログラムから始めて、壁時計時間が48秒から1.1秒に、ソースコードのサイズが4分の1になるまで一連の最適化を行いました。 私の診断用具 はこれでした . 一連の変更はこうだった。

• 最初に見つかった問題は、リストクラスタ（現在は、"イテレータ"と"コンテナクラス"と呼ばれています）の使用が半分以上の時間を占めていることでした。これらをかなり単純なコードに置き換えることで、所要時間は20秒に短縮されました。

• 今、最も時間がかかっているのは、リスト作成です。割合としては、以前はそれほど大きくなかったのですが、今はより大きな問題が取り除かれたからです。私はそれをスピードアップする方法を見つけ、時間は17秒に低下します。

• 今度は、明らかな原因を見つけるのが難しくなりましたが、いくつか小さな原因があり、それを何とかすることで、時間は13秒に短縮されました。

今、私は壁にぶつかったようです。サンプルは何をしているかを正確に教えてくれているのですが、改善できる点が見つからないようなのです。そこで、このプログラムの基本設計、つまりトランザクション駆動型の構造について考え、このプログラムが行っているすべてのリスト検索は、実は問題の要件によって義務付けられているのではないか、と問いかけました。

そこで私は、プログラムコードをより少ないソースから（プリプロセッサ・マクロによって）実際に生成し、プログラマが予測可能だと知っていることをプログラムが常に把握しないようにする、という再設計を思いついたのです。言い換えれば、やるべきことの順序を「解釈」するのではなく、「コンパイル」するのです。

• その再設計が行われ、ソースコードが4分の1に縮小され、時間も10秒に短縮されました。

さて、あまりに早くなってしまったので、サンプルにしにくいので、10倍の仕事量を与えていますが、以下の時間は、元の仕事量に基づくものです。

• さらに診断すると、待ち行列管理に時間を費やしていることがわかります。これらをインライニングすることで、7秒に短縮されます。

• いままでやっていた印刷の診断が大きなタイムテーパーになっています。これは4秒で終わります。

• 現在、最も時間を消費するのは、以下のコールです。 マロク と フリー . オブジェクトのリサイクル - 2.6秒。

• サンプリングを続けていると、やはり厳密には必要ない操作が見つかる - 1.1秒。

トータルの高速化要因 43.6

しかし、玩具以外のソフトウエアでは、いつもこのような経過をたどっています。まず簡単なものから始めて、次に難しいものに挑戦し、やがて収穫が少なくなってくる。そして、得られた知見によって設計が見直され、新たなスピードアップのラウンドが始まり、再び収穫逓減のポイントに到達するのでしょう。さて、このような状況になったとき、果たして ++i または i++ または for(;;) または while(1) の方が早いです。Stack Overflowでよく見かける質問です。

追伸：なぜプロファイラを使わなかったのかと思われるかもしれません。その答えは、これらの"問題"のほとんどすべてが、スタックサンプルがピンポイントで特定する関数呼び出しのサイトであったからです。プロファイラは、現在でも、関数全体よりもステートメントやコール命令の方が重要であり、修正しやすいという考え方にようやく近づいてきたところです。

私は実際にこのためにプロファイラーを作りましたが、コードが何をしているのかについて、本当の意味で親密になるには、自分の指で直接触れることに勝るものはないのです。サンプル数が少ないことは問題ではありません。なぜなら、発見された問題のどれもが、簡単に見逃してしまうような小さなものではないからです。

追記：jerryjvlさんから、いくつかの例をリクエストいただきました。これが最初の問題です。これは少数の別々のコード行から構成されており、合わせて半分以上の時間を費やしています。

 /* IF ALL TASKS DONE, SEND ITC_ACKOP, AND DELETE OP */
if (ptop->current_task >= ILST_LENGTH(ptop->tasklist){
. . .
/* FOR EACH OPERATION REQUEST */
for ( ptop = ILST_FIRST(oplist); ptop != NULL; ptop = ILST_NEXT(oplist, ptop)){
. . .
/* GET CURRENT TASK */
ptask = ILST_NTH(ptop->tasklist, ptop->current_task)

これらはリストクラスタILST（リストクラスに似ている）を使用していました。これらは通常の方法で実装されており、quot;information hiding" つまり、クラスのユーザはそれらがどのように実装されているかを気にする必要はないはずでした。これらの行が書かれたとき（およそ800行のコードのうち）、これらがボトルネックになるという考えはありませんでした（私はこの言葉が嫌いです）。これは単に推奨される方法なのです。簡単に言うと 今にして思えば しかし、私の経験では、これらは避けるべきでした。 すべて パフォーマンスの問題というのは、そういうものなんです。一般的に、パフォーマンスの問題を作らないようにするのは良いことです。また、（後から考えると）避けるべきであったにもかかわらず、発生した問題を発見し修正することは、さらに良いことです。このように、少しはご理解いただけたでしょうか？

ここで、2つ目の問題を2行に分けて説明します。

 /* ADD TASK TO TASK LIST */
ILST_APPEND(ptop->tasklist, ptask)
. . .
/* ADD TRANSACTION TO TRANSACTION QUEUE */
ILST_APPEND(trnque, ptrn)

これらは、リストの末尾に項目を追加することでリストを構築しています。(修正方法は、項目を配列に集め、リストを一度に構築することでした)。興味深いのは、これらの文は元の時間の3/48しかかかっていない（つまり、コールスタック上にある）ので、実際には大きな問題ではないことです。 はじめに . しかし、最初の問題を取り除いた後は、3/20の時間がかかるようになり、より大きな魚となったのです。一般的には、そういうものです。

このプロジェクトは、私が実際に手伝ったプロジェクトからの抜粋であることを付け加えておきます。そのプロジェクトでは、タスクが終了したかどうかを確認するために内部ループ内でデータベースアクセスルーチンを呼び出すなど、パフォーマンスの問題は（スピードアップも含めて）はるかに劇的なものだったのです。

の参照を追加しました。 オリジナルと再設計の両方のソースコードは、以下のサイトにあります。 www.ddj.com 1993年版は、ファイル9311.zip、ファイルslug.asc、slug.zipに収録されています。

edit 2011/11/26: 現在では SourceForgeプロジェクト Visual C++のソースコードと、そのチューニング方法の一通りの説明が含まれています。上記のシナリオの前半部分しか行っておらず、全く同じシーケンスにはなっていませんが、それでも2-3桁のスピードアップを実現しています。