F # vs OCaml: overflow dello stack

Question

Recentemente ho trovato una presentazione su F# for Python programmers e, dopo averlo visto, ho deciso di implementare una soluzione al "puzzle delle formiche" per conto mio.

C'è una formica che può camminare su una griglia planare. La formica può muovere uno spazio alla volta a sinistra, a destra, in alto o in basso. Cioè, dalla cellula (x, y) la formica può andare alle celle (x + 1, y), (x-1, y), (x, y + 1) e (x, y-1). I punti in cui la somma delle cifre delle coordinate xey sono maggiori di 25 non sono accessibili alla formica. Ad esempio, il punto (59,79) è inaccessibile perché 5 + 9 + 7 + 9 = 30, che è maggiore di 25. La domanda è: Quanti punti può accedere alla formica se inizia a (1000, 1000), incluso (1000, 1000) stesso?

ho implementato mia soluzione in 30 righe di OCaml first e provato fuori:

$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml 
$ time ./puzzle 
Points: 148848 

real 0m0.143s 
user 0m0.127s 
sys  0m0.013s 

accurato, il mio risultato è lo stesso di quello di leonardo's implementation, in D and C++. Paragonato all'implementazione del C++ di leonardo, la versione di OCaml funziona circa 2 volte più lentamente del C++. Che è OK, dato che Leonardo ha usato una coda per rimuovere la ricorsione.

Ho poi translated the code to F# ... ed ecco quello che ho ottenuto:

Thanassis@HOME /g/Tmp/ant.fsharp 
$ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs 
Microsoft (R) F# 2.0 Compiler build 2.0.0.0 
Copyright (c) Microsoft Corporation. All Rights Reserved. 

Thanassis@HOME /g/Tmp/ant.fsharp 
$ ./ant.exe 

Process is terminated due to StackOverflowException. 
Quit 

Thanassis@HOME /g/Tmp/ant.fsharp 
$ /g/Program\ Files/Microsoft\ F#/v4.0/Fsc.exe ant.fs 
Microsoft (R) F# 2.0 Compiler build 4.0.30319.1 
Copyright (c) Microsoft Corporation. All Rights Reserved. 

Thanassis@HOME /g/Tmp/ant.fsharp 
$ ./ant.exe 

Process is terminated due to StackOverflowException 

Stack overflow ... con entrambe le versioni di F # che ho nella mia macchina ... per curiosità, ho poi preso la generato binario (ant.exe) ed eseguirlo sotto Arch Linux/Mono:

$ mono -V | head -1 
Mono JIT compiler version 2.10.5 (tarball Fri Sep 9 06:34:36 UTC 2011) 

$ time mono ./ant.exe 
Points: 148848 

real 1m24.298s 
user 0m0.567s 
sys  0m0.027s 

Sorprendentemente, gira sotto Mono 2.10.5 (cioè senza overflow dello stack) - ma ci vogliono 84 secondi, vale a dire 587 volte più lento OCaml - oops.

Quindi questo programma ...

• funziona bene sotto OCaml
• non funziona affatto in .NET/F #
• opere, ma è molto lento, sotto Mono/F #.

Perché?

EDIT: Stranezze prosegue - Usando "--optimize + --checked-" rende il problema scompare, ma solo sotto ArchLinux/Mono; sotto Windows XP e Windows 7/64bit, anche la versione ottimizzata dello stack binario trabocca.

Final EDIT: Ho scoperto la risposta da solo - vedi sotto.

Answer 1

Sintesi:

• ho scritto una semplice implementazione di un algoritmo ... che non era ricorsiva in coda.
• L'ho compilato con OCaml sotto Linux.
• Ha funzionato bene e ha completato in 0,14 secondi.

Era quindi il momento di portarsi su F #.

• Ho tradotto il codice (traduzione diretta) in F #.
• Ho compilato Windows e l'ho eseguito: ho ricevuto uno stack overflow.
• Ho preso il binario sotto Linux e l'ho eseguito sotto Mono.
• Ha funzionato, ma funziona molto lentamente (84 secondi).

Ho quindi inviato a Stack Overflow - ma alcune persone hanno deciso di chiudere la domanda (sospiro).

• la compilazione con --optimize + --checked-
• Il binario ancora pila straripato sotto Windows ...
• ... ma gestito bene (e finito in 0,5 secondi) sotto Linux/Mono .

Era giunto il momento di verificare le dimensioni dello stack: in Windows, another SO post pointed out that it is set by default to 1MB. Sotto Linux, "uname -s" e a compilation of a test program hanno mostrato chiaramente che è 8 MB.

Questo spiega perché il programma ha funzionato sotto Linux e non sotto Windows (il programma ha utilizzato più di 1 MB di stack). Non ha spiegato perché la versione ottimizzata funzioni molto meglio in Mono rispetto a quella non ottimizzata: 0,5 secondi contro 84 secondi (anche se il --optimize + sembra essere impostato di default, vedi commento di Keith con "Expert F #" estratto). Probabilmente ha a che fare con il netturbino di Mono, che è stato in qualche modo spinto agli estremi dalla prima versione.

