Problem z mierzeniem czasu [Java]

0

Dzień dobry, robię właśnie zadanie na zajęcia z algorytmów. Moim zadaniem jest szukanie jakiegoś elementu tablicy z wykorzystaniem algorytmu interpolacyjnego. Mam to zrobić dla 10 tablic o różnych rozmiarach (100 000, 300 000 itd, mało istotne) i zmierzyć czas działania algorytmu i potem te czasy porównać za pomocą wykresu. Ogólnie wszystko mam już zrobione tak jak ma być, problem jednak leży w mierzeniu czasu. Czas mierzę w nanosekundach aby był jak najdokładniejszy i zamieniam go na sekundy z dokładnością do 6 miejsc po przecinku. Pobieram czas przed algorytmem i drugi raz zaraz po zakończeniu algorytmu. Następnie odejmuję te czasy od siebie i wyświetlam. Teoretycznie co może iść nie tak? Wszystko powinno być ok, jednak nie wiem dlaczego czasy są wyświetlane jakby randomowo. Prawidłowo czasy powinny rosnąć w każdej kolejnej tablicy, a tak się nie dzieje... Przy pierwszym mierzeniu czasu, obojętnie jaka by to nie była tablica, dla testów dałem nawet tablice 600 elementową, a wynik zawsze jest baaardzo duży. Dopiero za drugim razem jest w miarę normalny. Jednak raz wynik jest wiekszy, raz mniejszy, mimo tego, że cały czas powinny rosnać... Moi koledzy mają dokładnie to samo i nie potrafimy sobie z tym poradzić.
Wie ktoś może o co chodzi? Bo już nie mam siły do tego... Nie widzę tu nic co by mogło powodować ten błąd. Oto kod i wyniki w załączniku.

package javaapplication7;

public class JavaApplication7 {
    
    public static void zapelnij_tablice(int[] tab)
    {
        int k=0;
        for(int i=0;i<tab.length;i++)
        {
            tab[k]=i;
            k++;
        }
    }
    
    
    static int interpolationSearch(int[] tab, int x) 
    { 
        int lo = 0, hi = (tab.length - 1); 
       
        while (lo <= hi && x >= tab[lo] && x <= tab[hi]) 
        {  
            int pos = lo + (((hi-lo) / 
                  (tab[hi]-tab[lo]))*(x - tab[lo])); 
       
            if (tab[pos] == x) 
                return pos-1; 

            if (tab[pos] < x) 
                lo = pos + 1; 

            else
                hi = pos - 1; 
        } 
        return -1; 
    } 
    
    static void Sprawdzenie(int[] tab)
    {
        int x=20000;
        int index=interpolationSearch(tab, x);
        
        if(index!=-1)
        {
            System.out.println("Element znaleziony przy indeksie: "+index);
        }
        else System.out.println("Element nie został znaleziony.");
    }
    
    
    static void IleCzasu(int[] tab)
    {
        double poczatek=System.nanoTime();
        Sprawdzenie(tab);
        //System.out.println("Czas sortowania: "+ (System.nanoTime()-poczatek));
        System.out.format("Czas sortowania: [s] %.6f%n", ((System.nanoTime() - poczatek) / 1000000000));
        System.out.println();
    }
    
    public static void main(String[] args) {
        int n=3;
        int wartosc=100000;
        int[] tablica= new int [1*n*wartosc];
        int[] tablica2= new int [2*n*wartosc];
        int[] tablica3= new int [3*n*wartosc];
        int[] tablica4 = new int[4*n*wartosc];
        int[] tablica5 = new int[5*n*wartosc];
        int[] tablica6 = new int[6*n*wartosc];
        int[] tablica7 = new int[7*n*wartosc];
        int[] tablica8 = new int[8*n*wartosc];
        int[] tablica9 = new int[9*n*wartosc];
        int[] tablica10 = new int[10*n*wartosc];
        
        zapelnij_tablice(tablica);
        IleCzasu(tablica);
             
        zapelnij_tablice(tablica2);
        IleCzasu(tablica2);
        
        zapelnij_tablice(tablica3);
        IleCzasu(tablica3);
        
        zapelnij_tablice(tablica4);
        IleCzasu(tablica4);
        
        zapelnij_tablice(tablica5);
        IleCzasu(tablica5);
        
        zapelnij_tablice(tablica6);
        IleCzasu(tablica6);
        
        zapelnij_tablice(tablica7);
        IleCzasu(tablica7);
        
        zapelnij_tablice(tablica8);
        IleCzasu(tablica8);
        
        zapelnij_tablice(tablica9);
        IleCzasu(tablica9);
        
        zapelnij_tablice(tablica10);
        IleCzasu(tablica10);
       
        
        
    }
    
}
1

