Confronto di velocità con Project Euler: C vs Python vs Erlang vs Haskell




performance (15)

Ho preso il Problema # 12 da Project Euler come esercizio di programmazione e per confrontare le mie implementazioni (sicuramente non ottimali) in C, Python, Erlang e Haskell. Per ottenere tempi di esecuzione più elevati, cerco il numero del primo triangolo con più di 1000 divisori anziché 500 come indicato nel problema originale.

Il risultato è il seguente:

C:

[email protected]:~/erlang$ gcc -lm -o euler12.bin euler12.c
[email protected]:~/erlang$ time ./euler12.bin
842161320

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

Pitone:

[email protected]:~/erlang$ time ./euler12.py 
842161320

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

Python con PyPy:

[email protected]:~/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:

[email protected]:~/erlang$ erlc euler12.erl 
[email protected]:~/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:

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

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

Sommario:

  • C: 100%
  • Python: 692% (118% con PyPy)
  • Erlang: 436% (135% grazie a RichardC)
  • Haskell: 1421%

Suppongo che C abbia un grande vantaggio in quanto utilizza a lungo i calcoli e non gli interi di lunghezza arbitraria come gli altri tre. Inoltre non ha bisogno di caricare prima un runtime (Do gli altri?).

Domanda 1: Erlang, Python e Haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT ?

Domanda 2: Perché Haskell è così lento? C'è un flag del compilatore che spegne i freni o è la mia implementazione? (Quest'ultimo è abbastanza probabile visto che Haskell è un libro con sette sigilli per me.)

Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

MODIFICARE:

Domanda 4: Le mie implementazioni funzionali consentono LCO (l'ultima ottimizzazione delle chiamate, ovvero l'eliminazione della ricorsione di coda) e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Ho davvero cercato di implementare lo stesso algoritmo il più simile possibile nelle quattro lingue, anche se devo ammettere che la mia conoscenza di Haskell ed Erlang è molto limitata.

Codici sorgente utilizzati:

#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

Guardando la tua implementazione di Erlang. La tempistica ha incluso l'avvio dell'intera macchina virtuale, l'esecuzione del programma e l'arresto della macchina virtuale. Sono abbastanza sicuro che l'installazione e l'interruzione dell'erlang vm richiedono del tempo.

Se il tempismo fosse stato fatto all'interno della macchina virtuale di erlang stessa, i risultati sarebbero diversi poiché in tal caso avremmo il tempo effettivo solo per il programma in questione. Altrimenti, credo che il tempo totale impiegato dal processo di avvio e caricamento di Erlang Vm più quello di interromperlo (come lo inserisci nel tuo programma) sono tutti inclusi nel tempo totale che il metodo che stai usando per cronometrare il tempo il programma sta uscendo. Prendi in considerazione l'utilizzo della temporizzazione di erlang che utilizziamo quando vogliamo temporizzare i nostri programmi all'interno della macchina virtuale stessa timer:tc/1 or timer:tc/2 or timer:tc/3. In questo modo, i risultati di erlang escluderanno il tempo impiegato per avviare e fermare / uccidere / fermare la macchina virtuale. Questo è il mio ragionamento lì, pensaci, e poi prova di nuovo il tuo benchmark.

In realtà suggerisco di provare a programmare il programma (per le lingue che hanno un runtime), nel runtime di quelle lingue per ottenere un valore preciso. Ad esempio, C non ha un sovraccarico di avvio e di arresto di un sistema runtime come fanno Erlang, Python e Haskell (il 98% ne è sicuro - sto correggendo). Quindi (basato su questo ragionamento) concludo dicendo che questo benchmark non era abbastanza preciso / corretto per le lingue che girano su un sistema runtime. Lo facciamo di nuovo con questi cambiamenti.

EDIT: inoltre, anche se tutti i linguaggi disponevano di sistemi di runtime, il sovraccarico di avvio di ciascuno e interruzione sarebbe diverso. quindi suggerisco di passare il tempo all'interno dei sistemi di runtime (per le lingue per le quali questo si applica). L'Erlang VM è noto per avere un notevole overhead all'avvio!


