Jak zwiększyć rozmiar stosu Java?

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 TTpowyż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, nzwię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, -Xss18mwystarczyło w 7 na 10, i też -Xss19mnie zawsze było wystarczające, ale -Xss20mwystarczał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. StackObiektu, który jest zapełniany na stercie zamiast na stosie środowiska wykonawczego). W przypadku tej konkretnej factfunkcji 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, factfunkcja nie może obliczyć dokładnej silni liczb powyżej 65 (w rzeczywistości nawet powyżej 20), ponieważ typ wbudowany w Javie longbyłby przepełniony. Refaktoryzacja, factaby zwracała a BigIntegerzamiast longdawałaby dokładne wyniki również dla dużych danych wejściowych.

Hmm ... to działa dla mnie i przy znacznie mniej niż 999 MB stosu:

> java -Xss4m Test
0

(Windows JDK 7, maszyna wirtualna klienta kompilacji 17.0-b05 i Linux JDK 6 - te same informacje o wersji, które opublikowałeś)

Zakładam, że obliczyłeś „głębokość 1024” na podstawie powtarzających się linii w śladzie stosu?

Oczywiście długość tablicy śledzenia stosu w Throwable wydaje się być ograniczona do 1024. Wypróbuj następujący program:

public class Test {

    public static void main(String[] args) {

        try {
            System.out.println(fact(1 << 15));
        }
        catch (StackOverflowError e) {
            System.err.println("true recursion level was " + level);
            System.err.println("reported recursion level was " +
                               e.getStackTrace().length);
        }
    }

    private static int level = 0;
    public static long fact(int n) {
        level++;
        return n < 2 ? n : n * fact(n - 1);
    }
}

Jeśli chcesz bawić się rozmiarem stosu wątków, przyjrzyj się opcji -Xss w wirtualnej maszynie wirtualnej Hotspot. Może to być coś innego na maszynach wirtualnych innych niż Hotspot, ponieważ parametry -X maszyny JVM są specyficzne dla dystrybucji, IIRC.

W Hotspot wygląda to tak java -Xss16M , chcesz, aby rozmiar 16 megabajtów.

Rodzaj java -X -help jeśli chcesz zobaczyć wszystkie parametry maszyny JVM specyficzne dla dystrybucji, które możesz przekazać. Nie jestem pewien, czy działa to tak samo na innych maszynach JVM, ale wyświetla wszystkie parametry specyficzne dla Hotspot.

Na co warto - poleciłbym ograniczenie korzystania z metod rekurencyjnych w Javie. Optymalizacja ich nie jest zbyt dobra - po pierwsze JVM nie obsługuje rekurencji ogonowej (zobacz Czy JVM zapobiega optymalizacji wywołań ogonowych? ). Spróbuj refaktoryzować swój kod silni powyżej, aby użyć pętli while zamiast rekurencyjnych wywołań metod.

Jedynym sposobem kontrolowania rozmiaru stosu w procesie jest rozpoczęcie nowego Thread. Ale możesz także sterować, tworząc samowywołujący się proces języka Java z -Xssparametrem.

public class TT {
    private static int level = 0;

    public static long fact(int n) {
        level++;
        return n < 2 ? n : n * fact(n - 1);
    }

    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(null, null, "TT", 1000000) {
            @Override
            public void run() {
                try {
                    level = 0;
                    System.out.println(fact(1 << 15));
                } catch (StackOverflowError e) {
                    System.err.println("true recursion level was " + level);
                    System.err.println("reported recursion level was "
                            + e.getStackTrace().length);
                }
            }

        };
        t.start();
        t.join();
        try {
            level = 0;
            System.out.println(fact(1 << 15));
        } catch (StackOverflowError e) {
            System.err.println("true recursion level was " + level);
            System.err.println("reported recursion level was "
                    + e.getStackTrace().length);
        }
    }

}

Dodaj tę opcję

--driver-java-options -Xss512m

do polecenia spark-submit, rozwiąże ten problem.

