jump to navigation

Performance di alcuni linguaggi di programmazione 14 luglio 2008

Posted by fripp in About me, Algoritmi, C, GNU/Linux, Informatica, Java, Mac OS X, Matematica, Programmazione, Python, Ruby, Sistemi Operativi, Unix.
Tags: , , , , , , , , , , , ,
trackback

Non avendo nulla di meglio da fare, mi son messo a valutare le performance di esecuzione dei linguaggi che conosco nella risoluzione del “Problema di Flavio Giuseppe”, la cui soluzione vi permetterà di salvarvi nel caso abbiate deciso all’ultimo minuto di salvarvi da un suicidio di massa (leggete prima in cosa consiste il problema per capire la battutaccia 🙂 ).

Ho testato le prestazioni di C, Java, Python, Ruby, C# usando per tutti le stesse condizioni:

  • 100000 iterazioni
  • risoluzione, ad ogni iterazione, del problema che dovette affrontare Flavio Giuseppe in persona: 40 partecipanti al suicidio e determinazione del prossimo suicida contando a 3 a 3 a giro

I test sono stati fatti con questa configurazione:

OS: Mac OS 10.5.4

CPU: Intel(R) Core(TM)2 CPU T7600 @ 2.33GHz

RAM :2 GB

Il risultato del test è dato dal tempo medio (su 10 test )per ogni iterazione espresso in microsecondi.

Ecco la tabella dei risultati.

Linguaggio Versione Note Tempo medio per iterazione (microsecondi)
Ansi C Compilatore: i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465) Compilazione con flag -O3 0.235951
Ansi C++ Compilatore: i686-apple-darwin9-g++-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465) Compilazione con flag -O3
Uso di funzioni inline
0.205846
C# Mono Framework – 1.9.1_3 0.846871
Java java version “1.5.0_13” 1.898368
java version “1.6.0_5” 0.665434
Python Python 2.5.1 (r251:54863, Jan 17 2008, 19:35:17) 24.0439097881
Uso del compilatore JIT Psyco 1.6 5.55800628662
Ruby ruby 1.8.6 (2008-03-03 patchlevel 114) 55.700048

Per analizzare i risultati occorre precisare che mi sono rifatto allo standard C89 per il C (che non prevede le funzioni inline); ecco perchè il C++ con le funzioni inline risulta più performante.

Se provate a compilare i sorgenti C che seguono mettendo la parola chiave inline nell’implementazione della funzione e compilando usando il flag -std=c99 vedrete che le prestazioni di C e C++ saranno uguali. Nel C++ ciò che fa perder prestazioni è il binding tardivo: polimorfismo, template ecc.

Con notevole sorpresa, ho constatato come la JVM non sfigura affato; addirittura con Java 6 i tempi medi sono più che dimezzati.

I fanalini di coda (c’era da aspettarselo) sono Python e Ruby, col primo in vantaggio sul secondo; per l’occasione ho sperimentato in Python l’uso di Psyco, un compilatore JIT, e devo dire che i risultati si vedono: l’esecuzione del codice col modulo Psyco attivo è più veloce di circa l’80% rispetto a quella senza Psyco.

L’algoritmo che ho usato per risolvere il problema è trattato in questa pubblicazione; tale algoritmo ha una complessità pari a O(m + \log_{\frac{m}{m-1}} \left ( \frac{n}{m} \right ) ), dove n è il numero di persone nel gruppo e m è il numero usato per la conta.

Di seguito troverete il codice usato per fare il test nei vari linguaggi.

Codice C:

#include
#include
#include
#include

int solve(int,int);
int josephus(int,int);

int main(int argc, char **argv){
    int ITER;
    double DITER;
    int sec, msec, time;
    double mtime,tottime;
    struct timeval start, end;
    register int i,j;

    ITER = 100000;
    DITER = 100000.0;

    tottime = 0.0;

    for(j=0;j<10;j++){
        gettimeofday(&start,NULL);
        for(i = 0 ; i < ITER ; i++)             josephus(40,3);         gettimeofday(&end,NULL);         msec = end.tv_usec - start.tv_usec;         sec = end.tv_sec - start.tv_sec;         time = sec * 1000000 + msec;         mtime = time/DITER;         tottime += mtime;     }     fprintf(stdout,"Mean time per iteration= %f microseconds\n\r", tottime/10);     return 0; } int solve(int n, int q){     int jn = 0;     register int i;     for(i=1; i<=n; i++)         jn = (jn + q - 1) % i + 1;     return jn; } int josephus(int n, int q){     int t;     if(n <= q) return solve(q,q);     else{         int jn = josephus(((int) (n - floor(n/q))),q);         if(jn <= (n%q))             return jn + ((int) (floor(n/q)) * q);         else{             jn -= n % q;             t = ((int) (floor(jn/(q-1))) * q);             return !(jn%(q-1)) ? t-1 : t+jn%(q-1);         }     } } [/sourcecode] Codice C++: [sourcecode language="c++"] #include
#include
#include

using std::cout;
using std::endl;

int solve(int,int);
int josephus(int,int);