Usando GHC 7.0.3 , gcc 4.4.6 , Linux 2.6.29 su una macchina x86_64 Core2 Duo (2.5GHz), compilando usando ghc -O2 -fllvm -fforce-recomp per Haskell e gcc -O3 -lm per C.

  • La tua routine C viene eseguita in 8,4 secondi (più veloce della tua corsa probabilmente a causa di -O3 )
  • La soluzione Haskell funziona in 36 secondi (a causa del flag -O2 )
  • Il codice del tuo factorCount' non è stato digitato esplicitamente e predefinito su Integer (grazie a Daniel per correggere la mia diagnosi errata qui!). Dando una firma di tipo esplicita (che è comunque una pratica standard) usando Int e il tempo cambia a 11.1 secondi
  • in factorCount' hai inutilmente chiamato da fromIntegral . Tuttavia, una correzione non comporta alcun cambiamento (il compilatore è intelligente, fortunato per te).
  • Hai usato mod dove rem è più veloce e sufficiente. Questo cambia il tempo a 8,5 secondi .
  • factorCount' applica costantemente due argomenti extra che non cambiano mai ( number , sqrt ). Una trasformazione worker / wrapper ci dà:
 $ time ./so
 842161320  

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

Esatto, 7,95 secondi . Costantemente mezzo secondo più veloce della soluzione C. Senza il flag -fllvm sto ancora ottenendo 8.182 seconds , quindi anche il backend NCG sta andando bene in questo caso.

Conclusione: Haskell è fantastico.

Codice risultante

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: Così ora che abbiamo esplorato questo, lascia rispondere alle domande

Domanda 1: erlang, python e haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

In Haskell, l'uso di Integer è più lento di Int ma quanto più lento dipende dai calcoli eseguiti. Fortunatamente (per macchine a 64 bit) Int è sufficiente. Per motivi di portabilità dovresti probabilmente riscrivere il mio codice per usare Int64 o Word64 (C non è l'unica lingua con un long ).

Domanda 2: Perché haskell è così lento? C'è un flag del compilatore che spegne i freni o è la mia implementazione? (Quest'ultimo è abbastanza probabile poichè haskell è un libro con sette sigilli per me.)

Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

Questo è quello che ho risposto sopra. La risposta era

  • 0) Usa l'ottimizzazione tramite -O2
  • 1) Utilizzare i tipi veloci (in particolare: unbox-able) quando possibile
  • 2) rem not mod (un'ottimizzazione frequentemente dimenticata) e
  • 3) trasformazione worker / wrapper (forse l'ottimizzazione più comune).

Domanda 4: Le mie implementazioni funzionali consentono LCO e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Sì, non era questo il problema. Buon lavoro e felice che tu abbia preso in considerazione questo.


Modificare: case (divisor(T,round(math:sqrt(T))) > 500) of

A: case (divisor(T,round(math:sqrt(T))) > 1000) of

Questo produrrà la risposta corretta per l'esempio multiprocesso di Erlang.


Domanda 1: Erlang, Python e Haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

La domanda 1 può essere risolta in senso negativo per Erlang. Si risponde all'ultima domanda usando Erlang in modo appropriato, come in:

http://bredsaal.dk/learning-erlang-using-projecteuler-net

Dato che è più veloce del tuo esempio C iniziale, direi che ci sono numerosi problemi, come altri hanno già trattato in dettaglio.

Questo modulo Erlang viene eseguito su un netbook economico in circa 5 secondi ... Utilizza il modello di thread di rete in erlang e, come tale, dimostra come sfruttare il modello di eventi. Potrebbe essere distribuito su molti nodi. Ed è veloce. Non il mio codice

-module(p12dist).  
-author("Jannich Brendle, [email protected], http://blog.bredsaal.dk").  
-compile(export_all).

server() ->  
  server(1).

server(Number) ->  
  receive {getwork, Worker_PID} -> Worker_PID ! {work,Number,Number+100},  
  server(Number+101);  
  {result,T} -> io:format("The result is: \~w.\~n", [T]);  
  _ -> server(Number)  
  end.

worker(Server_PID) ->  
  Server_PID ! {getwork, self()},  
  receive {work,Start,End} -> solve(Start,End,Server_PID)  
  end,  
  worker(Server_PID).

start() ->  
  Server_PID = spawn(p12dist, server, []),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]).

