9

非常に高速にコンパイルするコンパイラを設計する方法を知りたいです。

最初に、私の質問に対する明らかな誤解を解消させてください。

  1. コンパイラによって生成されるコードの速度について話しているのではありません。生成されたコードを最適化する方法を学習するために利用できるリソースは、すでにたくさんあります。私が見つけるのに苦労しているのは、コンパイラを高速にするための情報です。

  2. また、C++ コンパイラが一般に Java コンパイラよりも遅い理由 (たとえば) についての議論にも興味がありません。特定の言語のコンパイラを高速化するために使用できる手法に興味があります。

  3. また、Microsoft の Incredibuild や Unix の distcc のような分散コンパイル システムについても聞きたくありません。これらのシステムは、より高速なコンパイラを提供するのではなく、より多くのコンパイラを提供するだけです。これは確かに便利ですが、それは私が求めている質問ではありません。単一の CPU 用の高速なコンパイラを設計する方法を知りたいです。

  4. ccache も私が探している答えではありません。これは、コンパイラの使用をまったく回避できるシステムですが、コンパイラが高速になるわけではありません。繰り返しますが、これは便利です。繰り返しますが、それは私が尋ねている質問ではありません。

私の質問が明確になったことを願っています。しかし、おそらくいくつかの歴史がそれをさらに明確にするでしょう。

C コンパイラは非常に低速でした。その後、1986 年に THINK Technologies が Macintosh 用の Lightspeed C を導入し、ほぼ瞬時にプログラムをコンパイルしました。Lightspeed C は、他のすべての C コンパイラよりもはるかに高速で、ほとんど比較できませんでした。(おそらく、Lightspeed C は新世代の超高速コンパイラの最初のものではありませんでしたが、私の経験では最初のものでした。Turbo Pascal は [1983 年] より早く登場しましたが、私はそれを使用した経験がなかったので、方法がわかりません。速度的に比較しました。)

それ以来、多くの高速コンパイラが利用できるようになりました。1980 年代にコンパイラ技術にある種の飛躍があったようで、特にそれを理解しようとしています。ブレークスルーは何でしたか？

答えは簡単かもしれません。Lightspeed や Turbo のような IDE では、統合エディタはすでに RAM にソース コードを持っています。コンパイラがそのデータを使用して動作する場合、コンパイラの中で最も遅い部分であるディスク I/O がなくなります。ソース コードのサイズがメモリ サイズに比べて小さい場合、これはおそらく速度の向上に非常に重要な貢献をします。(当時、RAM のサイズははるかに小さかったが、典型的なプログラムのサイズも同様だった。)

あれですか？それとも、他の重要な革新が関係していましたか? それ以来、コンパイラの速度に重要な改善がありましたか?

4

6 に答える 6

4
  • 1 回のパスで解析できる単純な構文。
  • シンプルなターゲット コード。マシンコードを直接ターゲットにしないと、多くのことを回避できます。
  • まったくコンパイルされていません。主に 1 回限りのスクリプトで高速な実行や設計を必要としない場合は、コードの分析に時間を費やす必要はありません。
  • 繰り返しますが、OS のディスク/キャッシュ管理を賢くしようとしないでください。いまいましいファイル全体を Mmap し、RAM から読み取るかのように読み取ります。仮想メモリがない場合、高速なコンパイルは心配する必要がありません。
  • AST の肥大化したデータ構造のような XML DOM を作成することは避けてください。演算子の優先順位をアニメートする必要はありません。何かをコピーするのではなく、マップされたデータへのポインターを保持します。
  • 高速にしたい場合は、コードをプロファイリングします。いつも。

添加：

  • さまざまな解析方法を学びます。パーサーの作成スキルにあまり自信がない場合は、antlr、lemon などの実績のあるパーサー/レクサー生成ツールを使用してください。
于 2010-09-13T20:06:41.080 に答える
2

1 つの問題は、生成されたコードに対して何を出力するかです。コンパイラの時間を好きなだけ最適化に費やすことができます。率直な世代は、おそらくばかげているように見えるかもしれませんが、時間を節約できます。もちろん、Turbo Pascal と Lightspeed C を使用していた頃は、きちんとした部分は実行可能ファイルを便利に取得することであり、最適化されていることではありませんでした。当時のデスクトップ コンパイラ テクノロジは、メインフレーム コンパイラ テクノロジに大きく遅れをとっていました。

Turbo Pascal と Lightspeed C のもう 1 つの点は、統合です。マルチタスクの家庭用コンピューターが登場する前の時代には特に、これは素晴らしいことでした。私が所有していた最初の C コンパイラ (CP/M 用) とは異なり、エディターで変更を加えて閉じ、コンパイルし、リンクし、実行する必要はありませんでした。これは、複雑なコマンドを入力する必要なく、コンポーネントを高速に実行できることの一部である可能性があります。Gnome デスクトップで複数のターミナルを実行することで、これを複製できます。1 つは vim 用、もう 1 つは gcc を実行するため、もう 1 つは実行用です。

それとは別に、I/O を減らすことは良いことです。高速な字句解析は、今日では基本的に解決済みの問題ですが、当時は必ずしもそうではありませんでした。解析についてはよくわかりません.20年前に最後に掘り下げたので、他の誰かが高速解析などについて案内してくれます.

