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 Aufrufe ack.
  • ghc-core zeigt Ints sind richtig bekommen umgewandelt, ohne Verpackung Int#, 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.

InformationsquelleAutor Phil | 2013-04-20
Schreibe einen Kommentar