La differenza tra i tempi di esecuzione di Linux/OCaml e Linux/Mono/F # (0,14 vs 0,5) è dovuta al modo semplice in cui l'ho misurata: "time ./binary ..." misura anche il tempo di avvio, che è significativo per Mono/.NET (beh, significativo per questo semplice piccolo problema).

Comunque, per risolvere questo volta per tutte, che wrote a tail-recursive version - dove la chiamata ricorsiva alla fine della funzione si trasforma in un loop (e quindi, nessun utilizzo stack è necessario - almeno in teoria).

La nuova versione funziona bene anche in Windows e termina in 0,5 secondi.

Quindi, morale della storia:

• Attenzione del vostro uso pila, soprattutto se si utilizza un sacco di esso ed eseguire sotto Windows. Utilizzare EDITBIN with the /STACK option per impostare i file binari in dimensioni di stack più grandi o, meglio ancora, scrivere il codice in un modo che non dipenda dall'utilizzo di un numero eccessivo di stack.
• OCaml può essere migliore nell'eliminazione della ricorsione in coda rispetto a F # - oppure il garbage collector sta facendo un lavoro migliore a questo particolare problema.
• non disperate su ... la gente rude chiudendo le vostre domande Stack Overflow, buona gente li contrastano alla fine - se le domande sono davvero buoni :-)

P.S. Qualche ulteriore input da parte del dott. Jon Harrop:

... sei stato solo fortunato che OCaml non ha traboccato troppo. Hai già identificato che le dimensioni effettive dello stack variano tra piattaforme. Un altro aspetto dello stesso problema è che le implementazioni linguistiche differenti occupano lo spazio di stack a velocità diverse e presentano caratteristiche di prestazione diverse in presenza di stack profondi. OCAML, Mono e.NET utilizzano tutte le rappresentazioni di dati e gli algoritmi GC che influiscono su questi risultati ... (a) OCaml utilizza gli interi con tag per distinguere i puntatori, dando frame stack compatti e attraversa tutto lo stack cercando i puntatori. Il tagging trasmette essenzialmente abbastanza informazioni per il runtime OCaml per poter attraversare l'heap (b) Mono tratta le parole sullo stack in modo conservativo come puntatori: se, come puntatore, una parola punterebbe a in un heap assegnato bloccare quindi quel blocco è considerato raggiungibile. (c) Non conosco l'algoritmo di .NET ma non sarei sorpreso se avesse mangiato più velocemente lo stack e continuasse a passare ogni parola nello stack (sicuramente lo soffre delle prestazioni patologiche del GC se un thread non correlato ha un deep stack!) ... Inoltre, l'uso di tuple allocate all'heap significa che dovrai riempire rapidamente la generazione di vivaio (ad es. gen0) e quindi facendo sì che il GC attraversi spesso quelle pile profonde ...

Answer 2

Lasciatemi provare a riassumere la risposta.

Ci sono 3 punti da effettuare:

• problema: overflow dello stack accade su una funzione ricorsiva
• succede solo sotto windows: su Linux, per le dimensioni proble esaminata, funziona
• stesso (o simile) codice OCaml funziona
• ottimizzare + bandiera compilatore, per le dimensioni proble esaminato, lavori

È molto comune che un'eccezione di Stack Overflow sia il risultato di un vall ricorsivo. Se la chiamata è in posizione di coda, il compilatore può riconoscerla e applicare l'ottimizzazione di tailcall, pertanto le chiamate ricorsive non occuperanno lo spazio di stack. Tailcall ottimizzazione può accadere in F #, nel CRL, o in entrambi:

CLR coda ottimizzazione 1

F # ricorsione (più generale) 2

F # coda chiama 3

la correttezza spiegazione per "fail su Windows, non in Linux", come detto, lo spazio di stack riservato predefinito sui due sistemi operativi. O meglio, lo spazio di stack riservato utilizzato dai compilatori sotto i due sistemi operativi. Per impostazione predefinita, VC++ riserva solo 1 MB di spazio nello stack. Il CLR è (probabilmente) compilato con VC++, quindi ha questa limitazione. Lo spazio di stack riservato può essere aumentato in fase di compilazione, ma non sono sicuro che possa essere modificato sugli eseguibili compilati.

EDIT: scopre che si può fare (vedi questo post http://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx) io non lo consiglio, ma in situazioni estreme, almeno è possibile.

La versione di OCaml potrebbe funzionare perché è stata eseguita sotto Linux. Tuttavia, sarebbe interessante provare anche la versione OCaml sotto Windows. So che il compilatore OCaml è più aggressivo nell'ottimizzazione della coda di chiamata di F # .. potrebbe anche estrarre una funzione di coda riutilizzabile dal codice originale?

La mia ipotesi su "--optimize +" è che causerà ancora la ripetizione del codice, quindi non funzionerà ancora in Windows, ma attenuerà il problema facendo accelerare l'esecuzione.

Infine, la soluzione definitiva consiste nell'utilizzare la ricorsione in coda (riscrivendo il codice o realizzando l'ottimizzazione aggressiva del compilatore); è un buon modo per evitare problemi di overflow dello stack con funzioni ricorsive.