Geschwindigkeitsvergleich mit Projekt Euler: C vs. Python vs. Erlang vs. Haskell

Question

Ich habe die Problem Nr. 12 de Projekt Euler als Programmierübung und zum Vergleich meiner (sicherlich nicht optimalen) Implementierungen in C, Python, Erlang und Haskell. Um eine höhere Ausführungszeit zu erreichen, suche ich nach der ersten Dreieckszahl mit mehr als 1000 Teilern statt 500, wie im ursprünglichen Problem angegeben.

Das Ergebnis ist das folgende:

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

Python:

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

real    1m16.632s
user    1m16.370s
sys 0m0.250s

Python mit PyPy:

lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 
842161320

real    0m13.082s
user    0m13.050s
sys 0m0.020s

Erlang:

lorenzo@enzo:~/erlang$ erlc euler12.erl 
lorenzo@enzo:~/erlang$ time erl -s euler12 solve
Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.4  (abort with ^G)
1> 842161320

real    0m48.259s
user    0m48.070s
sys 0m0.020s

Haskell:

lorenzo@enzo:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
lorenzo@enzo:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

Zusammenfassung:

• C: 100%
• Python: 692% (118% mit PyPy)
• Erlang: 436% (135% Dank an RichardC)
• Haskell: 1421%

Ich nehme an, dass C einen großen Vorteil hat, da es für die Berechnungen lange und nicht beliebig lange ganze Zahlen verwendet, wie die anderen drei. Außerdem muss es nicht erst eine Laufzeitumgebung laden (wie die anderen?).

Frage 1: Verlieren Erlang, Python und Haskell durch die Verwendung von Ganzzahlen beliebiger Länge an Geschwindigkeit, oder verlieren sie nicht, solange die Werte kleiner als MAXINT ?

Frage 2: Warum ist Haskell so langsam? Gibt es ein Compiler-Flag, das die Bremsen ausschaltet, oder liegt es an meiner Implementierung? (Letzteres ist sehr wahrscheinlich, da Haskell für mich ein Buch mit sieben Siegeln ist).

Frage 3: Können Sie mir Tipps geben, wie ich diese Implementierungen optimieren kann, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in jeder Hinsicht: schöner, schneller, "nativer" in der Sprache.

EDITAR:

Frage 4: Erlauben meine funktionalen Implementierungen LCO (Last Call Optimization, auch bekannt als Tail Recursion Elimination) und vermeiden damit das Hinzufügen unnötiger Frames auf dem Call Stack?

Ich habe wirklich versucht, denselben Algorithmus so ähnlich wie möglich in den vier Sprachen zu implementieren, obwohl ich zugeben muss, dass meine Kenntnisse in Haskell und Erlang sehr begrenzt sind.

---

Verwendete Quellcodes:

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square;
    int count = isquare == square ? -1 : 0;
    long candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

---

#! /usr/bin/env python3.2

import math

def factorCount (n):
    square = math.sqrt (n)
    isquare = int (square)
    count = -1 if isquare == square else 0
    for candidate in range (1, isquare + 1):
        if not n % candidate: count += 2
    return count

triangle = 1
index = 1
while factorCount (triangle) < 1001:
    index += 1
    triangle += index

print (triangle)

---

-module (euler12).
-compile (export_all).

factorCount (Number) -> factorCount (Number, math:sqrt (Number), 1, 0).

factorCount (_, Sqrt, Candidate, Count) when Candidate > Sqrt -> Count;

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

factorCount (Number, Sqrt, Candidate, Count) ->
    case Number rem Candidate of
        0 -> factorCount (Number, Sqrt, Candidate + 1, Count + 2);
        _ -> factorCount (Number, Sqrt, Candidate + 1, Count)
    end.

nextTriangle (Index, Triangle) ->
    Count = factorCount (Triangle),
    if
        Count > 1000 -> Triangle;
        true -> nextTriangle (Index + 1, Triangle + Index + 1)  
    end.

solve () ->
    io:format ("~p~n", [nextTriangle (1, 1) ] ),
    halt (0).

---

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' number sqrt candidate count
    | fromIntegral candidate > sqrt = count
    | number `mod` candidate == 0 = factorCount' number sqrt (candidate + 1) (count + 2)
    | otherwise = factorCount' number sqrt (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

Answer 1

使用方法 GHC 7.0.3 , gcc 4.4.6 , Linux 2.6.29 auf einem x86_64 Core2 Duo (2.5GHz) Rechner, kompiliert mit ghc -O2 -fllvm -fforce-recomp für Haskell und gcc -O3 -lm für C.

• Ihre C-Routine läuft in 8,4 Sekunden (schneller als Ihr Lauf, wahrscheinlich wegen der -O3 )
• Die Haskell-Lösung läuft in 36 Sekunden (aufgrund der -O2 Flagge)
• Ihr factorCount' Code nicht explizit typisiert ist und standardmäßig auf Integer (Dank an Daniel für die Korrektur meiner Fehldiagnose hier!). Die Angabe einer expliziten Typsignatur (was ohnehin Standardpraxis ist) mit Int und die Zeit ändert sich auf 11,1 Sekunden
• in factorCount' haben Sie unnötigerweise genannt fromIntegral . Eine Korrektur führt jedoch zu keiner Änderung (der Compiler ist schlau, zum Glück für Sie).
• Sie haben mod donde rem ist schneller und ausreichend. Dies verändert die Zeit bis 8,5 Sekunden .

• factorCount' wendet ständig zwei zusätzliche Argumente an, die sich nie ändern ( number , sqrt ). Eine Worker/Wrapper-Transformation liefert uns:

  $ time ./so 842161320

  real 0m7.954s
  user 0m7.944s
  sys 0m0.004s

Das ist richtig, 7,95 Sekunden . Durchgängig eine halbe Sekunde schneller als die C-Lösung . Ohne die -fllvm Flagge bekomme ich immer noch 8.182 seconds Das NCG-Backend macht sich also auch in diesem Fall gut.

Schlussfolgerung: Haskell ist großartig.

Resultierender Code

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
  where
  go candidate count
    | candidate > sqrt = count
    | number `rem` candidate == 0 = go (candidate + 1) (count + 2)
    | otherwise = go (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

EDIT: Nachdem wir das nun geklärt haben, können wir uns den Fragen zuwenden

Frage 1: Verlieren erlang, python und haskell an Geschwindigkeit durch die Verwendung von durch die Verwendung von Integern beliebiger Länge oder nicht, solange die Werte kleiner sind als als MAXINT sind?

In Haskell ist die Verwendung von Integer ist langsamer als Int aber wie viel langsamer, hängt von den durchgeführten Berechnungen ab. Glücklicherweise (für 64-Bit-Maschinen) Int ist ausreichend. Aus Gründen der Übertragbarkeit sollten Sie meinen Code wahrscheinlich so umschreiben, dass er Int64 o Word64 (C ist nicht die einzige Sprache mit einer long ).

Frage 2: Warum ist Haskell so langsam? Gibt es ein Compiler-Flag, das das die Bremsen ausschaltet, oder liegt es an meiner Implementierung? (Letzteres ist ziemlich wahrscheinlich, da Haskell für mich ein Buch mit sieben Siegeln ist.)

Frage 3: Können Sie mir einige Tipps geben, wie ich diese zu optimieren, ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in jeder Hinsicht: schöner, schneller, "nativer" in der Sprache.

Das habe ich oben beantwortet. Die Antwort war

• 0) Verwenden Sie die Optimierung über -O2
• 1) Verwenden Sie, wenn möglich, schnelle (vor allem: unbox-able) Typen
• 2) rem no mod (eine häufig vergessene Optimierung) und
• 3) Worker/Wrapper-Umwandlung (vielleicht die häufigste Optimierung).

Frage 4: Erlauben meine funktionalen Implementierungen LCO und damit das Hinzufügen unnötiger Frames auf dem Aufrufstapel vermeiden?

Ja, das war nicht das Thema. Gute Arbeit und schön, dass Sie das bedacht haben.

Answer 2

Es gibt einige Probleme mit der Erlang-Implementierung. Die von mir gemessene Ausführungszeit für Ihr unmodifiziertes Erlang-Programm betrug 47,6 Sekunden, verglichen mit 12,7 Sekunden für den C-Code.

Das erste, was Sie tun sollten, wenn Sie rechenintensiven Erlang-Code ausführen wollen, ist, nativen Code zu verwenden. Kompilieren mit erlc +native euler12 konnte die Zeit auf 41,3 Sekunden gesenkt werden. Dies ist jedoch eine viel geringere Beschleunigung (nur 15 %) als von der nativen Kompilierung bei dieser Art von Code erwartet, und das Problem ist Ihre Verwendung von -compile(export_all) . Dies ist für Experimente nützlich, aber die Tatsache, dass alle Funktionen potenziell von außen erreichbar sind, veranlasst den nativen Compiler, sehr konservativ zu sein. (Der normale BEAM-Emulator ist davon nicht so stark betroffen.) Ersetzt man diese Deklaration durch -export([solve/0]). führt zu einer wesentlich höheren Geschwindigkeit: 31,5 Sekunden (fast 35 % gegenüber dem Ausgangswert).

Aber der Code selbst hat ein Problem: für jede Iteration in der factorCount-Schleife führen Sie diesen Test durch:

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