int main(int argc, char **argv){
    int ITER;
    double DITER;
    int sec, msec, time;
    double mtime,tottime;
    struct timeval start, end;

    ITER = 100000;
    DITER = 100000.0;

    tottime = 0.0;

    for(int j=0;j<10;j++){
        gettimeofday(&start,NULL);
        for(int i = 0 ; i < ITER ; i++)             josephus(40,3);         gettimeofday(&end,NULL);         msec = end.tv_usec - start.tv_usec;         sec = end.tv_sec - start.tv_sec;         time = sec * 1000000 + msec;         mtime = time/DITER;         tottime += mtime;     }     cout << "Mean time per iteration = " << tottime/10 <<" microseconds" << endl;     return 0; } inline int solve(int n, int q){     int jn = 0;     register int i;     for(i=1; i<=n; i++)         jn = (jn + q - 1) % i + 1;     return jn; } inline int josephus(int n, int q){     int t;     if(n <= q) return solve(q,q);     else{         int jn = josephus(((int) (n - floor(n/q))),q);         if(jn <= (n%q))             return jn + ((int) (floor(n/q)) * q);         else{             jn -= n % q;             t = ((int) (floor(jn/(q-1))) * q);             return !(jn%(q-1)) ? t-1 : t+jn%(q-1);         }     } } [/sourcecode] Codice  C#: [sourcecode language="java"] using System; class MainClass{     public static void Main(string[] args){         double tottime=0.0;         for(int j=0;j<10;j++){             DateTime start = DateTime.Now;             for(int i=0;i<100000;i++)                 josephus(40,3);             TimeSpan elapsed = DateTime.Now - start;             double time = (elapsed.TotalMilliseconds * 1000.0)/100000.0;             tottime+=time;         }         Console.WriteLine("Time per iteration: {0} microseconds" ,tottime/10.0);     }     public static int solve(int n, int q){         int jn = 0;         for(int i=1;i<=n;i++)             jn = (jn + q -1) % i +1;         return jn;     }     public static int josephus(int n, int q){         if(n<=q)             return solve(q,q);         else{             int jn = josephus(n - ((int) Math.Floor(((double) n)/q)) ,q);             if(jn <= (n%q))                 return jn + (int) (Math.Floor(((double) n)/q) * q);             else{                 jn -= n%q;                 int t = (int) (Math.Floor(((double) jn)/(q-1)) * q);                 if(jn % (q-1) == 0)                     return t-1;                 else                     return t + jn % (q-1);             }         }     } } [/sourcecode] Codice Java: [sourcecode language="java"] public class jjos {     public static void main(String[] args) throws Exception {         int iter = 100000;         double tottime=0.0;         for(int j=0;j<10;j++){             long start = System.nanoTime();             for (int i = 0; i < iter; i++)                 josephus(40, 3);             long end = System.nanoTime();             double time = (end - start)/1000.0;             double mtime = time/100000.0;             tottime+=mtime;         }         System.out.println("Mean time per iteration = " + tottime/10.0                 + " microseconds.");     }     public static int josephus(int n, int q) {         int jn;         if (n <= q)             return solve(q, q);         else {             jn = josephus(n - (int) Math.round(Math.floor(n / q)), q);             if (jn <= (n % q)) {                 return jn + (int) (Math.round(Math.floor(n / q)) * q);             } else {                 jn = jn - (n % q);                 int t = (int) (Math.round(Math.floor(jn / (q - 1))) * q);                 if (jn % (q - 1) == 0)                     return t - 1;                 else                     return t + jn % (q - 1);             }         }     }     public static int solve(int n, int q) {         int jn = 0;         for (int i = 1; i <= n; i++)             jn = (jn + q - 1) % i + 1;         return jn;     } } [/sourcecode] Codice Python (con Psyco): [sourcecode language="python"] #!/usr/bin/python import time import sys import math import psyco def solve(n,q):     jn = 0     for i in xrange(1,n+1):         jn = (jn +q -1) % i +1     return jn def josephus(n,q):     if n <= q: return solve(q,q)     else:         jn = josephus(n-int(math.floor(n/q)),q)         if jn <= (n % q):             return jn + int(math.floor(n/q) * q)         else:             jn -= n % q             t = int(math.floor(jn/(q - 1)) * q)             if not jn % (q - 1):                 return t-1             else:                 return t + jn % (q - 1) if __name__ == "__main__":     psyco.full()     k = 100000     tottime = 0.0     for i in xrange(10):         start = time.time()         for i in xrange(k):             josephus(40,3)         end = time.time()         tottime += ((end - start) * 1000000 )/ k     print 'Mean time per iteration = %s microseconds ' % (tottime / 10.0) [/sourcecode] Codice Ruby: [sourcecode language="ruby"] #!/usr/bin/ruby -w def solve(n,q)     jn = 0     for i in 1..n         jn = (jn + q - 1) % i + 1     end     jn end def josephus(n,q)     if n <= q         solve(q,q)     else         jn = josephus(n-(n/q).floor,q)         if jn <= (n % q)             jn + (n/q).floor * q         else             jn -= n % q             t = (jn/(q-1)).floor * q             if jn % (q-1) == 0                 t-1             else                 t + jn % (q-1)             end         end     end end ITER = 100000 tottime = 0.0 10.times{     start = Time.now     ITER.times{         josephus(40,3)     }     ends=Time.now     tottime += ((ends - start) * 1000000) / ITER } puts 'Mean time per iteration = ' + (tottime / 10).to_s() + ' microseconds' [/sourcecode]

Annunci

Commenti»

No comments yet — be the first.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: