Dlaczego ta metoda wypisuje 4?

111

Zastanawiałem się, co się stanie, gdy spróbujesz złapać StackOverflowError i wymyśliłem następującą metodę:

class RandomNumberGenerator {

    static int cnt = 0;

    public static void main(String[] args) {
        try {
            main(args);
        } catch (StackOverflowError ignore) {
            System.out.println(cnt++);
        }
    }
}

Teraz moje pytanie:

Dlaczego ta metoda drukuje „4”?

Pomyślałem, że może to dlatego, że System.out.println()potrzebuje 3 segmentów na stosie wywołań, ale nie wiem, skąd pochodzi numer 3. Kiedy patrzysz na kod źródłowy (i kod bajtowy) programu System.out.println(), zwykle prowadzi to do znacznie większej liczby wywołań metod niż 3 (więc 3 segmenty na stosie wywołań nie byłyby wystarczające). Jeśli jest to spowodowane optymalizacjami, które stosuje Hotspot VM (metoda inlining), zastanawiam się, czy wynik byłby inny na innej VM.

Edytować :

Ponieważ dane wyjściowe wydają się być wysoce specyficzne dla JVM, otrzymuję wynik 4 przy użyciu
środowiska Java (TM) SE Runtime Environment (kompilacja 1.6.0_41-b02
) 64-bitowa maszyna wirtualna serwera Java HotSpot (TM) (wersja 20.14-b01, tryb mieszany)


Wyjaśnienie, dlaczego uważam, że to pytanie różni się od Zrozumienia stosu Java :

Moje pytanie nie dotyczy tego, dlaczego jest cnt> 0 (oczywiście, ponieważ System.out.println()wymaga rozmiaru stosu i rzuca inny, StackOverflowErrorzanim coś zostanie wydrukowane), ale dlaczego ma szczególną wartość 4, odpowiednio 0,3,8,55 lub coś innego na innym systemy.

flrnb
źródło
4
W moim lokalnym, zgodnie z oczekiwaniami otrzymuję „0”.
Reddy,
2
Może to dotyczyć wielu rzeczy związanych z architekturą. Więc lepiej opublikuj swoje wyjście z wersją jdk Dla mnie wyjście to 0 w jdk 1.7
Lokesh
3
Stałam 5, 6i 38Java 1.7.0_10
Kon
8
@Elist Nie będzie tego samego wyniku, gdy robisz sztuczki z podstawową architekturą;)
m0skit0
3
@flrnb To tylko styl, którego używam do wyrównywania szelek. Dzięki temu łatwiej mi wiedzieć, gdzie zaczynają się i kończą warunki i funkcje. Możesz to zmienić, jeśli chcesz, ale moim zdaniem w ten sposób jest bardziej czytelny.
syb0rg

Odpowiedzi:

41

Myślę, że inni wykonali dobrą robotę, wyjaśniając, dlaczego cnt> 0, ale nie ma wystarczająco dużo szczegółów dotyczących tego, dlaczego cnt = 4 i dlaczego cnt różni się tak bardzo w różnych ustawieniach. Spróbuję tutaj wypełnić tę pustkę.

Pozwolić

  • X oznacza całkowity rozmiar stosu
  • M być przestrzenią stosu używaną przy pierwszym wejściu do main
  • R oznacza wzrost miejsca na stosie za każdym razem, gdy wchodzimy do main
  • P oznacza przestrzeń stosu niezbędną do uruchomienia System.out.println

Kiedy po raz pierwszy wchodzimy do main, pozostała przestrzeń to XM. Każde wywołanie rekurencyjne zajmuje R więcej pamięci. Więc dla 1 wywołania rekurencyjnego (o 1 więcej niż oryginał), użycie pamięci wynosi M + R. Załóżmy, że StackOverflowError jest generowany po pomyślnych wywołaniach rekurencyjnych w C, to znaczy M + C * R <= X i M + C * (R + 1)> X. W momencie pierwszego StackOverflowError pozostała pamięć X - M - C * R.

Aby móc biegać System.out.prinln , potrzebujemy P ilość wolnego miejsca na stosie. Jeśli tak się stanie, że X - M - C * R> = P, to zostanie wydrukowane 0. Jeśli P wymaga więcej miejsca, usuwamy ramki ze stosu, uzyskując pamięć R kosztem cnt ++.