JVM robi dużo hard corowych optymalizacji, ale potrzebuje na to czasu, więc pierwsze przebiegi są wolne, dopiero za którymś razem działa optymalnie. Z tego wynika, żę źle Robicie benchmarki. W zależności od wielkości struktury danych, Zakodujcie jak najwięcej testów w pętlach, i Zwracajcie najkrótszy czas przebiegu.

3

JVM w standardowym trybie jest połączeniem interpretera oraz wielu poziomów JITa. Kod jest ładowany leniwie, a więc klasa jest ładowana przy pierwszym użyciu. Ładowanie klasy trwa jakiś czas (wyciąganie z JARa, parsowanie, weryfikowanie, etc) Przy pierwszym uruchomieniu kod jest zawsze interpretowany, gdyż JVMka w obecnej postaci nie zapisuje zJITowanego kodu w trwałej pamięci. Po ustalonej ilości wykonań danego kawałka kodu jest on poddawany kompilacji do kodu natywnego (JIT - Just In Time compilation) na pierwszym poziomie optymalizacji. Po osiągnięciu kolejnego progu ilości wykonań kod podlega kompilacji kompilatorem wyższego poziomu (kompilującego wolniej, ale optymalizującego kod natywny lepiej). Kawałki kodu, które są często wykonywane nazywane są hot spotami i od tego pochodzi nazwa JVMki: https://en.wikipedia.org/wiki/HotSpot Przed pomiarami wydajności musisz zadbać o rozgrzanie (czyli wielokrotne uruchomienie) wszystkich hot spotów, które mają znaczący (tutaj: mierzalny) wpływ na wydajność, tak by zostały skompilowane najwyższym stopniem kompilatora JIT. Możesz to robić samemu, ale to wymaga znajomości mechanizmu kompilacji JIT w Javie (czyli mniej więcej tego co napisałem, ale popartego doświadczeniem zdobytym obserwacjami zachowania JVMki).

Zamiast własnoręcznego tworzenia mechanizmu do mierzenia wydajności możesz skorzystać z gotowca, standardu w dziedzinie mierzenia wydajności mini algorytmów w Javie, czyli JMH: https://openjdk.java.net/projects/code-tools/jmh/ Opis wykorzystania jest np tutaj: http://tutorials.jenkov.com/java-performance/jmh.html albo w uproszczonej wersji (jeśli nie potrafisz angielskiego, co byłoby bardzo kiepskie) tutaj: http://sciezkaprogramisty.pl/jmh/

1

Java to średni wybór do takich celów bo ma JIT i GC, ale nawet jakbyście testowali kod natywny w C to też pojawia się problem natury technicznej taki jak CPU cache chociażby. To wszystko sprawia że faktyczne wykonanie na realnym sprzęcie może mocno odbiegać od modelu teoretycznego. Serio kazali wam to zrobić w javie?

0

Ok, dziękuję za odpowiedzi. Widzę, że takie łatwe to nie będzie :D Tak, prowadzący kazał nam robić wszystkie zadania w Javie.

0

Powinieneś dobrać tak rozmiary struktur aby czasy były przynajmniej w sekundach, wtedy wpływ "zakłóceń" powinien być pomijalny.
Chyba masz błąd w:
return pos-1;
wydaje się że powinno być
return pos
https://www.geeksforgeeks.org/interpolation-search/

To nie są czasy sortowania, ale czasy wyszukiwania.

Polecam zliczyć ile razy algorytm jest w pętli while (ile razy się pętli przy szukaniu). Odnoszę wrażenie, że w zasadzie od tego zależą różnice w czasie wykonania. Nawet tymczasowe wyświetlenie przed zwrotem wartości powinno być ok (tylko, musiało by to wszystko działać na dużych tabelach, bo tak to ten print na pewno zakłóci wynik)

