Quante sono le troppe chiamate di funzioni nidificate?

15

Citato da MSDN su StackOverflowException :

The exception that is thrown when the execution stack overflows because it contains too many nested method calls.

Too many è piuttosto vago qui. Come faccio a sapere quando troppi sono davvero troppi? Migliaia di chiamate di funzione? Milioni? Suppongo che debba essere correlato in qualche modo alla quantità di memoria nel computer, ma è possibile ottenere un ordine di grandezza approssimativamente preciso?

Sono preoccupato di questo perché sto sviluppando un progetto che comporta un uso massiccio di strutture ricorsive e chiamate di funzioni ricorsive. Non voglio che l'applicazione fallisca quando comincio ad usarlo per più di semplici test.

    
posta marco-fiset 06.03.2013 - 21:47
fonte

3 risposte

27

I'm concerned about this because I am developping a project which involves a heavy use of recursive structures and recursive function calls. I don't want the application to fail when I start using it for more than just small tests.

A meno che il tuo ambiente linguistico supporti ottimizzazione chiamata coda (e la tua ricorsione è chiamata coda) ), una regola empirica di base è: la profondità di ricorsione deve essere garantita come O (log n), cioè utilizzando algoritmi o strutture dati basate su divide-and-conquer (come gli alberi, la maggior parte degli algoritmi di ordinamento, ecc.) è OK, ma nulla di lineare (come le implementazioni ricorsive della gestione delle liste collegate) non lo è.

    
risposta data 06.03.2013 - 22:04
fonte
16

Per impostazione predefinita, CLR assegna 1 MB allo stack per ogni thread (vedere questo articolo ). Quindi, sono comunque molte le chiamate necessarie per superare questa quantità. Ciò varierà in base alla quantità di spazio nello stack utilizzato da ciascuna chiamata per cose come parametri e variabili locali.

Puoi persino lanciare un StackOverflowException con una sola chiamata se sei disposto a essere un po 'poco ortodosso:

private static unsafe void BlowUpTheStack()
{
    var x = stackalloc byte[1000000000];
    Console.WriteLine("Oh no, I've blown up the stack!");
}
    
risposta data 06.03.2013 - 21:58
fonte
2

Poiché Cole Campbell ha rilevato dimensioni della memoria e Michael Borgwardt ha rilevato ottimizzazione della chiamata a coda Non li coprirò.

Un'altra cosa a cui prestare attenzione è CPS che può essere utilizzata per ottimizzare diverse funzioni intrecciate in cui l'ottimizzazione della coda di chiamata è per singole funzioni.

Puoi aumentare la dimensione dello stack come abbiamo fatto qui e tieni presente che il codice a 64 bit mangia lo stack più velocemente del codice a 32 bit.

Da notare che abbiamo eseguito uno degli esempi in F # interattivo per più di 40 ore senza far esplodere lo stack. Sì, è stata una chiamata a una funzione che ha funzionato da sola continuamente fino al completamento.

Inoltre, se hai bisogno di fare copertura del codice per capire dove si verificano i problemi e non avere copertura del codice con VS, puoi usare TestDriven .NET

    
risposta data 06.03.2013 - 23:17
fonte

Leggi altre domande sui tag