Zadałem to pytanie, aby dowiedzieć się, jak zwiększyć rozmiar stosu wywołań środowiska wykonawczego w JVM. Mam odpowiedź na to pytanie, a także wiele przydatnych odpowiedzi i komentarzy dotyczących tego, jak Java radzi sobie z sytuacją, w której potrzebny jest duży stos środowiska wykonawczego. Moje pytanie rozszerzyłem o podsumowanie odpowiedzi.
Początkowo chciałem zwiększyć rozmiar stosu JVM, aby programy takie jak działały bez rozszerzenia StackOverflowError
.
public class TT {
public static long fact(int n) {
return n < 2 ? 1 : n * fact(n - 1);
}
public static void main(String[] args) {
System.out.println(fact(1 << 15));
}
}
Odpowiednim ustawieniem konfiguracyjnym jest java -Xss...
flaga wiersza polecenia z odpowiednio dużą wartością. W przypadku TT
powyższego programu działa to w następujący sposób z JVM OpenJDK:
$ javac TT.java
$ java -Xss4m TT
Jedna z odpowiedzi wskazuje również, że -X...
flagi są zależne od implementacji. Używałem
java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1~8.04.3)
OpenJDK 64-Bit Server VM (build 16.0-b13, mixed mode)
Możliwe jest również określenie dużego stosu tylko dla jednego wątku (zobacz w jednej z odpowiedzi, jak to zrobić). Jest to zalecane powyżejjava -Xss...
aby uniknąć marnowania pamięci dla wątków, które jej nie potrzebują.
Byłem ciekawy, jak duży stos dokładnie potrzebuje powyższy program, więc uruchomiłem go, n
zwiększając:
- -Xss4m może wystarczyć dla
fact(1 << 15)
- -Xss5m może wystarczyć dla
fact(1 << 17)
- -Xss7m może wystarczyć dla
fact(1 << 18)
- -Xss9m może wystarczyć dla
fact(1 << 19)
- -Xss18m może wystarczyć dla
fact(1 << 20)
- -Xss35m może wystarczyć do
fact(1 << 21)
- -Xss68m może wystarczyć dla
fact(1 << 22)
- -Xss129m może wystarczyć dla
fact(1 << 23)
- -Xss258m może wystarczyć do
fact(1 << 24)
- -Xss515m może wystarczyć
fact(1 << 25)
Z powyższych liczb wynika, że Java wykorzystuje około 16 bajtów na ramkę stosu dla powyższej funkcji, co jest rozsądne.
Powyższe wyliczenie może wystarczyć, a nie wystarczy , ponieważ wymagania dotyczące stosu nie są deterministyczne: uruchomienie go wiele razy z tym samym plikiem źródłowym i to samo -Xss...
czasami kończy się sukcesem, a czasami daje plik StackOverflowError
. Np. Na 1 << 20, -Xss18m
wystarczyło w 7 na 10, i też -Xss19m
nie zawsze było wystarczające, ale -Xss20m
wystarczało (w sumie 100 na 100). Czy wyrzucanie elementów bezużytecznych, włączanie się JIT lub coś innego powoduje to niedeterministyczne zachowanie?
Ślad stosu wydrukowany w a StackOverflowError
(i prawdopodobnie także w innych wyjątkach) pokazuje tylko najnowsze 1024 elementy stosu środowiska wykonawczego. Poniższa odpowiedź pokazuje, jak policzyć dokładną osiągniętą głębokość (która może być znacznie większa niż 1024).
Wiele osób, które odpowiedziały, wskazało, że dobrą i bezpieczną praktyką kodowania jest rozważenie alternatywnych, mniej obciążających stosy implementacji tego samego algorytmu. Ogólnie rzecz biorąc, jest możliwa konwersja do zestawu funkcji rekurencyjnych na funkcje iteracyjne (przy użyciu np. Stack
Obiektu, który jest zapełniany na stercie zamiast na stosie środowiska wykonawczego). W przypadku tej konkretnej fact
funkcji dość łatwo ją przekonwertować. Moja wersja iteracyjna wyglądałaby następująco:
public class TTIterative {
public static long fact(int n) {
if (n < 2) return 1;
if (n > 65) return 0; // Enough powers of 2 in the product to make it (long)0.
long f = 2;
for (int i = 3; i <= n; ++i) {
f *= i;
}
return f;
}
public static void main(String[] args) {
System.out.println(fact(1 << 15));
}
}
FYI, jak pokazuje to rozwiązanie iteracyjne powyżej, fact
funkcja nie może obliczyć dokładnej silni liczb powyżej 65 (w rzeczywistości nawet powyżej 20), ponieważ typ wbudowany w Javie long
byłby przepełniony. Refaktoryzacja, fact
aby zwracała a BigInteger
zamiast long
dawałaby dokładne wyniki również dla dużych danych wejściowych.