2

Generalnie to benchmarki na JVM rób przy pomocy JMH. Jest dużo tutowiali i video jak to użyć.
Próbowałem minimalnie przerobić na JVMoodporny ten kod:


public class JavaApplication7 {
    public static void zapelnij_tablice(int[] tab)
    {
        int k=0;
        for(int i=0;i<tab.length;i++)
        {
            tab[k]=i;
            k++;
        }
    }

    static int interpolationSearch(int[] tab, int x)
    {
        int lo = 0, hi = (tab.length - 1);

        while (lo <= hi && x >= tab[lo] && x <= tab[hi])
        {
            int pos = lo + (((hi-lo) /
                    (tab[hi]-tab[lo]))*(x - tab[lo]));

            if (tab[pos] == x)
                return pos;

            if (tab[pos] < x)
                lo = pos + 1;

            else
                hi = pos - 1;
        }
        return -2;
    }

    static int Sprawdzenie(int[] tab,int i)
    {

        int index=interpolationSearch(tab, i);

        if(index!=-2)
        {
            //System.out.println("Element znaleziony przy indeksie: "+index);
        }
        else System.out.println("Element nie został znaleziony.");
        return index;
    }

    static int IleCzasu(int[] tab)
    {
        long poczatek=System.nanoTime();
        int blackHole = 0;
        for (int i=0; i<1000000; i++) {
            blackHole += Sprawdzenie(tab, 1);
            blackHole += Sprawdzenie(tab, 2);
            blackHole += Sprawdzenie(tab, 3);
        }

        //System.out.println("Czas sortowania: "+ (System.nanoTime()-poczatek));
        System.out.format("Czas sortowania: [nanos] %d", ((System.nanoTime() - poczatek)));
        System.out.println();
        return blackHole;
    }

    public static void main(String[] args) {
        int n=5;

        int[] tablica= new int [n*1];
        int[] tablica2= new int [n*2];
        int[] tablica3= new int [n*10];
        int[] tablica4 = new int[n*100];
        int[] tablica5 = new int[n*1000];
        int[] tablica6 = new int[n*10000];
        int[] tablica7 = new int[n*100000];
        int[] tablica8 = new int[n*1000000];
        int[] tablica9 = new int[n*10000000];
        int[] tablica10 = new int[n*10000000];
        //warmup
        doIt(tablica, tablica2, tablica3, tablica4, tablica5, tablica6, tablica7, tablica8, tablica9, tablica10);
        doIt(tablica, tablica2, tablica3, tablica4, tablica5, tablica6, tablica7, tablica8, tablica9, tablica10);
        doIt(tablica, tablica2, tablica3, tablica4, tablica5, tablica6, tablica7, tablica8, tablica9, tablica10);
        System.out.println("****teraz sensowne dane**********");
        int bh = doIt(tablica, tablica2, tablica3, tablica4, tablica5, tablica6, tablica7, tablica8, tablica9, tablica10);
        System.out.println("kontrolna wartość "+ bh);

    }

    private static int doIt(int[] tablica, int[] tablica2, int[] tablica3, int[] tablica4, int[] tablica5, int[] tablica6, int[] tablica7, int[] tablica8, int[] tablica9, int[] tablica10) {
        int blackHole = 0;
        zapelnij_tablice(tablica);
        blackHole += IleCzasu(tablica);

        zapelnij_tablice(tablica2);
        blackHole += IleCzasu(tablica2);

        zapelnij_tablice(tablica3);
        blackHole += IleCzasu(tablica3);

        zapelnij_tablice(tablica4);
        blackHole += IleCzasu(tablica4);

        zapelnij_tablice(tablica5);
        blackHole += IleCzasu(tablica5);

        zapelnij_tablice(tablica6);
        blackHole += IleCzasu(tablica6);

        zapelnij_tablice(tablica7);
        blackHole += IleCzasu(tablica7);

        zapelnij_tablice(tablica8);
        blackHole += IleCzasu(tablica8);

        zapelnij_tablice(tablica9);
        blackHole += IleCzasu(tablica9);

        zapelnij_tablice(tablica10);
        blackHole += IleCzasu(tablica10);

        return blackHole;
    }
}

  1. Czasy muszą przebiegów być dłuższe niż nanosekundy inaczej pomiar czasu jest zbyt losowy - stąd pętla.
  2. Wyniki dobrze jakby do czegoś dodawać inaczej JVM może uznać, że funkcja nic nie robi i jej nie wykonywać - zresztą tak się działo. stąd dodany blackhole.
  3. Tablice miały w zasadzie te same rozmiary - przy tego typu funkcji róznice były bez znaczenia. Btw. skrajnie różne rozmiary tablic też nie mają znaczenia, przy takim liniowym rozkładzie pewnie w zwykle 2,4-tym kroku trafiasz liczbę :-)
  4. Wypluwanie na konsolę najdłużej trwa - wywalone. Ale element losowy (przycinki kompa nadal mocno wpływają).
  5. JMH by to ostatnie poprawił wiec polecam. (tylko trzeba się zaznajomić z mavenem...).
  6. Miałeś bład -> zera nie wykrywał. Podawał -1 i stwierdzał, że słabo - stąd to zabawne -2 też wrzuciłem.
    Tak czy siak teraz masz bardziej sensowne wyniki. Praktycznie równe dla wszystkich tablic.
