Javaを高速化:最適化!

先駆的なコンピューター科学者のドナルド・クヌースによれば、「時期尚早の最適化はすべての悪の根源です」。最適化に関する記事は、通常、最適化するよりも最適化しない理由の方が多いことを指摘することから始めなければなりません。

  • コードがすでに機能している場合、それを最適化することは、新しい、場合によっては微妙なバグを導入する確実な方法です。

  • 最適化により、コードの理解と維持が困難になる傾向があります

  • ここで紹介するテクニックのいくつかは、コードの拡張性を減らすことで速度を上げます

  • あるプラットフォーム用にコードを最適化すると、実際には別のプラットフォームでコードが悪化する可能性があります

  • パフォーマンスをほとんど向上させることなく、最適化に多くの時間を費やすことができ、コードが難読化される可能性があります

  • あなたがコードの最適化に過度に夢中になっている場合、人々はあなたをあなたの後ろのオタクと呼ぶでしょう

最適化する前に、最適化する必要があるかどうかを慎重に検討する必要があります。Javaでの最適化は、実行環境が異なるため、とらえどころのないターゲットになる可能性があります。より優れたアルゴリズムを使用すると、低レベルの最適化の量よりもパフォーマンスが大幅に向上し、すべての実行条件下で改善がもたらされる可能性が高くなります。原則として、低レベルの最適化を行う前に、高レベルの最適化を検討する必要があります。

では、なぜ最適化するのでしょうか。

それがそんなに悪い考えなら、なぜまったく最適化するのですか?まあ、理想的な世界ではあなたはそうしないでしょう。しかし、実際には、プログラムの最大の問題は、必要なリソースが多すぎることであり、これらのリソース(メモリ、CPUサイクル、ネットワーク帯域幅、またはその組み合わせ)が制限される場合があります。プログラム全体で複数回発生するコードフラグメントはサイズに敏感である可能性が高く、実行の反復が多いコードは速度に敏感である可能性があります。

Javaを高速化!

コンパクトなバイトコード、速度、またはバイトコードの欠如を伴うインタープリター言語として、Javaで問題として最も頻繁に現れるものです。小さなスペースに収まるのではなく、Javaをより高速に実行する方法を主に見ていきますが、これらのアプローチがメモリやネットワークの帯域幅にどのように影響するかを指摘します。焦点は、JavaAPIではなくコア言語になります。

ちなみに、ここで説明しないことの1つは、Cまたはアセンブリで記述されたネイティブメソッドの使用です。ネイティブメソッドを使用すると、究極のパフォーマンスを向上させることができますが、Javaのプラットフォームの独立性を犠牲にしてそうします。メソッドのJavaバージョンと選択したプラットフォームのネイティブバージョンの両方を作成することができます。これにより、すべてのプラットフォームで実行する機能を放棄することなく、一部のプラットフォームでパフォーマンスが向上します。しかし、JavaをCコードに置き換えることに関して私が言うのはこれだけです。(このトピックの詳細については、Javaのヒント「ネイティブメソッドの作成」を参照してください。)この記事では、Javaを高速化する方法に焦点を当てています。

90 / 10、80 / 20、小屋、小屋、ハイキング!

原則として、プログラムの実行時間の90%は、コードの10%の実行に費やされます。 (80%/ 20%のルールを使用する人もいますが、過去15年間にいくつかの言語で商用ゲームを作成および最適化した私の経験では、パフォーマンスを重視するプログラムでは、90%/ 10%の式が一般的であることが示されています。プログラムの残りの90%(実行時間の10%が費やされた場所)を最適化しても、パフォーマンスに目立った影響はありません。コードの90%を2倍の速度で実行できるとしたら、プログラムの速度は5%になります。したがって、コードを最適化する最初のタスクは、実行時間の大部分を消費するプログラムの10パーセント(多くの場合、これより少ない)を特定することです。これは違いますt常にあなたがそれがあると期待する場所。

一般的な最適化手法

使用されている言語に関係なく適用される一般的な最適化手法がいくつかあります。グローバルレジスタ割り当てなど、これらの手法の一部は、マシンリソース(CPUレジスタなど)を割り当てるための高度な戦略であり、Javaバイトコードには適用されません。基本的に、コードを再構築し、メソッド内で同等の操作を置き換えることを含む手法に焦点を当てます。

強度低下

強度低下は、操作がより高速に実行される同等の操作に置き換えられたときに発生します。強度低下の最も一般的な例は、シフト演算子を使用して整数を2の累乗で乗算および除算することです。たとえばx >> 2、の代わりにを使用してx / 4、をx << 1置き換えることができますx * 2

一般的な部分式除去

共通部分式除去により、冗長な計算が削除されます。書く代わりに

double x = d * (lim / max) * sx; double y = d * (lim / max) * sy;

共通部分式は1回計算され、両方の計算に使用されます。

double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;

コードモーション

コードモーションは、演算を実行するコード、または結果が変わらない、または不変である式を計算するコードを移動します。コードは、結果が必要になるたびに実行されるのではなく、結果が変更される可能性がある場合にのみ実行されるように移動されます。これはループで最も一般的ですが、メソッドの呼び出しごとに繰り返されるコードが含まれる場合もあります。以下は、ループ内の不変のコードモーションの例です。

for (int i = 0; i < x.length; i++) x [i] * = Math.PI * Math.cos(y); 

になります

double picosy = Math.PI * Math.cos(y); for (int i = 0; i < x.length; i++)x [i] * =ピコシー;

展開ループ

ループを展開すると、ループ全体で毎回複数の操作が実行され、その結果、実行される反復が少なくなるため、ループ制御コードのオーバーヘッドが削減されます。前の例から作業して、の長さx[]が常に2の倍数であることがわかっている場合は、ループを次のように書き直すことができます。

double picosy = Math.PI * Math.cos(y); for (int i = 0; i < x.length; i += 2) {x [i] * =ピコシー; x [i + 1] * =ピコシー; }

実際には、このようなループの展開(ループインデックスの値がループ内で使用され、個別にインクリメントする必要がある)では、バイトコードに「+1"配列インデックスに。

この記事のすべての最適化のヒントは、上記の一般的な手法の1つ以上を具体化したものです。

コンパイラを機能させる

最新のCおよびFortranコンパイラーは、高度に最適化されたコードを生成します。C ++コンパイラは通常、効率の低いコードを生成しますが、それでも最適なコードを生成するための道を進んでいます。これらのコンパイラはすべて、激しい市場競争の影響下で何世代にもわたって経ち、通常のコードからパフォーマンスの最後の一滴を絞り出すための洗練されたツールになりました。彼らはほぼ確実に上記の一般的な最適化手法をすべて使用しています。しかし、コンパイラーに効率的なコードを生成させるための秘訣はまだたくさん残っています。

javac、JIT、およびネイティブコードコンパイラ

javacこの時点でコードをコンパイルするときに実行される最適化のレベルは最小限です。デフォルトでは、次のようになります。

  • 定数畳み込み-コンパイラは、にi = (10 *10)コンパイルされるような定数式を解決しますi = 100

  • ブランチフォールディング(ほとんどの場合)-不要なgotoバイトコードは回避されます。

  • 限定的なデッドコードの除去-のようなステートメントのコードは生成されませんif(false) i = 1

javacが提供する最適化のレベルは、言語が成熟し、コンパイラベンダーがコード生成に基づいて真剣に競争し始めるにつれて、おそらく劇的に向上するはずです。Javaは今、第2世代のコンパイラを取得しています。

次に、実行時にJavaバイトコードをネイティブコードに変換するジャストインタイム(JIT)コンパイラがあります。いくつかはすでに利用可能であり、プログラムの実行速度を劇的に向上させることができますが、最適化は実行時に行われるため、実行できる最適化のレベルは制限されます。JITコンパイラーは、最速のコードを生成することよりも、コードを迅速に生成することに関心があります。

Javaをネイティブコードに直接コンパイルするネイティブコードコンパイラは、最高のパフォーマンスを提供するはずですが、プラットフォームの独立性が犠牲になります。幸い、ここで紹介するトリックの多くは将来のコンパイラーによって実現されますが、今のところ、コンパイラーを最大限に活用するには少し作業が必要です。

javac有効にできるパフォーマンスオプションが1つあります。-Oコンパイラに特定のメソッド呼び出しをインライン化させるオプションを呼び出すことです。

javac -O MyClass

メソッド呼び出しをインライン化すると、メソッドのコードがメソッド呼び出しを行うコードに直接挿入されます。これにより、メソッド呼び出しのオーバーヘッドがなくなります。小さなメソッドの場合、このオーバーヘッドは実行時間のかなりの割合を占める可能性があります。、、、またはのいずれかprivateとして宣言されたメソッドのみがインライン化の対象となる可能性があることに注意してください。これらのメソッドのみがコンパイラーによって静的に解決されるためです。また、メソッドはインライン化されません。コンパイラは、通常1行または2行のコードのみで構成される小さなメソッドのみをインライン化します。staticfinalsynchronized

残念ながら、javacコンパイラの1.0バージョンには、-Oオプションが使用されたときにバイトコードベリファイアを渡すことができないコードを生成するバグがあります。これはJDK1.1で修正されています。(バイトコードベリファイアは、実行が許可される前にコードをチェックして、Javaルールに違反していないことを確認します。)呼び出し元のクラスにアクセスできないクラスメンバーを参照するメソッドをインライン化します。たとえば、次のクラスが-Oオプションを使用して一緒にコンパイルされている場合

クラスA {private static int x = 10; public static void getX(){return x; }}クラスB {int y = A.getX(); }

クラスBでのA.getX()の呼び出しは、Bが次のように記述されているかのように、クラスBにインライン化されます。

クラスB {int y = Ax; }

ただし、これにより、バイトコードの生成は、Bのコードで生成されるプライベートAx変数にアクセスします。このコードは正常に実行されますが、Javaのアクセス制限に違反してIllegalAccessErrorいるため、コードが最初に実行されたときにベリファイアによってフラグが付けられます。

このバグによって-Oオプションが役に立たなくなるわけではありませんが、使用方法に注意する必要があります。単一のクラスで呼び出された場合、リスクなしでクラス内の特定のメソッド呼び出しをインライン化できます。潜在的なアクセス制限がない限り、複数のクラスをインライン化できます。また、一部のコード(アプリケーションなど)はバイトコードベリファイアの対象ではありません。コードがベリファイアを受けずにのみ実行されることがわかっている場合は、バグを無視できます。詳細については、私のjavac-OFAQを参照してください。

プロファイラー

幸い、JDKには、プログラムのどこで時間が費やされているかを特定するのに役立つプロファイラーが組み込まれています。各ルーチンで費やされた時間を追跡し、ファイルに情報を書き込みますjava.prof。プロファイラーを実行するには-prof、Javaインタープリターを呼び出すときにオプションを使用します。

java -prof myClass

またはアプレットで使用する場合:

java -prof sun.applet.AppletViewer myApplet.html

プロファイラーを使用する際の注意点がいくつかあります。プロファイラーの出力は、解読するのが特に簡単ではありません。また、JDK 1.0.2では、メソッド名が30文字に切り捨てられるため、一部のメソッドを区別できない場合があります。残念ながら、Macではプロファイラーを呼び出す手段がないため、Macユーザーは運が悪い。これらすべてに加えて、SunのJavaドキュメントページ(「参考文献」を参照)には、-profオプションのドキュメントが含まれなくなりました)。ただし、プラットフォームがこの-profオプションをサポートしている場合は、ウラジーミルブラトフのHyperProfまたはグレッグホワイトのProfileViewerを使用して、結果の解釈に役立てることができます(「参考文献」を参照)。