solve(N,End,_) when N =:= End -> no_solution;

solve(N,End,Server_PID) ->  
  T=round(N*(N+1)/2),
  case (divisor(T,round(math:sqrt(T))) > 500) of  
    true ->  
      Server_PID ! {result,T};  
    false ->  
      solve(N+1,End,Server_PID)  
  end.

divisors(N) ->  
  divisor(N,round(math:sqrt(N))).

divisor(_,0) -> 1;  
divisor(N,I) ->  
  case (N rem I) =:= 0 of  
  true ->  
    2+divisor(N,I-1);  
  false ->  
    divisor(N,I-1)  
  end.

Il test seguente si è svolto su una CPU Intel (R) Atom (TM) N270 a 1,60 GHz

~$ time erl -noshell -s p12dist start

The result is: 76576500.

^C

BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
       (v)ersion (k)ill (D)b-tables (d)istribution
a

real    0m5.510s
user    0m5.836s
sys 0m0.152s

Dai un'occhiata a questo blog . Nell'ultimo anno circa ha fatto alcuni dei problemi di Project Euler in Haskell e Python, e in genere ha trovato Haskell molto più veloce. Penso che tra quelle lingue abbia più a che fare con la tua scioltezza e lo stile di codifica.

Quando si tratta della velocità di Python, stai usando l'implementazione sbagliata! Prova PyPy e per cose come questa troverai che è molto, molto più veloce.


Con Haskell, non hai davvero bisogno di pensare esplicitamente alle ricorsioni.

factorCount number = foldr factorCount' 0 [1..isquare] -
                     (fromEnum $ square == fromIntegral isquare)
    where
      square = sqrt $ fromIntegral number
      isquare = floor square
      factorCount' candidate
        | number `rem` candidate == 0 = (2 +)
        | otherwise = id

triangles :: [Int]
triangles = scanl1 (+) [1,2..]

main = print . head $ dropWhile ((< 1001) . factorCount) triangles

Nel codice precedente, ho sostituito le ricorsioni esplicite nella risposta di @Thomas con le operazioni dell'elenco comune. Il codice fa ancora esattamente la stessa cosa senza preoccuparci della ricorsione della coda. Esegue (~ 7.49s ) circa il 6% più lento della versione nella risposta di @Thomas (~ 7.04s ) sulla mia macchina con GHC 7.6.2, mentre la versione C di @Raedwulf gira ~ 3.15s . Sembra che il GHC sia migliorato nel corso dell'anno.

PS. So che è una vecchia domanda, e mi ci imbattuto in ricerche di google (ho dimenticato quello che stavo cercando, ora ...). Volevo solo commentare la domanda su LCO ed esprimere i miei sentimenti su Haskell in generale. Volevo commentare la risposta in alto, ma i commenti non consentono blocchi di codice.


Ho modificato la versione "Jannich Brendle" a 1000 invece di 500. E elenco il risultato di euler12.bin, euler12.erl, p12dist.erl. Entrambi i codici erl usano '+ nativo' per compilare.

zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s p12dist start
The result is: 842161320.

real    0m3.879s
user    0m14.553s
sys     0m0.314s
zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s euler12 solve
842161320

real    0m10.125s
user    0m10.078s
sys     0m0.046s
zhengs-MacBook-Pro:workspace zhengzhibin$ time ./euler12.bin 
842161320

real    0m5.370s
user    0m5.328s
sys     0m0.004s
zhengs-MacBook-Pro:workspace zhengzhibin$

Ho ipotizzato che il numero di fattori sia grande solo se i numeri coinvolti hanno molti piccoli fattori. Quindi ho usato l'algoritmo eccellente di thaumkid, ma prima ho usato un'approssimazione del conteggio dei fattori che non è mai troppo piccola. È abbastanza semplice: controlla i fattori primi fino a 29, quindi controlla il numero rimanente e calcola un limite superiore per il numero di fattori. Usalo per calcolare un limite superiore per il numero di fattori, e se quel numero è abbastanza alto, calcola il numero esatto di fattori.

