問題
Java での単純な QuickSort 実装のベンチマークを行ったとき、n vs timeプロットしていたグラフィックスに予想外のこぶがありました。
特定のメソッドが頻繁に使用されているように見えると、HotSpot がコードをネイティブにコンパイルしようとすることがわかっているので、JVM を で実行しました-XX:+PrintCompilation。試行を繰り返した後、アルゴリズムのメソッドを常に同じ方法でコンパイルしているようです。
@ iteration 6 -> sorting.QuickSort::swap (15 bytes)
@ iteration 7 -> sorting.QuickSort::partition (66 bytes)
@ iteration 7 -> sorting.QuickSort::quickSort (29 bytes)
少しわかりやすくするために、この追加情報を使用して上記の図を繰り返します。
この時点で、私たちは皆自問する必要があります: コードがコンパイルされた後も、なぜまだこれらの醜いこぶが得られるのでしょうか? アルゴリズム自体に何か関係があるのでしょうか？確かにそうかもしれませんが、幸運なことに、次の方法で簡単に解決できます-XX:CompileThreshold=0。
残念！これは、JVM がバックグラウンドで実行しているものに違いありません。しかし、何？コードはコンパイルされていますが、コンパイルされたコードが実際に使用されるまでにはしばらく時間がかかる可能性があると理論付けました。いくつかの をあちこちに追加するThread.sleep()と、この問題を少し整理するのに役立つのではないでしょうか?
痛い！緑色の関数は、実行ごとに 1000 ミリ秒の内部時間で実行された QuickSort のコード (詳細は付録を参照) であり、青色の関数は古い関数 (比較用) です。
最初は、HotSpot に時間を割いても問題が悪化しているように見えます。キャッシングの問題など、他の要因によってのみ悪化しているように見えるのでしょうか?
免責事項 : 表示されているグラフィックの各ポイントに対して 1000 回の試行を実行しSystem.nanoTime()、結果を測定するために使用しています。
編集
この段階で、 を使用すると結果がどのようにsleep()歪むのか疑問に思う人もいるかもしれません。Red Plot (ネイティブ コンパイルなし) をもう一度実行しました。
怖い！
付録
QuickSort念のため、使用しているコードをここに示します。
public class QuickSort {
public <T extends Comparable<T>> void sort(int[] table) {
quickSort(table, 0, table.length - 1);
}
private static <T extends Comparable<T>> void quickSort(int[] table,
int first, int last) {
if (first < last) { // There is data to be sorted.
// Partition the table.
int pivotIndex = partition(table, first, last);
// Sort the left half.
quickSort(table, first, pivotIndex - 1);
// Sort the right half.
quickSort(table, pivotIndex + 1, last);
}
}
/**
* @author http://en.wikipedia.org/wiki/Quick_Sort
*/
private static <T extends Comparable<T>> int partition(int[] table,
int first, int last) {
int pivotIndex = (first + last) / 2;
int pivotValue = table[pivotIndex];
swap(table, pivotIndex, last);
int storeIndex = first;
for (int i = first; i < last; i++) {
if (table[i]-(pivotValue) <= 0) {
swap(table, i, storeIndex);
storeIndex++;
}
}
swap(table, storeIndex, last);
return storeIndex;
}
private static <T> void swap(int[] a, int i, int j) {
int h = a[i];
a[i] = a[j];
a[j] = h;
}
}
ベンチマークを実行するために使用しているコード:
public static void main(String[] args) throws InterruptedException, IOException {
QuickSort quickSort = new QuickSort();
int TRIALS = 1000;
File file = new File(Long.toString(System.currentTimeMillis()));
System.out.println("Saving @ \"" + file.getAbsolutePath() + "\"");
for (int x = 0; x < 30; ++x) {
// if (x > 4 && x < 17)
// Thread.sleep(1000);
int[] values = new int[x];
long start = System.nanoTime();
for (int i = 0; i < TRIALS; ++i)
quickSort.sort(values);
double duration = (System.nanoTime() - start) / TRIALS;
String line = x + "\t" + duration;
System.out.println(line);
FileUtils.writeStringToFile(file, line + "\r\n", true);
}
}
