mardi 4 janvier 2011

Performances du C et du Java, illustration par l'exemple

Bonjour à tous.

Pour ce premier article d'une liste que j'espère grandissante, je vous ferais part d'un constat tout frais, que j'ai fait en résolvant l'un des problèmes du site projecteuler.net: Problème 29

Je me suis amusé à résoudre ce problème avec le même algorithme, en C et en Java.
En C, j'ai utilisé les listes fournis par le projet glib, et les types et fonctions pour le traitement des grands nombres fournis par le projet GNU Multiple Precision Arithmetic Library.

Vous pouvez le compiler avec la commande suivante, sous Ubuntu:
gcc -std=c99 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -lglib-2.0 -lgmp  main.c -o main
___

#include <stdio.h>
#include <stdlib.h>
#include <glib.h>
#include <gmp.h>

inline static gint compare_mpzt(const gconstpointer a, const gconstpointer b) {
    if(a == NULL || b == NULL) return -1;
    else return mpz_cmp(* (mpz_t*) a, * (mpz_t*) b);
}

void clean(gpointer data, gpointer user_data) {
    free(data);
}

int main() {
    mpz_t mpz_a;
    mpz_init_set_ui(mpz_a,2);
    GSList* list = g_slist_alloc();
    for(int a=2; a<=100;a++) {
        for(int b=2; b<=100; b++) {
            mpz_t* pt_pow = malloc(sizeof(mpz_t));
            mpz_init(*pt_pow);
            mpz_set_ui(mpz_a,a);
            mpz_pow_ui(*pt_pow,mpz_a,b);
            if(!g_slist_find_custom(list,pt_pow,(GCompareFunc) compare_mpzt)) {
                list = g_slist_append(list,pt_pow);
            }
        }
    }
    printf("%i\n",g_slist_length(list)-1);
    g_slist_foreach(list,clean,NULL);
    g_slist_free(list);
    return 0;
}

___

Le temps d'exécution est de 0,59s sur ma machine.

En Java, j'ai utilisé la classe LinkedList et la classe BigInteger, qui sont fournies de base dans le JDK.

 ___

package euler29;

import java.math.BigInteger;
import java.util.LinkedList;

/**
 *
 * @author yann
 */
public class Main {

    public static void main(String[] args) {
        long before = System.currentTimeMillis();
        BigInteger bi1 = new BigInteger("1");
        BigInteger a = new BigInteger("2");
        int b = 2;
        BigInteger bi101 = new BigInteger("101");
        LinkedList<BigInteger> numbers = new LinkedList<BigInteger>();
        while(a.compareTo(bi101) == -1) {
            b = 2;
            while( b < 101) {
                BigInteger pow = a.pow(b);
                if(!numbers.contains(pow)) numbers.add(pow);
                b += 1;
            }
            a = a.add(bi1);
        }
        System.out.println(numbers.size());
        long after = System.currentTimeMillis();
        System.out.println(after - before + "ms");
    }

}

___

Le temps d'exécution est de 4,35s sur ma machine.

Le temps de développement, que j'aurais dû prendre la précaution de mesurer précisément aussi, était grosso modo 3 à 4 fois plus grand avec la version en C.

Que pensez vous de tels écarts de performances?

Loin de vouloir relancer le célèbre troll C VS Java, j'aimerais plutôt montrer le prix de la facilité offerte par le couple NetBeans/Java, et peut être avoir un retour sur les questions d'optimisation.