Il codice sotto non ha bisogno di questa assunzione per correttezza, ma per essere veloce. Sembra funzionare; solo circa uno su 100.000 numeri dà una stima che è abbastanza alta da richiedere un controllo completo.

Ecco il codice:

// Return at least the number of factors of n.
static uint64_t approxfactorcount (uint64_t n)
{
    uint64_t count = 1, add;

#define CHECK(d)                            \
    do {                                    \
        if (n % d == 0) {                   \
            add = count;                    \
            do { n /= d; count += add; }    \
            while (n % d == 0);             \
        }                                   \
    } while (0)

    CHECK ( 2); CHECK ( 3); CHECK ( 5); CHECK ( 7); CHECK (11); CHECK (13);
    CHECK (17); CHECK (19); CHECK (23); CHECK (29);
    if (n == 1) return count;
    if (n < 1ull * 31 * 31) return count * 2;
    if (n < 1ull * 31 * 31 * 37) return count * 4;
    if (n < 1ull * 31 * 31 * 37 * 37) return count * 8;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41) return count * 16;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43) return count * 32;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47) return count * 64;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53) return count * 128;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59) return count * 256;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61) return count * 512;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67) return count * 1024;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71) return count * 2048;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73) return count * 4096;
    return count * 1000000;
}

// Return the number of factors of n.
static uint64_t factorcount (uint64_t n)
{
    uint64_t count = 1, add;

    CHECK (2); CHECK (3);

    uint64_t d = 5, inc = 2;
    for (; d*d <= n; d += inc, inc = (6 - inc))
        CHECK (d);

    if (n > 1) count *= 2; // n must be a prime number
    return count;
}

// Prints triangular numbers with record numbers of factors.
static void printrecordnumbers (uint64_t limit)
{
    uint64_t record = 30000;

    uint64_t count1, factor1;
    uint64_t count2 = 1, factor2 = 1;

    for (uint64_t n = 1; n <= limit; ++n)
    {
        factor1 = factor2;
        count1 = count2;

        factor2 = n + 1; if (factor2 % 2 == 0) factor2 /= 2;
        count2 = approxfactorcount (factor2);

        if (count1 * count2 > record)
        {
            uint64_t factors = factorcount (factor1) * factorcount (factor2);
            if (factors > record)
            {
                printf ("%lluth triangular number = %llu has %llu factors\n", n, factor1 * factor2, factors);
                record = factors;
            }
        }
    }
}

Questo trova il 14.753.024th triangolare con 13824 fattori in circa 0,7 secondi, il numero triangolare 879,207,615th con 61,440 fattori in 34 secondi, il numero triangolare 12,524,486,975th con 138,240 fattori in 10 minuti 5 secondi e il numero triangolare 26,467,792,064th con 172,032 fattori in 21 minuti e 25 secondi (Core2 Duo 2,4 GHz), quindi questo codice richiede in media solo 116 cicli del processore per numero. L'ultimo numero triangolare è più grande di 2 ^ 68, quindi


Per quanto riguarda l'ottimizzazione di Python, oltre all'uso di PyPy (per accelerazioni piuttosto impressionanti con zero modifiche al codice), è possibile utilizzare la toolchain di traduzione di PyPy per compilare una versione compatibile con Cython o Cython per creare un modulo di estensione, entrambi che sono più veloci della versione C nei miei test, con il modulo Cython quasi due volte più veloce . Per riferimento, includo anche i risultati benchmark C e PyPy:

