Comparaison de la vitesse avec le projet Euler : C vs Python vs Erlang vs Haskell

Question

J'ai pris Problème n°12 de Projet Euler comme un exercice de programmation et pour comparer mes implémentations (sûrement pas optimales) en C, Python, Erlang et Haskell. Afin d'obtenir des temps d'exécution plus élevés, je cherche le premier nombre triangulaire avec plus de 1000 diviseurs au lieu de 500 comme indiqué dans le problème original.

Le résultat est le suivant :

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 avec 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

Résumé :

• C : 100%
• Python : 692% (118% avec PyPy)
• Erlang : 436% (135% grâce à RichardC)
• Haskell : 1421%

Je suppose que le C a un gros avantage car il utilise des longs pour les calculs et non des entiers de longueur arbitraire comme les trois autres. De plus, il n'a pas besoin de charger un runtime en premier (comme les autres ?).

Question 1 : Erlang, Python et Haskell perdent-ils de la vitesse en raison de l'utilisation d'entiers de longueur arbitraire ou non tant que les valeurs sont inférieures à MAXINT ?

Question 2 : Pourquoi Haskell est-il si lent ? Y a-t-il un drapeau du compilateur qui désactive les freins ou est-ce mon implémentation ? (Cette dernière hypothèse est tout à fait probable car Haskell est pour moi un livre à sept sceaux).

Question 3 : Pouvez-vous me donner quelques conseils pour optimiser ces implémentations sans changer la façon dont je détermine les facteurs ? Optimisation de quelque manière que ce soit : plus agréable, plus rapide, plus "native" au langage.

EDIT :

Question 4 : Mes implémentations fonctionnelles permettent-elles le LCO (last call optimization, c'est-à-dire l'élimination de la récursion de queue) et évitent-elles ainsi d'ajouter des trames inutiles sur la pile d'appels ?

J'ai vraiment essayé d'implémenter le même algorithme de manière aussi similaire que possible dans les quatre langages, même si je dois admettre que mes connaissances en Haskell et Erlang sont très limitées.

---

Codes sources utilisés :

#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

Utilisation de GHC 7.0.3 , gcc 4.4.6 , Linux 2.6.29 sur une machine x86_64 Core2 Duo (2.5GHz), en compilant à l'aide de ghc -O2 -fllvm -fforce-recomp pour Haskell et gcc -O3 -lm pour C.

• Votre routine C s'exécute en 8,4 secondes (plus vite que votre exécution probablement à cause de -O3 )
• La solution Haskell s'exécute en 36 secondes (en raison de l'utilisation de l'algorithme de l'utilisateur). -O2 drapeau)
• Votre factorCount' le code n'est pas explicitement typé et il est utilisé par défaut pour Integer (merci à Daniel d'avoir corrigé mon erreur de diagnostic !). Donner une signature de type explicite (ce qui est une pratique standard de toute façon) en utilisant Int et l'heure passe à 11,1 secondes
• sur factorCount' vous avez inutilement appelé fromIntegral . Une correction n'entraîne cependant aucun changement (le compilateur est intelligent, heureusement pour vous).
• Vous avez utilisé mod où rem est plus rapide et suffisante. Cela modifie le temps de 8,5 secondes .

• factorCount' applique constamment deux arguments supplémentaires qui ne changent jamais ( number , sqrt ). Une transformation worker/wrapper nous donne :

  $ time ./so 842161320

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

C'est vrai, 7,95 secondes . Constamment une demi-seconde plus rapide que la solution C . Sans le -fllvm flag j'ai toujours 8.182 seconds Le backend de la NCG fonctionne donc bien dans ce cas également.

Conclusion : Haskell est génial.

Code résultant

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 : Maintenant que nous avons exploré ce point, abordons les questions.

Question 1 : Est-ce qu'erlang, python et haskell perdent de la vitesse à cause de l'utilisation d'entiers de longueur arbitraire ? l'utilisation d'entiers de longueur arbitraire ou non, tant que les valeurs sont inférieures à que MAXINT ?

En Haskell, l'utilisation de Integer est plus lent que Int mais le degré de ralentissement dépend des calculs effectués. Par chance (pour les machines 64 bits) Int est suffisant. Pour des raisons de portabilité, vous devriez probablement réécrire mon code pour utiliser Int64 ou Word64 (Le C n'est pas le seul langage qui possède une fonction long ).