12 commentaires:

  1. Loins de moi l'idée de vouloir défendre java, mais en utilisant les bonne structures de donnée, ça va mieux !

    import java.math.BigInteger;
    import java.util.LinkedList;
    import java.util.TreeSet;


    public class Euler29Main {

    /**
    * @param args
    */
    public static void main(String[] args) {
    codeOriginal();
    monCode();

    }

    public static void monCode(){
    long before = System.currentTimeMillis();
    BigInteger bi1 = new BigInteger("1");
    BigInteger a = new BigInteger("2");
    int b = 2;
    BigInteger bi101 = new BigInteger("101");
    //LinkedList numbers = new LinkedList();
    TreeSet numbers = new TreeSet();
    while(a.compareTo(bi101) == -1) {
    b = 2;
    while( b < 101) {
    BigInteger pow = a.pow(b);
    numbers.add(pow);
    b += 1;
    }
    a = a.add(bi1);
    }
    long after = System.currentTimeMillis();
    System.out.println(numbers.size());

    System.out.println("My : " + (after - before) + "ms");
    }

    public static void codeOriginal(){
    long before = System.currentTimeMillis();
    BigInteger bi1 = new BigInteger("1");
    BigInteger a = new BigInteger("2");
    int b = 2;
    BigInteger bi101 = new BigInteger("101");
    LinkedList numbers = new LinkedList();
    while(a.compareTo(bi101) == -1) {
    b = 2;
    while( b < 101) {
    BigInteger pow = a.pow(b);
    if(!numbers.contains(pow)) numbers.add(pow);
    b += 1;
    }
    a = a.add(bi1);
    }
    long after = System.currentTimeMillis();
    System.out.println(numbers.size());
    System.out.println("Original : " + (after - before) + "ms");
    }

    }


    Et le résultat :
    9183
    Original : 953ms
    9183
    My : 39ms

    Ma machine semble être plus puissance que la tienne dans tous les cas, et je n'ai pas eu le courage de compiler la version C.

    RépondreSupprimer
  2. Je ne peux pas éditer, mais on voit assez bien l'effet JIT sur cet exemple. Si tu inverses l'ordre d'appel des 2 fonctions, la mienne met entre 60 et 90ms au lieux des 35-40. Il faut également ajouter un petit sleep avant le premier appel, histoire que eclipse (qui change son affichage) ai le temps de libérer le processeur avant que le travail démarre.

    RépondreSupprimer
  3. J'ai remplacé par TreeSet dans mon code:

    package euler29;

    import java.math.BigInteger;
    import java.util.TreeSet;

    /**
    *
    * @author yann
    */
    public class Main {

    public static void main(String[] args) {
    long before = System.currentTimeMillis();
    BigInteger bi1 = new BigInteger("1");
    BigInteger a = new BigInteger("2");
    int b = 2;
    BigInteger bi101 = new BigInteger("101");
    TreeSet numbers = new TreeSet();
    while(a.compareTo(bi101) == -1) {
    b = 2;
    while( b < 101) {
    BigInteger pow = a.pow(b);
    if(!numbers.contains(pow)) numbers.add(pow);
    b += 1;
    }
    a = a.add(bi1);
    }
    System.out.println(numbers.size());
    long after = System.currentTimeMillis();
    System.out.println(after - before + "ms");
    }

    }

    ___

    Et par GTree dans la version C:

    #include
    #include
    #include
    #include

    inline static gint compare_mpzt(const gconstpointer a, const gconstpointer b) {
    if(a == NULL || b == NULL) return -1;
    else return mpz_cmp(* (mpz_t*) a, * (mpz_t*) b);
    }

    gboolean clean(gpointer key, gpointer value, gpointer user_data) {
    free(key);
    return 0;
    }

    int main() {
    mpz_t mpz_a;
    mpz_init_set_ui(mpz_a,2);
    GTree* list = g_tree_new(compare_mpzt);
    for(int a=2; a<=100;a++) {
    for(int b=2; b<=100; b++) {
    mpz_t* pt_pow = malloc(sizeof(mpz_t));
    mpz_init(*pt_pow);
    mpz_set_ui(mpz_a,a);
    mpz_pow_ui(*pt_pow,mpz_a,b);
    if(!g_tree_search(list,(GCompareFunc) compare_mpzt,pt_pow)) {
    g_tree_insert(list,pt_pow,"FRAISE TAGADA");
    }
    }
    }
    printf("%i\n",g_tree_nnodes(list));
    g_tree_foreach(list,clean,(gpointer)NULL);
    return 0;
    }


    ___

    J'ai maintenant 90ms pour la version Java et 17ms pour la version C.

    Effectivement, j'avais employé un type de données lent, mais en répercutant cette optimisation des 2 cotés on constate toujours un gros écart.

    RépondreSupprimer
  4. C'est marrant, mes include C ont sauté. C'est les même qu'à l'origine, ils n'ont pas changé.

    RépondreSupprimer
  5. Dans le code java tu peux enlever le test avant le add, qui est deja fait dans le add. Tu devrais encore un peux gagner. Sinon ça me rassure que le c reste plus performant.

    RépondreSupprimer
  6. Il en est de même avec le GTree d'ailleurs, qui remplace la valeur si il possède déjà une clé identique.

    Du coup, j'ai enlevé les tests dans chacune des 2 implémentations, mais cela n'a pas influé sur les performances, j'obtiens la même chose.

    RépondreSupprimer
  7. Foarte captivant acest blog te astept pe la mine pe blog !

    RépondreSupprimer
  8. J'ai travaillé que sur la première version

    En C j'obtiens ca: http://img402.imageshack.us/img402/6159/perfn.png

    Et Java ca :
    V1
    9183
    515ms
    V2 List
    9183
    196ms
    V3 Set
    9183
    13ms

    avec ce code :
    http://pastebin.com/Lv7kndCA

    La vitesse de l'algo dépend beaucoup de la manière dont est implémentée la puissance.

    RépondreSupprimer
  9. On peut utiliser aussi une boucle for:

    http://pastebin.com/NgUjanuW

    RépondreSupprimer
  10. Il y a des choses qui se sont supprimés dans le message que j'ai publié.Je ne sais pas pourquoi? alors je supprime pour rectifier. comme cette phrase.

    On va essyer de calculer le terme XJ-XC. Si ce terme donne un nombre négatif(XJ-XC<0) alors
    XJ < XC sinon XJ > XC vu que (XJ-XC>0) .

    RépondreSupprimer
  11. Pour pouvoir comparer les deux durées selon les données que tu viens de mentionner il nous faut une base.On prend le cas de ta machine et on va considérer que les durées écoulés pour coder sont convertis en seconde.

    Si on désigne par XJ et XC comme le temps en seconde total que tu as passé pour développer et exécuter respectivement le programme en Java et en C.En désignant de même par eJ et eD le temps d’exécution seulement pour chacun;dJ et dC le temps de développement de même pour chaque langage.

    Alors on a XJ=eJ+dJ et XC=eC+dC
    On veut comparer XJ et XC.

    On a eC=0,59 et eJ=4,35 (pour ta machine)

    Pour coder en C il faut 3 à 4 fois le temps nécessaire en java. dJ et dC sont inconnu mais on a une relation entre les deux. On suppose que c'est 4 fois.
    => dC = 4dJ

    XJ = eJ + dJ
    XJ = 4,35 + dJ (1)
    et
    XC = eC + dC
    XC= 0,59 + dC
    XC= 0,59 + 4dJ (2)

    On va essyer de calculer le terme XJ-XC. Si ce terme donne un nombre négatif(XJ-XC<0) alors
    XJ < XC sinon XJ > XC vu que (XJ-XC>0) .

    XJ-XC = (eJ+dJ)-(eC+dC)
    = (4,35+dJ)-(0,59+4dJ)
    = 4,35 + dJ - 0,59 - 4dJ
    = 4,35 - 0,59 + (1-4)dJ
    = 4,35 - 0,59 + (1-4)dJ
    = 3,76 - 3dJ
    XJ-XC = -3dJ + 3,6
    Ce terme est-elle négatif ou positif?

    On sait que dJ c'est du temps coulé lors du codage alors c'est un nombre positif( dJ>0 ).

    dJ>0 => 3*dJ > 3*0=0 => 3*dJ > 0

    On sait qu'en multipliant par -1 les deux membres l'inégalité change:

    On a -3*dJ <0

    => 3,76 - 3*dJ < 3,76 .
    XJ-XC < 3,76 Le grand problème est là!!

    On a pu majorer XJ-XC par 3,76 .

    Cependant le fait d'avoir XJ-XC < 3,76 ne nous permet pas de décider.

    Alors on va chercher une solution.

    On va considérer que ce terme 3,76 - 3*dJ est une fonction qui dépend de dJ. dJ c'est une variable toujours positif.On pose dJ=x

    f(x)= -3x + 3,76 . f(x) est majoré par 3,76. f c'est une fonction affine décroissante,plus le temps de développement est grand plus le la fonction est négatif. N’oublions pas que dJ est en seconde.

    f(0)=3,76; f(1)=0,76; f(3,76/3)=f(1,253)=0;
    f(2)=-2,24; f(3)=-5,25;

    Alors on voit que pour un temps de développement supérieur à 1,253s la fonction est négatif.Or dans la réalité pour coder le petit bout de code demande plus que ce chiffe, alors on est sûr à 100% que x>1,253 même 2 secondes on pourrait dire dJ >2.
    On peut peut dire comme ça:
    dans les condition normales de développement f(x)<0.

    Et dans ce cas f(dJ)=XJ-XC<0

    d'où
    ||------------||
    || XJ < XC ||
    ||------------||

    Donc le temps totale de développement suivi de exécution en java et inférieur que le temps effectué en C. Mais quelqu'un peut dire que j'ai supposé que que ça demande 4 fois plus de temps pour développer en java qu'en C? Alors on suppose que c'est 3 fois plus.Si vous suiviez les même étapes f(x)= -2x + 3,76 toujours affine décroissante et négatif pour dJ grand; Et ici pour dJ supérieur à 1,88s. Si c'est 2 fois plus qu'en C. De même f(x)= -x + 3,76 . Encore négatif pour dJ supérieur à 3,76 seconde. XC sera supérieur à XJ si on suppose que dJ = dC ou dJ>dC. Pour dJ=dC f(x)=3,76 il sera constante toujours et positif dans ce cas XC < XJ.

    Mais il reste des paramètres pour dire qu'il faut choisir java et laisser C : -1. le nombre et le temps qu'on va rester à rexécuter l'aplication pour la tester ça augmentera exponentiellement XJ par rapport à XC. -2."L'UTILASATEUR SIBLE" qui est le plus important selon deux raison :

    -2.1 L'application est développé une fois et exécuté des centaines de fois.
    -2.2 Dans le calcul mathématique intense c'est catastrophique pour l'utilisateur,il va passer beaucoup de temps parfois des jour sans voir le résultat.

    Alors pour conclure laissons java pour les application de gestion,entreprise,web ... On développe vite et avec des outils poussé. Cependant souffrons en codant pour les code a calcul intense en C car c'est ce que veut l'utilisateur.

    RépondreSupprimer
  12. Java a un certain nombre d'avantages qui ne sont pas le sujet de cet article mais qui sont effectivement bien existants, qui en font un bon langage pour l'informatique de gestion, les intranets, le web, le middleware et pas mal d'autres choses.

    Je pense qu'il faut avant tout déterminer ce que l'on a besoin de faire, plutôt que de raisonner en rentabilité temps de dev/temps d’exécution.

    Tu parles de temps de test. En Java, il y a Junit qui est maintenant très bien intégré aux IDE. En C, je sais qu'il existe des technos de test unitaire mais ne les ai pas essayé.

    Je peux dire, en Java, que on peux même automatiser les builds et les tests unitaires d'une application avec Junit, Maven et Hudson. Je connais CMake qui équivaut au moins en partie à Maven, mais ne connais pas d'équivalent à Hudson pour automatiser les builds et tests d'une appli en C.

    Je pense que le C à effectivement encore de beaux jours devant lui pour le calcul à haute performance.

    Il faudrait que je vois ce que cela donne avec openMP et Scala, car ce problème semble facilement parallélisable.

    RépondreSupprimer