Ackermann sehr ineffizient mit Haskell/GHC
Ich versuche computing Ackermann(4,1)
und es gibt einen großen Unterschied in der Leistung zwischen verschiedenen Sprachen/Compilern. Unten sind die Ergebnisse auf meine Core i7-3820QM, 16G, Ubuntu 12.10 64bit,
C: 1.6 s, gcc -O3
(mit gcc 4.7.2)
int ack(int m, int n) {
if (m == 0) return n+1;
if (n == 0) return ack(m-1, 1);
return ack(m-1, ack(m, n-1));
}
int main() {
printf("%d\n", ack(4,1));
return 0;
}
OCaml: 3,6 s, ocamlopt
(mit ocaml 3.12.1)
let rec ack = function
| 0,n -> n+1
| m,0 -> ack (m-1, 1)
| m,n -> ack (m-1, ack (m, n-1))
in print_int (ack (4, 1))
Standard ML: 5.1 s mlton -codegen c -cc-opt -O3
(mit mlton 20100608)
fun ack 0 n = n+1
| ack m 0 = ack (m-1) 1
| ack m n = ack (m-1) (ack m (n-1));
print (Int.toString (ack 4 1));
Schläger: 11.5 s racket
(mit racket v5.3.3)
(require racket/unsafe/ops)
(define + unsafe-fx+)
(define - unsafe-fx-)
(define (ack m n)
(cond
[(zero? m) (+ n 1)]
[(zero? n) (ack (- m 1) 1)]
[else (ack (- m 1) (ack m (- n 1)))]))
(time (ack 4 1))
Haskell: unfinished, getötet vom system nach 22s ghc -O2
(mit ghc 7.4.2)
Haskell: 1.8 s ajhc
(mit ajhc 0.8.0.4)
main = print $ ack 4 1
where ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))
Die Haskell-version ist der einzige, der nicht ordentlich kündigen, denn es nimmt zu viel Speicher. Es friert meine Maschine und füllt den swap-Speicher, bevor Sie getötet wurden.
Was kann ich tun um es zu verbessern ohne zu stark fuglifying den code?
BEARBEITEN: ich Schätze einige der asymptotisch intelligentere Lösungen, aber Sie sind nicht genau das, was ich bin für Fragen. Es geht mehr um zu sehen, ob der compiler verarbeitet bestimmte Muster, die in einer relativ effizienten Art und Weise (stack, Schwanz ruft, unboxing, etc.) als Berechnung der ackermann-Funktion.
EDIT 2: Wie bereits von mehreren Antworten, scheint dies ein bug in den letzten Versionen von GHC. Versuche ich den gleichen code mit AJHC und viel besser performance.
Danke sehr 🙂
- Für jeden, der versucht dieser, das problem hier ist computational, nicht algorithmisch. Die nicht-memoized Aufruf
ack(4,1)
Ergebnisse in eine Rekursion der Tiefe 65535, und insgesamt 2862984010 Aufrufeack
. ghc-core
zeigtInt
s sind richtig bekommen umgewandelt, ohne VerpackungInt#
, also das ist nicht das problem.- Danke. Ich habe blind versucht diese.
- Den gleichen code in Frege führt in 8,3 s, aber die JVM braucht etwas zusätzliche stack-Speicher. Hardware ist i3 CPU M 350 @ 2.27 GHz
- JHC scheint besser mit micro-benchmarks wie folgt aus: haskell.org/pipermail/glasgow-haskell-users/2013-April/...
- Auf meinem macbook mit ghc-7.6 dieses Programm gibt die richtige Antwort; mit ghc-KOPF es gibt die gleiche Antwort in der gleichen absurde Menge Zeit. Es unterscheidet sich nur durch die Verwendung von weniger Speicher. Es gibt also keine echten Fehler. Der eigentliche Skandal ist, dass scheinbar absurde timing jeder gibt, was in der Tat folgt aus bekannten Tatsachen darüber, wie ghc mit den Dingen beschäftigt, was es wählt zu optimieren.
- Bitte beachten Sie, dass mein Benutzername ist eigentlich nicht applicative und ich denke, meine Frage wurde gelöscht, zusammen mit seinen Kommentaren... In jedem Fall, es ist nicht fair zu vergleichen strenge vs nichtstrikten Laufzeiten. Bitte fügen Sie strenge Anmerkungen wenn Sie wollen, um einen fairen Vergleich. Diese version hat eine sehr klare thunk Leck.
- Hi, die alternative ist, verwendet die Funktion Int, und GHC -O2 unboxes es in Int# schon. So gibt es keine Notwendigkeit für eine explizite annotation. Danke.
- Dies könnte interessant für Sie sein stackoverflow.com/questions/3241954/...
- Ich habe erwähnt, mlton früher, Fragen, warum, wenn Sie waren auf der Suche nach Skandal, Sie waren nicht überrascht, mlton dauerte länger als ocamlopt angesichts seiner berühmten Orientierung auf die ganze Programm-Optimierung, das ist eine ganz andere Vorgehensweise als z.B. der ghc. Es würde nicht auftreten, bis mir der tatsächliche Angriff SML oder mlton, die sind in meinen Augen beide göttlichen Dinge.
- FWIW, auf der ghc 8.6.4 mit entweder -kc2m oder -ki2m läuft es in 2,8 s auf einem 3-GHz-i5 auf einem Mac. Ohne diese Optionen, die es braucht, 10.5 s, vermutlich wegen der großen stack erforderlich, die kleinen anfänglichen stack-Größe und die small-stack-chunk-Größe auf ghc, die da ist, ist das erstellen von Beiträgen so einfach wie möglich.
Du musst angemeldet sein, um einen Kommentar abzugeben.
NB: Der hohe Speicherverbrauch Problem ist ein Fehler in der GHC RTS, wo auf stack-überlauf und Zuweisung neuer Stapel auf dem heap, es wurde nicht geprüft, ob die garbage-collection zurückzuführen ist. Es wurde bereits behoben GHC KOPF.
Ich war in der Lage, eine viel bessere Leistung von CPS-converting -
ack
:Ihre ursprüngliche Funktion verbraucht alle verfügbaren Speicher auf meinem Rechner, während dieser läuft in konstantem Platz.
Ocaml ist immer noch schneller, aber:
Edit: Bei der Kompilierung mit JHC, Ihre original-Programm ist etwa so schnell wie die Ocaml-version:
Edit 2: Etwas anderes habe ich entdeckt: läuft dein original-Programm mit einem größeren stack chunk-Größe (
+RTS -kc1M
) lässt es laufen in konstantem Platz. Die CPS-version ist noch ein bisschen schneller, aber.Edit 3: ich es geschafft, produzieren eine version, die läuft fast genauso schnell wie der Ocaml man durch manuelles abrollen des main-loop. Das funktioniert aber nur, wenn die Ausführung mit
+RTS -kc1M
(Dan Doel eingereicht hat einen bug über dieses Verhalten):Testen:
Bearbeiten 4: Offenbar, den Raum Leck wird behoben, in GHC KOPF, so
+RTS -kc1M
werden nicht in der Zukunft erforderlich.-XUnboxedTuples
), unabhängig davon, ob oder nicht Sie CPS-konvertieren (welches keine Verbesserung der Laufzeit zu deutlich).-kc1M
nimmt keinen zusätzlichen Platz, während-kc768K
finshes, aber mit viel Platz Verbrauch.Es scheint, dass es irgendeine Art von Fehler beteiligt. Was GHC-version verwenden Sie?
Mit GHC 7, bekomme ich das gleiche Verhalten wie du. Das Programm verbraucht alle verfügbaren Speichers, ohne die keine Ausgabe.
Aber wenn ich es kompilieren mit GHC 6.12.1 nur mit
ghc --make -O2 Ack.hs
, es funktioniert perfekt. Es berechnet das Ergebnis in 10.8 s auf meinem computer, während einfache C-version nimmt 7,8 s.Schlage ich vor, Sie zu melden Sie diese Fehler auf GHC-Website.
Diese version verwendet einige Eigenschaften der ackermann-Funktion. Es ist nicht äquivalent zu der
andere Versionen, aber es ist schnell :
Edit : Und dies ist eine version mit memoization , sehen wir, dass es einfach zu memoize eine Funktion in haskell, die einzige änderung besteht in der call-site :
Folgende ist eine idiomatische version, die die Vorteile von Haskell ist lazyness und GHC Optimierung der Konstanten top-level-Ausdrücke.
Hier, wir sind faul Aufbau einer matrix für alle die Werte der Ackermann-Funktion. Als Ergebnis werden nachfolgende Aufrufe
acks
wird nicht neu berechnen, nichts (D. H. die Bewertungacks !! 4 !! 1
wieder nicht doppelte Laufzeit).Dies ist zwar nicht die Schnellste Lösung, es sieht viel wie die naive Implementierung ist sehr effizient in Bezug auf Speicher verwenden, und es werden eine Haskell seltsamer Funktionen (lazyness) als eine Stärke.
./Test 82,38s user 0,44s system 92% cpu 1:29,98 total
Ich sehe nicht, dass dies ein Fehler überhaupt
ghc
einfach nicht unter Ausnutzung der Tatsache, dass es weiß, dass 4 und 1 sind die einzigen Argumente die Funktion wird immer aufgerufen werden, -- das heißt, um es klar zu sagen, es nicht zu betrügen. Es spielt auch nicht konstant Mathematik für Sie, so dass, wenn Sie geschrieben hattemain = print $ ack (2+2) 1
würde es nicht haben berechnet, dass 2+2 = 4 bis Laufzeit. Dieghc
hat viel mehr wichtige Dinge zu denken. Hilfe für die letztere Schwierigkeit ist verfügbar, wenn Sie für es sorgen http://hackage.haskell.org/package/const-math-ghc-plugin.So
ghc
ist geholfen, wenn Sie tun, ein wenig Mathematik z.B. ist mindestens hundert mal so schnell wie ein C-Programm mit 4 und 1 als Argumente. Aber versuchen Sie es mit 4 & 2:Diese geben dem Recht Antwort, alle ~20,000 Ziffern in weniger als einer Zehntel-Sekunde, in der Erwägung, dass die gcc, mit Ihrem Algorithmus, wird ewig dauern, bis die falsche Antwort geben.
Schreiben Sie den Algorithmus in Haskell in einer Weise, die ähnlich aussieht, wie Sie es geschrieben in C, ist nicht der gleiche Algorithmus, da die Semantik der Rekursion, sind ganz anders.
Hier ist eine version mit dem gleichen mathematische Algorithmus, aber wo wir darstellen, fordert der Ackermann-Funktion symbolisch mit einem Datentyp. Auf diese Weise können wir die Kontrolle der Semantik der Rekursion genauer.
Beim kompilieren mit Optimierung, diese version läuft in steter Erinnerung, aber es ist langsam - über 4,5 Minuten in einer Umgebung, ähnlich wie bei Ihnen. Aber ich bin sicher, es könnte so geändert werden, dass viel schneller. Dies ist nur zu geben, die Idee.
data
zu einemnewtype
, dachte, es würde Speicherplatz sparen, daher weniger Müll-Sammlung und weniger Zeit. Aber das Ergebnis war tatsächlich langsamer. Ändern zurück zudata
.Ack m
für die gleichenm
in eine, fügen Sie einen zusätzlichen parameter anAck
für die Anzahl, wie oft es wiederholt wird. Das reduziert die Menge der garbage collection. Dies reduziert meine Laufzeit um über 1 minute.Diesem performance-Problem (außer für GHC RTS-Fehler offensichtlich), scheint inzwischen behoben zu sein, die auf OS X 10.8 nach Apple
XCode
update zu4.6.2
. Ich kann immer noch reproduzieren es auf Linux (ich habe getestet mit GHC LLVM-backend, obwohl), aber nicht mehr auf OS X. Nachdem ich aktualisiert die XCode 4.6.2 zu nennen, die neue version zu haben scheint, beeinflusst Sie das GHC backend-code-Generierung für Ackermann deutlich (von dem, was ich erinnere mich aus der Suche in Objekt-dumps vor dem update). Ich war in der Lage zu reproduzieren die performance-Problem auf Mac vor dem XCode update - ich habe nicht die zahlen, aber Sie waren sicherlich sehr schlecht. So, es scheint, dass XCode update verbessert die GHC-code-Generierung für Ackermann.Nun, sowohl C-als auch GHC-Versionen sind ganz in der Nähe. C-code:
Zeit zum ausführen ack(4,1):
Haskell-code:
Zeit zum ausführen ack-4 1 (mit +RTS -kc1M):
Alle waren zusammengestellt, mit
-O2
flag (und-rtsopts
Flagge für GHC für RTS-bug workaround). Es ist durchaus ein Kopf scratcher, obwohl. Aktualisierung von XCode scheint einen großen Unterschied gemacht, durch die Optimierung von Ackermann in GHC.