Question 2 : Pourquoi Haskell est-il si lent ? Existe-t-il un drapeau de compilation qui qui désactive les freins ou est-ce mon implémentation ? (Cette dernière est tout à fait probable car haskell est un livre aux sept sceaux pour moi).

Question 3 : Pouvez-vous me donner quelques conseils pour optimiser ces implémentations sans changer la façon dont je détermine les facteurs ? Optimisation de quelque manière que ce soit : plus agréable, plus rapide, plus "native" au langage.

C'est ce que j'ai répondu ci-dessus. La réponse était

• 0) Utiliser l'optimisation via -O2
• 1) Utilisez des types rapides (notamment : non encastrables) lorsque cela est possible.
• 2) rem pas mod (une optimisation souvent oubliée) et
• 3) la transformation ouvrier/enveloppeur (peut-être l'optimisation la plus courante).

Question 4 : Est-ce que mes implémentations fonctionnelles permettent le LCO et donc d'éviter d'ajouter des trames inutiles sur la pile d'appels ?

Oui, ce n'était pas le problème. Bon travail et content que vous y ayez pensé.

Answer 2

Il y a quelques problèmes avec l'implémentation Erlang. Comme référence pour ce qui suit, le temps d'exécution que j'ai mesuré pour votre programme Erlang non modifié était de 47,6 secondes, comparé à 12,7 secondes pour le code C.

La première chose à faire si vous voulez exécuter du code Erlang à forte intensité de calcul est d'utiliser du code natif. Compiler avec erlc +native euler12 a permis de réduire le temps à 41,3 secondes. Il s'agit cependant d'un gain de vitesse beaucoup plus faible (seulement 15%) que celui attendu d'une compilation native sur ce type de code. -compile(export_all) . Ceci est utile pour l'expérimentation, mais le fait que toutes les fonctions soient potentiellement accessibles de l'extérieur fait que le compilateur natif est très conservateur. (L'émulateur BEAM normal n'est pas tellement affecté.) En remplaçant cette déclaration par -export([solve/0]). donne une bien meilleure accélération : 31,5 secondes (presque 35% par rapport à la ligne de base).

Mais le code lui-même a un problème : pour chaque itération dans la boucle factorCount, vous effectuez ce test :

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

Le code C ne fait pas ça. En général, il peut être délicat de faire une comparaison équitable entre différentes implémentations du même code, et en particulier si l'algorithme est numérique, car vous devez être sûr qu'elles font réellement la même chose. Une légère erreur d'arrondi dans une implémentation due à un typecast quelque part peut entraîner beaucoup plus d'itérations dans l'une que dans l'autre, même si les deux atteignent finalement le même résultat.

Pour éliminer cette source d'erreur possible (et se débarrasser du test supplémentaire à chaque itération), j'ai réécrit la fonction factorCount comme suit, en m'inspirant étroitement du code C :

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.

Cette réécriture, non export_all et la compilation native m'ont donné le temps d'exécution suivant :

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

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

ce qui n'est pas trop mal par rapport au code C :

$ time ./a.out 
842161320

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

Si l'on considère qu'Erlang n'est pas du tout orienté vers l'écriture de code numérique, le fait d'être seulement 50% plus lent que le C sur un programme comme celui-ci est plutôt bon.

Enfin, en ce qui concerne vos questions :

Question 1 : Est-ce que erlang, python et haskell perdent de la vitesse à cause de l'utilisation d'entiers de longueur arbitraire ou ne le font-ils pas tant que les valeurs sont inférieures à MAXINT ?

Oui, en quelque sorte. En Erlang, il n'y a aucun moyen de dire "utilisez l'arithmétique 32/64 bits avec enveloppement", donc à moins que le compilateur puisse prouver des limites sur vos entiers (et il ne le peut généralement pas), il doit vérifier tous les calculs pour voir s'ils peuvent tenir dans un seul mot étiqueté ou s'il doit les transformer en bignums alloués au tas. Même si aucun bignum n'est utilisé en pratique au moment de l'exécution, ces vérifications devront être effectuées. D'un autre côté, cela signifie que vous connaître que l'algorithme n'échouera jamais à cause d'un retournement inattendu des entiers si vous lui donnez soudainement des entrées plus importantes qu'auparavant.

Question 4 : Est-ce que mes implémentations fonctionnelles permettent le LCO et donc évitent d'ajouter des trames inutiles sur la pile d'appels ?

Oui, votre code Erlang est correct en ce qui concerne l'optimisation du dernier appel.

Answer 3

En ce qui concerne l'optimisation de Python, outre l'utilisation de PyPy (qui permet d'obtenir des gains de vitesse impressionnants sans modifier le code), vous pouvez utiliser l'outil de PyPy chaîne de traduction pour compiler une version conforme à RPython, ou Cython pour construire un module d'extension, les deux sont plus rapides que la version C dans mes tests, avec le module Cython presque deux fois plus rapide . Pour référence, j'ai également inclus les résultats des tests de référence en C et PyPy :

C (compilé avec 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 (utilisant la dernière révision de PyPy, 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

La version RPython comporte quelques modifications importantes. Pour traduire en un programme autonome, vous devez définir votre fichier target qui, dans ce cas, est le main fonction. Il est censé accepter sys.argv comme seul argument, et doit retourner un int. Vous pouvez le traduire en utilisant translate.py, % translate.py euler12-rpython.py qui traduit en C et le compile pour vous.

# 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

La version Cython a été réécrite comme un module d'extension. _euler12.pyx que j'importe et appelle à partir d'un fichier python normal. Le site _euler12.pyx est essentiellement la même que votre version, avec quelques déclarations de types statiques supplémentaires. Le fichier setup.py contient les éléments habituels pour construire l'extension, en utilisant les éléments suivants 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
)

J'ai honnêtement très peu d'expérience avec RPython ou Cython, et j'ai été agréablement surpris par les résultats. Si vous utilisez CPython, l'écriture de vos morceaux de code gourmands en ressources CPU dans un module d'extension Cython semble être un moyen très simple d'optimiser votre programme.

Answer 4

Question 3 : Pouvez-vous me donner quelques conseils pour optimiser ces implémentations sans changer la façon dont je détermine les facteurs ? Optimisation dans tous les sens manière : plus agréable, plus rapide, plus "native" pour le langage.

L'implémentation en C est sous-optimale (comme l'a laissé entendre Thomas M. DuBuisson), la version utilise des entiers 64 bits (c'est-à-dire long type de données). J'examinerai le listing d'assemblage plus tard, mais je pense qu'il y a des accès à la mémoire dans le code compilé, ce qui rend l'utilisation d'entiers 64 bits significativement plus lente. C'est ça ou le code généré (que ce soit le fait qu'on puisse mettre moins d'entiers 64 bits dans un registre SSE ou qu'arrondir un double à un entier 64 bits soit plus lent).

Voici le code modifié (il suffit de remplacer long avec int et j'ai explicitement inlined factorCount, bien que je ne pense pas que cela soit nécessaire avec gcc -O3) :

#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);
}

La course + le timing qu'elle donne :

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

Pour référence, l'implémentation de haskell par Thomas dans la réponse précédente donne :

$ 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

Conclusion : Je n'enlève rien à ghc, c'est un excellent compilateur, mais gcc génère normalement un code plus rapide.

Answer 5

Jetez un coup d'œil à ce blog . Au cours de l'année écoulée, il a réalisé quelques-uns des problèmes du projet Euler en Haskell et en Python, et il a trouvé en général que Haskell pour être beaucoup plus rapide. Je pense qu'entre ces langages, cela a plus à voir avec votre aisance et votre style de codage.

En ce qui concerne la vitesse de Python, vous utilisez la mauvaise implémentation ! Essayez PyPy et pour ce genre de choses, vous trouverez qu'il est beaucoup, beaucoup plus rapide.