Hoe de maximale aanroepdiepte van een recursieve methode voorspellen?

Wat is de (bij benadering) formule voor het berekenen van het geheugen dat wordt gebruikt voordat er waarschijnlijk een stackoverflow-fout optreedt?

Bewerken:

Velen hebben gereageerd met “het hangt ervan af”, wat redelijk is, dus laten we enkele variabelen verwijderen door een triviaal maar concreet voorbeeld te gebruiken:

public static int sumOneToN(int n) {
    return n < 2 ? 1 : n + sumOneToN(n - 1);
}

Het is gemakkelijk om aan te tonen dat het uitvoeren van dit in mijn Eclipse IDE explodeert voor nnet onder de 1000 (verrassend laag voor mij).
Kan deze limiet voor de gespreksdiepte geschat zijn zonder deze uit te voeren?

Bewerken: ik kan het niet helpen te denken dat Eclipse een vaste maximale oproepdiepte van 1000 heeft, omdat ik tot 998ben gekomen, maar er is één voor de hoofdaanroep en één voor de eerste aanroep naar de methode, wat in totaal 1000maakt. Dit is een “te rond” getal IMHO om toeval te zijn. Ik zal verder onderzoeken. Ik heb net Dux overhead de -Xss vm parameter; het is de maximale stapelgrootte, dus Eclipse Runner moet ergens -Xss1000hebben ingesteld

Antwoord 1, autoriteit 100%

Dit is duidelijk JVM- en mogelijk ook architectuurspecifiek.

Ik heb het volgende gemeten:

 static int i = 0;
  public static void rec0() {
      i++;
      rec0();
  }
  public static void main(String[] args) {
      ...
      try {
          i = 0; rec0();
      } catch (StackOverflowError e) {
          System.out.println(i);
      }
      ...
  }

met

Java(TM) SE Runtime Environment (build 1.7.0_09-b05)
Java HotSpot(TM) 64-Bit Server VM (build 23.5-b02, mixed mode)

draait op x86.

Met een Java-stack van 20 MB (-Xss20m) schommelden de afgeschreven kosten rond de 16-17 bytes per gesprek. De laagste die ik heb gezien was 16,15 bytes/frame. Ik concludeer daarom dat de kosten 16 bytes zijn en de rest andere (vaste) overhead is.

Een functie waarvoor een enkele intnodig is, heeft in principe dezelfde kosten, 16 bytes/frame.

Interessant is dat een functie die tien intsduurt, 32 bytes/frame nodig heeft. Ik weet niet zeker waarom de kosten zo laag zijn.

De bovenstaande resultaten zijn van toepassing nadat de code JIT is gecompileerd. Voorafgaand aan de compilatie zijn de kosten per frame veel, veelhoger. Ik heb nog geen manier gevonden om het betrouwbaar in te schatten. Dit betekent echter wel dat je geen hoop hebt op een betrouwbare voorspelling van de maximale recursiediepte totdat je betrouwbaar kunt voorspellen of de recursieve functie JIT-gecompileerd is.

Dit alles is getest met een ulimit-stackgrootte van 128K en 8MB. De resultaten waren in beide gevallen hetzelfde.

Antwoord 2, autoriteit 40%

Slechts een gedeeltelijk antwoord: van JVM Spec 7, 2.5.2, stapelframes kunnen op de heap worden toegewezen en de stapelgrootte kan dynamisch zijn. Ik zou het niet met zekerheid kunnen zeggen, maar het lijkt erop dat het mogelijk zou moeten zijn om je stapelgrootte alleen te laten begrenzen door je heapgrootte:

Omdat de Java-stack van de virtuele machine nooit rechtstreeks wordt gemanipuleerd, behalve om frames te pushen en te laten springen, kunnen frames worden toegewezen aan heaps.

en

Deze specificatie staat toe dat Java-stacks voor virtuele machines ofwel
een vaste grootte of om dynamisch uit te breiden en in te krimpen zoals vereist door de
berekening. Als de Java-stacks voor virtuele machines een vaste grootte hebben,
de grootte van elke Java virtual machine-stack kan worden gekozen
onafhankelijk wanneer die stapel wordt gemaakt.

Een Java-implementatie van een virtuele machine kan de programmeur of
de gebruikerscontrole over de initiële grootte van Java virtual machine-stacks,
evenals, in het geval van dynamisch uitbreiden of krimpen van Java
virtuele machine-stacks, controle over de maximale en minimale grootte.

Het is dus aan de JVM-implementatie.

Antwoord 3, autoriteit 16%

Toevoegen aan NPE’s antwoord:

De maximale stapeldiepte lijkt flexibelte zijn. Het volgende testprogramma drukt enormverschillende getallen af:

public class StackDepthTest {
    static int i = 0;
    public static void main(String[] args) throws Throwable {
        for(int i=0; i<10; ++i){
            testInstance();
        }
    }
    public static void testInstance() {
        StackDepthTest sdt = new StackDepthTest();
        try {
            i=0;
            sdt.instanceCall();
        } catch(StackOverflowError e){}
        System.out.println(i);
    }
    public void instanceCall(){
        ++i;
        instanceCall();
    }
}

De uitvoer is:

10825
10825
59538
59538
59538
59538
59538
59538
59538
59538

Ik heb de standaard van deze JRE gebruikt:

java version "1.7.0_09"
OpenJDK Runtime Environment (IcedTea7 2.3.3) (7u9-2.3.3-0ubuntu1~12.04.1)
OpenJDK 64-Bit Server VM (build 23.2-b09, mixed mode)

Dus de conclusie is: als je pus genoeg hebt gehad (d.w.z. meer dan twee keer), krijg je een tweede kans 😉

Antwoord 4, autoriteit 12%

Het antwoord is, het hangt er allemaal vanaf.

Allereerst kan de grootte van de Java-stack worden gewijzigd.

Ten tweede kan de grootte van het stapelframe van een bepaalde methode variëren op basis van verschillende variabelen. Je kunt de sectie Call Stack Frame Size van Call stack – Wikipediabekijken voor meer details.

Antwoord 5, autoriteit 8%

hangt af van uw systeemarchitectuur (32- of 64-bits adressen), het aantal lokale variabelen en parameters van de methode.
Als het tail-recursivegeen overhead is, als de compiler het optimaliseert tot een lus .

Zie je, geen eenvoudig antwoord.

Antwoord 6, autoriteit 8%

Je kunt de empirische weg inslaan en experimenteren met je code en de instelling -Xss. Zie hier voor meer: ​​JVM-optie -Xss – Wat doet het precies?