C (compilato con 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 (usando l'ultima revisione 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 versione di RPython ha un paio di cambiamenti chiave. Per tradurre in un programma standalone devi definire il tuo target , che in questo caso è la funzione main . Si presuppone che accetti sys.argv poiché è solo un argomento ed è necessario per restituire un int. Puoi tradurlo usando translate.py, % translate.py euler12-rpython.py che si traduce in C e lo compila per te.

# 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 versione di Cython è stata riscritta come un modulo di estensione _euler12.pyx , che _euler12.pyx e richiamo da un normale file python. _euler12.pyx è essenzialmente uguale alla tua versione, con alcune dichiarazioni di tipo statico aggiuntive. Setup.py ha il normale boilerplate per costruire l'estensione, usando 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
)

Sinceramente ho avuto pochissima esperienza con RPython o Cython, e sono rimasto piacevolmente sorpreso dai risultati. Se stai usando CPython, scrivere i bit di codice a uso intensivo della CPU in un modulo di estensione Cython sembra un modo davvero semplice per ottimizzare il tuo programma.


Altri numeri e spiegazioni per la versione C. Apparentemente nessuno lo fece durante tutti quegli anni. Ricordati di revocare questa risposta in modo che possa essere in grado di vedere e imparare da tutti.

Primo passo: benchmark dei programmi dell'autore

Specifiche del laptop:

  • CPU i3 M380 (931 MHz - modalità di risparmio massimo della batteria)
  • Memoria da 4 GB
  • Win7 64 bit
  • Microsoft Visual Studio 2012 Ultimate
  • Cygwin con gcc 4.9.3
  • Python 2.7.10

comandi:

compiling on VS x64 command prompt > `for /f %f in ('dir /b *.c') do cl /O2 /Ot /Ox %f -o %f_x64_vs2012.exe`
compiling on cygwin with gcc x64   > `for f in ./*.c; do gcc -m64 -O3 $f -o ${f}_x64_gcc.exe ; done`
time (unix tools) using cygwin > `for f in ./*.exe; do  echo "----------"; echo $f ; time $f ; done`

.

----------
$ time python ./original.py

real    2m17.748s
user    2m15.783s
sys     0m0.093s
----------
$ time ./original_x86_vs2012.exe

real    0m8.377s
user    0m0.015s
sys     0m0.000s
----------
$ time ./original_x64_vs2012.exe

real    0m8.408s
user    0m0.000s
sys     0m0.015s
----------
$ time ./original_x64_gcc.exe

real    0m20.951s
user    0m20.732s
sys     0m0.030s

I nomi dei file sono: integertype_architecture_compiler.exe

  • integertype è lo stesso del programma originale per ora (ne riparleremo più avanti)
  • l'architettura è x86 o x64 a seconda delle impostazioni del compilatore
  • il compilatore è gcc o vs2012

Fase due: indagare, migliorare e valutare nuovamente

VS è il 250% più veloce di gcc. I due compilatori dovrebbero dare una velocità simile. Ovviamente, c'è qualcosa di sbagliato nel codice o nelle opzioni del compilatore. Investighiamo!

Il primo punto di interesse sono i tipi interi. Le conversioni possono essere costose e la coerenza è importante per una migliore generazione e ottimizzazione del codice. Tutti gli interi devono essere dello stesso tipo.

È un miscuglio misto di inte in longquesto momento. Miglioreremo questo. Che tipo usare? Il più veloce. Devo segnarli tutti quanti!

----------
$ time ./int_x86_vs2012.exe

real    0m8.440s
user    0m0.016s
sys     0m0.015s
----------
$ time ./int_x64_vs2012.exe

real    0m8.408s
user    0m0.016s
sys     0m0.015s
----------
$ time ./int32_x86_vs2012.exe

real    0m8.408s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int32_x64_vs2012.exe

real    0m8.362s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int64_x86_vs2012.exe

real    0m18.112s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int64_x64_vs2012.exe

real    0m18.611s
user    0m0.000s
sys     0m0.015s
----------
$ time ./long_x86_vs2012.exe

real    0m8.393s
user    0m0.015s
sys     0m0.000s
----------
$ time ./long_x64_vs2012.exe

real    0m8.440s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint32_x86_vs2012.exe

real    0m8.362s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint32_x64_vs2012.exe

real    0m8.393s
user    0m0.015s
sys     0m0.015s
----------
$ time ./uint64_x86_vs2012.exe

real    0m15.428s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint64_x64_vs2012.exe

real    0m15.725s
user    0m0.015s
sys     0m0.015s
----------
$ time ./int_x64_gcc.exe

real    0m8.531s
user    0m8.329s
sys     0m0.015s
----------
$ time ./int32_x64_gcc.exe

real    0m8.471s
user    0m8.345s
sys     0m0.000s
----------
$ time ./int64_x64_gcc.exe

real    0m20.264s
user    0m20.186s
sys     0m0.015s
----------
$ time ./long_x64_gcc.exe

real    0m20.935s
user    0m20.809s
sys     0m0.015s
----------
$ time ./uint32_x64_gcc.exe

real    0m8.393s
user    0m8.346s
sys     0m0.015s
----------
$ time ./uint64_x64_gcc.exe

real    0m16.973s
user    0m16.879s
sys     0m0.030s

I tipi interi sono int long int32_t uint32_t int64_te uint64_tda#include <stdint.h>

Ci sono molti tipi interi in C, più alcuni firmati / non firmati con cui giocare, più la scelta di compilare come x86 o x64 (da non confondere con la dimensione intera effettiva). Sono molte versioni da compilare ed eseguire ^^

Terzo passo: Capire i numeri

Conclusioni definitive:

  • I numeri interi a 32 bit sono ~ 200% più veloci rispetto agli equivalenti a 64 bit
  • interi a 64 bit senza segno sono più veloci del 25% rispetto ai 64 bit con segno (purtroppo, non ho alcuna spiegazione per quello)

Domanda di trucco: "Quali sono le dimensioni di int e long in C?"
La risposta corretta è: le dimensioni di int e long in C non sono ben definite!

Dalla specifica C:

int è almeno
lungo 32 bit è almeno un int

Dalla pagina man di gcc (flag -m32 e -m64):

L'ambiente a 32 bit imposta int, long e puntatore su 32 bit e genera codice che gira su qualsiasi sistema i386.
L'ambiente a 64 bit imposta int a 32 bit, long e puntatore a 64 bit e genera il codice per l'architettura x86-64 di AMD.

Dalla documentazione MSDN (Data Type Ranges) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

int, 4 byte, sa anche come firmato
long, 4 byte, anche conosciuto come long int e firmato long int

Per concludere: lezioni apprese

  • 32 bit interi sono più veloci di numeri interi a 64 bit.

  • I tipi di interi standard non sono ben definiti in C o C ++, variano a seconda dei compilatori e delle architetture. Quando hai bisogno di coerenza e prevedibilità, usa la uint32_tfamiglia intera da #include <stdint.h>.

  • Problemi di velocità risolti. Tutte le altre lingue sono tornate indietro di centinaia, C & C ++ vincono di nuovo! Lo fanno sempre. Il prossimo miglioramento sarà il multithreading usando OpenMP: D


Ci sono alcuni problemi con l'implementazione di Erlang. Come base per quanto segue, il mio tempo di esecuzione misurato per il tuo programma Erlang non modificato era di 47,6 secondi, rispetto ai 12,7 secondi del codice C.

La prima cosa che dovresti fare se vuoi eseguire un codice Erlang ad alta intensità di calcolo è usare il codice nativo. La compilazione con erlc +native euler12 ha erlc +native euler12 il tempo a 41,3 secondi. Questa è comunque una velocità molto più bassa (solo il 15%) del previsto dalla compilazione nativa su questo tipo di codice, e il problema è l'uso di -compile(export_all) . Questo è utile per la sperimentazione, ma il fatto che tutte le funzioni siano potenzialmente raggiungibili dall'esterno fa sì che il compilatore nativo sia molto conservativo. (Il normale emulatore BEAM non è molto influenzato.) Sostituzione di questa dichiarazione con -export([solve/0]). offre una velocità molto migliore: 31,5 secondi (quasi il 35% dalla linea di base).

Ma il codice stesso ha un problema: per ogni iterazione nel ciclo factorCount, si esegue questo test:

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

Il codice C non lo fa. In generale, può essere complicato fare un confronto equo tra le diverse implementazioni dello stesso codice, e in particolare se l'algoritmo è numerico, perché è necessario essere sicuri che stiano facendo la stessa cosa. Un leggero errore di arrotondamento in un'implementazione a causa di qualche typecast da qualche parte può far sì che faccia molte più iterazioni rispetto all'altra, anche se entrambe alla fine raggiungono lo stesso risultato.

Per eliminare questa possibile fonte di errore (e sbarazzarmi del test aggiuntivo in ogni iterazione), ho riscritto la funzione factorCount come segue, modellata sul codice 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.

Questa riscrittura, nessun export_all e la compilazione nativa mi hanno dato il seguente tempo di esecuzione:

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

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

che non è male rispetto al codice C:

$ time ./a.out 
842161320

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

considerando che Erlang non è affatto orientato alla scrittura di codice numerico, essendo solo il 50% più lento di C su un programma come questo è abbastanza buono.

Infine, riguardo alle tue domande:

Domanda 1: erlang, python e haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

Sì, un po '. In Erlang, non c'è modo di dire "usa aritmetica a 32/64 bit con wrap-around", quindi a meno che il compilatore non possa provare dei limiti sui tuoi numeri interi (e di solito non può farlo), deve controllare tutti i calcoli per vedere se possono rientrare in una singola parola con tag o se devono trasformarli in bignums allocati in heap. Anche se in pratica non vengono mai utilizzati bignum in fase di esecuzione, questi controlli dovranno essere eseguiti. D'altra parte, ciò significa che tu sai che l'algoritmo non fallirà mai a causa di un inaspettato numero intero inaspettato se improvvisamente gli dai input più grandi di prima.

Domanda 4: Le mie implementazioni funzionali consentono LCO e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Sì, il tuo codice Erlang è corretto rispetto all'ottimizzazione dell'ultima chiamata.


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

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square+1;
    long candidate = 2;
    int count = 1;
    while(candidate <= isquare && candidate<=n){
        int c = 1;
        while (n % candidate == 0) {
           c++;
           n /= candidate;
        }
        count *= c;
        candidate++;
    }
    return count;
}

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