Kiedy w printlnkońcu będzie można uruchomić, X - M - (C - cnt) * R> = P. Więc jeśli P jest duże dla konkretnego systemu, to cnt będzie duże.

Spójrzmy na to z kilkoma przykładami.

Przykład 1: Załóżmy

  • X = 100
  • M = 1
  • R = 2
  • P = 1

Wtedy C = podłoga ((XM) / R) = 49, a cnt = sufit ((P - (X - M - C * R)) / R) = 0.

Przykład 2: Załóżmy, że

  • X = 100
  • M = 1
  • R = 5
  • P = 12

Wtedy C = 19 i cnt = 2.

Przykład 3: Załóżmy, że

  • X = 101
  • M = 1
  • R = 5
  • P = 12

Wtedy C = 20 i cnt = 3.

Przykład 4: Załóżmy, że

  • X = 101
  • M = 2
  • R = 5
  • P = 12

Wtedy C = 19 i cnt = 2.

Widzimy więc, że zarówno system (M, R i P), jak i rozmiar stosu (X) mają wpływ na cnt.

Na marginesie, nie ma znaczenia, ile miejsca catchpotrzeba na rozpoczęcie. Dopóki nie ma na to miejsca catch, cnt nie wzrośnie, więc nie ma efektów zewnętrznych.

EDYTOWAĆ

Cofam to, o czym mówiłem catch. Odgrywa rolę. Załóżmy, że do uruchomienia potrzeba T miejsca. cnt zaczyna zwiększać się, gdy pozostała przestrzeń jest większa niż T iprintln działa, gdy pozostała przestrzeń jest większa niż T + P. To dodaje dodatkowy krok do obliczeń i jeszcze bardziej zagmatwa i tak już mętną analizę.

EDYTOWAĆ

W końcu znalazłem czas, aby przeprowadzić kilka eksperymentów, aby potwierdzić moją teorię. Niestety, teoria wydaje się nie zgadzać się z eksperymentami. To, co się właściwie dzieje, jest zupełnie inne.

Konfiguracja eksperymentu: serwer Ubuntu 12.04 z domyślnym java i default-jdk. Xss począwszy od 70 000 z przyrostem 1 bajta do 460 000.

Wyniki są dostępne pod adresem : https://www.google.com/fusiontables/DataSource?docid=1xkJhd4s8biLghe6gZbcfUs3vT5MpS_OnscjWDbM Stworzyłem kolejną wersję, w której każdy powtarzający się punkt danych jest usuwany. Innymi słowy, wyświetlane są tylko punkty różniące się od poprzednich. Dzięki temu łatwiej dostrzec anomalie. https://www.google.com/fusiontables/DataSource?docid=1XG_SRzrrNasepwZoNHqEAKuZlHiAm9vbEdwfsUA

John Tseng
źródło
Dziękuję za dobre podsumowanie, myślę, że wszystko sprowadza się do pytania: co wpływa na M, R i P (skoro X można ustawić opcją VM -Xss)?
flrnb
@flrnb M, R i P są specyficzne dla systemu. Nie możesz ich łatwo zmienić. Spodziewam się, że będą się różnić również między niektórymi wydaniami.
John Tseng,
Dlaczego więc otrzymuję różne wyniki, zmieniając Xss (inaczej X)? Zmiana X ze 100 na 10000, biorąc pod uwagę, że M, R i P pozostają takie same, nie powinna wpływać na cnt według twojego wzoru, czy się mylę?
flrnb,
Sam @flrnb X zmienia cnt ze względu na dyskretny charakter tych zmiennych. Przykłady 2 i 3 różnią się tylko na X, ale cnt jest inny.
John Tseng,
1
@JohnTseng twoją odpowiedź również uważam za najbardziej zrozumiałą i kompletną do tej pory - w każdym razie byłbym naprawdę zainteresowany tym, jak faktycznie wygląda stos w momencie StackOverflowErrorrzucenia i jak wpływa to na wynik. Jeśli zawierało tylko odniesienie do ramki stosu na stercie (jak zasugerował Jay), to wynik powinien być dość przewidywalny dla danego systemu.
flrnb
20