コードに明示的なタイミングを挿入することにより、コードを「プロファイリング」することもできます。

long start = System.currentTimeMillis(); // do operation to be timed here long time = System.currentTimeMillis() - start;

System.currentTimeMillis()1/1000分の1秒で時間を返します。ただし、Windows PCなどの一部のシステムには、1/1000秒よりも低い(はるかに低い)解像度のシステムタイマーがあります。1/1000秒でさえ、多くの操作の時間を正確に計るのに十分な長さではありません。このような場合、または低解像度のタイマーを備えたシステムでは、操作をn回繰り返すのにかかる時間を計り、合計時間をnで割って実際の時間を取得する必要がある場合があります。プロファイリングが利用可能な場合でも、この手法は特定のタスクまたは操作のタイミングをとるのに役立ちます。

プロファイリングに関するいくつかの締めくくりのメモは次のとおりです。

  • 少なくともテストプラットフォームでは、変更によってプログラムが改善されたことを確認するために、変更を加える前後に常にコードの時間を計ってください。

  • 同じ条件下で各タイミングテストを行うようにしてください

  • 可能であれば、ユーザーの応答の変動によって結果が変動する可能性があるため、ユーザー入力に依存しないテストを考案してください。

ベンチマークアプレット

ベンチマークアプレットは、操作を数千回(または数百万回)実行するのにかかる時間を測定し、テスト以外の操作(ループオーバーヘッドなど)の実行に費やした時間を差し引いて、この情報を使用して各操作の時間を計算します取った。各テストを約1秒間実行します。コンピューターがテスト中に実行する可能性のある他の操作からのランダムな遅延を排除するために、各テストを3回実行し、最良の結果を使用します。また、テストの要素としてガベージコレクションを排除しようとします。このため、ベンチマークで使用できるメモリが多いほど、ベンチマーク結果はより正確になります。