gcc -lm -Ofast euler.c

tempo ./a.out

2.79s utente 0.00 sistema 99% cpu 2.794 totale


Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

L'implementazione C è subottimale (come suggerito da Thomas M. DuBuisson), la versione utilizza interi a 64 bit (cioè un tipo di dati lungo ). Analizzerò l'elenco di assembly in seguito, ma con un'ipotesi plausibile, ci sono alcuni accessi di memoria in corso nel codice compilato, che rendono l'utilizzo di numeri interi a 64 bit molto più lento. È quello o il codice generato (sia che sia possibile inserire meno di 64 bit in un registro SSE o arrotondare un doppio a un intero a 64 bit è più lento).

Ecco il codice modificato (semplicemente sostituisci long con int e I in modo esplicito in factorCount, anche se non penso che questo sia necessario con 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);
}

Running + timing dà:

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

Come riferimento, l'implementazione haskell di Thomas nella risposta precedente fornisce:

$ 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

Conclusione: non prendere nulla da ghc, è un ottimo compilatore, ma gcc normalmente genera codice più veloce.


L'implementazione di Haskell potrebbe essere notevolmente accelerata utilizzando alcune funzioni dei pacchetti Haskell. In questo caso ho usato i primes, che sono stati appena installati con 'cabal install primi';)