Trudno jest znaleźć rozsądne rozwiązanie, ponieważ chcesz unikać wszelkich rozsądnych podejść. Dobrym rozwiązaniem jest refaktoryzacja jednej linii kodu.

Uwaga: Użycie -Xss ustawia rozmiar stosu każdego wątku i jest bardzo złym pomysłem.

Innym podejściem jest manipulacja kodem bajtowym w celu zmiany kodu w następujący sposób;

public static long fact(int n) { 
    return n < 2 ? n : n > 127 ? 0 : n * fact(n - 1); 
}

dana każda odpowiedź dla n> 127 wynosi 0. Pozwala to uniknąć zmiany kodu źródłowego.

Dziwne! Mówisz, że chcesz wygenerować rekursję 1 << 15 głębokości ??? !!!!

Proponuję NIE próbować. Rozmiar stosu będzie 2^15 * sizeof(stack-frame). Nie wiem, jaki jest rozmiar ramki stosu, ale 2 ^ 15 to 32,768. Prawie ... Cóż, jeśli zatrzyma się na 1024 (2 ^ 10), będziesz musiał uczynić go 2 ^ 5 razy większy, czyli 32 razy większy niż przy aktualnym ustawieniu.

Inne plakaty wskazywały, jak zwiększyć pamięć i że można zapamiętywać rozmowy. Sugerowałbym, że dla wielu zastosowań można użyć wzoru Stirlinga do przybliżenia dużego n! bardzo szybko, prawie bez śladu pamięci.

Spójrz na ten post, który zawiera analizę funkcji i kodu:

http://threebrothers.org/brendan/blog/stirlings-approximation-formula-clojure/

Zrobiłem Anagram excersize , który jest podobny do problemu Count Change, ale z 50 000 nominałów (monet). Nie jestem pewien, czy da się to zrobić iteracyjnie , nie obchodzi mnie to. Wiem tylko, że opcja -xss nie przyniosła żadnego efektu - zawsze zawodziło po 1024 klatkach stosu (być może scala źle radzi sobie z dostarczaniem do java lub ograniczenia printStackTrace. Nie wiem). To zła opcja, jak wyjaśniono w każdym razie. Nie chcesz, aby wszystkie wątki w aplikacji były potworne. Jednak wykonałem kilka eksperymentów z nowym wątkiem (rozmiar stosu). To rzeczywiście działa,

  def measureStackDepth(ss: Long): Long = {
    var depth: Long = 0
      val thread: Thread = new Thread(null, new Runnable() {
        override def run() {
          try {
          def sum(n: Long): Long = {depth += 1; if (n== 0) 0 else sum(n-1) + 1}
          println("fact = " + sum(ss * 10))
          } catch {
            case e: StackOverflowError => // eat the exception, that is expected
          }
        }
      }, "deep stack for money exchange", ss)
      thread.start()
      thread.join()
    depth
  }                                               //> measureStackDepth: (ss: Long)Long


  for (ss <- (0 to 10)) println("ss = 10^" +  ss + " allows stack of size " -> measureStackDepth((scala.math.pow (10, ss)).toLong) )
                                                  //> fact = 10
                                                  //| (ss = 10^0 allows stack of size ,11)
                                                  //| fact = 100
                                                  //| (ss = 10^1 allows stack of size ,101)
                                                  //| fact = 1000
                                                  //| (ss = 10^2 allows stack of size ,1001)
                                                  //| fact = 10000
                                                  //| (ss = 10^3 allows stack of size ,10001)
                                                  //| (ss = 10^4 allows stack of size ,1336)
                                                  //| (ss = 10^5 allows stack of size ,5456)
                                                  //| (ss = 10^6 allows stack of size ,62736)
                                                  //| (ss = 10^7 allows stack of size ,623876)
                                                  //| (ss = 10^8 allows stack of size ,6247732)
                                                  //| (ss = 10^9 allows stack of size ,62498160)

Widzisz, że stos może rosnąć wykładniczo głębiej z wykładniczo większym stosem przeznaczonym na wątek.