C производительность и параметры компиляции
У меня есть две аналогичные реализации (Java и C ++) для тривиального алгоритма, как сортировка выбора.
public interface SortingAlgorithm {
public void sort(int[] a);
}
public class SelectionSort implements SortingAlgorithm {
@Override
public void sort(int[] a) {
for (int i = 0; i < a.length; i++) {
int lowerElementIndex = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[lowerElementIndex]) {
lowerElementIndex = j;
}
}
swap(a, lowerElementIndex, i);
}
}
private void swap(int[] a, int i, int j) {
if (i == j) {
return;
}
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
и c один:
inline void swap(int* a, int i, int j);
void s_sort(int* a, int size) {
int i;
for (i = 0; i < size; i++) {
int lowerElementIndex = i, j;
for (j = i + 1; j < size; j++) {
if (a[j] < a[lowerElementIndex]) {
lowerElementIndex = j;
}
}
swap(a, lowerElementIndex, i);
}
}
inline void swap(int* a, int i, int j) {
if (i == j) {
return;
}
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
Теперь я попробовал протестировать их на большом массиве (100000 случайных чисел). Сначала результаты были java: ~ 17 секунд (скомпилировано и выполнено с помощью oracle jdk / jvm) c: ~ 22 секунд (скомпилировано с gcc v4.8 без какой-либо оптимизации)
Конечно, я тогда попытался оптимизировать свою версию c через cflags. Результаты (я сообщаю только cflags): -O1: ~ 18.4
-O2: ~ 18,4
-O {3-9}: ~ 20,9
Теперь мой первый вопрос: какие cflacs мне использовать для компиляции?
Итак, я прочитал руководство GNU по оптимизации. Добавление -march = native не помогло. После некоторого времени, потраченного на другие варианты, я вошел в опцию -fprofile-arcs. Добавление его в мои флаги заставило мой код завершить тестирование примерно за 11 секунд! Однако некоторые файлы появились в моих папках: результаты профилирования. Как я понимаю, я должен использовать их с -fbranch-probabilities и перекомпилировать код. Повторная компиляция результатов через ~ 18,5 сек.И это то, что я действительно хочу спросить.
Как моя программа может работать так быстро, если ей приходится записывать файлы и собирать информацию о профилировании, а вместо этого она работает в 1,5 раза медленнее, чем когда она этого не делает?
Я забыл упомянуть, что у меня старый компьютер с процессором Intel Celeron @ 2.8GHz и linux (fedora 20 с xfce). Если вам нужна другая информация об оборудовании, просто спросите! ;)
Изменить: код, который я использую для теста:
Ява:
public class Test {
public static void main(String[] args) {
int[] a = new int[100000];
int[] a2 = new int[100000];
for (int i = 0; i < a.length; i++) {
a[i] = (int)(Math.random()*100000);
a2[i] = a[i];
}
SelectionSort s = new SelectionSort();
InsertionSort s1 = new InsertionSort();
double start = System.nanoTime();
s.sort(a);
double end = System.nanoTime();
double time = (end-start)/1000000000.0;
System.out.println("Selection: "+time);
start = System.nanoTime();
s1.sort(a2);
end = System.nanoTime();
time = (end-start)/1000000000.0;
System.out.println("Insertion: "+time);
}
}
И с:
#include "insertion_sort.h"
#include "selection_sort.h"
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int main() {
int max = 100000, i;
srand(time(NULL));
int array[100000], array2[100000];
for(i=0; i<100000; i+=1) {
array[i] = rand()%100000;
}
memcpy(array2, &array[0], 100000 * sizeof(int));
clock_t inizio = clock();
s_sort(array, max);
clock_t fine = clock();
float tempoEsecuzione = (float)(fine - inizio) / CLOCKS_PER_SEC;
printf("Selection: %2.3f\n", tempoEsecuzione);
inizio = clock();
i_sort(array2, max);
fine = clock();
tempoEsecuzione = (float)(fine - inizio) / CLOCKS_PER_SEC;
printf("Insertion: %2.3f\n", tempoEsecuzione);
return 0;
}
Код содержит ссылки на функцию сортировки вставкой, которую я не включил в остальную часть вопроса, потому что (как и ожидалось) Java работает медленнее, чем c.