java Vs C

Portrait de trax
Soumis par trax le mer, 29/09/2010 - 21:08

Petit exercice de l'umlv. Exercice 5 :
http://igm.univ-mlv.fr/~forax/ens/java/licence06-07/td1.html

Code d'origine en C : 

     #include <stdio.h>
     #include <stdlib.h>
 
     int pascal (int nBut, int pBut){
       int * tab;
       unsigned int n, i;
 
       tab = (int *)malloc ((nBut+1)*sizeof(int));
       if(tab==NULL){
         fprintf(stderr,"Pas assez de place\n");
         exit(0);
       }
 
       tab[0] = 1;
 
       for(n=1; n<=nBut; n++){
         tab[n] = 1;
 
         for(i=n-1; i>0; i--)
           tab[i] = tab[i-1] + tab[i];
       }
 
       int result=tab[pBut];
       free(tab);
       return result;
     }
 
     int main(int argc, char * argv[]) {
       printf(" Cn, p = %d\n", pascal (30000, 250));
       return 0;
     }
public class Plop{
     public static int pascal (int nBut, int pBut){
 
        int tab[] = new int[nBut+1];
 
       tab[0] = 1;
 
       for(int n=1; n<=nBut; n++){
         tab[n] = 1;
 
         for(int i=n-1; i>0; i--)
           tab[i] = tab[i-1] + tab[i];
       }
 
       int result=tab[pBut];
       return result;
     }
 
      	public static void main(String[] args){
       System.out.println(" Cn, p = "+ pascal (30000, 250));
     }
}

Résultats : 

$ time java Plop
 Cn, p = -1742193024
real	0m0.625s
user	0m0.564s
sys	0m0.025s

Code C gcc -Wall plop.c

$ time ./a.out 
 Cn, p = -1742193024
 
real	0m3.787s
user	0m3.775s
sys	0m0.003s

(honte suprême)

Code C avec optimisation de gccgcc -Wall -O3 plop.c

$ time ./a.out 
 Cn, p = -1742193024
 
real	0m0.861s
user	0m0.859s
sys	0m0.002s

Bien mieux mais toujours la honte

Et si nous ré-écrivions un peu tout ça : 

     int pascal (int nBut, int pBut){
       int * tab, *tab0, *tab1;
       unsigned int n, i;
 
       tab = (int *)malloc ((nBut+1)*sizeof(int));
       if(tab==NULL){
         fprintf(stderr,"Pas assez de place\n");
         exit(0);
       }
 
       tab[0] = 1;
        tab0 =tab;
 
       for(n=1; n<=nBut; n++){
        tab1 =tab0;
        tab0++;
        *tab0 = 1;
         for(i=n-1; i>0; i--){
           *tab1 = *(tab1-1) + *tab1;
                tab1--;
         }
       }
 
 
       int result=tab[pBut];
       free(tab);
       return result;
     }

=>

$ time ./a.out 
 Cn, p = -1742193024
 
real	0m0.329s
user	0m0.328s
sys	0m0.001s

gcc wins !

int pascal (unsigned int nBut, int pBut){
  int *tab0,  *tab2;
  register int *tab1;
 
 
/*[...]*/
 
 
  nBut++;
  for(n=1; n<nBut; n++){
    tab1 = tab0;
    tab0++;
    *tab0 = 1;
    while (tab < tab1){
      *tab1 = *(tab1-1) + *tab1;
      tab1--;
    }
  }
 
/*[...]*/
}

Qui dit mieux ?

Commentaires

Portrait de kubu

Submitted by kubu on ven, 01/10/2010 - 21:57.

Voici un exemple qui vaut mieux qu'un long discourt :
http://www.clubnix.fr/node/266

Portrait de furet

Submitted by furet on lun, 04/10/2010 - 16:50.

J'avoue que c'est surprenant !

Portrait de coco

Submitted by coco on lun, 08/11/2010 - 23:55.

boucle descendante, simplification des tests : gain de 4%

for(n = nBut; n; n--)
{
	tab1 = tab0;
	tab0++;
	*tab0 = 1;
	while (tab != tab1)
	{
    		*tab1 = *(tab1-1) + *tab1;
    		tab1--;
    	}
}
Portrait de trax

Submitted by trax on mar, 09/11/2010 - 11:09.

A chaque opération sur une variable les drapeaux arithmétiques sont positionés
=> si n == 0, le drapeau qui va bien est mis a 1.

Pas besoin de faire un cmp mais juste un saut conditionnel en fonction du bit en question.

2B G33K || !2B

Portrait de nepta

Submitted by nepta on sam, 12/07/2014 - 06:42.

uh?
tu utilise un proco spécial parce que j'ai pas du tous les même résultat : x

nepta@Nicaia /tmp/Pascal $ javac pascal.java && time java pascal
 Cn, p = -1742193024
 
real    0m0.421s
user    0m0.420s
sys     0m0.008s
nepta@Nicaia /tmp/Pascal $ gcc pascal.c && time ./a.out
 Cn, p = -1742193024
 
real    0m0.492s
user    0m0.488s
sys     0m0.000s

(version java original et pour le C c'est la dernière version à 0.329s (j'ai test toute les versions j'arrive pas a descendre en dessous du java : x))

Portrait de nepta

Submitted by nepta on sam, 12/07/2014 - 07:22.

intéressant, java créé plein de thread pour executer ce programme
maintenant si on prend en compte aussi la mémoire on a 1Mo pour le C et 30Mo pour le java (sans compter la VM qui alloue 2Go :- ° (en swap pour stocker des valeurs intermédiaire où des iteration de boucle précalculé))