Coder plus vite avec des conditionnelles inutiles ?

Question

J'ai la fonction Java suivante, pour compter les éléments communs dans deux tableaux triés. Notez la ligne avec le point d'interrogation.

public static int overlap(int[] a, int[] b)
{
    int i = 0, j = 0;

    int res = 0;

    while(i < a.length && j < b.length)
    {
        if(a[i] > b[j])
            j ++;
        else if(a[i] < b[j])
            i ++;
        else if(a[i] == b[j])  // ?
        {
            res ++;
            i ++;
            j ++;
        }
    }

    return res;
}

Il est clair que la dernière déclaration if n'a pas besoin d'être là : à ce stade, nous savons que les deux valeurs sont égales. Cependant, lorsque je teste la vitesse (je vérifiais si l'ordre des vérifications faisait une différence), la méthode avec la vérification superflue est invariablement plus rapide que celle sans vérification (parfois par un facteur de deux).

Que se passe-t-il ici ? Une optimisation mystérieuse ? Ai-je oublié quelque chose d'évident ? J'utilise le compilateur stand, version 1.8. Je ne peux pas lire le bytecode, donc je ne sais pas ce qui se passe sous le capot.

Voici une classe de test complète : https://gist.github.com/pbloem/1523283211454ec58ce9c5b45204eebd

Bytecode : https://gist.github.com/pbloem/ce4f6758f0bb1424c155c26e83ca88a1

Answer 1

Il est possible que le JIT permute l'ordre des "if" pour obtenir les meilleures performances, mais il ne peut pas permuter l'ordre d'un simple "else" (sans "if") avec un autre "if" au début, donc lorsque vous avez ajouté "if" après "else", il l'a essayé comme première vérification, et si le chevauchement du tableau est de l'ordre de %90, alors il a pu garder ce dernier "if" à la première place.

    if(a[i] == b[j])  // say %70 probability after N iterations
    {                 // or less randomized branching
        res ++;
        i ++;
        j ++;
    }
    else if(a[i] > b[j]) // %20 probability, medium branching
        j ++;
    else if(a[i] < b[j]) // %10, totally random branching, not predictable
        i ++;

est possible lorsque des tableaux ordonnant

a > b ou b < a

sont plus aléatoires que les tableaux qui se chevauchent.

Lorsqu'il y a des if+if+else, le JIT peut ne pas prédire ce que vous voulez dire. En ajoutant une égalité, vous éliminez de nombreux cas à l'exception de l'équation.

Pourriez-vous essayer avec un tableau ordonné et un tableau totalement aléatoire ?

Ou alors c'est juste pour aider le prédicteur de branche du processeur comme l'a dit @noahnu dans les commentaires.

Answer 2

En utilisant System.currentTimeMillis() vous ne pouvez pas obtenir le temps exact écoulé par le programme car il peut parfois être erroné en raison de l'optimisation JIT. Essayez d'utiliser System.nanoTime() .

Faites également en sorte que les variables utilisées dans le calcul du temps soient des variables globales pour un micro benchmark correct.

double sumWith = 0.0 ; double sumWithout = 0.0 ;