C’est un truc de fou quand-même.

Imaginons de faire un tableau avec des nombres aléatoires dedans :

while (howmany != 0) {
    out[index] = random();
    index += 1;
    hownany--;
}

Ceci, coûte environ 3 cycles CPU par itération.

Maintenant, disons que l’on veuille mettre des nombres aléatoires, mais seulement paires :

while (howmany != 0) {
    var = random();
    if (val is odd) {
        out[index] = val;
        index += 1;
    }
    hownany--;
}

Comme il dit, on pourrait penser que c’est aussi rapide (le test de parité se fait en regardant seulement le bit de poids faible), voire plus rapide car le tableau de sortie est en moyenne moitié moins gros.

En réalité, c’est 5 fois plus lent à 15 cycles CPU par ittération !

Ceci est plus rapide :

while (howmany != 0) {
    val = random();
    out[index] = val;
    index += (val bitand 1);
    howmany--;
}

Ça fait la même chose : l’index est incrémenté par le bit de poids faible (BPF) du nombre créé. Autrement dit, si le nombre est pair, le BPF est 1, donc l’index est incrémenté, et au prochain tour de boucle, on passe à l’index suivant du tableau.
Si le nombre est impaire, le BPF est 0, et le nombre sera écrasé dans le tour de boucle suivant.

Ici, on trouve la vitesse de la méthode initiale, à environ 4 cycle CPU par tour de boucle.

Pourquoi ?

Parce que les CPU modernes font du calcul prédictif. Ils essayent de gagner de temps en calculant un résultat futur.
Si la prédiction est bonne, on aura gagné du temps : le calcul est déjà fait.
Mais s’il est faux, on aura calculé pour rien ET on devra faire le calcul réel. On aura donc perdu davantage de temps à essayer d’en gagner, que ce qu’on on aurait perdu à ne pas vouloir en gagner. Si les CPU intègrent ça, c’est que le gain est globalement plus important que la perte dans la majorité des cas.

Dans notre exemple, lors de la seconde méthode avec un if, la méthode change à chaque tour de boucle. Autrement dit, tout le travail de prédiction ne sert systématiquement à rien et le CPU perd du temps à jeter la prédiction et à en recalculer une autre, qui sera à son tour jetée au tour suivant… à chaque fois !
Le calcul prédictif est là, mais il n’est pas encore assez évolué pour reconnaître le patern qu’on fait ici (c’est du très bas niveau ici, et on est encore loin d’une IA intégrée dans les CPU).

C’est pour ça que le dernier bout de code est plus rapide : la logique utilisée est la même à chaque tour de boucle. Il n’y a pas "if", le calcul est toujours le même.

On réalise ceci en limitant le nombre de niveaux d’embranchement dans le code (moins de IF). Il est préférable de faire plus de calculs sans branches que moins de calculs avec des branches.

Je ne sais pas trop dans quelles mesures tout ceci peut s’appliquer à du calcul de haut niveau (affichage d’une page web, par exemple et dans mon cas), je pense que ça reste limité, hormis pour les très grosses quantité de JSON ou les gros travaux sur le DOM, mais pour du calcul plus compliqué, comme le calcul 3D d’un jeu vidéo, ça doit jouer énormément.

Dans une certaine mesure, il ne m’étonnerait pas que certains vieux jeux tournent plus rapidement sur des CPU/GPU qui leur seraient contemporains que sur des systèmes modernes, qui perdraient alors plus de temps à vouloir en gagner. Dans les faits, le gain de la vitesse pure des CPU modernes sera toujours là, mais si ça arrive, faudra pas s’étonner je pense.

— (permalink)