06 Dec 2019

Haskell versus C

Alex hat mir gesagt, er hätte noch nie ein vernünftiges Programm in Haskell gesehen, und zweifelt den Sinn von Haskell ansich an. Dem versuche ich, auf den Grund zu gehen, so sei der Vorteil von Haskell doch das schnelle Berechnen großer Zahlen.

Ich folge im großen und ganzen diesem Howto: Haskell in 5 Schritten und habe zu jedem der dort vorgestellten 3 Haskell-Programme schnell ein C-Äquivalent programmiert und versuche, das einzuordnen.

Die Kandidaten

hello.hs

main = putStrLn "Hello, World!"

hello.c

#include <stdio.h>
int main()
{
   printf("Hello, World!\n");
   return 0;
}

fac.hs

fac 0 = 1
fac n = n * fac (n-1)

main =  do
    print (fac 20) 
    print (fac 42)

fac.c

#include <stdio.h>
unsigned long long do_fac(int n) 
{
    int i;
    unsigned long long fac = 1;
    for (i = 1; i <= n; ++i) {
        fac *= i;
    }
    return fac;
}
int main() {
    printf("%llu\n",do_fac(20));
    printf("%llu\n",do_fac(42));
    return 0;
}

A.hs

import Control.Parallel

main = do
    a `par` b `par` c `pseq` 
          putStrLn("fac:" ++ show b ++ "\nack:"++ show a ++ "\nfib:" ++ show c)
    where
        a = ack 3 10
        b = fac 20
        c = fib 34

-- ackerman function
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))

-- faculty
fac 0 = 1
fac n = n * fac (n-1)

-- fibonacci
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2

A.c

#include <stdio.h>
/* faculty */
unsigned long long do_fac(int n) 
{
    int i;
    unsigned long long fac = 1;
    for (i = 1; i <= n; ++i) {
        fac *= i;
    }
    return fac;
}

/* fibonacci recursive */
unsigned long long do_fib(int n)
{
    if (n == 0 || n == 1)
        return n;
    else
        return (do_fib(n-1) + do_fib(n-2));
}

/* Ackermann */
unsigned long long ackermann(int m, int n)
{
        if (!m) return n + 1;
        if (!n) return ackermann(m - 1, 1);
        return ackermann(m - 1, ackermann(m, n - 1));
}

int main() {
    printf("fac: %llu\n",do_fac(20));
    printf("ack: %llu\n",ackermann(3,10));
    printf("fib: %llu\n",do_fib(34));
    return 0;
}

Alle Listings mit makefile kann man hier herunterladen: haskell-vs-c.tar.gz

Vorbereitungen, kompilieren

  • Wenn bei Haskell dieser Fehler auftritt
chrissie@fehmarn ~/haskell $ ghc -O2 --make A.hs -threaded -rtsopts
[1 of 1] Compiling Main             ( A.hs, A.o )

A.hs:2:1: error:
    Failed to load interface for ‘Control.Parallel’
    Use -v to see a list of the files searched for.

Muss man die Parallel-Bibliothek installieren, unter Gentoo geht das so:

# emerge dev-haskell/parallel

Und los gehts!

  • Einfache Dinge
~/haskell-vs-c $ ./hello-hs
Hello, World!
~/haskell-vs-c $ ./hello-c
Hello, World!
~/haskell-vs-c $ ./fac-hs 
2432902008176640000
1405006117752879898543142606244511569936384000000000
~/haskell-vs-c $ ./fac-c
2432902008176640000
7538058755741581312

Hier sieht man, dass in C der long long überläuft, man muss wohl eine Big-Numbers-Bibliothek verwenden. Das wäre ein Vorteil von Haskell, dass dies per default einfach so nicht passieren kann.

  • Der letze Test:
~/haskell-vs-c $ time ./A-hs 
fac:2432902008176640000
ack:8189
fib:5702887

real	0m2.014s
user	0m2.005s
sys	0m0.009s

~/haskell-vs-c $ time ./A-c
fac: 2432902008176640000
ack: 8189
fib: 5702887

real	0m0.084s
user	0m0.083s
sys	0m0.000s

Jetzt bin ich enttäuscht, von Haskell hätte ich hier eine viel bessere Performance erwartet. Und es wurde unter C noch nichtmal die GNU Parallel Library verwendet. Hier besteht Klärungsbedarf!

Ein Link zu den Evolutionsstufen des Haskell-Programmierers darf natürlich trotzdem nicht fehlen!

Bleibt nur noch ein Meme

Expanding Brain