0

Użyj JMH i nie mędrkuj.
Łap: https://openjdk.java.net/projects/code-tools/jmh/

0

Przy takich benchmarkach trzeba też bardzo uważać na efekty związane z pamięcią (cache).
Jeśli będziesz powtarzać to samo wyszukiwanie milion razy, to będziesz mieć inny czas, niż jeśli milion razy będziesz szukał za każdym razem innego elementu.

W benchmarku wyżej wyszukujesz ciągle te same elementy, więc tai benchmark jest niereprezentatywny dla typowego użycia kodu. I dlatego rozmiar tablicy nie ma tu znaczenia. Natomiast w prawdziwym świecie rozmiar tablicy będzie mieć bardzo duże znaczenie - inaczej się będzie zachowywało wyszukiwanie w tablicy 1 kB, która cała zmieści się w L1, a inaczej w tablicy, której 90% będzie poza L3, a jeszcze inaczej w tablicy, która wyjdzie na swap.

Polecam zliczyć ile razy algorytm jest w pętli while (ile razy się pętli przy szukaniu). Odnoszę wrażenie, że w zasadzie od tego zależą różnice w czasie wykonania.

Czas wykonania algorytmów, które skaczą po tablicy, niemal wyłącznie liczy się w liczbach nietrafień w cache. Pierwsze wyszukiwanie może być kilkadziesiąt razy wolniejsze niż kolejne wyszukiwanie tego samego elementu.

0

Ciekawe czy prowadzacy slyszal o JMH :) Generalnie microbenchmarking w Javie jest trudniejszy niz sie wydaje.

Link startowy do JMH: http://psy-lob-saw.blogspot.com/p/jmh-related-posts.html

I artykul na poczatek: https://shipilev.net/blog/2014/nanotrusting-nanotime/ fajnie pokazuej jak uzywac JMH.

Przy czym jako ciekawostka, pobieranie czasu w Javie tez potrafilo miec bugi :)

Rowniez w C moze byc zalezne od OS, uzytej komendy itp. O ile sie nie myle bylo cos takiego jak gettimeofday ktore nie mialo gwarancji monotonicznosci wiec mogly wyjsc dziwne wyniki.

0

Dziękuję wszystkim za rady. Z problemem poradziłem sobie zapętlając kod, aby wykonało się to wszystko 100 razy. I faktycznie za tym setnym razem wyniki wyszły zadawalające :)

0

@annonymouzinho: ale wiesz ze w microbenchmarkingu i testach wydajnosciowych nie chodzi o to by otrzymac wyniki potwierdzajace teorie tylko zeby zmierzyc stan faktyczny ? A te rzeczy potrafia byc bardzo nieintuicyjne :)

0

Zdaje sobie z tego sprawę, ale tez wiem, ze mojemu prowadzącemu nie o to chodziło :D Ogólnie jeśli chodzi o te rzeczy, które mi tu wszyscy doradzali to pierwszy raz słyszę o czymś takim. W ogóle w Javie pisze tylko na tych zajęciach.

1 użytkowników online, w tym zalogowanych: 0, gości: 1