F # vs OCaml: Stack overflow

Question

Niedawno znalazłem prezentację o F# for Python programmers, a po jej obejrzeniu zdecydowałem się na samodzielne wdrożenie rozwiązania "mrówki".

Istnieje mrówka, która może chodzić po planarnej kratce. Mrówka może poruszać się o jedno pole w lewo, w prawo, w górę lub w dół. Oznacza to, że z komórki (x, y) mrówka może przejść do komórek (x + 1, y), (x-1, y), (x, y + 1) i (x, y-1). Punkty, w których suma cyfr współrzędnych x i y jest większa niż 25, jest niedostępna dla mrówki. Na przykład punkt (59,79) jest niedostępny, ponieważ 5 + 9 + 7 + 9 = 30, który jest większy niż 25. Pytanie brzmi: Ile punktów może mieć dostęp do mrówki, jeśli zaczyna się od (1000, 1000), w tym (1000, 1000)?

I wdrożone moje rozwiązanie w 30 liniach OCaml first i spróbował go:

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

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

Neat, mój wynik jest taki sam jak leonardo's implementation, in D and C++. W porównaniu do implementacji C++ leonarda, wersja OCaml działa około 2 razy wolniej niż C++. Co jest w porządku, biorąc pod uwagę, że Leonardo używał kolejki do usuwania rekursji.

Potem translated the code to F# ... i oto co mam:

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 

przepełnienie stosu ... obiema wersjami F # mam w moim komputerze ... z ciekawości, ja potem wziął generowane binarne (ant.exe) i uruchomić go pod 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 

Niespodziewanie biegnie pod Mono 2.10.5 (czyli bez przepełnienia stosu) - ale to trwa 84 sekund, czyli 587 razy wolniej niż OCaml - oops.

Więc ten program ...

• działa poprawnie pod SML
• nie działa w ogóle pod .NET/C#
• działa, ale jest bardzo powolny, pod Mono/F #.

Dlaczego?

EDIT: Weirdness kontynuuje - Używanie "--optimize + --checked-" sprawia, że ​​problem zniknie, ale tylko pod ArchLinux/Mono; pod Windows XP i Windows 7/64bit, nawet zoptymalizowana wersja przepełnienia stosu binarnego.

Ostateczna edycja: Sam dowiedziałem się odpowiedzi - patrz poniżej.

Answer 1

Streszczenie:

• napisałem prostą implementację algorytmu ... że nie był ogon rekurencyjnej.
• Skompilowałem to z OCaml pod Linuksem.
• To działało bez zarzutu i zakończyło się w 0,14 sekundy.

To był czas na przeniesienie do F #.

• Przetłumaczyłem kod (tłumaczenie bezpośrednie) na F #.
• Skompilowałem pod Windows i uruchomiłem - mam przepełnienie stosu.
• Wziąłem binarium pod Linuksem i uruchomiłem pod Mono.
• Zadziałało, ale działa bardzo wolno (84 sekundy).

Wysłałem następnie do Stack Overflow - ale niektóre osoby postanowiły zamknąć pytanie (westchnienie).

• Próbowałem kompilacji z --optimize + --checked-
• binarnym jeszcze stos przepełniony pod Windows ...
• ... ale działają dobrze (i wykończone w 0,5 sekundy) pod Linux/Mono .

Nadszedł czas, aby sprawdzić rozmiar stosu: pod Windows, another SO post pointed out that it is set by default to 1MB. Pod Linuksem "uname -s" i a compilation of a test program wyraźnie pokazały, że jest to 8 MB.

Wyjaśniono, dlaczego program działał pod Linuksem, a nie pod Windows (program używał więcej niż 1MB stosu). Nie wyjaśniało to, dlaczego zoptymalizowana wersja działa o wiele lepiej pod Mono niż zoptymalizowana: 0,5 sekundy vs 84 sekundy (chociaż opcja --optimize + wydaje się być domyślnie ustawiona, patrz komentarz Keitha z "Expert F #" wyciąg). Prawdopodobnie ma to związek z śmieciarzem Mono, który w jakiś sposób doprowadził do skrajności w pierwszej wersji.

Różnica między czasami wykonania Linux/OCaml i Linux/Mono/F # (0.14 vs 0.5) wynika z prostego sposobu, w jaki to zmierzyłem: "time ./binary ..." mierzy również czas uruchamiania, który jest znaczący dla Mono/.NET (cóż, znaczący dla tego prostego małego problemu).

W każdym razie, aby rozwiązać to raz na zawsze, I wrote a tail-recursive version - gdzie wywołanie rekursywne na końcu funkcji jest przekształcane w pętlę (a zatem nie jest wymagane użycie stosu - przynajmniej w teorii).

Nowa wersja działa również pod Windows, a zakończyła się w 0,5 sekundy.

Więc morał z tej historii:

• Strzeż swojego stosu użytkowania, zwłaszcza jeśli używasz dużo to i uruchomić pod Windows. Użyj opcji EDITBIN with the /STACK option, aby ustawić pliki binarne na większe rozmiary stosów, lub jeszcze lepiej, napisz swój kod w sposób, który nie zależy od użycia zbyt dużego stosu.
• OCaml może być lepszy w eliminacji rekursji ogonowej niż F # - lub jego zbieracz nie pracuje lepiej w tym konkretnym problemie.
• nie rozpaczaj o ... rude ludzi zamykając swoje pytania przepełnienie stosu, dobrzy ludzie będą przeciwdziałać im w końcu - jeśli pytania są naprawdę dobre :-)

PS: Kilka dodatkowych informacji od dr. Jona Harropa:

... miałeś szczęście, że OCaml również się nie przepełnił. Zidentyfikowano już, że rzeczywiste rozmiary stosów różnią się w zależności od platformy. Innym aspektem tego samego problemu jest to, że różne implementacje językowe jedzą przestrzeń stosu w różnym tempie i mają różne właściwości w obecności głębokich stosów. OCaml, Mono i.NET wszystkie używają różnych reprezentacji danych i algorytmów GC, które mają wpływ na te wyniki ... (a) OCaml używa znaczników liczb całkowitych do rozróżniania wskaźników, dając kompaktowe ramki stosu i będzie przemierzać wszystko na stosie szukając wskazówek. Znacznik przekazuje tylko tyle informacji, ile wynosi dla czasu działania OCaml, aby móc przemierzyć stertę (b) Mono traktuje słowa na stosie zachowawczo jako wskaźniki: jeśli jako wskaźnik, słowo wskazywałoby na przydzieloną stertę blok, to ten blok jest uważany za osiągalny. (c) Nie znam algorytmu .NET, ale nie byłbym zaskoczony, gdyby szybciej zjadł stos o rozmiarze i nadal przeszukiwał każde słowo na stosie (z pewnością cierpi na patologiczną wydajność z GC, jeśli niezwiązany wątek ma głęboki stos!) ... Ponadto, używanie krotek przydzielonych stertom oznacza, że ​​będziesz wypełniać pokolenie szkółki (np. gen0) szybko, a zatem, powodując, że GC często przemierza te głębokie stosy ...

Answer 2

Pozwól mi spróbować podsumować odpowiedź.

Istnieją 3 punkty, które należy wprowadzić:

• Problem: przepełnienie stosu dzieje się na funkcji rekurencyjnej
• zdarza się tylko pod Windows: W systemie Linux za proble wielkości badanego, to działa
• sam (lub podobny) w SML kod działa
• Optymalizacja + flag kompilatora dla proble wielkości badanego, pracuje

Bardzo często zdarza się, że wyjątek Stack Overflow jest wynikiem rekurencyjnego vall. Jeśli wywołanie znajduje się w pozycji ogonowej, kompilator może je rozpoznać i zastosować optymalizację tailcall, dlatego wywołania rekursywne nie zajmą miejsca stosu. optymalizacja Tailcall może się zdarzyć w F #, w CRL, czy w obu:

ogonowej CLR optymalizacji 1

F # rekursji (bardziej ogólnie) 2

F # tail zwraca 3

poprawnego wyjaśnienia "niepowodzenie w oknach, a nie w linuksie" to, jak już powiedziano, domyślne zarezerwowane miejsce stosu w dwóch systemach operacyjnych. Lub lepiej, zarezerwowane miejsce stosu używane przez kompilatory w ramach dwóch systemów operacyjnych. Domyślnie VC++ rezerwuje tylko 1 MB miejsca na stosie. CLR jest (prawdopodobnie) skompilowany z VC++, więc ma to ograniczenie. Zarezerwowane miejsce na stosie można zwiększyć podczas kompilacji, ale nie jestem pewien, czy można go zmodyfikować na skompilowanych plikach wykonywalnych.

EDYCJA: okazuje się, że można to zrobić (zobacz ten wpis na blogu: http://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx) Nie polecam go, ale w ekstremalnych sytuacjach przynajmniej jest to możliwe.

Wersja OCaml może działać, ponieważ została uruchomiona pod Linuksem. Warto jednak przetestować także wersję OCaml pod Windows. Wiem, że kompilator OCaml jest bardziej agresywny w zakresie optymalizacji wywołań ogonowych niż F #. Czy mógłby nawet wyodrębnić funkcję wielokrotnego wczytywania kodu z oryginalnego kodu?

Zgaduję, że "--optimize +" będzie powodowało, że kod będzie się powtarzał, w związku z tym nadal będzie działał w systemie Windows, ale zmniejszy problem, powodując, że plik wykonywalny będzie działał szybciej.

Wreszcie, ostatecznym rozwiązaniem jest użycie rekurencji ogonowej (przez przepisanie kodu lub realistyczną agresywną optymalizację kompilatora); jest to dobry sposób na uniknięcie problemu przepełnienia stosu z funkcjami rekursywnymi.