Est-ce que le déplacement des bits est plus rapide que la multiplication et la division en Java?.NET Je ne sais pas. [fermé]

presque n'importe quel environnement digne de ce nom l'optimisera pour vous. Et si ce n'est pas le cas, vous avez de plus gros poissons à frire. Sérieusement, ne perdez pas une seconde de plus à y réfléchir. Vous saurez quand vous avez des problèmes de performances. et après avoir lancé un profileur, vous saurez ce qui le provoque, et il devrait être assez clair comment le corriger.

vous n'entendrez jamais personne dire "mon application était trop lente, alors j'ai commencé au hasard remplacer x * 2 par x << 1 et tout est réparé!"Les problèmes de Performance sont généralement résolus en trouvant un moyen de faire un travail d'un ordre de grandeur moins, pas en trouvant un moyen de faire le même travail 1% plus rapide.

les humains ont tort dans ces cas.

99% quand ils essaient de deviner en second lieu un compilateur moderne (et tout futur).

99,9% lorsqu'ils tentent de deviner les JITs modernes (et tous futurs) en même temps.

99.999% quand ils essaient de deviner des optimisations de CPU modernes (et futures).

programme d'une manière qui décrit précisément ce que vous voulez accomplir, pas comment le faire. Les futures versions de le JIT, le VM, le compilateur et le CPU peuvent tous être améliorés et optimisés de manière indépendante. Si vous spécifiez quelque chose de si petit et spécifique, vous perdez le bénéfice de toutes les optimisations futures.

vous pouvez presque certainement compter sur la puissance littérale de l'optimisation de multiplication à deux pour une opération de changement. C'est l'une des premières optimisations que les étudiants de compilateur construction d'apprendre. :)

cependant, je ne pense pas qu'il y ait de garantie pour cela. Votre code source doit refléter votre intention , plutôt que d'essayer de dire à l'optimiseur quoi faire. Si vous faites une plus grande quantité, utilisez la multiplication. Si vous déménagez un champ de bits d'un endroit à un autre (pensez à la manipulation des couleurs du RVB), utilisez une opération de décalage. Dans tous les cas, votre code source reflétera ce que vous faites réellement.

notez que le déplacement vers le bas et la division donnera (en Java, certainement) des résultats différents pour les nombres impairs négatifs.

int a = -7;
System.out.println("Shift: "+(a >> 1));
System.out.println("Div:   "+(a / 2));

Imprime:

Shift: -4
Div:   -3

comme Java n'a pas de numéros non signés, il n'est pas vraiment possible pour un compilateur Java d'optimiser cela.

sur les ordinateurs que j'ai testés, les divisions entières sont 4 à 10 fois plus lent que les autres opérations.

quand les compilateurs peuvent remplacer les divisions par des multiples de 2 et vous faire voir aucune différence, les divisions par Pas de multiples de 2 sont beaucoup plus lents.

par exemple, j'ai un programme (graphique) avec beaucoup beaucoup de nombreuses divisions par 255. En fait mon calcul est :

r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23;

je peux assurer qu'il est beaucoup plus rapide que mon calcul précédent :

r = ((top.R - bottom.R) * alpha + (bottom.R * 255)) / 255;

donc, non, les compilateurs ne peuvent pas faire tous les trucs de l'optimisation.

je demanderais " qu'est-ce que tu fais pour que ça change quelque chose?". Concevez d'abord votre code pour la lisibilité et la maintenabilité. La probabilité que la multiplication standard de bit shifting versets fasse une différence de performance est extrêmement faible.

Il est dépendant du matériel. Si nous parlons de micro-controller ou i386, alors le déplacement pourrait être plus rapide mais, comme l'indiquent plusieurs réponses, votre compilateur fera habituellement l'optimisation pour vous.

sur le matériel moderne (Pentium Pro et au-delà) le pipelinage rend cela totalement hors de propos et s'écarter des sentiers battus signifie généralement que vous perdez beaucoup plus d'optimisations que vous pouvez gagner.

Micro-optimisations ne sont pas seulement un gaspillage de votre temps, ils sont aussi extrêmement difficile d'obtenir le droit.

si le compilateur (constante de temps de compilation) ou JIT (constante de temps d'exécution) sait que le diviseur ou multiplicande est une puissance de deux et l'arithmétique entière est effectuée, il le convertira en un décalage pour vous.

je suis abasourdi alors que je viens d'écrire ce code et j'ai réalisé que le déplacement par un est en fait plus lent que la multiplication par deux!

(EDIT: changé le code pour arrêter le débordement d'après Michael Myers suggestion, mais le résultat est le même! Quel est le problème ici?)

import java.util.Date;

public class Test {
    public static void main(String[] args) {
        Date before = new Date();
        for (int j = 1; j < 50000000; j++) {
            int a = 1 ;
            for (int i = 0; i< 10; i++){
                a *=2;
            }
        }
        Date after = new Date();
        System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds");
        before = new Date();
        for (int j = 1; j < 50000000; j++) {
            int a = 1 ;
            for (int i = 0; i< 10; i++){
                a = a << 1;
            }
        }
        after = new Date();
        System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds");
    }
}

les résultats sont:

multipliant 639 millisecondes

Shifting 718 millisecondes

selon les résultats de ce microbenchmark , le déplacement est deux fois plus rapide que la division (Oracle Java 1.7.0_72).

la plupart des compilateurs transformeront la multiplication et la division en décalage de bits lorsque cela est approprié. C'est l'une des optimisations les plus faciles à faire. Ainsi, vous devriez faire ce qui est plus facilement lisible et approprié pour la tâche donnée.

C'est une analyse de la référence faite par de Savvas Dalkitsis. Bien que ce test vérifie la vitesse de multiplication sur le déplacement de bits, les valeurs utilisées ne sont pas les mêmes, cochez le code ci-dessous en C# qui affiche les valeurs)

for (int i = 0, j = 1, k = 1; i < 10; i++)
{
  j = j * 2;
  k <<= 2;
  Console.WriteLine("{0} {1}", j, k);
}

le code équivalent de L'exemple Savvas Dalkitsis avec les valeurs affichées en C# sera

    public static void Main(String[] args)
    {
        for (int i = 0, j = 1, k = 1; i < 10; i++)
        {
            j = j * 2; k <<= 2;
            Console.WriteLine("{0} {1}", j, k);
        }
        Console.WriteLine("-----------------------------------------------");


        DateTime before = DateTime.Now;
        for (int j = 1; j < 500000000; j++)
        {
            int a = 1;
            for (int i = 0; i < 10; i++) a *= 2;
        }
        DateTime after = DateTime.Now;

        Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds");

        before = DateTime.Now;
        for (int j = 1; j < 500000000; j++)
        {
            int a = 1;
            for (int i = 0; i < 10; i++) a = a << 1;
        }
        after = DateTime.Now;
        Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds");
        Console.ReadKey();
    }