import Data.Numbers.Primes
import Data.List

triangleNumbers = scanl1 (+) [1..]
nDivisors n = product $ map ((+1) . length) (group (primeFactors n))
answer = head $ filter ((> 500) . nDivisors) triangleNumbers

main :: IO ()
main = putStrLn $ "First triangle number to have over 500 divisors: " ++ (show answer)

Tempi:

Il tuo programma originale:

PS> measure-command { bin\012_slow.exe }

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Migliore implementazione

PS> measure-command { bin\012.exe }

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Come puoi vedere, questo viene eseguito in 38 millisecondi sulla stessa macchina in cui il tuo ha funzionato in 16 secondi :)

Comandi di compilazione:

ghc -O2 012.hs -o bin\012.exe
ghc -O2 012_slow.hs -o bin\012_slow.exe

Domanda 1: erlang, python e haskell perdono velocità a causa dell'utilizzo di numeri interi di lunghezza arbitrari o non lo fanno fintanto che i valori sono inferiori a MAXINT?

Questo è improbabile. Non posso dire molto di Erlang e Haskell (beh, forse un po 'di Haskell in basso), ma posso indicare molti altri colli di bottiglia in Python. Ogni volta che il programma tenta di eseguire un'operazione con alcuni valori in Python, dovrebbe verificare se i valori sono del tipo corretto e costa un po 'di tempo. factorCount funzione factorCount assegna solo una lista con range (1, isquare + 1) varie volte e runtime, l'allocazione della memoria con malloc è molto più lenta di iterare su un intervallo con un contatore come si fa in C. In particolare, il factorCount() è chiamato più volte e quindi assegna un sacco di liste. Inoltre, non dimentichiamo che Python è interpretato e l'interprete CPython non si concentra molto sull'ottimizzazione.

EDIT : oh, beh, noto che stai usando Python 3 quindi range() non restituisce una lista, ma un generatore. In questo caso, il mio punto sull'allocazione delle liste è metà sbagliato: la funzione alloca solo oggetti di range , che sono comunque inefficienti ma non altrettanto inefficienti quanto l'assegnazione di una lista con molti articoli.

Domanda 2: Perché haskell è così lento? C'è un flag del compilatore che spegne i freni o è la mia implementazione? (Quest'ultimo è abbastanza probabile poichè haskell è un libro con sette sigilli per me.)