Der C-Code tut dies nicht. Im Allgemeinen kann es schwierig sein, einen fairen Vergleich zwischen verschiedenen Implementierungen desselben Codes anzustellen, insbesondere wenn es sich um einen numerischen Algorithmus handelt, weil man sicher sein muss, dass sie tatsächlich dasselbe tun. Ein kleiner Rundungsfehler in der einen Implementierung aufgrund eines Typcasts kann dazu führen, dass sie viel mehr Iterationen durchführt als die andere, obwohl beide letztendlich das gleiche Ergebnis erzielen.

Um diese mögliche Fehlerquelle zu beseitigen (und den zusätzlichen Test in jeder Iteration loszuwerden), habe ich die factorCount-Funktion wie folgt umgeschrieben, in enger Anlehnung an den C-Code:

factorCount (N) ->
    Sqrt = math:sqrt (N),
    ISqrt = trunc(Sqrt),
    if ISqrt == Sqrt -> factorCount (N, ISqrt, 1, -1);
       true          -> factorCount (N, ISqrt, 1, 0)
    end.

factorCount (_N, ISqrt, Candidate, Count) when Candidate > ISqrt -> Count;
factorCount ( N, ISqrt, Candidate, Count) ->
    case N rem Candidate of
        0 -> factorCount (N, ISqrt, Candidate + 1, Count + 2);
        _ -> factorCount (N, ISqrt, Candidate + 1, Count)
    end.

Diese Neufassung, nein export_all und der nativen Kompilierung erhielt ich folgende Laufzeit:

$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320

real    0m19.468s
user    0m19.450s
sys 0m0.010s

was im Vergleich zum C-Code nicht allzu schlecht ist:

$ time ./a.out 
842161320

real    0m12.755s
user    0m12.730s
sys 0m0.020s

Wenn man bedenkt, dass Erlang überhaupt nicht auf das Schreiben von numerischem Code ausgerichtet ist, ist es ziemlich gut, bei einem Programm wie diesem nur 50% langsamer als C zu sein.

Abschließend möchte ich auf Ihre Fragen eingehen:

Frage 1: Verlieren Erlang, Python und Haskell an Geschwindigkeit durch die Verwendung von Ganzzahlen beliebiger Länge oder nicht, solange die Werte kleiner als MAXINT sind?

Ja, ein wenig. In Erlang gibt es keine Möglichkeit, zu sagen "benutze 32/64-Bit-Arithmetik mit Wrap-Around", so dass der Compiler, sofern er keine Grenzen für die Integerzahlen nachweisen kann (und das kann er normalerweise nicht), alle Berechnungen daraufhin überprüfen muss, ob sie in ein einzelnes getaggtes Wort passen oder ob er sie in Bignums mit Heap-Zuweisung umwandeln muss. Selbst wenn in der Praxis zur Laufzeit keine Bignums verwendet werden, müssen diese Prüfungen durchgeführt werden. Andererseits bedeutet das, dass Sie wissen dass der Algorithmus niemals wegen eines unerwarteten Integer-Wraparound versagt, wenn Sie ihm plötzlich größere Eingaben als zuvor geben.

Frage 4: Erlauben meine funktionalen Implementierungen LCO und vermeiden damit das Hinzufügen unnötiger Frames auf dem Aufrufstapel?

Ja, Ihr Erlang-Code ist in Bezug auf die Optimierung des letzten Aufrufs korrekt.

Answer 3

Was die Python-Optimierung betrifft, so können Sie zusätzlich zur Verwendung von PyPy (für ziemlich beeindruckende Geschwindigkeitssteigerungen ohne Änderung Ihres Codes) auch die PyPy-Funktion Übersetzungs-Toolchain um eine RPython-kompatible Version zu kompilieren, oder Cython um ein Erweiterungsmodul zu erstellen, die beide in meinen Tests schneller sind als die C-Version, mit dem Cython-Modul fast doppelt so schnell . Als Referenz füge ich auch C- und PyPy-Benchmark-Ergebnisse bei:

C (kompiliert mit gcc -O3 -lm )

% time ./euler12-c 
842161320

./euler12-c  11.95s 
 user 0.00s 
 system 99% 
 cpu 11.959 total

PyPy 1.5

% time pypy euler12.py
842161320
pypy euler12.py  
16.44s user 
0.01s system 
99% cpu 16.449 total

RPython (mit der letzten PyPy-Revision, c2f583445aee )

% time ./euler12-rpython-c
842161320
./euler12-rpy-c  
10.54s user 0.00s 
system 99% 
cpu 10.540 total

Cython 0.15

% time python euler12-cython.py
842161320
python euler12-cython.py  
6.27s user 0.00s 
system 99% 
cpu 6.274 total