于 2010-09-15T17:09:20.147 に答える
1

一般的な知恵は、手作業でコーディングされたトップダウン再帰降下ベースのパーサーは、yacc によって構築されたルールベースの LALR(k) パーサーよりも高速であるということです。手動でコーディングされたパーサーは、場合によってはより適切なエラー メッセージを表示することもあります。

OTOH、yacc のようなものを使用する正当な理由は、LALR(1) が再帰降下よりも大きなクラスの言語を明確に解析できることです。これは、私の記憶が正しければ、言語の LL(1) クラスと同等です。また、手作りのパーサーよりも yacc スタイルのパーサーを作成および修正するのにかかる時間が短くなります。

人々が議論してきた他のすべての問題と比較して、解析がパフォーマンスのボトルネックであることは明らかではありません。つまり、ファイル IO や AST トラバーサルで下手な仕事をすると、かなりの損害を被る可能性があります。おそらく、わずかに効率の悪いパーサーを使用するよりもはるかに多くの損害を被る可能性があります。

私がよく知っている非常に高速なコンパイラは、手作りの再帰降下パーサーを使用しています。専門的にコンパイラを扱うようになってから数年が経ちましたが、ある時点ではそれが私の日常業務の一部でした。

于 2010-09-17T19:24:18.143 に答える
0

今日では、使用可能なすべてのコアをコンパイラに使用させることは間違いありません。私は分散コンパイルについて書いているのではなく、並列コンパイルについて書いています。複数のコアを使用するようにコンパイラをゼロから設計してください。明らかなアプローチの 1 つは、コンパイラのさまざまな段階をパイプライン化することです。ASTの書き換えも確かに並列化できます

そして、入力を惜しまないでください。このアプローチが「ルール」によって除外されているとは言わないでください。あなたのルールは、おそらく浮動小数点演算を最適化するための浮動小数点ユニットの使用を禁止するか、1 GHz を超えるクロック速度のプロセッサの使用を禁止するでしょう。

今日のコンピューター用に高速なプログラムを書きたい場合は、昨日の CPU ではなく、今日の CPU 用に作成します。今日のコンピューターはマルチコア CPU を使用しています。

于 2010-09-15T16:48:58.610 に答える
0

Turbo Pascal での大きな変更点の 1 つは、以前の多くのコンパイラ/アセンブラ/リンカでは、コンパイラ/アセンブラ/リンカの一部と同様に、ソース コードとオブジェクト コードの両方がディスク上にあったことです。1 つのドライブで複数のファイルを同時に読み書きしようとすると、多くの場合、1 つのファイルの読み書きよりも 2 倍以上遅くなります。Turbo Pascal は開発システム全体を RAM に保持し、多くの場合、ソース コードまたはオブジェクト コードも RAM に保持していました。

コモドール 64 の後期には、Fast Assembler と呼ばれるアセンブラーがありました。このアセンブラーは、基本的なインタープリターにパッチを適用して、アセンブリ言語のオペコードといくつかの新しいディレクティブを追加しました。ORG ディレクティブは、ターゲット コードの場所と「パス」フラグを設定します。「パス」フラグがクリアされている場合、各オペコードはターゲット コードの場所を命令サイズだけバンプしますが、コードを生成せず、範囲外の分岐について文句を言うこともありません。pass フラグが設定されている場合、コードが生成されます。プログラムをアセンブルするには、プログラムを for/next ループで囲んで 3 回実行し、最後に "pass" フラグを設定します。すべてが RAM に保持されていたため、編集、アセンブル、テストのサイクルは、以前のどのアセンブラよりも非常に高速でした。

于 2010-10-02T18:58:30.643 に答える
0

C++ コンパイラは Java コンパイラよりも低速です。主な理由は、(通常) 最適化されたネイティブ コードを生成するのに対し、Java コンパイラはそれほど最適化されていないバイトコードを生成し、最終的な最適化とネイティブ コードの生成を JIT コンパイラ (実行時に実行) に任せているためです。 ）。本格的な最適化にはネイティブ コードの知識が必要なため、バイトコード コンパイラが実行できる処理には限界があります。

ここで、Lightspeed についてコメントすることはできませんが (私はそれについて何も知らないため)、Lattice & Microsoft C (遅い) と Borland TurboC (速い) の場合、Borland はすべてのファイルをメモリに保持し、そこでコンパイルしました (プログラムがクラッシュすると、IDE がダウンし、保存されていないソース コードが失われる可能性があります!)。Micrsoft の IDE は常にファイルをディスクに保存し、別のプログラムを起動してディスクを読み取り、コンパイルします。

プリコンパイラ ヘッダー ファイルの使用も、c/C++ コンパイルの高速化に役立ちました。

コンパイルの高速化に役立つもう 1 つのことは、シングルパス コンパイルを可能にするように設計された言語です。たとえば、Pascal では、すべての関数を使用する前に定義する必要があります (C++ のように宣言するだけではありません) (これが、メイン関数がソース ファイルの最後にある必要がある理由です)。

于 2010-09-13T20:05:56.803 に答える