Problem z mierzeniem czasu [Java]

Odpowiedz Nowy wątek
2019-01-02 12:29
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);

    }

}

Pozostało 580 znaków

2019-01-02 12:35

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.


Pozostało 580 znaków

2019-01-02 13:12
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/


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2019-01-02 13:15

Pozostało 580 znaków

2019-01-02 13:19
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?


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
JIT i GC można akurat łatwo odsunąć na bok w takim teście. Na JIT wystarczy dobry warmup. Na GC nie alokować obiektów na mierzonej ścieżce (analogicznie jak w C nie używać malloc na mierzonej ścieżce, bo jest równie nieprzewidywalny). W Javie można też zweryfikować czy JIT / GC się uruchamiają w czasie benchmarku. - Krolik 2019-01-02 15:26
To prawda, zresztą @Wibowit też o tym wspominał, niemniej generalnie robienie takich benchmarków w javie jest trudne, szczególnie jeśli ktoś chce tu pokazać jakieś wyniki zgodne z teorią. - Shalom 2019-01-02 15:32
Są jednak narzędzia do odsiewania przebiegów z niepełnego JITa bądź z aktywnością GC, np http://scalameter.github.io/ automatically eliminate noise due to JIT compilation, garbage collection or undesired heap allocation patterns - Wibowit 2019-01-02 15:36
Tak, jest trochę trudniejsze. Choć robienie takich benchmarków w C też wcale nie jest takie łatwe i oczywiste - też jest wiele innych pułapek: kompilator, cache, system operacyjny itp. Też jest dużo warstw pod spodem. - Krolik 2019-01-02 15:37
Ponadto od Javy 11 mamy Epsilon GC :) https://openjdk.java.net/jeps/318 - Wibowit 2019-01-02 15:37

Pozostało 580 znaków

2019-01-02 13:22
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.

Pozostało 580 znaków

2019-01-02 13:40
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)

Pozostało 580 znaków

2019-01-02 14:26
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.

Bardzo lubie Singletony, dlatego robię po kilka instancji każdego.
edytowany 4x, ostatnio: jarekr000000, 2019-01-02 14:30

Pozostało 580 znaków

2019-01-02 15:10
Chory Karp
0

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

Pozostało 580 znaków

2019-01-02 15:15
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.

edytowany 2x, ostatnio: Krolik, 2019-01-02 15:23
To zadanko jest ze złożoności obliczeniowej a nie architektury Javy i komputerów. Wynik ma być spójny z tym ile razy pętla będzie się kręcić. - krsp 2019-01-02 16:12
No w tej sytuacji to nie powinno być w ogóle na komputerze uruchomione, tylko przeanalizowane na kartce. Albo na maszynie Turinga :D - Krolik 2019-01-02 17:05
Problem ze złożonością asymptotyczną liczoną na zajęciach teoretycznych jest taki, że liczy się ją na modelu, który nijak ma się do rzeczywistości, a założenia są mocno uproszczone i złe. http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html Ani dostęp do pamięci nie jest O(1), ani operacje arytmetyczne (np. w ww przypadku porównania) nie są O(1). Tak więc, jesli wynik wyjdzie Ci spójny z teorią, to wręcz na 100% robisz coś źle :P - Krolik 2019-01-02 17:11
I nie, nie chodzi o Javę. We wszystkich komputerach ten problem występuje. - Krolik 2019-01-02 17:15
Podejrzewam, że da się skonstruować warunki/kod (rozmiary tablicy) tak aby te dostępy do ramu i cache były pomijalne. Problem jest w tym, że autor zdecydował się na: mierzymy w nano żeby było dokładnie - a właśnie wtedy nie jest dokładnie. - krsp 2019-01-02 17:51

Pozostało 580 znaków

2019-01-02 15:53
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.

Pozostało 580 znaków

2019-01-03 11:50
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 :)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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