Проблема
При сравнении простой реализации QuickSort на Java я столкнулся с неожиданными горбами в графике n vs time, которую я рисовал:
Я знаю, что HotSpot попытается скомпилировать код для native после того, как кажется, что некоторые методы сильно используются, поэтому я запускал 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() здесь и там может помочь нам немного разобраться в этой проблеме?
Ой! Функция зеленого цвета - это код QuickSort, работающий с интервалом 1000 мс между каждым прогоном (подробности в приложении), а функция синего цвета - наша старая (только для сравнения).
В кулак, уступая время 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);
}
}
