Mam dwie podobne implementacje (java i c ++) dla trywialnego algorytmu, takiego jak sortowanie wyboru.

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;
    }
}

i c 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;
}

Teraz próbowałem przetestować je na dużej tablicy (100000 losowych int). Wyniki na początku były java: ~ 17 sekund (skompilowane i wykonane z oracle jdk / jvm) c: ~ 22 sekund (skompilowane z gcc v4.8 bez jakiejkolwiek optymalizacji)

Oczywiście próbowałem zoptymalizować moją wersję c za pomocą cflagów. Wyniki są (Zgłaszam tylko cflagi): -O1: ~ 18.4

-O2: ~ 18,4

-O {3-9}: ~ 20,9

Moje pierwsze pytanie brzmi: które cflacs należy użyć do kompilacji?

Więc przeczytałem podręcznik gnu dotyczący optymalizacji. Dodanie -march = native nie pomogło. Po pewnym czasie spędzonym na próbowaniu innych opcji, wszedłem do opcji -fprofile-arcs. Dodanie go do moich flag sprawiło, że mój kod zakończył test w około 11 sekund! Jednak niektóre pliki pojawiły się w moich folderach: wyniki profilowania. Jak rozumiem, powinienem ich używać z prawdopodobieństwami -fbranch i przekompilować kod. Ponowna kompilacja wyników za ~ 18,5 sek.I o to naprawdę chcę zapytać.

Jak to możliwe, że mój program działa tak szybko, jeśli musi pisać pliki i zbierać informacje o profilowaniu, a zamiast tego działa 1,5 raza wolniej, gdy nie działa?

Zapomniałem wspomnieć, że jestem na starym komputerze z zainstalowanym procesorem Intel Celeron @ 2,8 GHz i linuxem (fedora 20 z xfce). Jeśli potrzebujesz innych informacji na temat sprzętu, po prostu zapytaj! ;)

Edytuj: Kod, którego używam do testu to:

Jawa:

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);
    }
}

I c:

#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;
}

Kod zawiera odniesienia do funkcji sortowania wstawiania, której nie uwzględniłem w pozostałej części pytania, ponieważ (zgodnie z oczekiwaniami) java działa wolniej niż c.