To jest ofiara złego wywołania rekurencyjnego. Ponieważ zastanawiasz się, dlaczego wartość cnt jest różna, dzieje się tak, ponieważ rozmiar stosu zależy od platformy. Java SE 6 w systemie Windows ma domyślny rozmiar stosu 320 KB w 32-bitowej maszynie wirtualnej i 1024 KB w 64-bitowej maszynie wirtualnej. Możesz przeczytać więcej tutaj .

Możesz uruchomić z różnymi rozmiarami stosów, a zobaczysz różne wartości cnt, zanim stos się przepełni.

java -Xss1024k RandomNumberGenerator

Nie widzisz, że wartość cnt jest drukowana wiele razy, mimo że czasami wartość jest większa niż 1, ponieważ instrukcja print również generuje błąd, który możesz debugować, aby mieć pewność, że za pomocą Eclipse lub innych IDE.

Możesz zmienić kod na następujący, aby debugować na wykonanie instrukcji, jeśli wolisz:

static int cnt = 0;

public static void main(String[] args) {                  

    try {     

        main(args);   

    } catch (Throwable ignore) {

        cnt++;

        try { 

            System.out.println(cnt);

        } catch (Throwable t) {   

        }        
    }        
}

AKTUALIZACJA:

Ponieważ przyciąga to dużo więcej uwagi, posłużmy się innym przykładem, aby wszystko było jaśniejsze:

static int cnt = 0;

public static void overflow(){

    try {     

      overflow();     

    } catch (Throwable t) {

      cnt++;                      

    }

}

public static void main(String[] args) {

    overflow();
    System.out.println(cnt);

}

Stworzyliśmy inną metodę o nazwie overflow, aby wykonać złą rekurencję i usunęliśmy instrukcję println z bloku catch, aby nie zaczęła generować kolejnego zestawu błędów podczas próby drukowania. Działa to zgodnie z oczekiwaniami. Możesz spróbować umieścić System.out.println (cnt); instrukcja po cnt ++ powyżej i skompiluj. Następnie uruchom wiele razy. W zależności od platformy możesz uzyskać różne wartości cnt .

Dlatego generalnie nie łapiemy błędów, ponieważ tajemnica w kodzie nie jest fantazją.

Sajal Dutta
źródło
13

