Pourquoi ce code Java 6x est-il plus rapide que le code C # identique?

J’ai quelques solutions différentes au problème de Project Euler 5 , mais la différence de temps d’exécution entre les deux langages / plates-formes dans cette implémentation particulière m’insortinggue. Je n’ai fait aucune optimisation avec les indicateurs du compilateur, juste javac (via la ligne de commande) et csc (via Visual Studio).

Voici le code Java. Il se termine dans 55ms.

  classe publique Problem005b
 {
     main statique vide statique (Ssortingng [] args)
     {
         long begin = System.currentTimeMillis ();
         int i = 20;
         tandis que (vrai)
         {
             si (
                     (i% 19 == 0) &&
                     (i% 18 == 0) &&
                     (i% 17 == 0) &&
                     (i% 16 == 0) &&
                     (i% 15 == 0) &&
                     (i% 14 == 0) &&
                     (i% 13 == 0) &&
                     (i% 12 == 0) &&
                     (i% 11 == 0)
                 )
             {
                 Pause;
             }
             i + = 20;
         }
         long end = System.currentTimeMillis ();
         System.out.println (i);
         System.out.println (end-begin + "ms");
     } 
}

Voici le code C # identique. Il finit en 320ms

  en utilisant le système;

 espace de noms ProjectEuler05
 {
     classe problem005
     {
         statique vide principal (Ssortingng [] args)
         {
             DateTime begin = DateTime.Now;
             int i = 20;
             tandis que (vrai)
             {
                 si (
                         (i% 19 == 0) &&
                         (i% 18 == 0) &&
                         (i% 17 == 0) &&
                         (i% 16 == 0) &&
                         (i% 15 == 0) &&
                         (i% 14 == 0) &&
                         (I% 13 == 0) &&
                         (i% 12 == 0) &&
                         (i% 11 == 0)
                     )
                     {
                         Pause;
                     }
                 i + = 20;
             }
             DateTime end = DateTime.Now;
             TimeSpan elapsed = end - begin;
             Console.WriteLine (i);
             Console.WriteLine (écoulé.TotalMilliseconds + "ms");
         }
     }
 } 

    La clé pour que ces deux personnes se rapprochent est de s’assurer que la comparaison est juste.

    Tout d’abord, vous assurer que les coûts associés à l’exécution des versions Debug, en chargeant les symboles pdb comme vous l’avez fait.

    Ensuite, vous devez vous assurer que les coûts initiaux ne sont pas comptabilisés. Évidemment, ce sont des coûts réels, et peuvent être importants pour certaines personnes, mais dans ce cas-ci, nous nous intéressons à la boucle elle-même.

    Ensuite, vous devez gérer le comportement spécifique de la plate-forme. Si vous utilisez une machine Windows 64 bits, vous pouvez être en mode 32 bits ou 64 bits. En mode 64 bits, le JIT est différent à bien des égards, modifiant souvent le code résultant. Plus précisément, et j’imagine , vous avez access à deux fois plus de registres à usage général.

    Dans ce cas, la section interne de la boucle, traduite naïvement en code machine, devrait charger dans les registres les constantes utilisées dans les tests modulo. S’il n’y a pas assez de place pour contenir tout ce qui est nécessaire dans la boucle, il faut les pousser de la mémoire. Même en venant du cache de niveau 1, ce serait un succès important par rapport au fait de garder tout dans les registres.

    Dans VS 2010 MS a modifié la cible par défaut de anycpu à x86 . Je n’ai rien à voir avec les ressources ou les connaissances du client face à MSFT, donc je ne vais pas essayer de le deviner. Cependant, toute personne qui regarde quelque chose comme l’parsing de performance que vous faites devrait certainement essayer les deux.

    Une fois ces disparités éliminées, les chiffres semblent beaucoup plus raisonnables. Toute différence supplémentaire nécessiterait probablement des suppositions plus judicieuses que des connaissances plus approfondies, mais nécessiterait une étude des différences réelles dans le code machine généré.

    Je pense que cela pourrait être intéressant pour un compilateur optimisé.

    • Ceux déjà mentionnés:
      • L’option lcm est intéressante mais je ne vois pas de rédacteur de compilateur se soucier.
      • la réduction de la division en multiplication et en masquage.
        • Je n’en sais pas assez à ce sujet, mais d’ autres personnes ont remarqué que le séparateur des puces Intel les plus récentes était nettement amélioré.
        • Vous pourriez peut-être même organiser quelque chose de complexe avec SSE2.
        • Certes, l’opération modulo 16 est prête à être convertie en masque ou en équipe.
      • Un compilateur pourrait détecter qu’aucun des tests n’a d’effets secondaires.
        • il pourrait essayer d’évaluer plusieurs d’entre eux en même temps, sur un processeur super scalaire, cela pourrait pomper un peu plus vite, mais dépendrait fortement de la manière dont la disposition des compilateurs interagirait avec le moteur d’exécution OO.
      • Si la pression du registre était serrée, vous pourriez implémenter les constantes en tant que variable unique, définie au début de chaque boucle puis incrémentée au fur et à mesure.

    Ce sont toutes des suppositions absolues et doivent être considérées comme des méandres inutiles. Si vous voulez savoir le démonter.

    1. Pour exécuter du code temporel, vous devez utiliser la classe StopWatch .
    2. En outre, vous devez tenir compte du JIT, du temps d’exécution, etc. Laissez le test s’exécuter suffisamment de fois (10 000, 100 000 fois, par exemple) et obtenez une sorte de moyenne. Il est important d’exécuter le code plusieurs fois, pas le programme. Écrivez donc une méthode et bouclez la méthode principale pour obtenir vos mesures.
    3. supprimer tous les éléments de débogage des assemblys et laisser le code s’exécuter de manière autonome dans une version validée

    Il y a quelques optimisations possibles. Peut-être que le JIT Java les exécute et que le CLR ne l’est pas.

    Optimisation # 1:

     (x % a == 0) && (x % b == 0) && ... && (x % z == 0) 

    est équivalent à

     (x % lcm(a, b, ... z) == 0) 

    Ainsi, dans votre exemple, la chaîne de comparaison pourrait être remplacée par

     if (i % 232792560 == 0) break; 

    (mais bien sûr, si vous avez déjà calculé le LCM, il ne sert à rien de lancer le programme en premier lieu!)

    Optimisation # 2 :

    Ceci est également équivalent:

     if (i % (14549535 * 16)) == 0 break; 

    ou

     if ((i % 16 == 0) && (i % 14549535 == 0)) break; 

    La première division peut être remplacée par un masque et comparer à zéro:

     if (((i & 15) == 0) && (i % 14549535 == 0)) break; 

    La deuxième division peut être remplacée par une multiplication par l’inverse modulaire:

     final long LCM = 14549535; final long INV_LCM = 8384559098224769503L; // == 14549535**-1 mod 2**64 final long MAX_QUOTIENT = Long.MAX_VALUE / LCM; // ... if (((i & 15) == 0) && (0 <= (i>>4) * INV_LCM) && ((i>>4) * INV_LCM < MAX_QUOTIENT)) { break; } 

    Il est peu probable que le JIT l'utilise, mais ce n'est pas aussi exagéré que vous pourriez le penser - certains compilateurs C implémentent la soustraction du pointeur de cette façon.

    C’est une tâche trop courte pour effectuer le bon timing. Vous devez exécuter les deux au moins 1000 fois et voir ce qui se passe. On dirait que vous les exécutez depuis une ligne de commande, auquel cas vous comparez éventuellement les compilateurs JIT pour les deux. Essayez de placer les deux derrière des boutons dans une simple interface graphique et faites en sorte que ce bouton soit bouclé quelques centaines de fois au moins avant de renvoyer le temps écoulé. Même en ignorant la compilation JIT, la granularité du planificateur du système d’exploitation pourrait retarder la synchronisation.

    Oh, et à cause de JIT … ne comptez que le SECOND résultat d’une pression sur un bouton. 🙂

    Peut-être parce que la construction des objects DateTime est beaucoup plus coûteuse que celle de System.currentTimeMillis .

    En Java, j’utiliserais System.nanoTime (). Tout test qui prend moins de 2 secondes doit être exécuté plus longtemps. Il convient de noter que Java est très efficace pour optimiser le code ou le code inefficace qui ne fait rien. Un test plus intéressant serait si vous optimisez le code.

    Vous essayez d’obtenir une solution que vous pouvez déterminer sans utiliser de boucle. c’est-à-dire un problème qui se ferait mieux autrement.

    Vous voulez le produit des facteurs de 11 à 20, qui sont 2,2,2,2,3,3,5,7,11,13,17,19. Multipliez-les ensemble et vous avez la réponse.

    (Déplacé de l’OP)

    En changeant la cible de x86 à anycpu, le temps d’exécution moyen a été réduit à 84 ms par exécution, contre 282 ms. Peut-être que je devrais diviser cela en un deuxième thread?

    METTRE À JOUR:
    Merci à Femaref ci-dessous qui a signalé quelques problèmes de test , et en effet, après avoir suivi ses suggestions, les temps sont plus courts, indiquant que le temps d’installation de la VM était important en Java, mais probablement pas en C #. En C #, ce sont les symboles de débogage qui étaient significatifs.

    J’ai mis à jour mon code pour exécuter chaque boucle 10 000 fois et ne générer que la moyenne des ms à la fin. Le seul changement significatif que j’ai apporté a été la version C # où je suis passé à la classe [StopWatch] [3] pour une meilleure résolution. Je suis resté avec des millisecondes parce que ça suffit.

    Résultats:
    Les changements de test n’expliquent pas pourquoi Java est (encore) plus rapide que C #. Les performances C # étaient meilleures, mais cela peut s’expliquer entièrement par la suppression des symboles de débogage. Si vous lisez [Mike Two] [4] et moi-même sur les commentaires attachés à cet OP, vous verrez que j’ai obtenu une moyenne de ~ 280 ms en cinq exécutions du code C # simplement en passant de Debug à Release.

    Nombres:

    • Une boucle de 10 000 points du code Java non modifié m’a donné une moyenne de 45 ms (au lieu de 55 ms)
    • Une boucle de 10 000 points du code C # utilisant la classe StopWatch m’a donné une moyenne de 282 ms (au lieu de 320 ms)

    Tout cela laisse la différence inexpliquée. En fait, le différentiel a empiré. Java est passé d’environ 5.8x plus vite à 6.2x plus vite.