Stai usando gli Hugs ? Hugs è un interprete molto lento. Se lo stai usando, forse puoi ottenere un tempo migliore con GHC - ma io sono solo un'ipotesi incentrata sul cogit, il tipo di roba che un buon compilatore Haskell fa sotto la cappa è piuttosto affascinante e ben oltre la mia comprensione :)

Domanda 3: Puoi darmi qualche suggerimento su come ottimizzare queste implementazioni senza modificare il modo in cui determino i fattori? Ottimizzazione in qualsiasi modo: più bello, più veloce, più "nativo" per la lingua.

Direi che stai giocando un gioco poco divertente. La parte migliore di conoscere le varie lingue è usarle nel modo più diverso possibile :) Ma sto divagando, non ho alcuna raccomandazione per questo punto. Scusa, spero che qualcuno possa aiutarti in questo caso :)

Domanda 4: Le mie implementazioni funzionali consentono LCO e quindi evitare l'aggiunta di frame non necessari nello stack di chiamate?

Per quanto mi ricordo, devi solo assicurarti che la tua chiamata ricorsiva sia l'ultimo comando prima di restituire un valore. In altre parole, una funzione come quella di seguito potrebbe utilizzare tale ottimizzazione:

def factorial(n, acc=1):
    if n > 1:
        acc = acc * n
        n = n - 1
        return factorial(n, acc)
    else:
        return acc

Tuttavia, non avresti tale ottimizzazione se la tua funzione fosse simile a quella qui sotto, perché c'è un'operazione (moltiplicazione) dopo la chiamata ricorsiva:

def factorial2(n):
    if n > 1:
        f = factorial2(n-1)
        return f*n
    else:
        return 1

Ho separato le operazioni in alcune variabili locali per chiarire quali operazioni sono state eseguite. Tuttavia, il più comune è vedere queste funzioni come sotto, ma sono equivalenti per il punto che sto facendo:

def factorial(n, acc=1):
    if n > 1:
        return factorial(n-1, acc*n)
    else:
        return acc

def factorial2(n):
    if n > 1:
        return n*factorial(n-1)
    else:
        return 1

Si noti che spetta al compilatore / interprete decidere se eseguire la ricorsione in coda. Ad esempio, l'interprete Python non lo fa se ricordo bene (ho usato Python nel mio esempio solo per la sua sintassi fluente). Ad ogni modo, se trovi cose strane come le funzioni fattoriali con due parametri (e uno dei parametri ha nomi come acc , accumulator ecc.) Ora sai perché le persone lo fanno :)







erlang