Die RPython-Version hat einige wichtige Änderungen. Um in ein eigenständiges Programm zu übersetzen, müssen Sie Ihre target , die in diesem Fall die main Funktion. Es wird erwartet, dass sie Folgendes akzeptiert sys.argv als einziges Argument und muss einen int zurückgeben. Sie können es mit translate.py übersetzen, % translate.py euler12-rpython.py das es in C übersetzt und für Sie kompiliert.

# euler12-rpython.py

import math, sys

def factorCount(n):
    square = math.sqrt(n)
    isquare = int(square)
    count = -1 if isquare == square else 0
    for candidate in xrange(1, isquare + 1):
        if not n % candidate: count += 2
    return count

def main(argv):
    triangle = 1
    index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle
    return 0

if __name__ == '__main__':
    main(sys.argv)

def target(*args):
    return main, None

Die Cython-Version wurde als Erweiterungsmodul umgeschrieben _euler12.pyx , die ich aus einer normalen Python-Datei importiere und aufrufe. Die _euler12.pyx ist im Wesentlichen die gleiche wie Ihre Version, mit einigen zusätzlichen statischen Typdeklarationen. Die setup.py hat die normale Boilerplate, um die Erweiterung zu bauen, mit python setup.py build_ext --inplace .

# _euler12.pyx
from libc.math cimport sqrt

cdef int factorCount(int n):
    cdef int candidate, isquare, count
    cdef double square
    square = sqrt(n)
    isquare = int(square)
    count = -1 if isquare == square else 0
    for candidate in range(1, isquare + 1):
        if not n % candidate: count += 2
    return count

cpdef main():
    cdef int triangle = 1, index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle

# euler12-cython.py
import _euler12
_euler12.main()

# setup.py
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

ext_modules = [Extension("_euler12", ["_euler12.pyx"])]

setup(
  name = 'Euler12-Cython',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules
)

Ich habe ehrlich gesagt nur sehr wenig Erfahrung mit RPython oder Cython und war von den Ergebnissen angenehm überrascht. Wenn Sie CPython verwenden, scheint es eine wirklich einfache Möglichkeit zu sein, Ihr Programm zu optimieren, indem Sie Ihre CPU-intensiven Code-Bits in ein Cython-Erweiterungsmodul schreiben.

Answer 4

Frage 3: Können Sie mir einige Tipps geben, wie ich diese Implementierungen optimieren kann? ohne die Art und Weise zu ändern, wie ich die Faktoren bestimme? Optimierung in jeder Weise: schöner, schneller, "nativer" für die Sprache.

Die C-Implementierung ist suboptimal (wie von Thomas M. DuBuisson angedeutet), die Version verwendet 64-Bit-Ganzzahlen (d.h. lang Datentyp). Ich werde das Assembler-Listing später untersuchen, aber ich vermute, dass im kompilierten Code einige Speicherzugriffe stattfinden, die die Verwendung von 64-Bit-Ganzzahlen deutlich langsamer machen. Entweder das oder der generierte Code (sei es die Tatsache, dass weniger 64-Bit-Integer in ein SSE-Register passen oder das Runden eines Doubles auf einen 64-Bit-Integer langsamer ist).

Hier ist der geänderte Code (einfach ersetzen lang con int und ich habe factorCount explizit inlined, obwohl ich nicht glaube, dass dies mit gcc -O3 notwendig ist):

#include <stdio.h>
#include <math.h>

static inline int factorCount(int n)
{
    double square = sqrt (n);
    int isquare = (int)square;
    int count = isquare == square ? -1 : 0;
    int candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    int triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index++;
        triangle += index;
    }
    printf ("%d\n", triangle);
}

Laufen + Zeitmessung gibt es:

$ gcc -O3 -lm -o euler12 euler12.c; time ./euler12
842161320
./euler12  2.95s user 0.00s system 99% cpu 2.956 total

Als Referenz gibt die Haskell-Implementierung von Thomas in der früheren Antwort:

$ ghc -O2 -fllvm -fforce-recomp euler12.hs; time ./euler12                                                                                      [9:40]
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12 ...
842161320
./euler12  9.43s user 0.13s system 99% cpu 9.602 total

Schlussfolgerung: Nichts weg von ghc, es ist ein großartiger Compiler, aber gcc erzeugt normalerweise schnelleren Code.

Answer 5

Werfen Sie einen Blick auf dieser Blog . Im Laufe des letzten Jahres hat er einige der Projekt-Euler-Probleme in Haskell und Python bearbeitet, und er fand im Allgemeinen Haskell viel schneller zu sein. Ich denke, dass es bei diesen Sprachen eher auf Ihre Sprachkenntnisse und Ihren Programmierstil ankommt.

Wenn es um die Geschwindigkeit von Python geht, verwenden Sie die falsche Implementierung! Versuchen Sie PyPy und für Dinge wie diese werden Sie feststellen, dass es viel, viel schneller geht.