Zachowanie zależy od rozmiaru stosu (który można ustawić ręcznie za pomocą Xss. Rozmiar stosu zależy od architektury. Z kodu źródłowego JDK 7 :

// Domyślny rozmiar stosu w systemie Windows jest określany przez plik wykonywalny (java.exe
// ma domyślną wartość 320 KB / 1 MB [32-bitowy / 64-bitowy]). W zależności od wersji systemu Windows zmiana
// ThreadStackSize na wartość niezerową może mieć znaczący wpływ na użycie pamięci.
// Zobacz komentarze w os_windows.cpp.

Więc kiedy StackOverflowErrorjest rzucany, błąd jest przechwytywany w bloku catch. Oto println()kolejne wywołanie stosu, które ponownie zgłasza wyjątek. To się powtarza.

Ile razy to się powtarza? - Cóż, to zależy od tego, kiedy JVM myśli, że nie jest to już przepełnienie stosu. A to zależy od rozmiaru stosu każdego wywołania funkcji (trudne do znalezienia) i Xss. Jak wspomniano powyżej, domyślny całkowity rozmiar i rozmiar każdego wywołania funkcji (zależy od rozmiaru strony pamięci itp.) Zależy od platformy. Stąd inne zachowanie.

Wywołanie javapołączenia z -Xss 4Mdaje mi 41. Stąd korelacja.

Jatin
źródło
4
Nie rozumiem, dlaczego rozmiar stosu miałby wpływać na wynik, skoro jest już przekroczony, gdy próbujemy wydrukować wartość cnt. Zatem jedyna różnica może pochodzić z „rozmiaru stosu każdego wywołania funkcji”. I nie rozumiem, dlaczego powinno się to różnić w przypadku 2 maszyn z tą samą wersją JVM.
flrnb
Dokładne zachowanie można uzyskać tylko ze źródła JVM. Ale powodem może być to. Pamiętaj, że nawet catchjest blokiem i zajmuje pamięć na stosie. Nie wiadomo, ile pamięci zajmuje każde wywołanie metody. Kiedy stos zostanie wyczyszczony, dodajesz jeszcze jeden blok catchi tak dalej. To może być zachowanie. To tylko spekulacje.
Jatin,
Rozmiar stosu może się różnić w przypadku dwóch różnych maszyn. Rozmiar stosu zależy od wielu czynników związanych z systemem operacyjnym, takich jak rozmiar strony pamięci itp.
Jatin
6

Myślę, że wyświetlona liczba to czas, przez jaki System.out.printlnpołączenie zgłasza Stackoverflowwyjątek.

Prawdopodobnie zależy to od implementacji printlni liczby wywołań stosowych, które są w nim wykonywane.

Jako ilustracja:

main()Wywołanie wyzwalacza Stackoverflowwyjątek na połączenia i. Wywołanie i-1 main przechwytuje wyjątek i printlnwywołuje sekundę Stackoverflow. cntpobierz przyrost do 1. Wywołanie i-2 main catch teraz wyjątek i wywołanie println. W printlnmetodzie nazywa się wyzwalanie trzeciego wyjątku. cntuzyskać przyrost do 2. To kontynuuje, aż będzie printlnmożna wykonać wszystkie potrzebne wywołania i ostatecznie wyświetlić wartośćcnt .

Zależy to wtedy od faktycznej implementacji println.

W przypadku JDK7 albo wykrywa wywołanie cykliczne i zgłasza wyjątek wcześniej albo zachowuje trochę zasobów stosu i rzuca wyjątek przed osiągnięciem limitu, aby dać trochę miejsca na logikę naprawczą albo printlnimplementacja nie wykonuje wywołań albo operacja ++ jest wykonywana po printlnpołączenie jest w ten sposób przez przejściu przez wyjątku.

Kazaag
źródło
To właśnie miałem na myśli mówiąc „Myślałem, że może to dlatego, że System.out.println potrzebuje 3 segmentów na stosie wywołań” - ale byłem zdziwiony, dlaczego to dokładnie ta liczba, a teraz jestem jeszcze bardziej zdziwiony, dlaczego liczba różni się tak bardzo między różnymi (wirtualne) maszyny
flrnb
Częściowo się z tym zgadzam, ale nie zgadzam się ze stwierdzeniem „zależy od rzeczywistej implementacji println”. Ma to związek z rozmiarem stosu w każdym jvm, a nie z implementacją.
Jatin,
6
  1. mainpowtarza się do momentu przepełnienia stosu na głębokości rekurencji R.
  2. Uruchamiany jest blok catch na głębokości rekurencji R-1.
  3. R-1Ocenia się blok catch na głębokości rekurencji cnt++.
  4. Blok catch na głębokości R-1wywołuje println, umieszczając cntstarą wartość na stosie. printlnbędzie wewnętrznie wywoływać inne metody i używać lokalnych zmiennych i rzeczy. Wszystkie te procesy wymagają miejsca na stosie.
  5. Ponieważ stos już printlnprzekraczał limit, a wywołanie / wykonanie wymaga miejsca na stosie, nowe przepełnienie stosu jest wyzwalane na głębokości R-1zamiast na głębokości R.
  6. Kroki 2-5 powtarzają się, ale na głębokości rekurencji R-2.
  7. Kroki 2-5 powtarzają się, ale na głębokości rekurencji R-3.
  8. Kroki 2-5 powtarzają się, ale na głębokości rekurencji R-4.
  9. Kroki 2-4 powtarzają się, ale na głębokości rekurencji R-5.
  10. Zdarza się, że jest teraz wystarczająco dużo miejsca na stosie printlndo zakończenia (zwróć uwagę, że jest to szczegół implementacji, może się różnić).
  11. cnt był postinkrementowany na głębokościach R-1 , R-2, R-3, R-4, a na koniec w R-5. Piąty post-inkrementacja zwrócił cztery, czyli to, co zostało wydrukowane.
  12. Po mainpomyślnym zakończeniu na głębokości R-5cały stos jest rozwijany bez uruchamiania kolejnych bloków catch i program kończy się.
Craig Gidney
źródło
1

Po pewnym czasie nie mogę powiedzieć, że znalazłem odpowiedź, ale myślę, że jest już blisko.

Po pierwsze, musimy wiedzieć, kiedy StackOverflowErrorzostanie wyrzucony testament. W rzeczywistości stos wątku Java przechowuje ramki, które zawierają wszystkie dane potrzebne do wywołania metody i wznowienia. Zgodnie ze specyfikacjami języka Java dla JAVA 6 podczas wywoływania metody

Jeśli nie ma wystarczającej ilości pamięci do utworzenia takiej ramki aktywacji, generowany jest błąd StackOverflowError.

Po drugie, powinniśmy wyjaśnić, co oznacza „ brak wystarczającej ilości pamięci do utworzenia takiej ramki aktywacji ”. Zgodnie ze specyfikacjami maszyn wirtualnych Java dla JAVA 6 ,

ramki mogą być alokowane na stercie.

Tak więc po utworzeniu ramki powinno być wystarczająco dużo miejsca na sterty, aby utworzyć ramkę stosu i wystarczająco dużo miejsca na stosie, aby zapisać nowe odniesienie, które wskazuje na nową ramkę stosu, jeśli ramka jest przydzielona na sterty.

Wróćmy teraz do pytania. Z powyższego możemy wiedzieć, że gdy metoda jest wykonywana, może to po prostu kosztować taką samą ilość miejsca na stosie. A wywołanie System.out.println(może) wymagać 5 poziomów wywołania metody, więc należy utworzyć 5 ramek. Następnie, gdy StackOverflowErrorzostanie wyrzucony, musi cofnąć się 5 razy, aby uzyskać wystarczająco dużo miejsca na stosie do przechowywania odwołań do 5 ramek. Stąd 4 jest drukowane. Dlaczego nie 5? Ponieważ używasz cnt++. Zmień to na ++cnt, a otrzymasz 5.

Zauważysz, że kiedy rozmiar stosu osiągnie wysoki poziom, czasami otrzymasz 50. Dzieje się tak, ponieważ wtedy należy wziąć pod uwagę ilość dostępnego miejsca na stercie. Kiedy rozmiar stosu jest zbyt duży, może zabraknie miejsca na stosie przed stosem. I (być może) rzeczywisty rozmiar klatek stosu System.out.printlnwynosi około 51 razy main, więc cofa się 51 razy i drukuje 50.

Sójka
źródło
Moją pierwszą myślą było również policzenie poziomów wywołań metod (i masz rację, nie zwróciłem uwagi na fakt, że publikuję cnt inkrementacji), ale gdyby rozwiązanie było tak proste, dlaczego wyniki miałyby się tak bardzo różnić na różnych platformach i implementacje maszyn wirtualnych?
flrnb
@flrnb Dzieje się tak, ponieważ różne platformy mogą wpływać na rozmiar ramki stosu, a różne wersje środowiska jre będą miały wpływ na implementację System.out.printlub strategię wykonywania metody. Jak opisano powyżej, implementacja maszyny wirtualnej ma również wpływ na to, gdzie ramka stosu będzie faktycznie przechowywana.
Jay
0

To nie jest dokładna odpowiedź na pytanie, ale chciałem tylko dodać coś do pierwotnego pytania, na które się natknąłem i jak zrozumiałem problem:

W pierwotnym problemie wyjątek jest wychwytywany tam, gdzie było to możliwe:

Na przykład w przypadku jdk 1.7 jest łapany w pierwszym miejscu wystąpienia.

ale we wcześniejszych wersjach jdk wygląda na to, że wyjątek nie jest wychwytywany w pierwszym miejscu, stąd 4, 50 itd.

Teraz, jeśli usuniesz blok try catch w następujący sposób

public static void main( String[] args ){
    System.out.println(cnt++);
    main(args);
}

Wtedy zobaczysz wszystkie wartości cntant wyrzuconych wyjątków (w jdk 1.7).

Użyłem netbeans, aby zobaczyć dane wyjściowe, ponieważ cmd nie pokaże wszystkich danych wyjściowych i zgłoszonych wyjątków.

me_digvijay
źródło